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.util;
018:
019: import java.util.ArrayList;
020: import java.util.Iterator;
021: import java.util.List;
022:
023: import junit.framework.TestCase;
024:
025: import org.geotools.graph.GraphTestUtil;
026: import org.geotools.graph.build.GraphGenerator;
027: import org.geotools.graph.build.basic.BasicGraphGenerator;
028: import org.geotools.graph.structure.Edge;
029: import org.geotools.graph.structure.GraphVisitor;
030: import org.geotools.graph.structure.Graphable;
031: import org.geotools.graph.structure.Node;
032: import org.geotools.graph.util.graph.GraphFuser;
033:
034: public class GraphFuserTest extends TestCase {
035:
036: private GraphGenerator m_gen;
037:
038: public GraphFuserTest(String name) {
039: super (name);
040: }
041:
042: protected void setUp() throws Exception {
043: super .setUp();
044:
045: m_gen = createGenerator();
046: }
047:
048: /**
049: * Create a no bifurcation graph and fuse it. <BR>
050: * <BR>
051: * Expected: 1. Resulting graph should only have 2 nodes and 1 edge. <BR>
052: * <BR>
053: * O---O---O-...-O---O---O ==FUSER=> O-------...-------O
054: *
055: */
056: public void test_0() {
057: final int nnodes = 100;
058: Node[] ends = GraphTestUtil.buildNoBifurcations(generator(),
059: nnodes);
060: GraphGenerator fused = createGenerator();
061:
062: GraphFuser fuser = new GraphFuser(generator().getGraph(),
063: generator().getGraphBuilder(), createEdgeMerger());
064: assertTrue(fuser.fuse());
065:
066: assertTrue(generator().getGraph().getNodes().size() == 2);
067: assertTrue(generator().getGraph().getEdges().size() == 1);
068:
069: GraphVisitor visitor = new GraphVisitor() {
070: public int visit(Graphable component) {
071: String id = (String) component.getObject();
072: assertTrue(id.equals("0")
073: || id.equals(String.valueOf(nnodes - 1)));
074: return (0);
075: }
076: };
077: generator().getGraph().visitNodes(visitor);
078:
079: visitor = new GraphVisitor() {
080: public int visit(Graphable component) {
081: Edge e = (Edge) component;
082: String id0 = (String) e.getNodeA().getObject();
083: String id1 = (String) e.getNodeB().getObject();
084:
085: assertTrue((id0.equals("0") && id1.equals(String
086: .valueOf(nnodes - 1)))
087: || (id0.equals(String.valueOf(nnodes - 1)) && id1
088: .equals("0")));
089:
090: return (0);
091: }
092: };
093: generator().getGraph().visitEdges(visitor);
094: }
095:
096: /**
097: * Build a no bifurcation graph and then add a cycle containing two adjacent
098: * nodes and fuse. <BR>
099: * <BR>
100: * Expected: 1. The graph should have 4 nodes and 4 edges. <BR>
101: * <BR>
102: * ___ ___
103: * / \ / \
104: * O---O-...-O O-...-O---O ==FUSER=> O--...--O O--...--O
105: * \___/ \___/
106: *
107: */
108: public void test_1() {
109: final int nnodes = 100;
110: final int cyc = 50;
111:
112: Node[] ends = GraphTestUtil.buildNoBifurcations(generator(),
113: nnodes);
114: generator().add(
115: new Object[] { String.valueOf(cyc),
116: String.valueOf(cyc + 1) });
117: GraphGenerator fused = createGenerator();
118:
119: GraphFuser fuser = new GraphFuser(generator().getGraph(),
120: generator().getGraphBuilder(), createEdgeMerger());
121: assertTrue(fuser.fuse());
122:
123: assertTrue(generator().getGraph().getNodes().size() == 4);
124: assertTrue(generator().getGraph().getEdges().size() == 4);
125:
126: GraphVisitor visitor = new GraphVisitor() {
127: public int visit(Graphable component) {
128: String id = (String) component.getObject();
129: assertTrue((id.equals("0") || id.equals(String
130: .valueOf(nnodes - 1)))
131: || (id.equals(String.valueOf(cyc)) || id
132: .equals(String.valueOf(cyc + 1))));
133: return (0);
134: }
135: };
136: generator().getGraph().visitNodes(visitor);
137:
138: visitor = new GraphVisitor() {
139: public int visit(Graphable component) {
140: Edge e = (Edge) component;
141: String id0 = (String) e.getNodeA().getObject();
142: String id1 = (String) e.getNodeB().getObject();
143:
144: assertTrue((id0.equals("0") && id1.equals(String
145: .valueOf(cyc)))
146: || (id0.equals(String.valueOf(cyc)) && id1
147: .equals("0"))
148: || (id0.equals(String.valueOf(cyc)) && id1
149: .equals(String.valueOf(cyc + 1)))
150: || (id0.equals(String.valueOf(cyc + 1)) && id1
151: .equals(String.valueOf(cyc)))
152: || (id0.equals(String.valueOf(cyc + 1)) && id1
153: .equals(String.valueOf(nnodes - 1)))
154: || (id0.equals(String.valueOf(nnodes - 1)) && id1
155: .equals(String.valueOf(cyc + 1))));
156:
157: return (0);
158: }
159: };
160: generator().getGraph().visitEdges(visitor);
161: }
162:
163: /**
164: * Create a graph with no bifurcations and a cycle between containing three
165: * nodes and fuse it. <BR>
166: * <BR>
167: * Expected: 1. The graph should have 4 nodes and 4 edges. <BR>
168: * <BR>
169: * _____ _____
170: * / \ / \
171: * O---O-...-O---O---O-...-O---O ==FUSER=> O--...-O------O-...--O
172: *
173: */
174: public void test_2() {
175: final int nnodes = 100;
176: final int cyc = 50;
177:
178: Node[] ends = GraphTestUtil.buildNoBifurcations(generator(),
179: nnodes);
180: generator().add(
181: new Object[] { String.valueOf(cyc),
182: String.valueOf(cyc + 2) });
183: GraphGenerator fused = createGenerator();
184:
185: GraphFuser fuser = new GraphFuser(generator().getGraph(),
186: generator().getGraphBuilder(), createEdgeMerger());
187: assertTrue(fuser.fuse());
188:
189: assertTrue(generator().getGraph().getNodes().size() == 4);
190: assertTrue(generator().getGraph().getEdges().size() == 4);
191:
192: GraphVisitor visitor = new GraphVisitor() {
193: public int visit(Graphable component) {
194: String id = (String) component.getObject();
195: assertTrue((id.equals("0") || id.equals(String
196: .valueOf(nnodes - 1)))
197: || (id.equals(String.valueOf(cyc)) || id
198: .equals(String.valueOf(cyc + 2))));
199: return (0);
200: }
201: };
202: generator().getGraph().visitNodes(visitor);
203:
204: visitor = new GraphVisitor() {
205: public int visit(Graphable component) {
206: Edge e = (Edge) component;
207: String id0 = (String) e.getNodeA().getObject();
208: String id1 = (String) e.getNodeB().getObject();
209:
210: assertTrue((id0.equals("0") && id1.equals(String
211: .valueOf(cyc)))
212: || (id0.equals(String.valueOf(cyc)) && id1
213: .equals("0"))
214: || (id0.equals(String.valueOf(cyc)) && id1
215: .equals(String.valueOf(cyc + 2)))
216: || (id0.equals(String.valueOf(cyc + 2)) && id1
217: .equals(String.valueOf(cyc)))
218: || (id0.equals(String.valueOf(cyc + 2)) && id1
219: .equals(String.valueOf(nnodes - 1)))
220: || (id0.equals(String.valueOf(nnodes - 1)) && id1
221: .equals(String.valueOf(cyc + 2))));
222:
223: return (0);
224: }
225: };
226: generator().getGraph().visitEdges(visitor);
227: }
228:
229: /**
230: * Create a circular graph and fuse it. <BR>
231: * <BR>
232: * Expected: 1. The graph should have 1 node and 1 edge, a loop on one node.
233: *
234: */
235: public void test_3() {
236: int nnodes = 100;
237: GraphTestUtil.buildCircular(generator(), nnodes);
238:
239: GraphGenerator fused = createGenerator();
240:
241: GraphFuser fuser = new GraphFuser(generator().getGraph(),
242: generator().getGraphBuilder(), createEdgeMerger());
243: assertTrue(fuser.fuse());
244:
245: assertTrue(generator().getGraph().getNodes().size() == 1);
246: assertTrue(generator().getGraph().getEdges().size() == 1);
247: }
248:
249: protected GraphGenerator createGenerator() {
250: return (new BasicGraphGenerator());
251: }
252:
253: protected GraphGenerator generator() {
254: return (m_gen);
255: }
256:
257: protected GraphFuser.EdgeMerger createEdgeMerger() {
258: return (new GraphFuser.EdgeMerger() {
259: public Object merge(List edges) {
260: ArrayList ends = new ArrayList();
261: for (Iterator itr = edges.iterator(); itr.hasNext();) {
262: Edge edge = (Edge) itr.next();
263: if (edge.getNodeA().getDegree() != 2
264: || edge.getNodeB().getDegree() != 2)
265: ends.add(edge);
266: }
267:
268: Object[] obj = new Object[2];
269:
270: if (ends.size() == 2) {
271: Edge end0 = (Edge) ends.get(0);
272: Edge end1 = (Edge) ends.get(1);
273:
274: obj[0] = end0.getNodeA().getDegree() == 2 ? end0
275: .getNodeB().getObject() : end0.getNodeA()
276: .getObject();
277: obj[1] = end1.getNodeA().getDegree() == 2 ? end1
278: .getNodeB().getObject() : end1.getNodeA()
279: .getObject();
280: } else if (ends.size() == 0) {
281: obj[0] = ((Edge) edges.get(0)).getNodeA()
282: .getObject();
283: obj[1] = ((Edge) edges.get(0)).getNodeA()
284: .getObject();
285: } else
286: throw new IllegalStateException("Found "
287: + ends.size() + " ends.");
288:
289: return (obj);
290: }
291:
292: public void setMergedObject(Edge newEdge, Object merged) {
293: newEdge.setObject(merged);
294: }
295:
296: public void setMergedObject(Edge newEdge, Object merged,
297: List edges) {
298: newEdge.setObject(merged);
299: }
300: });
301: }
302: }
|