1
2
3
4 package net.sf.bddbddb;
5
6 import java.util.Collection;
7 import java.util.Collections;
8 import java.util.HashMap;
9 import java.util.Iterator;
10 import java.util.LinkedList;
11 import java.util.List;
12 import java.util.Map;
13 import java.io.PrintStream;
14 import java.math.BigInteger;
15 import jwutil.collections.Pair;
16 import jwutil.graphs.Graph;
17 import jwutil.graphs.Navigator;
18 import jwutil.util.Assert;
19
20 /***
21 * Allows relations to be treated as edges in a graph, so we can use
22 * graph algorithms on them.
23 *
24 * @author jwhaley
25 * @version $Id: RelationGraph.java 350 2004-10-20 01:15:41Z joewhaley $
26 */
27 public class RelationGraph implements Graph {
28
29 /***
30 * Trace flag.
31 */
32 protected boolean TRACE = false;
33
34 /***
35 * Trace output stream.
36 */
37 protected PrintStream out = System.out;
38
39 /***
40 * The rule term that represents the set of roots.
41 */
42 RuleTerm root;
43
44 /***
45 * The variable used as the root.
46 */
47 Variable rootVariable;
48
49 /***
50 * List of rule terms that represent edges in the graph.
51 */
52 List
53
54 /***
55 * Construct a new relation graph with the given root term, root variable, and list
56 * of terms that represent edges in the graph.
57 *
58 * @param root root term
59 * @param rootVar root variable
60 * @param edges list of terms representing edges in the graph
61 */
62 RelationGraph(RuleTerm root, Variable rootVar, List
63 this.root = root;
64 this.rootVariable = rootVar;
65 this.edges = edges;
66 }
67
68 /***
69 * Construct a new relation graph that uses a given relation as the set of
70 * roots and another as the set of edges. This is just an easier way of
71 * constructing a simple graph so that you don't have to build up rule terms.
72 *
73 * @param roots set of roots
74 * @param edges set of edges
75 */
76 RelationGraph(Relation roots, Relation edges) {
77 Assert._assert(roots.attributes.size() == 1);
78 Assert._assert(edges.attributes.size() == 2);
79 Attribute a = (Attribute) roots.attributes.get(0);
80 Domain fd = a.attributeDomain;
81 this.rootVariable = new Variable(fd.toString(), fd);
82 List varList = Collections.singletonList(rootVariable);
83 this.root = new RuleTerm(roots, varList);
84 Assert._assert(edges.getAttribute(0).attributeDomain == fd);
85 Assert._assert(edges.getAttribute(1).attributeDomain == fd);
86 List varList2 = new Pair(rootVariable, rootVariable);
87 RuleTerm edge = new RuleTerm(edges, varList2);
88 this.edges = Collections.singletonList(edge);
89 }
90
91 /***
92 * A node in the relation graph.
93 */
94 static class GraphNode {
95 Variable v;
96 BigInteger number;
97
98 /***
99 * Make a new graph node with the given variable and value.
100 *
101 * @param var variable
102 * @param num value
103 */
104 GraphNode(Variable var, BigInteger num) {
105 this.v = var;
106 this.number = num;
107 }
108
109
110
111
112 public int hashCode() {
113 return v.hashCode() ^ number.hashCode();
114 }
115
116 /***
117 * @see java.lang.Object#equals(java.lang.Object)
118 */
119 public boolean equals(GraphNode that) {
120 return this.v == that.v && this.number.equals(that.number);
121 }
122
123
124
125
126 public boolean equals(Object o) {
127 return equals((GraphNode) o);
128 }
129
130
131
132
133 public String toString() {
134 return v.toString() + ":" + number;
135 }
136 }
137
138 /***
139 * Make a new graph node with the given variable and value.
140 *
141 * @param v variable
142 * @param num value
143 * @return new graph node
144 */
145 static GraphNode makeGraphNode(Variable v, BigInteger num) {
146 return new GraphNode(v, num);
147 }
148
149 /***
150 * Navigator object for this graph.
151 */
152 Nav navigator = new Nav();
153
154 /***
155 * Navigator for a relation graph.
156 */
157 class Nav implements Navigator {
158
159 Map prevCache;
160 Map nextCache;
161 int cacheHit, cacheMiss;
162
163 Nav() {
164 prevCache = new HashMap();
165 nextCache = new HashMap();
166 }
167
168 /***
169 * Get the edges from a node where the from and to variables match the indices given.
170 *
171 * @param node graph node
172 * @param fromIndex index of from variable
173 * @param toIndex index of to variable
174 * @return collection of edges
175 */
176 Collection getEdges(Object node, int fromIndex, int toIndex) {
177 GraphNode gn = (GraphNode) node;
178 if (TRACE) out.println("Getting edges of " + gn + " indices (" + fromIndex + "," + toIndex + ")");
179 Collection c = new LinkedList();
180 for (Iterator a = edges.iterator(); a.hasNext();) {
181 RuleTerm rt = (RuleTerm) a.next();
182 if (rt.variables.get(fromIndex) == gn.v) {
183 if (TRACE) out.println("Rule term " + rt + " matches");
184 Variable v2 = (Variable) rt.variables.get(toIndex);
185 TupleIterator i = rt.relation.iterator(fromIndex, gn.number);
186 while (i.hasNext()) {
187 BigInteger[] j = i.nextTuple();
188 c.add(new GraphNode(v2, j[toIndex]));
189 }
190 }
191 }
192 if (TRACE) out.println("Edges: " + c);
193 return c;
194 }
195
196 void printCacheRatio() {
197 System.out.print("Navigating relation graph: ");
198 System.out.print(cacheHit+"/"+(cacheHit+cacheMiss)+": ");
199 System.out.print(((double)cacheHit/(cacheHit+cacheMiss)));
200 System.out.print(" \r");
201 }
202
203
204
205
206
207
208 public Collection next(Object node) {
209 Collection result = (Collection) nextCache.get(node);
210 if (result == null) {
211 cacheMiss++;
212 nextCache.put(node, result = getEdges(node, 0, 1));
213 } else {
214 cacheHit++;
215 }
216 if ((cacheMiss + cacheHit) % 256 == 0) printCacheRatio();
217 return result;
218 }
219
220
221
222
223
224
225 public Collection prev(Object node) {
226 Collection result = (Collection) prevCache.get(node);
227 if (result == null) {
228 cacheMiss++;
229 prevCache.put(node, result = getEdges(node, 1, 0));
230 } else {
231 cacheHit++;
232 }
233 if ((cacheMiss + cacheHit) % 256 == 0) printCacheRatio();
234 return result;
235 }
236 }
237
238
239
240
241
242
243 public Collection getRoots() {
244 Relation rootRelation = root.relation;
245 int k = root.variables.indexOf(rootVariable);
246 Collection roots = new LinkedList();
247 TupleIterator i = rootRelation.iterator(k);
248 while (i.hasNext()) {
249 BigInteger j = i.nextTuple()[0];
250 roots.add(new GraphNode(rootVariable, j));
251 }
252 if (TRACE) out.println("Roots of graph: " + roots);
253 return roots;
254 }
255
256
257
258
259
260
261 public Navigator getNavigator() {
262 return navigator;
263 }
264 }