1 package org.simantics.modeling.scl;
\r
3 import gnu.trove.list.array.TIntArrayList;
\r
4 import gnu.trove.set.hash.THashSet;
\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
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
16 public class RouteGraphMatching {
\r
18 public static boolean TRACE = false;
\r
20 private static class Link {
\r
24 public Link(int a, int b) {
\r
30 private static class MatchingProcess {
\r
32 DiagramResource DIA;
\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
39 @SuppressWarnings("unchecked")
\r
40 public MatchingProcess(ReadGraph graph, int size) {
\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
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
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
61 while(!stack.isEmpty()) {
\r
62 while(!stack.isEmpty()) {
\r
63 int pos = stack.removeAt(stack.size()-1);
\r
67 if(!removeKnownResourcesFromAlternatives())
\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
79 private boolean removeKnownResourcesFromAlternatives() throws DatabaseException {
\r
80 for(int i=0;i<result.length;++i) {
\r
81 ArrayList<Resource> alt = alternatives[i];
\r
83 alt.removeAll(knownResources);
\r
86 if(alt.size() == 1) {
\r
87 result[i] = alt.get(0);
\r
88 alternatives[i] = null;
\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
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
113 System.out.println();
\r
117 private boolean propagate(int pos) throws DatabaseException {
\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
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
137 private boolean setKnown(int i, Resource value) throws DatabaseException {
\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
145 alternatives[i] = null;
\r
152 private boolean setAlternatives(int i, Collection<Resource> values) throws DatabaseException {
\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
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
166 oldAlternatives.retainAll(values);
\r
167 if(oldAlternatives.isEmpty())
\r
169 if(oldAlternatives.size() == 1)
\r
170 return setKnown(i, oldAlternatives.get(0));
\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
182 return Arrays.asList(process.result);
\r