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