/*******************************************************************************
 * Copyright (c) 2004-2008 Akos Horvath, Gergely Varro and Daniel Varro
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *    Akos Horvath, Gergely Varro - initial API and implementation
 *******************************************************************************/

 package org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.algorithms;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.TreeMap;
import java.util.Vector;

import org.eclipse.emf.common.util.TreeIterator;
import org.eclipse.emf.ecore.EObject;
import org.eclipse.viatra2.core.IModelManager;
import org.eclipse.viatra2.gtasm.patternmatcher.ParameterMode;
import org.eclipse.viatra2.gtasm.patternmatcher.PatternCallSignature;
import org.eclipse.viatra2.gtasm.patternmatcher.exceptions.PatternMatcherCompileTimeException;
import org.eclipse.viatra2.gtasm.patternmatcher.exceptions.PatternMatcherRuntimeException;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.exceptions.GTRuleBuildingException;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.internal.GTElementMapping;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.internal.GTElementMappingType;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.internal.GTOperationContext;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.internal.GTOperationGenerator;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.internal.operation.DeleteModelElement;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.internal.operation.ElementManipulationOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.internal.operation.IUpdatePlanOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.gtmatcher.validation.GTRuleValidator;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.EdgeType;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.MatchingFrame;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.PatternMatcherErrorStrings;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.VPMModelElementType;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.VariableID;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph.BodyNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph.DanglingVPMElementDTO;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph.FlattenedPattern;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph.PatternNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph.PatternNodeIncremental;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph.PatternReferenceNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.CheckOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.ISearchPlanOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.SearchPlanOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.AbstractNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.ConstantSearchGraphNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.EdgeTypeinAlgorithm;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.PatternCallSearchGraphNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.SearchGraphEdge;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.SearchGraphNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.VariableSearchGraphNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.traceability.AbstractTraceabilityElement;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.traceability.ConstantNodeTraceabilityElement;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.traceability.EdgeTraceabilityElement;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.traceability.NodeTraceabilityElement;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.traceability.PatternCallNodeTraceabilityElement;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.traceability.VariableNodeTraceabilityElement;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.core.AnnotatedElement;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.enums.ContainmentMode;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.terms.Constant;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.terms.Term;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.terms.VariableReference;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.gt.ContainmentConstraint;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.gt.GTPatternBody;
import org.eclipse.viatra2.gtasmmodel.vpm.editmodel.Entity;
import org.eclipse.viatra2.gtasmmodel.vpm.editmodel.ModelElement;
import org.eclipse.viatra2.gtasmmodel.vpm.editmodel.Relation;
import org.eclipse.viatra2.gtasmmodel.vpm.editmodel.Relationship;
import org.eclipse.viatra2.gtasmmodel.vpm.editmodel.SupertypeOf;
import org.eclipse.viatra2.gtasmmodel.vpm.editmodel.TypeOf;
import org.eclipse.viatra2.gtasmmodel.vpm.editmodel.VPMElement;


/**A search graph implementation for the VPM models
 * @author Akos Horvath
 *
 */
public class VPMBasedSearchGraph implements  ISearchGraph {
    public static final int BELOW_WEIGHT = 40;
    public static final int IN_WEIGHT = 10;
    public static final int INSTANCEOF_WEIGHT = 20;
    public static final int SUPERTYPE_WEIGHT = 10;
    public static final int RELATION_WEIGHT = 15;
    public static final int PATTERNCALLINV_WEIGHT = 4; //Must be the lowest weight !!!
    public static final int PATTERNCALL_WEIGHT = 20;
    public static final int PATTERNCALL_INCREMENTAL_WEIGHT = 9;
    public static final int PATTERNCALL_STORAGE_INCREMENTAL_WEIGHT = 7;

    private static final int VPM_ENTITY = -1;
    private static final int VPM_RELATION = -2;
    private static final int PATTERN_CALL_STORAGE_NODE = -3;
    private static final int CONSTANTNODE_STARTING_ID = -4;
    // in case the pattern has ENTITY or RELATION as Modelelement
    // or in case the pattern call is a collector node,
    // then  they have to added to the constantnodes collection


    private int constantNodesNumber = CONSTANTNODE_STARTING_ID;

    /**
     * The class represents the data structure for the search plan evaluation
     */
    private final ChuiEdmonds alg;

	private TreeMap<Integer,SearchGraphNode> searchNodes;
    private SearchGraphNode[] searchNodeOrder = null;  //SearchGraphNode! not SearcPlanOperation!!!
    private final TreeMap<String,Integer> constantNodes;
    private Map<SearchGraphNode,Boolean> hasOneInConstraint;
    private final ArrayList<DanglingVPMElementDTO> danglingElements;
    private final Map<AbstractNode,AbstractTraceabilityElement> traceabilityMapping;

    private final int constantNodeNumber = CONSTANTNODE_STARTING_ID;

    public VPMBasedSearchGraph(IModelManager manager) {
        this.alg = new ChuiEdmonds(manager);
    	this.searchNodes = new TreeMap<Integer, SearchGraphNode>();
    	this.constantNodes = new TreeMap<String, Integer>();
    	this.danglingElements = new ArrayList<DanglingVPMElementDTO>();
    	this.traceabilityMapping = new HashMap<AbstractNode, AbstractTraceabilityElement>();
    }

	public void setSearchNodes(TreeMap<Integer,SearchGraphNode> searchGraph) {
		this.searchNodes = searchGraph;
	}

	public TreeMap<String, Integer> getConstantNodes() {
		return constantNodes;
	}

	public TreeMap<Integer, SearchGraphNode> getSearchNodes() {
		return searchNodes;
	}

	public int getConstantNodeNumber() {
		return constantNodeNumber;
	}

	public SearchGraphNode getSearchNode(Integer key) {
		return searchNodes.get(key);
	}

