1 package org.simantics.modeling.scl;
3 import gnu.trove.list.array.TIntArrayList;
4 import gnu.trove.set.hash.THashSet;
6 import java.util.ArrayList;
7 import java.util.Arrays;
8 import java.util.Collection;
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;
18 public class RouteGraphMatching {
20 private static final Logger LOGGER = LoggerFactory.getLogger(RouteGraphMatching.class);
21 public static boolean TRACE = false;
23 private static class Link {
27 public Link(int a, int b) {
33 private static class MatchingProcess {
38 ArrayList<Resource>[] alternatives;
39 TIntArrayList stack = new TIntArrayList();
40 THashSet<Resource> knownResources = new THashSet<Resource>();
42 @SuppressWarnings("unchecked")
43 public MatchingProcess(ReadGraph graph, int size) {
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);
53 public void addLink(int a, int b) {
54 Link link = new Link(a, b);
59 public boolean match(List<Resource> known) throws DatabaseException {
60 for(int i=0;i<known.size();++i) {
61 result[i] = known.get(i);
64 while(!stack.isEmpty()) {
65 while(!stack.isEmpty()) {
66 int pos = stack.removeAt(stack.size()-1);
70 if(!removeKnownResourcesFromAlternatives())
73 for(int i=0;i<result.length;++i)
74 if(result[i] == null) {
75 LOGGER.warn("Didn't resolve resource " + i + ".");
82 private boolean removeKnownResourcesFromAlternatives() throws DatabaseException {
83 for(int i=0;i<result.length;++i) {
84 ArrayList<Resource> alt = alternatives[i];
86 alt.removeAll(knownResources);
90 result[i] = alt.get(0);
91 alternatives[i] = null;
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) {
107 for(Resource r : alternatives[i])
108 sb.append(" " + r.getResourceId());
111 sb.append(" unknown");
112 if(!ls[i].isEmpty()) {
113 sb.append(", links to");
115 sb.append(" " + (l.a==i ? l.b : l.a));
119 LOGGER.info(sb.toString());
122 private boolean propagate(int pos) throws DatabaseException {
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);
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))
142 private boolean setKnown(int i, Resource value) throws DatabaseException {
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))
150 alternatives[i] = null;
157 private boolean setAlternatives(int i, Collection<Resource> values) throws DatabaseException {
159 System.out.println("setAlternatives(" + i + ", " + values + ")");
160 if(result[i] != null)
161 return values.contains(result[i]);
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);
171 oldAlternatives.retainAll(values);
172 if(oldAlternatives.isEmpty())
174 if(oldAlternatives.size() == 1)
175 return setKnown(i, oldAlternatives.get(0));
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))
187 return Arrays.asList(process.result);