001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph;
018:
019: import java.util.ArrayList;
020: import java.util.HashMap;
021:
022: import org.geotools.graph.build.GraphBuilder;
023: import org.geotools.graph.build.GraphGenerator;
024: import org.geotools.graph.build.opt.OptDirectedGraphBuilder;
025: import org.geotools.graph.build.opt.OptGraphBuilder;
026: import org.geotools.graph.structure.Edge;
027: import org.geotools.graph.structure.GraphVisitor;
028: import org.geotools.graph.structure.Graphable;
029: import org.geotools.graph.structure.Node;
030: import org.geotools.graph.structure.opt.OptDirectedNode;
031: import org.geotools.graph.structure.opt.OptNode;
032: import org.geotools.graph.util.FIFOQueue;
033:
034: public class GraphTestUtil {
035:
036: /**
037: * Builds a graph with no bifurcations made up of a specified number of nodes.
038: * Nodes are numbered from 0 to (# of nodes - 1).<BR>
039: * <BR>
040: * O----O----O--...--O----O----O
041: *
042: * @param builder Builder to use to construct graph.
043: * @param nnodes Number of nodes in graph.
044: *
045: * @return 2 element object array containing references to the end points of
046: * the graph. (The nodes of degree 1 at the end of the graph.
047: */
048: public static Node[] buildNoBifurcations(GraphBuilder builder,
049: int nnodes) {
050: Node n1 = builder.buildNode();
051: builder.addNode(n1);
052: n1.setID(0);
053:
054: Node n2 = null;
055: Edge e = null;
056: Node first = n1;
057:
058: for (int i = 1; i < nnodes; i++) {
059: n2 = builder.buildNode();
060: builder.addNode(n2);
061: n2.setID(i);
062:
063: e = builder.buildEdge(n1, n2);
064: builder.addEdge(e);
065: e.setID(i - 1);
066:
067: n1 = n2;
068: }
069:
070: return (new Node[] { first, n1 });
071: }
072:
073: public static Node[] buildNoBifurcations(GraphGenerator gen,
074: int nnodes) {
075: String[] nodes = new String[nnodes];
076: Node[] ends = new Node[2];
077:
078: for (int i = 0; i < nnodes; i++) {
079: nodes[i] = new String(String.valueOf(i));
080: if (i > 0) {
081: Edge e = (Edge) gen.add(new String[] { nodes[i - 1],
082: nodes[i] });
083: if (i == 1)
084: ends[0] = e.getNodeA();
085: if (i == nnodes - 1)
086: ends[1] = e.getNodeB();
087: }
088: }
089:
090: return (ends);
091: }
092:
093: public static Object[] buildNoBifurcations(OptGraphBuilder builder,
094: int nnodes) {
095: //use maps for id since optimized graphable doesn't use id's
096: HashMap node2id = new HashMap();
097: HashMap edge2id = new HashMap();
098:
099: OptNode n1 = (OptNode) builder.buildNode();
100: n1.setDegree(1);
101:
102: builder.addNode(n1);
103: node2id.put(n1, new Integer(0));
104:
105: OptNode n2 = null;
106: Edge e = null;
107: OptNode first = n1;
108:
109: for (int i = 1; i < nnodes; i++) {
110: n2 = (OptNode) builder.buildNode();
111: if (i < nnodes - 1)
112: n2.setDegree(2);
113: else
114: n2.setDegree(1);
115:
116: builder.addNode(n2);
117: node2id.put(n2, new Integer(i));
118:
119: e = builder.buildEdge(n1, n2);
120: builder.addEdge(e);
121: edge2id.put(e, new Integer(i - 1));
122:
123: n1 = n2;
124: }
125:
126: return (new Object[] { first, n1, node2id, edge2id });
127: }
128:
129: public static Object[] buildNoBifurcations(
130: OptDirectedGraphBuilder builder, int nnodes) {
131: //use maps for id since optimized graphable doesn't use id's
132: HashMap node2id = new HashMap();
133: HashMap edge2id = new HashMap();
134:
135: OptDirectedNode n1 = (OptDirectedNode) builder.buildNode();
136: n1.setInDegree(0);
137: n1.setOutDegree(1);
138:
139: builder.addNode(n1);
140: node2id.put(n1, new Integer(0));
141:
142: OptDirectedNode n2 = null;
143: Edge e = null;
144: OptDirectedNode first = n1;
145:
146: for (int i = 1; i < nnodes; i++) {
147: n2 = (OptDirectedNode) builder.buildNode();
148: if (i < nnodes - 1) {
149: n2.setInDegree(1);
150: n2.setOutDegree(1);
151: } else {
152: n2.setInDegree(1);
153: n2.setOutDegree(0);
154: }
155:
156: builder.addNode(n2);
157: node2id.put(n2, new Integer(i));
158:
159: e = builder.buildEdge(n1, n2);
160: builder.addEdge(e);
161: edge2id.put(e, new Integer(i - 1));
162:
163: n1 = n2;
164: }
165:
166: return (new Object[] { first, n1, node2id, edge2id });
167: }
168:
169: public static Node[] buildSingleBifurcation(
170: final GraphBuilder builder, int nnodes,
171: final int bifurcation) {
172: Node[] ends = buildNoBifurcations(builder, nnodes - 1);
173: final Node n = builder.buildNode();
174: final ArrayList bif = new ArrayList();
175:
176: builder.getGraph().visitNodes(new GraphVisitor() {
177: public int visit(Graphable component) {
178: if (component.getID() == bifurcation) {
179: bif.add(component);
180: }
181:
182: return (0);
183: }
184: });
185:
186: Edge e = builder.buildEdge(n, (Node) bif.get(0));
187: builder.addNode(n);
188: builder.addEdge(e);
189:
190: Node[] bifends = new Node[] { ends[0], ends[1],
191: (Node) bif.get(0) };
192: return (bifends);
193: }
194:
195: /**
196: * Creates a balanced binary tree consisting of a specefied number of levels.
197: * Each node created contains a string representing the nodes location in
198: * the tree.<BR>
199: * <BR>
200: * locstring(root) = "0";
201: * locstring(node) = locstring(parent) + ".0" (if left child);
202: * locstring(node) = locstring(parent) + ".1" (if right child);
203: *
204: * @param builder Builder to construct graph with
205: * @param levels Number of levels in the tree.
206: *
207: * @return A 2 element object array.
208: * 0 = root node
209: * 1 = map of locstring to node
210: */
211: public static Object[] buildPerfectBinaryTree(GraphBuilder builder,
212: int levels) {
213: HashMap id2node = new HashMap();
214:
215: //a balanced binary tree
216: Node root = builder.buildNode();
217: root.setObject(new String("0"));
218: id2node.put(root.getObject(), root);
219:
220: builder.addNode(root);
221:
222: FIFOQueue queue = new FIFOQueue((int) Math.pow(2, levels + 1));
223: queue.enq(root);
224:
225: //build a complete binary tree
226: // number of nodes = 2^(n+1) - 1
227: int level = 0;
228: while (level < levels) {
229: int nnodes = (int) Math.pow(2, level);
230: for (int i = 0; i < nnodes; i++) {
231: Node n = (Node) queue.deq();
232:
233: Node ln = builder.buildNode();
234: ln.setObject(n.getObject() + ".0");
235: id2node.put(ln.getObject(), ln);
236:
237: Node rn = builder.buildNode();
238: rn.setObject(n.getObject() + ".1");
239: id2node.put(rn.getObject(), rn);
240:
241: Edge le = builder.buildEdge(n, ln);
242: Edge re = builder.buildEdge(n, rn);
243:
244: builder.addNode(ln);
245: builder.addNode(rn);
246: builder.addEdge(le);
247: builder.addEdge(re);
248:
249: queue.enq(ln);
250: queue.enq(rn);
251: }
252: level++;
253: }
254:
255: return (new Object[] { root, id2node });
256: }
257:
258: public static Object[] buildPerfectBinaryTree(
259: OptGraphBuilder builder, int levels) {
260: OptNode root = (OptNode) builder.buildNode();
261: root.setDegree(2);
262: builder.addNode(root);
263:
264: FIFOQueue queue = new FIFOQueue((int) Math.pow(2, levels + 1));
265: queue.enq(root);
266:
267: //build a complete binary tree
268: // number of nodes = 2^(n+1) - 1
269: int level = 0;
270: while (level < levels) {
271: int nnodes = (int) Math.pow(2, level);
272: for (int i = 0; i < nnodes; i++) {
273: Node n = (Node) queue.deq();
274:
275: OptNode ln = (OptNode) builder.buildNode();
276: if (level < levels - 1)
277: ln.setDegree(3);
278: else
279: ln.setDegree(1);
280:
281: OptNode rn = (OptNode) builder.buildNode();
282: if (level < levels - 1)
283: rn.setDegree(3);
284: else
285: rn.setDegree(1);
286:
287: Edge le = builder.buildEdge(n, ln);
288: Edge re = builder.buildEdge(n, rn);
289:
290: builder.addNode(ln);
291: builder.addNode(rn);
292: builder.addEdge(le);
293: builder.addEdge(re);
294:
295: queue.enq(ln);
296: queue.enq(rn);
297: }
298: level++;
299: }
300:
301: return (new Object[] { root });
302:
303: }
304:
305: public static Object[] buildPerfectBinaryTree(
306: OptDirectedGraphBuilder builder, int levels) {
307: OptDirectedNode root = (OptDirectedNode) builder.buildNode();
308: root.setInDegree(0);
309: root.setOutDegree(2);
310: builder.addNode(root);
311:
312: FIFOQueue queue = new FIFOQueue((int) Math.pow(2, levels + 1));
313: queue.enq(root);
314:
315: //build a complete binary tree
316: // number of nodes = 2^(n+1) - 1
317: int level = 0;
318: while (level < levels) {
319: int nnodes = (int) Math.pow(2, level);
320: for (int i = 0; i < nnodes; i++) {
321: Node n = (Node) queue.deq();
322:
323: OptDirectedNode ln = (OptDirectedNode) builder
324: .buildNode();
325: if (level < levels - 1) {
326: ln.setInDegree(1);
327: ln.setOutDegree(2);
328: } else {
329: ln.setInDegree(1);
330: ln.setOutDegree(0);
331: }
332:
333: OptDirectedNode rn = (OptDirectedNode) builder
334: .buildNode();
335: if (level < levels - 1) {
336: rn.setInDegree(1);
337: rn.setOutDegree(2);
338: } else {
339: rn.setInDegree(1);
340: rn.setOutDegree(0);
341: }
342:
343: Edge le = builder.buildEdge(n, ln);
344: Edge re = builder.buildEdge(n, rn);
345:
346: builder.addNode(ln);
347: builder.addNode(rn);
348: builder.addEdge(le);
349: builder.addEdge(re);
350:
351: queue.enq(ln);
352: queue.enq(rn);
353: }
354: level++;
355: }
356:
357: return (new Object[] { root });
358:
359: }
360:
361: public static Node[] buildCircular(GraphBuilder builder, int nnodes) {
362: //build a graph with no bifurcations then join the first and last verticies
363: Node[] ends = buildNoBifurcations(builder, nnodes);
364: Edge e = builder.buildEdge(ends[1], ends[0]);
365: builder.addEdge(e);
366:
367: return (ends);
368: }
369:
370: public static Node[] buildCircular(GraphGenerator gen, int nnodes) {
371: Node[] ends = buildNoBifurcations(gen, nnodes);
372: gen.add(new Object[] { "0", String.valueOf(nnodes - 1) });
373:
374: return (ends);
375: }
376: }
|