	public boolean containsKey(Object key) {
		return searchNodes.containsKey(key);
	}

//	private void debug(Logger logger) {
//	    for (SearchGraphNode node : searchNodes.values()) {
//	        logger.debug(node.getName()+" "+node.getOutgoingTreeEdgeNumber()+ " "+ node.isChecked());
//	        for(SearchGraphEdge edge: node.getSources()) {
//	            logger.debug(//"  *****Name "+edge.getName()+" *****Type: "+edge.getVPMEdgeType()
//	                    ""+"  "+edge.getSourceNode().getName()+" -> "+ edge.getTargetNode().getName()+"  "+edge.getWeight()+" "+edge.getOldWeight()+" "+edge.isChecked()+" "+ edge.getEdgeTypeinAlgorithm());
//	        }
//	        if(node.getTreeEdge() != null) {
//	            logger.debug("   TREEEDGE   "+node.getTreeEdge().getName()+"  "+node.getTreeEdge().getSourceNode().getName()+" -> "+ node.getTreeEdge().getTargetNode().getName()+"  "+node.getTreeEdge().getWeight()+" "+node.getTreeEdge().getOldWeight()+" "+node.getTreeEdge().isChecked());
//	        }
//	    }
//	}

    // sets back the searchGraph to the beginning state
    public void initSearchGraph() {
    	alg.init();

    	for (SearchGraphNode node : searchNodes.values()) {
    		node.setChecked(false);
    		node.setVirtualSearchGraphNode(null);
    		for (SearchGraphEdge edge : node.getSources()) {
    			edge.setEdgeTypeinAlgorithm(EdgeTypeinAlgorithm.FREE);
    			edge.setChecked(false);
    			edge.setWeight(edge.getOldWeight());
    			//alg.init();
    			//resets the outgoing tree edge number
    			node.setOutgoingTreeEdgeNumber(0);
    		}
    		node.setTreeEdge(null);
    	}//input parameter of a VariableSearchGraph is set by the FlattenedPattern
	}

    public void add(BodyNode bodyNode, FlattenedPattern result) throws PatternMatcherCompileTimeException {
    	GTPatternBody body = bodyNode.getBody();
		// VPM nodes and edges are mapped to SearchGraphNodes

		TreeIterator<EObject> elements_iter = body.getPatternGraph().eAllContents();
		//map the VPM relations and entites to SearchGraph nodes
		while(elements_iter.hasNext()) {
		    Object obj = elements_iter.next();
		    if(obj instanceof Relation || obj instanceof Entity)
		        evaluateModelElement((ModelElement) obj,result,bodyNode);
		}

		//maps the connections of the local VPM model elements to search graph edges
		elements_iter = body.getPatternGraph().eAllContents();
		while(elements_iter.hasNext()) {
		    Object obj = elements_iter.next();

		    if(obj instanceof Relation)
		        connectElements((Relation) obj,result,bodyNode);
		    if(obj instanceof Relationship)
		        evaluateRelationship((Relationship) obj,result,bodyNode);
		}

		//saves the dangling relations
		Iterator<Relation> iter_dangling = body.getDanglingRelations().iterator();
		while(iter_dangling.hasNext())
			danglingElements.add(new DanglingVPMElementDTO(iter_dangling.next(), bodyNode));

		//saves the dangling relationships
		Iterator<Relationship> iter_dangling_relship = body.getDanglingRelationships().iterator();
		while(iter_dangling_relship.hasNext())
			danglingElements.add(new DanglingVPMElementDTO(iter_dangling.next(), bodyNode));

		// containment
		ListIterator<ContainmentConstraint> containmentConstraints = body.getContainmentConstraints().listIterator();
		while(containmentConstraints.hasNext()) {
		    //ContainmentConstraint conCons = containmentConstraints.next();
		    evaluateContainmentConstraints(containmentConstraints.next(),result,bodyNode);
		}
    }

	private void evaluateContainmentConstraints(ContainmentConstraint conCons , FlattenedPattern result, BodyNode bodyNode){
	    SearchGraphEdge edge = new SearchGraphEdge();
	    SearchGraphEdge invedge = new SearchGraphEdge();
	    SearchGraphNode target =  getSearchNode(result.getIndex(bodyNode.getVariableID(conCons.getVariable())));

	    //traceability
		EdgeTraceabilityElement edgeTraceability = new EdgeTraceabilityElement(edge,conCons);
		traceabilityMapping.put(edge, edgeTraceability);

	    //inverse
	    EdgeTraceabilityElement inverseEdgeTraceability = new EdgeTraceabilityElement(invedge,conCons);
		traceabilityMapping.put(invedge, inverseEdgeTraceability);

	    if(conCons.getMode() == ContainmentMode.BELOW_LITERAL) {
	        edge.setVPMEdgeType(EdgeType.BELOW);
	        edge.setOldWeight(BELOW_WEIGHT);
	        edge.setWeight(BELOW_WEIGHT);
	        invedge.setVPMEdgeType(EdgeType.BELOW);
	        invedge.setOldWeight(BELOW_WEIGHT*2);
	        invedge.setWeight(BELOW_WEIGHT*2);
	    } else {
	        edge.setVPMEdgeType(EdgeType.IN);
	        edge.setOldWeight(IN_WEIGHT);
	        edge.setWeight(IN_WEIGHT);
	        invedge.setVPMEdgeType(EdgeType.IN);
	        invedge.setOldWeight(IN_WEIGHT*2);
	        invedge.setWeight(IN_WEIGHT*2);
	    }

	    if(conCons.getParent() instanceof VariableReference &&
	        result.containsIndex(bodyNode.getVariableID(((VariableReference)conCons.getParent()).getVariable())))
	        {
	    	VariableID parentID = bodyNode.getVariableID(((VariableReference)conCons.getParent()).getVariable());
	        VariableSearchGraphNode source;

	        if (searchNodes.containsKey(result.getIndex(parentID)))
	        	{
	            source = (VariableSearchGraphNode) getSearchNode(result.getIndex(
	                    parentID));
	        	}
	        else
	        	{
	            source = new VariableSearchGraphNode();
	            source.setVpmModelElementType(VPMModelElementType.ENTITY);
	            source.setInput(true);
	            source.setName(parentID.toString());
	            source.setId(result.getIndex(parentID));
	            searchNodes.put(source.getId(),source);			//variablereference

	            //traceability
		        VariableNodeTraceabilityElement traceability = new VariableNodeTraceabilityElement(source,conCons.getParent());
		        traceabilityMapping.put(source, traceability);
	        	}

	        edge.setName(conCons.getVariable().getName()+"_Containment");
	        edge.setTargetNode(target);
	        edge.setSourceNode(source);
	        edge.setSource(true);
	        target.addSource(edge);

	        edge.setInverseEdge(invedge);

	        invedge.setName(conCons.getVariable().getName()+"_ContainmentInverse");
	        invedge.setTargetNode(source);
	        invedge.setSourceNode(target);
	        invedge.setSource(false);
	        source.addSource(invedge);
	    } else if (conCons.getParent() instanceof Constant) {

	    	ConstantSearchGraphNode source;
	        //a bit complicated...
	        Constant constant = ((Constant)conCons.getParent());

	        if(constantNodes.containsKey(constant.getValue()))
	 	       {
	        	source = (ConstantSearchGraphNode) getSearchNode(constantNodes.get(constant.getValue()));
	           }
	        else
	        	{
	        	source = new ConstantSearchGraphNode();
		        source.setElement(constant.getValue());
		        source.setName(constant.getValue());
		        searchNodes.put(constantNodesNumber,source);
		        constantNodes.put(source.getName(), constantNodesNumber);
		        constantNodesNumber--;

		        //traceability
		        ConstantNodeTraceabilityElement traceability = new ConstantNodeTraceabilityElement(source,conCons.getParent());
		        traceabilityMapping.put(source, traceability);
	        	}
	        edge.setName(conCons.getVariable().getName()+"_Containment");
	        edge.setTargetNode(target);
	        edge.setSourceNode(source);
	        edge.setSource(true);
	        target.addSource(edge);
	    } else {
	        // general case for the Term of the containment constraint
	        int index = result.addVariable(null);
	        CheckOperation operation =
	        	bodyNode.getTermEvaluationOperation(result.getTermHandler(), conCons, index);
//                handler.getTermEvaluationOperation(parent.pattern, currentLocation, conCons.getParent(), index);
	        result.addPreSearchPlanOperation(operation);

	        VariableSearchGraphNode source = new VariableSearchGraphNode();
            source.setInput(true);
            source.setVpmModelElementType(VPMModelElementType.ENTITY);
            source.setName("PROCCESEDTERM_"+index);
            source.setId(index);
            searchNodes.put(index,source);			//variablereference

            //traceability
	        VariableNodeTraceabilityElement traceability = new VariableNodeTraceabilityElement(source,conCons.getParent());
	        traceabilityMapping.put(source, traceability);

            edge.setName(conCons.getVariable().getName()+"_Containment");
	        edge.setTargetNode(target);
	        edge.setSourceNode(source);
	        edge.setSource(true);
	        target.addSource(edge);
        }
	}

	private void connectElements(Relation rel, FlattenedPattern result, BodyNode bodyNode) throws PatternMatcherCompileTimeException {
		SearchGraphNode source;
		SearchGraphNode target;
		SearchGraphNode relationnode;

		String fromStr = rel.getFromStr();
		String toStr = rel.getToStr();

		Integer toIndex = result.getIndex(bodyNode.getVariableID(toStr));
		Integer fromIndex = result.getIndex(bodyNode.getVariableID(fromStr));
		Integer relIndex = result.getIndex(bodyNode.getVariableID(rel));

		if(fromIndex != null
				&& searchNodes.containsKey(fromIndex)) {
			source =  getSearchNode(fromIndex);
        }
		else if(constantNodes.containsKey(fromStr))  {
			source =  getSearchNode(constantNodes.get(fromStr));
        }
		else{
			String[] context ={rel.getName(), rel.getFromStr()};
			throw new PatternMatcherCompileTimeException(PatternMatcherErrorStrings.INTERNAL_SEARCGRAPH_RELATION_SOURCE_MISSING
    			,context
    			,rel);
		}

		if(toIndex != null
				&& searchNodes.containsKey(toIndex)) {
			target = getSearchNode(toIndex);
        } else if(constantNodes.containsKey(toStr)) {
			target =  getSearchNode(constantNodes.get(toStr));
        } else {
        	//TODO: if the target of the relation is missing it is a dangling relation but not contained in the DanlingRelations list :-)
        	// Needs to be added to the danglingElements collection
        	danglingElements.add(new DanglingVPMElementDTO(rel, bodyNode));
        	return;
//        	String[] context ={rel.getName()};
//        	throw new PatternMatcherCompileTimeException(PatternMatcherErrorStrings.INTERNAL_SEARCGRAPH_RELATION_TARGET_MISSING
//        			,context
//        			,rel);
        }

        if(relIndex != null
				&& searchNodes.containsKey(relIndex)) {
			relationnode =  getSearchNode(relIndex);
        } else if(constantNodes.containsKey(rel.getName())) {
			relationnode =  getSearchNode(constantNodes.get(rel.getName()));
        } else {
        	String[] context ={rel.getName()};
        	throw new PatternMatcherCompileTimeException(PatternMatcherErrorStrings.INTERNAL_SEARCGRAPH_RELATION_MISSING
        			,context
        			,rel);
        }

        SearchGraphEdge edgeTarget = new SearchGraphEdge();
		SearchGraphEdge edgeTargetinverse = new SearchGraphEdge();

		SearchGraphEdge edgeSource = new SearchGraphEdge();
		SearchGraphEdge edgeSourceinverse = new SearchGraphEdge();

		//		<--Source--     --Target-->
		// Source        Relation          Target
		//      --invSource->  <-invTarget--

		//Source
		edgeSource.setSourceNode(relationnode);
		edgeSource.setTargetNode(source);
		edgeSource.setSource(true);
		edgeSource.setWeight(RELATION_WEIGHT);
		edgeSource.setOldWeight(RELATION_WEIGHT);
		edgeSource.setVPMEdgeType(EdgeType.SOURCE);
		edgeSource.setName(relationnode.getName()+"->"+source.getName());
		//edgeSource.setParentinEMF(rel);
		source.addSource(edgeSource);

		//inverse source edge
		edgeSourceinverse.setSourceNode(source);
		edgeSourceinverse.setTargetNode(relationnode);
		edgeSourceinverse.setSource(false);
		edgeSourceinverse.setWeight(RELATION_WEIGHT);
		edgeSourceinverse.setOldWeight(RELATION_WEIGHT);
		edgeSourceinverse.setVPMEdgeType(EdgeType.SOURCE);
		edgeSourceinverse.setName(source.getName()+"->"+relationnode.getName());
		//edgeSourceinverse.setParentinEMF(rel);
		relationnode.addSource(edgeSourceinverse);

		edgeSource.setInverseEdge(edgeSourceinverse);


		//Target
		edgeTarget.setTargetNode(target);
		edgeTarget.setSourceNode(relationnode);
		edgeTarget.setSource(true);
		edgeTarget.setWeight(RELATION_WEIGHT);
		edgeTarget.setOldWeight(RELATION_WEIGHT);
		edgeTarget.setVPMEdgeType(EdgeType.TARGET);
		edgeTarget.setName(relationnode.getName()+"->"+target.getName());
		//edgeTarget.setParentinEMF(rel);
		target.addSource(edgeTarget);

		//inverse Target edge
		edgeTargetinverse.setTargetNode(relationnode);
		edgeTargetinverse.setSourceNode(target);
		edgeTargetinverse.setSource(false);
		edgeTargetinverse.setWeight(RELATION_WEIGHT);
		edgeTargetinverse.setOldWeight(RELATION_WEIGHT);
		edgeTargetinverse.setVPMEdgeType(EdgeType.TARGET);
		edgeTargetinverse.setName(target.getName()+"->"+relationnode.getName());
		//edgeTargetinverse.setParentinEMF(rel);
		relationnode.addSource(edgeTargetinverse);

		edgeTarget.setInverseEdge(edgeTargetinverse);

		//traceability
		//source
		EdgeTraceabilityElement sourceEdgeTraceability = new EdgeTraceabilityElement(edgeSource,rel);
		traceabilityMapping.put(edgeSource, sourceEdgeTraceability);

	    //source inverse
	    EdgeTraceabilityElement sourceInverseEdgeTraceability = new EdgeTraceabilityElement(edgeSourceinverse,rel);
		traceabilityMapping.put(edgeSourceinverse, sourceInverseEdgeTraceability);

		//target
		EdgeTraceabilityElement targetEdgeTraceability = new EdgeTraceabilityElement(edgeTarget,rel);
		traceabilityMapping.put(edgeTarget, targetEdgeTraceability);

	    //target inverse
	    EdgeTraceabilityElement targetInverseEdgeTraceability = new EdgeTraceabilityElement(edgeTargetinverse,rel);
		traceabilityMapping.put(edgeTargetinverse, targetInverseEdgeTraceability);
	}

