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