--- /dev/null
+package org.simantics.modeling.scl;\r
+\r
+import gnu.trove.list.array.TIntArrayList;\r
+import gnu.trove.set.hash.THashSet;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Arrays;\r
+import java.util.Collection;\r
+import java.util.List;\r
+\r
+import org.simantics.db.ReadGraph;\r
+import org.simantics.db.Resource;\r
+import org.simantics.db.exception.DatabaseException;\r
+import org.simantics.diagram.stubs.DiagramResource;\r
+\r
+public class RouteGraphMatching {\r
+\r
+ public static boolean TRACE = false;\r
+ \r
+ private static class Link {\r
+ public final int a;\r
+ public final int b;\r
+ \r
+ public Link(int a, int b) {\r
+ this.a = a;\r
+ this.b = b;\r
+ }\r
+ }\r
+ \r
+ private static class MatchingProcess {\r
+ ReadGraph graph;\r
+ DiagramResource DIA;\r
+ Resource[] result;\r
+ ArrayList<Link>[] ls;\r
+ ArrayList<Resource>[] alternatives;\r
+ TIntArrayList stack = new TIntArrayList();\r
+ THashSet<Resource> knownResources = new THashSet<Resource>(); \r
+ \r
+ @SuppressWarnings("unchecked")\r
+ public MatchingProcess(ReadGraph graph, int size) {\r
+ this.graph = graph;\r
+ this.DIA = DiagramResource.getInstance(graph);\r
+ this.result = new Resource[size];\r
+ this.ls = new ArrayList[size];\r
+ this.alternatives = new ArrayList[size];\r
+ for(int i=0;i<size;++i)\r
+ this.ls[i] = new ArrayList<Link>(2);\r
+ }\r
+ \r
+ public void addLink(int a, int b) {\r
+ Link link = new Link(a, b);\r
+ ls[link.a].add(link);\r
+ ls[link.b].add(link);\r
+ }\r
+\r
+ public boolean match(List<Resource> known) throws DatabaseException {\r
+ for(int i=0;i<known.size();++i) {\r
+ result[i] = known.get(i);\r
+ stack.add(i);\r
+ }\r
+ while(!stack.isEmpty()) {\r
+ while(!stack.isEmpty()) {\r
+ int pos = stack.removeAt(stack.size()-1);\r
+ if(!propagate(pos))\r
+ return false;\r
+ }\r
+ if(!removeKnownResourcesFromAlternatives())\r
+ return false;\r
+ }\r
+ for(int i=0;i<result.length;++i)\r
+ if(result[i] == null) {\r
+ System.err.println("Didn't resolve resource " + i + ".");\r
+ printState();\r
+ return false;\r
+ }\r
+ return true;\r
+ }\r
+\r
+ private boolean removeKnownResourcesFromAlternatives() throws DatabaseException {\r
+ for(int i=0;i<result.length;++i) {\r
+ ArrayList<Resource> alt = alternatives[i];\r
+ if(alt != null) {\r
+ alt.removeAll(knownResources);\r
+ if(alt.isEmpty())\r
+ return false;\r
+ if(alt.size() == 1) {\r
+ result[i] = alt.get(0);\r
+ alternatives[i] = null;\r
+ stack.add(i);\r
+ }\r
+ }\r
+ }\r
+ return true;\r
+ }\r
+\r
+ private void printState() {\r
+ for(int i=0;i<result.length;++i) {\r
+ System.out.print(" {" + i + "} ");\r
+ if(result[i] != null)\r
+ System.out.print(" = " + result[i].getResourceId());\r
+ else if(alternatives[i] != null) {\r
+ System.out.print(" in");\r
+ for(Resource r : alternatives[i])\r
+ System.out.print(" " + r.getResourceId());\r
+ }\r
+ else\r
+ System.out.print(" unknown");\r
+ if(!ls[i].isEmpty()) {\r
+ System.out.print(", links to");\r
+ for(Link l : ls[i])\r
+ System.out.print(" " + (l.a==i ? l.b : l.a));\r
+ }\r
+ System.out.println();\r
+ }\r
+ }\r
+\r
+ private boolean propagate(int pos) throws DatabaseException {\r
+ if(TRACE)\r
+ System.out.println("propagate(" + pos + ")");\r
+ Resource r = result[pos];\r
+ knownResources.add(r);\r
+ ArrayList<Resource> neighbors = \r
+ new ArrayList<Resource>(graph.getObjects(r, DIA.AreConnected));\r
+ neighbors.removeAll(knownResources);\r
+ \r
+ for(Link link : ls[pos]) {\r
+ int other = link.a == pos ? link.b : link.a;\r
+ ls[other].remove(link);\r
+ if(!setAlternatives(other, neighbors))\r
+ return false;\r
+ }\r
+ ls[pos].clear();\r
+ \r
+ return true;\r
+ }\r
+\r
+ private boolean setKnown(int i, Resource value) throws DatabaseException {\r
+ if(TRACE)\r
+ System.out.println("setKnown(" + i + ", " + value + ")");\r
+ if(result[i] != null) \r
+ return result[i].equals(value);\r
+ if(alternatives[i] != null) {\r
+ if(!alternatives[i].contains(value))\r
+ return false;\r
+ alternatives[i] = null;\r
+ }\r
+ result[i] = value;\r
+ stack.add(i);\r
+ return true;\r
+ }\r
+ \r
+ private boolean setAlternatives(int i, Collection<Resource> values) throws DatabaseException {\r
+ if(TRACE)\r
+ System.out.println("setAlternatives(" + i + ", " + values + ")");\r
+ if(result[i] != null)\r
+ return values.contains(result[i]);\r
+ if(values.isEmpty())\r
+ return false;\r
+ if(values.size() == 1)\r
+ return setKnown(i, values.iterator().next());\r
+ ArrayList<Resource> oldAlternatives = alternatives[i];\r
+ if(oldAlternatives == null) {\r
+ alternatives[i] = new ArrayList<Resource>(values);\r
+ return true;\r
+ }\r
+ oldAlternatives.retainAll(values);\r
+ if(oldAlternatives.isEmpty())\r
+ return false;\r
+ if(oldAlternatives.size() == 1)\r
+ return setKnown(i, oldAlternatives.get(0));\r
+ return true;\r
+ }\r
+ }\r
+ \r
+ public static List<Resource> matchRouteGraph(ReadGraph graph, \r
+ List<Resource> connectors, int routeLineCount, List<Integer> links) throws DatabaseException {\r
+ MatchingProcess process = new MatchingProcess(graph, connectors.size() + routeLineCount);\r
+ for(int i=0;i<links.size();i+=2)\r
+ process.addLink(links.get(i), links.get(i+1));\r
+ if(!process.match(connectors))\r
+ return null;\r
+ return Arrays.asList(process.result);\r
+ }\r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff