bundles/org.simantics.modeling/src/org/simantics/modeling/scl/RouteGraphMatching.java

   1 package org.simantics.modeling.scl;\r
   2 \r
   3 import gnu.trove.list.array.TIntArrayList;\r
   4 import gnu.trove.set.hash.THashSet;\r
   5 \r
   6 import java.util.ArrayList;\r
   7 import java.util.Arrays;\r
   8 import java.util.Collection;\r
   9 import java.util.List;\r
  10 \r
  11 import org.simantics.db.ReadGraph;\r
  12 import org.simantics.db.Resource;\r
  13 import org.simantics.db.exception.DatabaseException;\r
  14 import org.simantics.diagram.stubs.DiagramResource;\r
  15 \r
  16 public class RouteGraphMatching {\r
  17 \r
  18     public static boolean TRACE = false;\r
  19     \r
  20     private static class Link {\r
  21         public final int a;\r
  22         public final int b;\r
  23         \r
  24         public Link(int a, int b) {\r
  25             this.a = a;\r
  26             this.b = b;\r
  27         }\r
  28     }\r
  29     \r
  30     private static class MatchingProcess {\r
  31         ReadGraph graph;\r
  32         DiagramResource DIA;\r
  33         Resource[] result;\r
  34         ArrayList<Link>[] ls;\r
  35         ArrayList<Resource>[] alternatives;\r
  36         TIntArrayList stack = new TIntArrayList();\r
  37         THashSet<Resource> knownResources = new THashSet<Resource>(); \r
  38         \r
  39         @SuppressWarnings("unchecked")\r
  40         public MatchingProcess(ReadGraph graph, int size) {\r
  41             this.graph = graph;\r
  42             this.DIA = DiagramResource.getInstance(graph);\r
  43             this.result = new Resource[size];\r
  44             this.ls = new ArrayList[size];\r
  45             this.alternatives = new ArrayList[size];\r
  46             for(int i=0;i<size;++i)\r
  47                 this.ls[i] = new ArrayList<Link>(2);\r
  48         }\r
  49         \r
  50         public void addLink(int a, int b) {\r
  51             Link link = new Link(a, b);\r
  52             ls[link.a].add(link);\r
  53             ls[link.b].add(link);\r
  54         }\r
  55 \r
  56         public boolean match(List<Resource> known) throws DatabaseException {\r
  57             for(int i=0;i<known.size();++i) {\r
  58                 result[i] = known.get(i);\r
  59                 stack.add(i);\r
  60             }\r
  61             while(!stack.isEmpty()) {\r
  62                 while(!stack.isEmpty()) {\r
  63                     int pos = stack.removeAt(stack.size()-1);\r
  64                     if(!propagate(pos))\r
  65                         return false;\r
  66                 }\r
  67                 if(!removeKnownResourcesFromAlternatives())\r
  68                     return false;\r
  69             }\r
  70             for(int i=0;i<result.length;++i)\r
  71                 if(result[i] == null) {\r
  72                     System.err.println("Didn't resolve resource " + i + ".");\r
  73                     printState();\r
  74                     return false;\r
  75                 }\r
  76             return true;\r
  77         }\r
  78 \r
  79         private boolean removeKnownResourcesFromAlternatives() throws DatabaseException {\r
  80             for(int i=0;i<result.length;++i) {\r
  81                 ArrayList<Resource> alt = alternatives[i];\r
  82                 if(alt != null) {\r
  83                     alt.removeAll(knownResources);\r
  84                     if(alt.isEmpty())\r
  85                         return false;\r
  86                     if(alt.size() == 1) {\r
  87                         result[i] = alt.get(0);\r
  88                         alternatives[i] = null;\r
  89                         stack.add(i);\r
  90                     }\r
  91                 }\r
  92             }\r
  93             return true;\r
  94         }\r
  95 \r
  96         private void printState() {\r
  97             for(int i=0;i<result.length;++i) {\r
  98                 System.out.print("    {" + i + "} ");\r
  99                 if(result[i] != null)\r
 100                     System.out.print(" = " + result[i].getResourceId());\r
 101                 else if(alternatives[i] != null) {\r
 102                     System.out.print(" in");\r
 103                     for(Resource r : alternatives[i])\r
 104                         System.out.print(" " + r.getResourceId());\r
 105                 }\r
 106                 else\r
 107                     System.out.print(" unknown");\r
 108                 if(!ls[i].isEmpty()) {\r
 109                     System.out.print(", links to");\r
 110                     for(Link l : ls[i])\r
 111                         System.out.print(" " + (l.a==i ? l.b : l.a));\r
 112                 }\r
 113                 System.out.println();\r
 114             }\r
 115         }\r
 116 \r
 117         private boolean propagate(int pos) throws DatabaseException {\r
 118             if(TRACE)\r
 119                 System.out.println("propagate(" + pos + ")");\r
 120             Resource r = result[pos];\r
 121             knownResources.add(r);\r
 122             ArrayList<Resource> neighbors = \r
 123                     new ArrayList<Resource>(graph.getObjects(r, DIA.AreConnected));\r
 124             neighbors.removeAll(knownResources);\r
 125             \r
 126             for(Link link : ls[pos]) {\r
 127                 int other = link.a == pos ? link.b : link.a;\r
 128                 ls[other].remove(link);\r
 129                 if(!setAlternatives(other, neighbors))\r
 130                     return false;\r
 131             }\r
 132             ls[pos].clear();\r
 133             \r
 134             return true;\r
 135         }\r
 136 \r
 137         private boolean setKnown(int i, Resource value) throws DatabaseException {\r
 138             if(TRACE)\r
 139                 System.out.println("setKnown(" + i + ", " + value + ")");\r
 140             if(result[i] != null) \r
 141                 return result[i].equals(value);\r
 142             if(alternatives[i] != null) {\r
 143                 if(!alternatives[i].contains(value))\r
 144                     return false;\r
 145                 alternatives[i] = null;\r
 146             }\r
 147             result[i] = value;\r
 148             stack.add(i);\r
 149             return true;\r
 150         }\r
 151         \r
 152         private boolean setAlternatives(int i, Collection<Resource> values) throws DatabaseException {\r
 153             if(TRACE)\r
 154                 System.out.println("setAlternatives(" + i + ", " + values + ")");\r
 155             if(result[i] != null)\r
 156                 return values.contains(result[i]);\r
 157             if(values.isEmpty())\r
 158                 return false;\r
 159             if(values.size() == 1)\r
 160                 return setKnown(i, values.iterator().next());\r
 161             ArrayList<Resource> oldAlternatives = alternatives[i];\r
 162             if(oldAlternatives == null) {\r
 163                 alternatives[i] = new ArrayList<Resource>(values);\r
 164                 return true;\r
 165             }\r
 166             oldAlternatives.retainAll(values);\r
 167             if(oldAlternatives.isEmpty())\r
 168                 return false;\r
 169             if(oldAlternatives.size() == 1)\r
 170                 return setKnown(i, oldAlternatives.get(0));\r
 171             return true;\r
 172         }\r
 173     }\r
 174     \r
 175     public static List<Resource> matchRouteGraph(ReadGraph graph, \r
 176             List<Resource> connectors, int routeLineCount, List<Integer> links) throws DatabaseException {\r
 177         MatchingProcess process = new MatchingProcess(graph, connectors.size() +  routeLineCount);\r
 178         for(int i=0;i<links.size();i+=2)\r
 179             process.addLink(links.get(i), links.get(i+1));\r
 180         if(!process.match(connectors))\r
 181             return null;\r
 182         return Arrays.asList(process.result);\r
 183     }\r
 184     \r
 185 }\r