	/** True if element is a dangling edge in the bodyNode and not contained in the alreadyProcessed list
	 * @param element The element to test
	 * @param bodyNode Body node containing the GT pattern
	 * @param alreadyProcessedDanglings List containing the already processed dangling edges
	 * @return
	 */
	private boolean isDangling(VPMElement element,BodyNode bodyNode, List<DanglingVPMElementDTO> alreadyProcessedDanglings) {
		GTPatternBody body = bodyNode.getBody();

		if(alreadyProcessedDanglings.contains(element))
			return Boolean.FALSE;

		Iterator<Relation> iter = body.getDanglingRelations().iterator();
		while(iter.hasNext())
			{
			TreeIterator<EObject> elements_iter = ((EObject)iter.next()).eAllContents();
			while(elements_iter.hasNext())
				{if(elements_iter.next().equals(element))
			        return Boolean.TRUE;
				}
			}
		Iterator<Relationship> iter2 = body.getDanglingRelationships().iterator();
		while(iter.hasNext())
			{
			TreeIterator<EObject> elements_iter = ((EObject)iter2.next()).eAllContents();
			while(elements_iter.hasNext())
				{if(elements_iter.next().equals(element))
			        return Boolean.TRUE;
				}
			}
		return Boolean.FALSE;
	}


	/** Adds the dangling relations & relationships (and their additional relations and relationships) to the search graph
	 * @param danglings List of Dangling model elements
	 * @param result The Flattened pattern containing the resulting search graph
	 * @param alreadyProcessedDanglings Dangling elements already processed during the evaluation (to check circles between dangling edges)
	 * @throws PatternMatcherCompileTimeException
	 */
	private void evaluateDanglingElements(List<DanglingVPMElementDTO> danglings, FlattenedPattern result, List<DanglingVPMElementDTO> alreadyProcessedDanglings) throws PatternMatcherCompileTimeException{
		 ArrayList<DanglingVPMElementDTO> additionalDanglingElements = new ArrayList<DanglingVPMElementDTO>();

		 	for(DanglingVPMElementDTO dto: danglings){
				VPMElement element = dto.getElement();
				BodyNode bodyNode= dto.getBodyNode();

				if(element instanceof Relation)
					{
					evaluateModelElement((ModelElement) element,result,bodyNode);
					for (ModelElement elem: ((Relation)element).getType()) {
						if(isDangling(elem,bodyNode,alreadyProcessedDanglings))
							additionalDanglingElements.add(new DanglingVPMElementDTO(elem,bodyNode));
					}
					for (Relationship elem : ((Relation)element).getSuperRelationships()) {
						if(isDangling(elem,bodyNode,alreadyProcessedDanglings))
							additionalDanglingElements.add(new DanglingVPMElementDTO(elem,bodyNode));
					}
					for (Relation elem : ((Relation)element).getRelationsFrom()) {
						if(isDangling(elem,bodyNode,alreadyProcessedDanglings))
							additionalDanglingElements.add(new DanglingVPMElementDTO(elem,bodyNode));
					}
					for (Relation elem : ((Relation)element).getRelationsTo()) {
						if(isDangling(elem,bodyNode,alreadyProcessedDanglings))
							additionalDanglingElements.add(new DanglingVPMElementDTO(elem,bodyNode));
						}

					connectElements((Relation)element, result, bodyNode);

					}
				else if(element instanceof Relationship)
					{
					VariableID supplierID = bodyNode.getVariableID(((Relationship) element).getSupplierStr());
					//supplier is a constant -> cannot be unresolvable dangling relation
					if (!result.containsIndex(supplierID))
						{
						evaluateRelationship((Relationship)element, result, bodyNode);
						}
					else
						{
						//supplier is a variable input type or not defined in the actual body
						SearchGraphNode suppliernode = getSearchNode(result.getIndex(supplierID));

						//the supplier node is an unresolvable dangling element
						if(suppliernode == null)
							{
							String[] context ={ element instanceof SupertypeOf ?"supertypeOf":"instanceOf",((Relationship)element).getSupplierStr() };
							throw new PatternMatcherCompileTimeException(PatternMatcherErrorStrings.INTERNAL_SEARCGRAPH_RELATION_SOURCE_MISSING
					    			,context
					    			,element);
							}

						//it has a supplier can be processed
						evaluateRelationship((Relationship)element, result, bodyNode);
						}
					}
				else
					{String[] context = {element.toString()};
					throw new PatternMatcherCompileTimeException(PatternMatcherErrorStrings.INTERNAL_ERROR_DANGLING_RELATION_FAILED
								,context
								,element);
					}

				alreadyProcessedDanglings.add(dto);
		 	}

			if(additionalDanglingElements.size()!= 0)
				evaluateDanglingElements(additionalDanglingElements, result, alreadyProcessedDanglings);
	}

