KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > traverse > AbstractGraphIteratorTest


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* ------------------------------
26  * AbstractGraphIteratorTest.java
27  * ------------------------------
28  * (C) Copyright 2003-2006, by Liviu Rau and Contributors.
29  *
30  * Original Author: Liviu Rau
31  * Contributor(s): Barak Naveh
32  *
33  * $Id: AbstractGraphIteratorTest.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 30-Jul-2003 : Initial revision (LR);
38  * 06-Aug-2003 : Test traversal listener & extract a shared superclass (BN);
39  *
40  */
41 package org.jgrapht.traverse;
42
43 import org.jgrapht.*;
44 import org.jgrapht.event.*;
45 import org.jgrapht.graph.*;
46
47
48 /**
49  * A basis for testing {@link org.jgrapht.traverse.BreadthFirstIterator} and
50  * {@link org.jgrapht.traverse.DepthFirstIterator} classes.
51  *
52  * @author Liviu Rau
53  * @since Jul 30, 2003
54  */
55 public abstract class AbstractGraphIteratorTest
56     extends EnhancedTestCase
57 {
58
59     //~ Instance fields -------------------------------------------------------
60
61     StringBuffer JavaDoc result;
62
63     //~ Methods ---------------------------------------------------------------
64
65     /**
66      * .
67      */
68     public void testDirectedGraph()
69     {
70         result = new StringBuffer JavaDoc();
71
72         DirectedGraph<String JavaDoc, DefaultEdge> graph = createDirectedGraph();
73
74         AbstractGraphIterator<String JavaDoc, DefaultEdge> iterator =
75             createIterator(graph, "1");
76         iterator.addTraversalListener(new MyTraversalListener());
77
78         while (iterator.hasNext()) {
79             result.append(iterator.next());
80
81             if (iterator.hasNext()) {
82                 result.append(',');
83             }
84         }
85
86         assertEquals(getExpectedStr2(), result.toString());
87     }
88
89     abstract String JavaDoc getExpectedStr1();
90
91     abstract String JavaDoc getExpectedStr2();
92
93     DirectedGraph<String JavaDoc, DefaultEdge> createDirectedGraph()
94     {
95         DirectedGraph<String JavaDoc, DefaultEdge> graph =
96             new DefaultDirectedWeightedGraph<String JavaDoc, DefaultEdge>(
97                 DefaultWeightedEdge.class);
98
99         //
100 String JavaDoc v1 = "1";
101         String JavaDoc v2 = "2";
102         String JavaDoc v3 = "3";
103         String JavaDoc v4 = "4";
104         String JavaDoc v5 = "5";
105         String JavaDoc v6 = "6";
106         String JavaDoc v7 = "7";
107         String JavaDoc v8 = "8";
108         String JavaDoc v9 = "9";
109
110         graph.addVertex(v1);
111         graph.addVertex(v2);
112         graph.addVertex("3");
113         graph.addVertex("4");
114         graph.addVertex("5");
115         graph.addVertex("6");
116         graph.addVertex("7");
117         graph.addVertex("8");
118         graph.addVertex("9");
119
120         graph.addVertex("orphan");
121
122         // NOTE: set weights on some of the edges to test traversals like
123 // ClosestFirstIterator where it matters. For other traversals, it
124 // will be ignored. Rely on the default edge weight being 1.
125 graph.addEdge(v1, v2);
126         Graphs.addEdge(graph, v1, v3, 100);
127         Graphs.addEdge(graph, v2, v4, 1000);
128         graph.addEdge(v3, v5);
129         Graphs.addEdge(graph, v3, v6, 100);
130         graph.addEdge(v5, v6);
131         Graphs.addEdge(graph, v5, v7, 200);
132         graph.addEdge(v6, v1);
133         Graphs.addEdge(graph, v7, v8, 100);
134         graph.addEdge(v7, v9);
135         graph.addEdge(v8, v2);
136         graph.addEdge(v9, v4);
137
138         return graph;
139     }
140
141     abstract AbstractGraphIterator<String JavaDoc, DefaultEdge> createIterator(
142         DirectedGraph<String JavaDoc, DefaultEdge> g,
143         String JavaDoc startVertex);
144
145     //~ Inner Classes ---------------------------------------------------------
146
147     /**
148      * Internal traversal listener.
149      *
150      * @author Barak Naveh
151      */
152     private class MyTraversalListener
153         implements TraversalListener<String JavaDoc, DefaultEdge>
154     {
155         private int componentNumber = 0;
156         private int numComponentVertices = 0;
157
158         /**
159          * @see TraversalListener#connectedComponentFinished(ConnectedComponentTraversalEvent)
160          */
161         public void connectedComponentFinished(
162             ConnectedComponentTraversalEvent e)
163         {
164             switch (componentNumber) {
165             case 1:
166                 assertEquals(getExpectedStr1(), result.toString());
167                 assertEquals(9, numComponentVertices);
168
169                 break;
170
171             case 2:
172                 assertEquals(getExpectedStr2(), result.toString());
173                 assertEquals(1, numComponentVertices);
174
175                 break;
176
177             default:
178                 assertFalse();
179
180                 break;
181             }
182
183             numComponentVertices = 0;
184         }
185
186         /**
187          * @see TraversalListener#connectedComponentStarted(ConnectedComponentTraversalEvent)
188          */
189         public void connectedComponentStarted(
190             ConnectedComponentTraversalEvent e)
191         {
192             componentNumber++;
193         }
194
195         /**
196          * @see TraversalListener#edgeTraversed(EdgeTraversalEvent)
197          */
198         public void edgeTraversed(EdgeTraversalEvent<String JavaDoc, DefaultEdge> e)
199         {
200             // to be tested...
201 }
202
203         /**
204          * @see TraversalListener#vertexTraversed(VertexTraversalEvent)
205          */
206         public void vertexTraversed(VertexTraversalEvent<String JavaDoc> e)
207         {
208             numComponentVertices++;
209         }
210     }
211 }
212
Popular Tags