plugins/org.eclipse.emf.henshin.sam.invcheck/src/org/eclipse/emf/henshin/sam/invcheck/filter/MergeSubgraphFilter.java

package org.eclipse.emf.henshin.sam.invcheck.filter;

import java.util.BitSet;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.emf.henshin.sam.invcheck.algorithm.IsomorphicPartMatcher;
import org.eclipse.emf.henshin.sam.invcheck.filter.CombinationProducer.Pair;
import org.eclipse.emf.henshin.sam.model.samannotation.AnnotatedElem;
import org.eclipse.emf.henshin.sam.model.samgraph.Edge;
import org.eclipse.emf.henshin.sam.model.samgraph.Graph;
import org.eclipse.emf.henshin.sam.model.samgraph.Node;
import org.eclipse.emf.henshin.sam.model.samrules.GraphRule;
import org.eclipse.emf.henshin.sam.model.samrules.RuleGraph;
import org.eclipse.emf.henshin.sam.model.samrules.SamrulesPackage;
import org.eclipse.emf.henshin.sam.model.samtrace.Match;
import org.eclipse.emf.henshin.sam.model.samtrace.SamtraceFactory;
import org.eclipse.emf.henshin.sam.model.samtypegraph.EdgeDirection;
import org.eclipse.emf.henshin.sam.model.samtypegraph.NodeType;
import org.eclipse.emf.henshin.sam.paf.FilterSkeleton;
import org.eclipse.emf.henshin.sam.paf.annotation.ResultDictEntry;