	public void connectDanglingRelations(FlattenedPattern result) throws PatternMatcherCompileTimeException {
		//TODO: is it possible to have a dangling edge with constant source or target node?
	    if(danglingElements.size()!= 0)
	    	evaluateDanglingElements(danglingElements, result, new ArrayList<DanglingVPMElementDTO>());
	}

	/** Creates the corresponding SearchGraphnode with type information about the input ModelElement
	 * @param rel The model element that has to be added to the search graph
	 * @param result Container for the search graph
	 * @param bodyNode The body node describes the search graph that has to be built up
	 */
	private void evaluateModelElement(ModelElement rel, FlattenedPattern result, BodyNode bodyNode) {
		SearchGraphEdge edge = null;
		VariableID relID = bodyNode.getVariableID(rel);

		// don't have explicit type relation, have to connect it to the Entity or relation global type
		if(rel.getType().size() == 0) {
			edge = new SearchGraphEdge();
			edge.setVPMEdgeType(EdgeType.INSTANCEOF);
			edge.setWeight(INSTANCEOF_WEIGHT*3);
			edge.setOldWeight(INSTANCEOF_WEIGHT*3);
			edge.setSource(true);
			//traceability Information
			EdgeTraceabilityElement edgeTraceability = new EdgeTraceabilityElement(edge,rel);
			traceabilityMapping.put(edge, edgeTraceability);

			//its an Entity
			if(rel instanceof Entity) {
			    // have to create the entity searchGraph node
			    if( getSearchNode(VPM_ENTITY) == null) {
			        ConstantSearchGraphNode ent = new ConstantSearchGraphNode();
			        ent.setName("Entity");
			        ent.setElement(VPM_ENTITY_FQN);
			        searchNodes.put(VPM_ENTITY, ent);
			        //traceability Information
			        ConstantNodeTraceabilityElement traceability = new ConstantNodeTraceabilityElement(ent,rel);
			        //TODO what to do if it is the vpm.Entity element? Currently it is the pattern variable (rel)
			        traceabilityMapping.put(ent, traceability);
			    }
			    edge.setSourceNode( getSearchNode(VPM_ENTITY));
			    edge.setName("Entity-ins->"+rel.getName());
			} else {
                // have to create the Relation SearchGraph node
			    if( getSearchNode(VPM_RELATION) == null) {
			        ConstantSearchGraphNode ent = new ConstantSearchGraphNode();
			        ent.setName("Relation");
			        ent.setElement(VPM_RELATION_FQN);
			        searchNodes.put(VPM_RELATION, ent);

			        //traceability Information
			        ConstantNodeTraceabilityElement traceability = new ConstantNodeTraceabilityElement(ent,rel);
			        //TODO what to do if it is the vpm.Relation element?
			        traceabilityMapping.put(ent, traceability);
			    }
			    edge.setSourceNode( getSearchNode(VPM_RELATION));
			    edge.setName("Relation-ins->"+rel.getName());
			}
		}

		if(result.containsIndex(relID)) {
		//its a variable type element
		    if(!searchNodes.containsKey(result.getIndex(relID))) {
		        VariableSearchGraphNode node = new VariableSearchGraphNode();
		        node.setId(result.getIndex(relID));
		        node.setName(relID.getFancyName());
		        searchNodes.put(node.getId(),node);

		        //traceability
		        VariableNodeTraceabilityElement traceability = new VariableNodeTraceabilityElement(node,rel);
		        traceabilityMapping.put(node, traceability);

		        //create new else branch needed for every new IMOdelElement type
 		        if(rel instanceof Entity)
		        	node.setVpmModelElementType(VPMModelElementType.ENTITY);
 		        if(rel instanceof Relation)
 		        	node.setVpmModelElementType(VPMModelElementType.RELATION);

 		        if(rel.getType().size() == 0) {
		            edge.setTargetNode(node);
		            node.addSource(edge);
		        }
		    }
		} else
		//its a constant node
		if(constantNodes.containsKey(rel.getName())) {
			ConstantSearchGraphNode node = new ConstantSearchGraphNode();
			node.setElement(rel.getRealElement());
			node.setName(rel.getRealElement());
			searchNodes.put(constantNodesNumber,node);
			constantNodes.put(node.getName(), constantNodesNumber);
			constantNodesNumber--;

			 //traceability Information
	        ConstantNodeTraceabilityElement traceability = new ConstantNodeTraceabilityElement(node,rel);
	        traceabilityMapping.put(node, traceability);

			if(rel.getType().size() == 0) {
			    edge.setTargetNode(node);
			    node.addSource(edge);
			}
		}
	}

	private void evaluateRelationship(Relationship rel, FlattenedPattern result, BodyNode bodyNode) {
		SearchGraphNode suppliernode = null;
		SearchGraphEdge edge = new SearchGraphEdge();
		SearchGraphEdge invedge = null;
		//supplier
		ModelElement supplier = rel.getSupplier();
		String supplierName = rel.getSupplierStr();
		VariableID supplierID = bodyNode.getVariableID(supplierName);
		//client
		//ModelElement client = rel.getClient();
		String clientName = rel.getClientStr();
		VariableID clientID = bodyNode.getVariableID(clientName);

		VariableSearchGraphNode clientnode =(VariableSearchGraphNode)searchNodes.get(result.getIndex(clientID));

		if (result.containsIndex(supplierID)) {
		    //supplier is a variable input type or not defined in the actual body
			suppliernode = getSearchNode(result.getIndex(supplierID));

			//the supplier node is a dangling element, needs to be processed later
			if(suppliernode == null)
				{
				danglingElements.add(new DanglingVPMElementDTO(rel, bodyNode));
	        	return;
				}
		} else {
            // supplier is a constant
			if (constantNodes.containsKey(supplierName)) {
				suppliernode =  getSearchNode(constantNodes.get(supplierName));
			} else {
				suppliernode = new ConstantSearchGraphNode();
			    ((ConstantSearchGraphNode)suppliernode).setElement(supplier.getRealElement());
			    suppliernode.setName(((ConstantSearchGraphNode)suppliernode).getElement());
			    searchNodes.put(constantNodesNumber,suppliernode);
			    constantNodes.put(suppliernode.getName(), constantNodesNumber);
			    constantNodesNumber--;

			    //Traceability
			    ConstantNodeTraceabilityElement traceability = new ConstantNodeTraceabilityElement((ConstantSearchGraphNode)suppliernode,supplier);
		        traceabilityMapping.put(suppliernode, traceability);
			}
		}

		if (rel instanceof TypeOf) {
			edge.setVPMEdgeType(EdgeType.INSTANCEOF);
			edge.setTargetNode(clientnode);
			edge.setWeight(INSTANCEOF_WEIGHT);
			edge.setOldWeight(INSTANCEOF_WEIGHT);
			edge.setSource(true);
			edge.setSourceNode(suppliernode);
			edge.setName(suppliernode.getName()+"_instanceof_"+clientnode.getName());
			clientnode.addSource(edge);

			//inverse of instanceof
			if (suppliernode instanceof VariableSearchGraphNode) {
				invedge = new SearchGraphEdge();
				invedge.setVPMEdgeType(EdgeType.INSTANCEOF);
				invedge.setTargetNode(suppliernode);
				invedge.setWeight(INSTANCEOF_WEIGHT*2);
				invedge.setOldWeight(INSTANCEOF_WEIGHT*2);
				invedge.setSource(false);
				invedge.setSourceNode(clientnode);
				invedge.setName(suppliernode.getName()+"_instanceofINV_"+clientnode.getName());
				suppliernode.addSource(invedge);

				edge.setInverseEdge(invedge);

				//traceability inverse
				EdgeTraceabilityElement inverseEdgeTraceability = new EdgeTraceabilityElement(invedge,rel);
				traceabilityMapping.put(invedge, inverseEdgeTraceability);
			}
		} else {
			edge.setVPMEdgeType(EdgeType.SUPERTYPEOF);
			edge.setTargetNode(suppliernode);
			edge.setSourceNode(clientnode);
			edge.setSource(true);
			edge.setWeight(SUPERTYPE_WEIGHT);
			edge.setOldWeight(SUPERTYPE_WEIGHT);
			edge.setName(suppliernode.getName()+"_supertypeof_"+clientnode.getName());
			//edge.setParentinEMF(rel);
			suppliernode.addSource(edge);

			//inverse
			invedge = new SearchGraphEdge();
			invedge.setVPMEdgeType(EdgeType.SUPERTYPEOF);
			invedge.setTargetNode(clientnode);
			invedge.setSourceNode(suppliernode);
			invedge.setSource(false);
			invedge.setWeight(SUPERTYPE_WEIGHT*2);
			invedge.setOldWeight(SUPERTYPE_WEIGHT*2);
			invedge.setName(suppliernode.getName()+"_supertypeof_INV"+clientnode.getName());
			clientnode.addSource(invedge);

			edge.setInverseEdge(invedge);

			//inverse relationship traceability
			EdgeTraceabilityElement inverseEdgeTraceability = new EdgeTraceabilityElement(invedge,rel);
			traceabilityMapping.put(invedge, inverseEdgeTraceability);
		}

		//relationship traceability
		EdgeTraceabilityElement edgeTraceability = new EdgeTraceabilityElement(edge,rel);
		traceabilityMapping.put(edge, edgeTraceability);
	}

