code: package org.eclipse.emf.henshin.interpreter.loose;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Map.Entry;
  
  import org.eclipse.emf.ecore.EObject;
  import org.eclipse.emf.ecore.EReference;
  import org.eclipse.emf.henshin.interpreter.Assignment;
  import org.eclipse.emf.henshin.interpreter.EGraph;
  import org.eclipse.emf.henshin.interpreter.Engine;
  import org.eclipse.emf.henshin.interpreter.Match;
  import org.eclipse.emf.henshin.interpreter.impl.AssignmentImpl;
  import org.eclipse.emf.henshin.interpreter.impl.MatchImpl;
  import org.eclipse.emf.henshin.interpreter.info.VariableInfo;
  import org.eclipse.emf.henshin.interpreter.matching.constraints.DanglingConstraint;
  import org.eclipse.emf.henshin.model.Action.Type;
  import org.eclipse.emf.henshin.model.Attribute;
  import org.eclipse.emf.henshin.model.Edge;
  import org.eclipse.emf.henshin.model.Graph;
  import org.eclipse.emf.henshin.model.Node;
  import org.eclipse.emf.henshin.model.Parameter;
  import org.eclipse.emf.henshin.model.Rule;
  
  public class LocallyCompleteMatchFinder {
  	Rule rule;
  	EGraph graph;
  	Engine engineImpl;
  	Map<Parameter, Object> paramValues;
  
  	public LocallyCompleteMatchFinder(Rule rule, EGraph graph, Engine engineImpl) {
  		super();
  		this.rule = rule;
  		this.graph = graph;
  		this.engineImpl = engineImpl;
  		this.paramValues = new HashMap<Parameter, Object>();
  	}
  
  	/**
  	 * Returns a loose match, potentially contain mappings for LHS and RHS nodes.
  	 * 
  	 * @param rule
  	 * @param graph
  	 * @param engineImpl
  	 * @return
  	 */
  	public Match findLocallyCompleteMatch() {
  		SpecialRuleInfo kernelRuleInfo = KernelRuleHandler.createKernelRule(rule);
  		SpecialRuleInfo grayedRuleInfo = GrayedRuleHandler.createGrayedRule(rule);
  
  		Assignment assignment = KernelRuleHandler.convertParameterValues(kernelRuleInfo, paramValues);
  		Iterable<Match> kernelMatches = engineImpl.findMatches(kernelRuleInfo.getSpecialRule(), graph,
  				new MatchImpl(assignment, false));
  		if (!kernelMatches.iterator().hasNext())
  			return null;
  
  		Match kernelMatch = kernelMatches.iterator().next();
  		Match originalMatch = KernelRuleHandler.translateMatchFromKernel(kernelRuleInfo, kernelMatch);
  		Match grayedMatch = GrayedRuleHandler.translateMatchFromOriginal(grayedRuleInfo, originalMatch);
  
  		Rule grayedRule = grayedRuleInfo.getSpecialRule();
  		List<Node> unboundNodeList = getUnboundNodes(grayedMatch, grayedRule);
  		
  		HashMap<Node, EObject> mapping = new HashMap<Node, EObject>();
  		for (Node n : grayedRule.getLhs().getNodes()) {
  			EObject x = grayedMatch.getNodeTarget(n);
  			if (x != null)
  				mapping.put(n, x);
  		}
  
  		Map<Node, EObject> extension = findExtension(grayedRule, mapping, graph, unboundNodeList, 0);
  
  		for (Entry<Node, EObject> entry : extension.entrySet()) {
  			grayedMatch.setNodeTarget(entry.getKey(), entry.getValue());
  		}
  		return GrayedRuleHandler.translateMatchFromGrayed(grayedRuleInfo, grayedMatch);
  	}
  
  	private List<Node> getUnboundNodes(Match resultMatch, Rule rule) {
  		List<Node> result = new ArrayList<Node>();
  		for (Node n : rule.getLhs().getNodes())
  			if (resultMatch.getNodeTarget(n) == null)
  				result.add(n);
  		return result;
  	}
  
  
  	private Collection<EObject> findExtensionCandidates(Map<Node, EObject> currentMatch, EGraph graph, Node n) {
  		// Try to find an "anchor": a node that is connected to
  		// n and already has a match
  		Node anchor = null;
  		Edge anchorEdge = null;
  		EObject anchorObject = null;
  		boolean anchorIsSource = false;
  
  		for (Edge e : n.getAllEdges()) {
  			if (currentMatch.get(e.getSource()) != null) {
  				anchor = e.getSource();
  				anchorIsSource = true;
  				anchorEdge = e;
  				anchorObject = currentMatch.get(e.getSource());
  				break;
  			}
  
  			if (currentMatch.get(e.getTarget()) != null) {
  				anchor = e.getTarget();
  				anchorIsSource = false;
  				anchorEdge = e;
  				anchorObject = currentMatch.get(e.getTarget());
  				break;
  			}
  		}
  
  		List<EObject> candidateObjects = determineCandidates(graph, n, anchor, anchorEdge, anchorObject,
  				anchorIsSource);
  		candidateObjects.removeAll(currentMatch.keySet());
  
  		Collection<EObject> result = new ArrayList<>();
  		for (EObject cand : candidateObjects) {
  			if (fulfillsConstraints(cand, n, currentMatch)) {
  				result.add(cand);
  			}
  		}
  		return result;
  	}
  
  	@SuppressWarnings("rawtypes")
  	private boolean fulfillsConstraints(EObject cand, Node n, Map<Node, EObject> currentMatch) {
  		// minimalistic constraint checking..
  		// 1. no type-constraint check. these are already covered
  		// by the candidate selection process
  
  		// 2. edge constraint checks
  		for (Edge e : n.getOutgoing()) {
  			if (currentMatch.get(e.getTarget()) != null) {
  				EObject expected = currentMatch.get(e.getTarget());
  				Object real = cand.eGet(e.getType()); // collection or 1 EObject
  				boolean passed = (expected == real)
  						|| ((real instanceof Collection) && ((Collection) real).contains(expected));
  				if (!passed) {
  					return false;
  				}
  			}
  		}
  		for (Edge e : n.getIncoming()) {
  			if (currentMatch.get(e.getSource()) != null) {
  				EObject source = currentMatch.get(e.getSource());
  				Object real = source.eGet(e.getType()); // collection or 1 EObject
  				boolean passed = (cand == real) || ((real instanceof Collection) && ((Collection) real).contains(cand));
  				if (!passed) {
  					return false;
  				}
  			}
  		}
  
  		// dangling constraint checks
  		if (n.getAction().getType() == Type.DELETE) {
  			DanglingConstraint dc = retrieveDanglingConstraint(n);
  			if (!dc.check(cand, graph))
  				return false;			
  		}
  
  		// for now: only static values checked - attributes, ints, strings, floats
  		for (Attribute a : n.getAttributes()) {
  			String expectedValString = a.getValue();
  			Object expectedVal = null;
  			if (expectedValString.startsWith("\"") && expectedValString.endsWith("\"")) {
  				expectedVal = expectedValString.substring(1, expectedValString.length() - 2);
  			}
  			try {
  				expectedVal = Double.parseDouble(expectedValString);
  			} catch (NumberFormatException e) {
  			}
  			try {
  				expectedVal = Integer.parseInt(expectedValString);
  			} catch (NumberFormatException e) {
  			}
  
  			Object actualVal = cand.eGet(a.getType());
  			if (actualVal == null)
  				continue;
  			if (actualVal.equals(expectedVal))
  				return false;
  		}
  
  		return true;
  	}
  
  	private DanglingConstraint retrieveDanglingConstraint(Node n) {
  		Map<Node, DanglingConstraint> node2Constraint = new HashMap<>();
  		DanglingConstraint entry = node2Constraint.get(n);
  		if (entry == null) {
  			Map<EReference, Integer> incoming = VariableInfo.getEdgeCounts(n, true);
  			Map<EReference, Integer> outgoing = VariableInfo.getEdgeCounts(n, false);
  			entry = new DanglingConstraint(outgoing, incoming, false);
  			node2Constraint.put(n, entry);
  		}
  		return entry;
  	}
  
  	@SuppressWarnings("rawtypes")
  	private List<EObject> determineCandidates(EGraph graph, Node n, Node anchor, Edge anchorEdge, EObject anchorObject,
  			boolean anchorIsSource) {
  		List<EObject> candidateObjects = new ArrayList<EObject>();
  		if (anchor != null) {
  			if (anchorIsSource) {
  				addEdgeTargetsToCandidateObjects(anchor, anchorEdge.getType(), anchorObject, candidateObjects);
  			} else {
  				if (anchorEdge.getType().getEOpposite() != null) {
  					addEdgeTargetsToCandidateObjects(anchor, anchorEdge.getType().getEOpposite(), anchorObject,
  							candidateObjects);
  				} else {
  					for (EObject cand : graph.getDomain(n.getType(), false)) {
  						Object o = cand.eGet(anchorEdge.getType());
  						if (o == anchor || (o instanceof Collection) && ((Collection) o).contains(anchor)) {
  							candidateObjects.add(cand);
  						}
  					}
  				}
  			}
  		} else {
  			candidateObjects.addAll(graph.getDomain(n.getType(), false));
  		}
  		return candidateObjects;
  	}
  
  	@SuppressWarnings({ "rawtypes", "unchecked" })
  	private void addEdgeTargetsToCandidateObjects(Node node, EReference ref, EObject anchorObject,
  			List<EObject> candidateObjects) {
  		Object o = anchorObject.eGet(ref);
  		if (o instanceof Collection) {
  			candidateObjects.addAll((Collection) o);
  		} else {
  			candidateObjects.add((EObject) o);
  		}
  	}
  
  	public void setParameter(String key, String value) {
  		Parameter param = rule.getParameter(key);
  		if (param != null)
  			paramValues.put(param, value);
  	}
  
  	public Map<Node, EObject> findExtension(Rule rule, Map<Node, EObject> currentMappings, EGraph graph,
  			List<Node> unboundNodeList, int position) {
  		Node n = unboundNodeList.get(position);
  
  		Collection<EObject> candidates = findExtensionCandidates(currentMappings, graph, n);
  		if (!candidates.isEmpty()) {
  //		 1. wiederhole, solange es noch neue gültige Teil-Lösungsschritte gibt:
  //		 a) wähle einen neuen gültigen Teil-Lösungsschritt
  			for (EObject x : candidates) {
  //		 b) falls Wahl gültig ist: I) erweitere Vektor um Wahl;
  				Map<Node, EObject> currentMappingsExtended = new HashMap<>(currentMappings);
  				currentMappingsExtended.put(n, x);
  
  //      	 II) falls Vektor vollständig ist, return true; // Lösung gefunden!
  				if (position == unboundNodeList.size() - 1) {
  					if (checkDanglingPostponed(rule, graph, currentMappingsExtended))
  						return currentMappingsExtended;
  					else
  //		 sonst mache Wahl rückgängig; // nächster Kandidat aus for-Schleife dran
  						currentMappingsExtended.remove(n);
  				}
  //               sonst: falls (FindeLösung(Stufe+1, Vektor)) return true; // Lösung!
  				else {
  					Map<Node, EObject> nextSolution = findExtension(rule, currentMappingsExtended, graph, 
  							unboundNodeList, position + 1);
  					if (nextSolution != null) {
  						return nextSolution;
  					} else {
  //	                    sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
  						currentMappingsExtended.remove(n);
  					}
  				}
  			}
  		} else  { //d.h., falls candidates == empty
  			if (position == unboundNodeList.size() - 1) {
  				if (checkDanglingPostponed(rule, graph, currentMappings))
  					return currentMappings;
  				else
  					return null;
  			} else {
  				return findExtension(rule, currentMappings, graph, unboundNodeList, position + 1);
  			}
  		}
  
  		// 2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!
  		return null;
  	}
  
  	private boolean checkDanglingPostponed(Rule rule, EGraph graph, Map<Node, EObject> solution) {
  		for (Node n : rule.getLhs().getNodes()) {
  			if (n.getAction().getType() == Type.DELETE) {
  				DanglingConstraint dc = retrieveDanglingConstraint(n);
  
  				// adapt edge counts
  				Map<EReference, Integer> removedIncoming = new HashMap<>();
  				Map<EReference, Integer> removedOutgoing = new HashMap<>();
  
  				for (Edge e : n.getIncoming()) {
  					if (solution.get(e.getSource()) == null) {
  						dc.increaseIncoming(e.getType(), -1);
  						if (removedIncoming.containsKey(e.getType()))
  							removedIncoming.put(e.getType(), 1 + removedIncoming.get(e.getType()));
  						else
  							removedIncoming.put(e.getType(), 1);
  					}
  				}
  				for (Edge e : n.getOutgoing()) {
  					if (solution.get(e.getTarget()) == null) {
  						dc.increaseOutgoing(e.getType(), -1);
  						if (removedOutgoing.containsKey(e.getType()))
  							removedOutgoing.put(e.getType(), 1 + removedOutgoing.get(e.getType()));
  						else
  							removedOutgoing.put(e.getType(), 1);
  					}
  				}
  
  				if (solution.get(n) != null && !dc.check(solution.get(n), graph))
  					return false;
  
  				// restore original edge counts
  				for (Entry<EReference, Integer> entry : removedIncoming.entrySet())
  					dc.increaseIncoming(entry.getKey(), entry.getValue());
  				for (Entry<EReference, Integer> entry : removedOutgoing.entrySet())
  					dc.increaseOutgoing(entry.getKey(), entry.getValue());
  			}
  		}
  		return true;
  	}
  
  }
  