public class MergeSubgraphFilter
		extends FilterSkeleton<Pair<Pair<Graph, GraphRule>, Set<AnnotatedElem>>, Pair<Pair<Graph, GraphRule>, Match>> {

	private IsomorphicPartMatcher ipm;

	@ResultDictEntry(entryName = "Number of read items")
	private int readItems = 0;

	@ResultDictEntry(entryName = "Number of generated subgraphs")
	private int wroteItems = 0;

	public static void iterate(Graph host, Graph pattern) {
		// restrict to node types present in both graphs
		// Map<NodeType, Integer> typeCount = new HashMap<NodeType, Integer>();
		Map<NodeType, List<Node>> typedNodes = new HashMap<NodeType, List<Node>>();

		for (Node node : host.getNodes()) {
			/*
			 * if (typeCount.containsKey(node.getInstanceOf())) {
			 * typeCount.put(node.getInstanceOf(),
			 * typeCount.get(node.getInstanceOf()) + 1); } else {
			 * typeCount.put(node.getInstanceOf(), 1); }
			 */
			if (typedNodes.containsKey(node.getInstanceOf())) {
				typedNodes.get(node.getInstanceOf()).add(node);
			} else {
				typedNodes.put(node.getInstanceOf(), new LinkedList<Node>());
				typedNodes.get(node.getInstanceOf()).add(node);
			}
		}

		Node[][] nodes = new Node[typedNodes.keySet().size()][];
		Map<NodeType, Integer> typeMap = new HashMap<NodeType, Integer>();

		int typeIndex = 0;
		for (NodeType nodeType : typedNodes.keySet()) {
			typeMap.put(nodeType, typeIndex);
			nodes[typeIndex] = new Node[typedNodes.get(nodeType).size()];

			int nodeIndex = 0;
			for (Node n : typedNodes.get(nodeType)) {
				nodes[typeIndex][nodeIndex] = n;
				nodeIndex++;
			}
			typeIndex++;
		}

		// repeat for edges and edge types?

	}

	public void produce() {
		if (this.currentInput.second.size() == 0) {
			if (this.currentInput.first.first.eClass() == SamrulesPackage.eINSTANCE.getRuleGraph()
					&& ((RuleGraph) this.currentInput.first.first).getCondition() != null) {
				// disjoint case
				try {
					this.defaultOutputPipe.queue(new CombinationProducer.Pair<Pair<Graph, GraphRule>, Match>(
							this.currentInput.first, SamtraceFactory.eINSTANCE.createMatch()));
				} catch (InterruptedException e) {
					this.running = false;
				}
			}
		} else {
			this.ipm.setCurrentSubGraph(this.currentInput.second);
			this.ipm.reset();
			Match gm = this.ipm.getNextMatching();
			while (running && gm != null) {
				// assuming that the node-only optimization is used:
				// this loops over matches of the current node-only subgraph
				// and for each match should generate all possible combinations
				// of matches including edges.
				// Thus, we find matching edges for as much edges as possible
				// and then build the Cartesian product.

				// Another thing. In the future, we should think about
				// generating not all combinations
				// but only those leading to a possible counterexample. Not sure
				// yet how this can be determined in advance.

				// Even more general idea: Do not investigate subgraphs but
				// match all nodes individually.
				// Then create all subgraphs with all possible matchings.
				// Repetition of matches would not be
				// necessary - investigate whether this is a
				// performance/complexity gain.
				// Then do the same with all edges. Right now, edges are matched
				// multiple times
				// as they occur in multiple subgraphs. With the new approach,
				// each edge would only be matched once.
				// The validity of the edge for a specific subgraph then depends
				// on the nodes in the subgraph
				// and their matches.

				// added
				try {
					this.wroteItems++;
					this.defaultOutputPipe.queue(new CombinationProducer.Pair<Pair<Graph, GraphRule>, Match>(
							this.currentInput.first, gm.copy()));
				} catch (InterruptedException e) {
					this.running = false;
				}
				Match edgeMatching = SamtraceFactory.eINSTANCE.createMatch();
				for (Edge e : this.currentInput.first.second.getRight().getEdges()) {
					Node srcInHost = gm.getNodeMatching().get(e.getSource());
					Node tarInHost = gm.getNodeMatching().get(e.getTarget());
					if (srcInHost != null && tarInHost != null) {
						// source and target is contained in current subgraph,
						// edge is valid and should be matched
						Edge matchingEdge = null;
						for (Edge currentEdge : srcInHost.getOutgoing()) {
							if (this.currentInput.first.first.getEdges().contains(currentEdge)
									&& !edgeMatching.getEdgeMatching().containsValue(matchingEdge)) {
								// need to check this because an outgoing or
								// incoming edge might belong to a nac in the
								// host
								if (currentEdge.getTarget() == tarInHost
										&& currentEdge.getInstanceOf() == e.getInstanceOf()) {
									// the edges match. However, there might be
									// another possible matching edge
									// if there are multiple edges of the same
									// type between the nodes.
									// Since such a match would be isomorphic to
									// the current match
									// we do not need to consider it. This would
									// be relevant if there were
									// attributes or identifying names attached
									// to the edges.
									matchingEdge = currentEdge;
									break;
								}
							}
						}
						if (matchingEdge == null) {
							for (Edge currentEdge : srcInHost.getIncoming()) {
								if (this.currentInput.first.first.getEdges().contains(currentEdge)
										&& !edgeMatching.getEdgeMatching().containsValue(matchingEdge)) {
									// need to check this because an outgoing or
									// incoming edge might belong to a nac in
									// the host
									if (currentEdge.getTarget() == srcInHost
											&& currentEdge.getInstanceOf() == e.getInstanceOf()
											&& e.getInstanceOf().getDirection() == EdgeDirection.UNDIRECTED) {
										// undirected edges may have src/tar
										// node reversed
										// not all isomorphic combinations - see
										// above
										matchingEdge = currentEdge;
										break;
									}
								}
							}
						}
						if (matchingEdge != null) {
							edgeMatching.getEdgeMatching().put(e, matchingEdge);
						}
					}
				}

				if (edgeMatching.getEdgeMatching().size() > 0) {
					Edge[] edges = new Edge[edgeMatching.getEdgeMatching().size()];
					int i = 0;
					for (Edge e : edgeMatching.getEdgeMatching().keySet()) {
						edges[i] = e;
						i++;
					}
					BitSet bs = new BitSet(edges.length);
					// boolean finished = false;
					while (bs.cardinality() < edges.length && running) {
						incrementBitSet(bs);
						Match completedMatch = gm.copy();
						for (int j = bs.nextSetBit(0); j >= 0; j = bs.nextSetBit(j + 1)) {
							completedMatch.getEdgeMatching().put(edges[j],
									edgeMatching.getEdgeMatching().get(edges[j]));
						}
						this.wroteItems++;
						try {
							this.defaultOutputPipe.queue(new CombinationProducer.Pair<Pair<Graph, GraphRule>, Match>(
									this.currentInput.first, completedMatch));
							running = this.getFilterDispatcher().isContinueComputation();
						} catch (InterruptedException e) {
							this.running = false;
						}
					}
				}
				gm = this.ipm.getNextMatching();
				// normal part
				/*
				 * this.wroteItems++; try { this.defaultOutputPipe.queue(new
				 * CombinationProducer.Pair<Pair<Graph, GraphRule>,
				 * Match>(this.currentInput.first, gm)); running =
				 * this.getFilterDispatcher().isContinueComputation(); if
				 * (running) { gm = this.ipm.getNextMatching(); } } catch
				 * (InterruptedException e) { this.running = false; }
				 */
			}
		}
	}

	private void incrementBitSet(final BitSet bs) {
		final int firstClear = bs.nextClearBit(0);
		bs.set(firstClear);
		for (int i = firstClear - 1; i >= 0; i--) {
			bs.clear(i);
		}
	}

	public void consume() {
		try {
			final Pair<Pair<Graph, GraphRule>, Set<AnnotatedElem>> newPair = this.defaultInputPipe.dequeue();
			this.readItems++;
			if (this.currentInput == null || newPair.first != this.currentInput.first) {
				this.ipm.setHostGraph(newPair.first.first);
				this.ipm.setPattern(newPair.first.second.getRight());
			}
			this.currentInput = newPair;
		} catch (IllegalStateException ise) {
			this.running = false;
		} catch (InterruptedException ie) {
			this.running = false;
		}
	}

	@Override
	protected void initFilter() {
		super.initFilter();
		this.filterName = "MatchSubgraphFilter"; //$NON-NLS-1$
		this.ipm = new IsomorphicPartMatcher();
	}
}