	public void add(PatternReferenceNode prNode, FlattenedPattern result) throws PatternMatcherCompileTimeException {
		final PatternNode reference = prNode.getReference();
		final List<Term> actualParameters = prNode.getActualParameters();
		final BodyNode parent = (BodyNode) prNode.getParent();
		int weight = PATTERNCALL_WEIGHT;
		//the parameter order of the pattern call mapped to the id values of the searchGraphNodes
		Integer[] parameterMapping = new Integer[actualParameters.size()];

		//The pattern call node
		PatternCallSearchGraphNode patternCallNode = new PatternCallSearchGraphNode();
		int index = result.addVariable(null);

        patternCallNode.setName("PatternCallof_"+reference.getPattern().getName());
        patternCallNode.setId(index);
        patternCallNode.setVpmModelElementType(VPMModelElementType.OPERATION);
        patternCallNode.setPatternNode(reference);
        searchNodes.put(patternCallNode.getId(),patternCallNode);


        //traceability pattern call
		PatternCallNodeTraceabilityElement patternCallTraceabilityElement= new PatternCallNodeTraceabilityElement(patternCallNode,prNode.getPatternCall());
		traceabilityMapping.put(patternCallNode, patternCallTraceabilityElement);

		//if it is an incrementally matched pattern call new weigh values are set and it is attached to the Storage node
        if(prNode.getReference() instanceof PatternNodeIncremental)
        	{//TODO: traceability of the storage node and its edge? Is it needed?
        	weight = PATTERNCALL_INCREMENTAL_WEIGHT;

        	SearchGraphEdge edge = null;
    		edge = new SearchGraphEdge();
    		edge.setVPMEdgeType(EdgeType.PATTERN_CALL_STORAGE);
    		edge.setWeight(PATTERNCALL_STORAGE_INCREMENTAL_WEIGHT);
    		edge.setOldWeight(PATTERNCALL_STORAGE_INCREMENTAL_WEIGHT);
    		edge.setSource(true);
    		// have to create the Storage node
    		if( getSearchNode(PATTERN_CALL_STORAGE_NODE) == null) {
    		       ConstantSearchGraphNode ent = new ConstantSearchGraphNode();
    		       ent.setName("Pattern_Call_Storage_Node");
    		       ent.setElement(VPM_ENTITY_FQN);
    		       searchNodes.put(PATTERN_CALL_STORAGE_NODE, ent);
    		    }
    		//sets the target and the source nodes
    		edge.setSourceNode( getSearchNode(PATTERN_CALL_STORAGE_NODE));
    		edge.setName("PatternStorage-store->"+patternCallNode.getName());

    		edge.setTargetNode(patternCallNode);
    		patternCallNode.addSource(edge);
        	}

        //connecting the variables to the pattern call
        for (int i = 0; i < actualParameters.size(); i++) {
        	if (actualParameters.get(i) instanceof VariableReference) {
	        	VariableReference varRef= (VariableReference) actualParameters.get(i);
	        	SearchGraphNode inputNode = null;
	        	//the node is already processed in the flattened pattern
	        	Integer variableIndex = result.getIndex(parent.getVariableID(varRef.getVariable()));
	        	if (searchNodes.containsKey(variableIndex)) {
	        		inputNode =  getSearchNode(variableIndex);
	        		parameterMapping[i] = ((VariableSearchGraphNode)inputNode).getId();
	        	} else {
	        		// new search graph node only used in the pattern call!
	        		inputNode = new VariableSearchGraphNode();

	        		int id;
	        		inputNode.setName(parent.getVariableID(varRef.getVariable()).toString());
	        		//recursive pattern matching call
	        		if (result.getIndex(parent.getVariableID(varRef.getVariable())) != null) {
	        			//the parameter is passed through the pattern
	        			//already has an index
	        			id = result.getIndex(parent.getVariableID(varRef.getVariable()));
	        		} else{
	        			//new id
	        			id = result.addVariable(parent.getVariableID(varRef.getVariable()));
	        		}

	        		((VariableSearchGraphNode)inputNode).setId(id);
	        		searchNodes.put(((VariableSearchGraphNode)inputNode).getId(), inputNode);

	        		parameterMapping[i] = id;

	        		//traceability
			        VariableNodeTraceabilityElement traceability = new VariableNodeTraceabilityElement((VariableSearchGraphNode) inputNode,varRef);
			        traceabilityMapping.put(inputNode, traceability);

	        		//System.out.println("Pattern Call inside GT pattern with through-passed variables");
	        	}
	        	//connects the pattern node to its input parameter nodes
	        	SearchGraphEdge edgePatternCall = new SearchGraphEdge();
	    		SearchGraphEdge edgePatternCallinverse = new SearchGraphEdge();

	    		//		        <--PatternCall--
	    		// Input Variable                  Pattern Call
	    		//              --PatternCallinverse->

	    		//pattern call edge
	    		edgePatternCall.setSourceNode(inputNode);
	    		edgePatternCall.setTargetNode(patternCallNode);
	    		edgePatternCall.setSource(true);
	    		edgePatternCall.setWeight(weight);
	    		edgePatternCall.setOldWeight(weight);
	    		edgePatternCall.setVPMEdgeType(EdgeType.PATTERN_CALL_PARAMETER);
	    		edgePatternCall.setName(inputNode.getName()+"->"+patternCallNode.getName());
	    		//edgeSource.setParentinEMF();
	    		patternCallNode.addSource(edgePatternCall);

	    		//inverse pattern call edge
	    		edgePatternCallinverse.setSourceNode(patternCallNode);
	    		edgePatternCallinverse.setTargetNode(inputNode);
	    		edgePatternCallinverse.setSource(false);
	    		edgePatternCallinverse.setWeight(PATTERNCALLINV_WEIGHT);
	    		edgePatternCallinverse.setOldWeight(PATTERNCALLINV_WEIGHT);
	    		edgePatternCallinverse.setVPMEdgeType(EdgeType.PATTERN_CALL_PARAMETER);
	    		edgePatternCallinverse.setName(patternCallNode.getName()+"->"+inputNode.getName());
	    		//edgeSourceinverse.setParentinEMF(rel);
	    		inputNode.addSource(edgePatternCallinverse);

	    		edgePatternCall.setInverseEdge(edgePatternCallinverse);

	    		//traceability edge
	    		EdgeTraceabilityElement edgeTraceability = new EdgeTraceabilityElement(edgePatternCall,varRef);
	    		traceabilityMapping.put(edgePatternCall, edgeTraceability);

	    		//traceability edge
	    		EdgeTraceabilityElement inverseEdgeTraceability = new EdgeTraceabilityElement(edgePatternCallinverse,varRef);
	    		traceabilityMapping.put(edgePatternCallinverse, inverseEdgeTraceability);
	        } else {
	        	String[] context = {""+i, prNode.getPatternCall().getCalledPattern().getName()};
	        	PatternMatcherCompileTimeException e = new PatternMatcherCompileTimeException(PatternMatcherErrorStrings.ILLEGAL_INPUT_PARAMETER
	        			,context
	        			,actualParameters.get(i));
	        	throw e;
	        }
        }
        patternCallNode.setInputParameterMapping(parameterMapping);
	}

