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.io.standard;
018:
019: import java.io.File;
020: import java.util.HashSet;
021: import java.util.Map;
022: import java.util.StringTokenizer;
023:
024: import junit.framework.TestCase;
025:
026: import org.geotools.graph.GraphTestUtil;
027: import org.geotools.graph.build.GraphBuilder;
028: import org.geotools.graph.build.basic.BasicGraphBuilder;
029: import org.geotools.graph.structure.Edge;
030: import org.geotools.graph.structure.Graph;
031: import org.geotools.graph.structure.GraphVisitor;
032: import org.geotools.graph.structure.Graphable;
033: import org.geotools.graph.structure.Node;
034:
035: public class BasicGraphSerializerTest extends TestCase {
036:
037: private GraphBuilder m_builder;
038: private GraphBuilder m_rebuilder;
039: private SerializedReaderWriter m_serializer;
040:
041: public BasicGraphSerializerTest(String name) {
042: super (name);
043: }
044:
045: protected void setUp() throws Exception {
046: super .setUp();
047:
048: m_builder = createBuilder();
049: m_rebuilder = createRebuilder();
050: m_serializer = new SerializedReaderWriter();
051: m_serializer.setProperty(SerializedReaderWriter.BUILDER,
052: rebuilder());
053: }
054:
055: /**
056: * Create a simple graph with no bifurcations and serialize, then deserialize
057: * <BR>
058: * <BR>
059: * Expected: 1. before and after graph should have same structure.
060: *
061: */
062: public void test_0() throws Exception {
063: final int nnodes = 100;
064: GraphTestUtil.buildNoBifurcations(builder(), nnodes);
065: File victim = File.createTempFile("graph", null);
066: victim.deleteOnExit();
067:
068: m_serializer.setProperty(SerializedReaderWriter.FILENAME,
069: victim.getAbsolutePath());
070:
071: m_serializer.write(builder().getGraph());
072:
073: Graph before = builder().getGraph();
074: Graph after = m_serializer.read();
075:
076: //ensure same number of nodes and edges
077: assertTrue(before.getNodes().size() == after.getNodes().size());
078: assertTrue(before.getEdges().size() == after.getEdges().size());
079:
080: //ensure same graph structure
081: GraphVisitor visitor = new GraphVisitor() {
082: public int visit(Graphable component) {
083: Edge e = (Edge) component;
084:
085: assertTrue(e.getNodeA().getID() == e.getID());
086: assertTrue(e.getNodeB().getID() == e.getID() + 1);
087:
088: return (0);
089: }
090: };
091: after.visitEdges(visitor);
092:
093: visitor = new GraphVisitor() {
094: public int visit(Graphable component) {
095: Node n = (Node) component;
096:
097: if (n.getDegree() == 1) {
098: assertTrue(n.getID() == 0
099: || n.getID() == nnodes - 1);
100: } else {
101: assertTrue(n.getDegree() == 2);
102:
103: Edge e0 = (Edge) n.getEdges().get(0);
104: Edge e1 = (Edge) n.getEdges().get(1);
105:
106: assertTrue((e0.getID() == n.getID() - 1 && e1
107: .getID() == n.getID())
108: || (e1.getID() == n.getID() - 1 && e0
109: .getID() == n.getID()));
110:
111: }
112:
113: return (0);
114: }
115: };
116: after.visitNodes(visitor);
117: }
118:
119: /**
120: * Create a perfect binary tree, serialize it and deserialize it. <BR>
121: * <BR>
122: * Expected: 1. Same structure before and after.
123: *
124: */
125: public void test_1() {
126: final int k = 5;
127: Object[] obj = GraphTestUtil.buildPerfectBinaryTree(builder(),
128: k);
129: final Node root = (Node) obj[0];
130: final Map obj2node = (Map) obj[1];
131:
132: try {
133: File victim = File.createTempFile("graph", null);
134: victim.deleteOnExit();
135: m_serializer.setProperty(SerializedReaderWriter.FILENAME,
136: victim.getAbsolutePath());
137:
138: m_serializer.write(builder().getGraph());
139:
140: Graph before = builder().getGraph();
141: Graph after = m_serializer.read();
142:
143: //ensure same number of nodes and edges
144: assertTrue(before.getNodes().size() == after.getNodes()
145: .size());
146: assertTrue(before.getEdges().size() == after.getEdges()
147: .size());
148:
149: //ensure same structure
150: GraphVisitor visitor = new GraphVisitor() {
151: public int visit(Graphable component) {
152: Node n = (Node) component;
153: String id = (String) n.getObject();
154:
155: assertTrue(obj2node.get(id) != null);
156:
157: StringTokenizer st = new StringTokenizer(id, ".");
158:
159: if (st.countTokens() == 1) {
160: //root
161: assertTrue(n.getDegree() == 2);
162:
163: Node n0 = ((Edge) n.getEdges().get(0))
164: .getOtherNode(n);
165: Node n1 = ((Edge) n.getEdges().get(1))
166: .getOtherNode(n);
167:
168: assertTrue(n0.getObject().equals("0.0")
169: && n1.getObject().equals("0.1")
170: || n0.getObject().equals("0.1")
171: && n1.getObject().equals("0.0"));
172: } else if (st.countTokens() == k + 1) {
173: //leaf
174: assertTrue(n.getDegree() == 1);
175:
176: Node parent = ((Edge) n.getEdges().get(0))
177: .getOtherNode(n);
178: String parentid = (String) parent.getObject();
179:
180: assertTrue(parentid.equals(id.substring(0, id
181: .length() - 2)));
182: } else {
183: //internal
184: assertTrue(n.getDegree() == 3);
185:
186: String id0 = ((Edge) n.getEdges().get(0))
187: .getOtherNode(n).getObject().toString();
188: String id1 = ((Edge) n.getEdges().get(1))
189: .getOtherNode(n).getObject().toString();
190: String id2 = ((Edge) n.getEdges().get(2))
191: .getOtherNode(n).getObject().toString();
192:
193: String parentid = id.substring(0,
194: id.length() - 2);
195:
196: assertTrue(id0.equals(parentid)
197: && id1.equals(id + ".0")
198: && id2.equals(id + ".1")
199: || id0.equals(parentid)
200: && id2.equals(id + ".0")
201: && id1.equals(id + ".1")
202: || id1.equals(parentid)
203: && id0.equals(id + ".0")
204: && id2.equals(id + ".1")
205: || id1.equals(parentid)
206: && id2.equals(id + ".0")
207: && id0.equals(id + ".1")
208: || id2.equals(parentid)
209: && id0.equals(id + ".0")
210: && id1.equals(id + ".1")
211: || id2.equals(parentid)
212: && id1.equals(id + ".0")
213: && id0.equals(id + ".1"));
214: }
215:
216: return (0);
217: }
218: };
219: after.visitNodes(visitor);
220:
221: } catch (Exception e) {
222: e.printStackTrace();
223: assertTrue(false);
224: }
225: }
226:
227: /**
228: * Create a simple graph and disconnect two nodes (remove all edges)
229: * then serialize and deserialize. <BR>
230: * <BR>
231: * Exepcted: 1. Same graph structure.
232: *
233: */
234: public void test_2() {
235: final int nnodes = 100;
236: Node[] ends = GraphTestUtil.buildNoBifurcations(builder(),
237: nnodes);
238:
239: HashSet toRemove = new HashSet();
240: toRemove.addAll(ends[0].getEdges());
241: toRemove.addAll(ends[1].getEdges());
242:
243: //disconnect end nodes
244: builder().removeEdges(toRemove);
245:
246: assertTrue(builder().getGraph().getNodes().size() == nnodes);
247: assertTrue(builder().getGraph().getEdges().size() == nnodes - 3);
248:
249: try {
250: File victim = File.createTempFile("graph", null);
251: victim.deleteOnExit();
252: m_serializer.setProperty(SerializedReaderWriter.FILENAME,
253: victim.getAbsolutePath());
254:
255: m_serializer.write(builder().getGraph());
256:
257: Graph before = builder().getGraph();
258: Graph after = m_serializer.read();
259:
260: //ensure same number of nodes and edges
261: assertTrue(before.getNodes().size() == after.getNodes()
262: .size());
263: assertTrue(before.getEdges().size() == after.getEdges()
264: .size());
265:
266: GraphVisitor visitor = new GraphVisitor() {
267: public int visit(Graphable component) {
268: Node n = (Node) component;
269: if (n.getID() == 0 || n.getID() == nnodes - 1)
270: assertTrue(n.getDegree() == 0);
271: else if (n.getID() == 1 || n.getID() == nnodes - 2)
272: assertTrue(n.getDegree() == 1);
273: else
274: assertTrue(n.getDegree() == 2);
275:
276: return (0);
277: }
278: };
279: after.visitNodes(visitor);
280: } catch (Exception e) {
281: e.printStackTrace();
282: assertTrue(false);
283: }
284: }
285:
286: protected GraphBuilder createBuilder() {
287: return (new BasicGraphBuilder());
288: }
289:
290: protected GraphBuilder createRebuilder() {
291: return (new BasicGraphBuilder());
292: }
293:
294: protected GraphBuilder builder() {
295: return (m_builder);
296: }
297:
298: protected GraphBuilder rebuilder() {
299: return (m_rebuilder);
300: }
301:
302: protected SerializedReaderWriter serializer() {
303: return (m_serializer);
304: }
305:
306: }
|