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

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