	public GTOperationContext generateGTOperations(Collection<GTElementMapping> gtElementMappings
			,IModelManager manager
	        ,PatternCallSignature[] signatures)
	throws GTRuleBuildingException {

		initSearchGraph();
		ArrayList<IUpdatePlanOperation> manipulationOperations = new ArrayList<IUpdatePlanOperation>();
		ArrayList<ISearchPlanOperation> checkSet = new ArrayList<ISearchPlanOperation>();
		Collection<IUpdatePlanOperation> postSearchPlanOperations = new Vector<IUpdatePlanOperation>();
		ElementManipulationOperation operation = null;
		hasOneInConstraint = new HashMap<SearchGraphNode, Boolean>();

		//Adds the to delete input variables to the manipulation operation plan
		if(gtElementMappings != null)
		 for(GTElementMapping map: gtElementMappings)
			//have to keep the element
			if(searchNodes.containsKey(map.getRhsInputOrderIndex()))
				{map.setMappingType(GTElementMappingType.KEEP);
				//all mapped elements are input parameters for the RHS
				((VariableSearchGraphNode) getSearchNode(map.getRhsInputOrderIndex())).setInput(true);
				((VariableSearchGraphNode) getSearchNode(map.getRhsInputOrderIndex())).setChecked(true);
				}
			else//have to delete the element
				{
				map.setMappingType(GTElementMappingType.DEL);
				manipulationOperations.add(new DeleteModelElement(manager, map.getRhsInputOrderIndex()));
				}

        // All input parameter specific operations + Check set are generated
    	for (int j = 0; j < signatures.length; j++) {
             if (searchNodes.containsKey(j) &&  getSearchNode(j) instanceof VariableSearchGraphNode) {
            	VariableSearchGraphNode node = (VariableSearchGraphNode)  getSearchNode(j);
                if(signatures[j].getParameterMode().equals(ParameterMode.INPUT)) {
                	{node.setInput(true);
                	 Collection<IUpdatePlanOperation> _temp= GTOperationGenerator.getInputSpecificOperation(node,manager,checkSet);
                	 if(_temp != null && _temp.size() > 0)
                		 postSearchPlanOperations.addAll(_temp);
                	}
                } else {
                	node.setInput(false);
                }
             }
        }
    	//generateInit(inputMapping, signature, template,manager, gtElementMappings);
		searchNodeOrder = alg.evaluateSearchPlan(this);
		//boolean hasINConstraint = false;
		for(SearchGraphNode node : searchNodeOrder) {
			if(node instanceof ConstantSearchGraphNode) {
				node.setChecked(true);
            }
			GTRuleValidator.validateContainment(node, manager,hasOneInConstraint);
			//all not mapped variable search graph node have to be created
			if((!node.isChecked()) && node.getTreeEdge() != null
					&& (!node.getTreeEdge().isChecked())) {
				 operation = GTOperationGenerator.getModelManipulationOperation((VariableSearchGraphNode)node, manager,checkSet,this);
				 if(operation!= null) {
				     //operation.toString();
				     manipulationOperations.add(operation);
				 }
			}
			//edges that have to be created
			for(SearchGraphEdge edge: node.getSources()) {
				if(edge.getSourceNode().isChecked() && edge.getTargetNode().isChecked() && !edge.isChecked()) {
				    operation = GTOperationGenerator.getModelManipulationOperation(edge,  manager,checkSet,this);
				    if(operation!= null) {
				        //operation.toString();
				        manipulationOperations.add(operation);
				    }
				}
			}
		}
//		 have to check if there are unchecked element in the searchGraph (they must be created or simply checked)
		boolean noUncheckedOperation = true;

		do {
		noUncheckedOperation = true;
			for(SearchGraphNode node : searchNodeOrder) {
				if(!node.isChecked()) {
					//System.out.println("Node: "+node.getName());
					operation = GTOperationGenerator.getModelManipulationOperation((VariableSearchGraphNode)node, manager , checkSet,this);
					if(operation == null)
						{noUncheckedOperation = false;}
					else {
						manipulationOperations.add(operation);
						node.setChecked(true);
					}
				}
				//edge checking
				for(SearchGraphEdge edge : node.getSources())
					if(!edge.isChecked()
							&& edge.getSourceNode().isChecked()
							&& edge.getTargetNode().isChecked())
						{operation = GTOperationGenerator.getModelManipulationOperation(edge, manager, checkSet,this);
						//System.out.println("Edge: "+node.getName());
						if(operation == null)
							{noUncheckedOperation = false;}
						else
							{
							manipulationOperations.add(operation);
							edge.setChecked(true);
							}
						}
			}
		} while(!noUncheckedOperation);

		if(postSearchPlanOperations.size() != 0)
			manipulationOperations.addAll(postSearchPlanOperations);

		GTRuleValidator gtRuleValidator = new GTRuleValidator();
		gtRuleValidator.validateOperationPlan(manipulationOperations,checkSet,gtElementMappings,this);


		return new GTOperationContext(null,manipulationOperations,checkSet);
	}

	public Collection<SearchPlanOperation> generateSearchPlan(FlattenedPattern pattern, Boolean[] adornment, IModelManager manager) throws PatternMatcherRuntimeException{
        // Search graph initialization and search plan generation
    	for (int j = 0; j < adornment.length; j++) {
    		SearchGraphNode node = getSearchNode(j);
            if (node instanceof VariableSearchGraphNode) {
            	((VariableSearchGraphNode) node).setInput(adornment[j]);
            }
        }
    	searchNodeOrder= alg.evaluateSearchPlan(pattern.getSearchGraph());
    	return VPMPatternOperationGenerator.evaluateVPMOperationPlan(searchNodeOrder, new MatchingFrame(pattern),manager);
	}

	public AnnotatedElement getGTASMRepresentation(AbstractNode node) {
		return node.getTraceabilityElement().getRepresentativeEMFElement();
	}

	public void addTraceabilityElement(SearchGraphEdge edge, EdgeTraceabilityElement element){
		traceabilityMapping.put(edge, element);
	}

	public void addTraceabilityElement(SearchGraphNode node, NodeTraceabilityElement element){
		traceabilityMapping.put(node, element);
	}
}