KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > generate > GraphGeneratorTest


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  * GraphGeneratorTest.java
27  * -----------------------
28  * (C) Copyright 2003-2006, by John V. Sichi and Contributors.
29  *
30  * Original Author: John V. Sichi
31  * Contributor(s): -
32  *
33  * $Id: GraphGeneratorTest.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 17-Sep-2003 : Initial revision (JVS);
38  * 07-May-2006 : Changed from List<Edge> to Set<Edge> (JVS);
39  *
40  */
41 package org.jgrapht.generate;
42
43 import java.util.*;
44
45 import junit.framework.*;
46
47 import org.jgrapht.*;
48 import org.jgrapht.graph.*;
49
50
51 /**
52  * .
53  *
54  * @author John V. Sichi
55  * @since Sep 17, 2003
56  */
57 public class GraphGeneratorTest
58     extends TestCase
59 {
60
61     //~ Static fields/initializers --------------------------------------------
62
63     private static final int SIZE = 10;
64
65     //~ Instance fields -------------------------------------------------------
66
67     private VertexFactory<Object JavaDoc> vertexFactory =
68         new VertexFactory<Object JavaDoc>() {
69             private int i;
70
71             public Object JavaDoc createVertex()
72             {
73                 return new Integer JavaDoc(++i);
74             }
75         };
76
77
78     //~ Methods ---------------------------------------------------------------
79
80     /**
81      * .
82      */
83     public void testEmptyGraphGenerator()
84     {
85         GraphGenerator<Object JavaDoc, DefaultEdge, Object JavaDoc> gen =
86             new EmptyGraphGenerator<Object JavaDoc, DefaultEdge>(SIZE);
87         DirectedGraph<Object JavaDoc, DefaultEdge> g =
88             new DefaultDirectedGraph<Object JavaDoc, DefaultEdge>(DefaultEdge.class);
89         Map<String JavaDoc, Object JavaDoc> resultMap = new HashMap<String JavaDoc, Object JavaDoc>();
90         gen.generateGraph(g, vertexFactory, resultMap);
91         assertEquals(SIZE, g.vertexSet().size());
92         assertEquals(0, g.edgeSet().size());
93         assertTrue(resultMap.isEmpty());
94     }
95
96     /**
97      * .
98      */
99     public void testLinearGraphGenerator()
100     {
101         GraphGenerator<Object JavaDoc, DefaultEdge, Object JavaDoc> gen =
102             new LinearGraphGenerator<Object JavaDoc, DefaultEdge>(SIZE);
103         DirectedGraph<Object JavaDoc, DefaultEdge> g =
104             new DefaultDirectedGraph<Object JavaDoc, DefaultEdge>(DefaultEdge.class);
105         Map<String JavaDoc, Object JavaDoc> resultMap = new HashMap<String JavaDoc, Object JavaDoc>();
106         gen.generateGraph(g, vertexFactory, resultMap);
107         assertEquals(SIZE, g.vertexSet().size());
108         assertEquals(SIZE - 1, g.edgeSet().size());
109
110         Object JavaDoc startVertex = resultMap.get(LinearGraphGenerator.START_VERTEX);
111         Object JavaDoc endVertex = resultMap.get(LinearGraphGenerator.END_VERTEX);
112         Iterator vertexIter = g.vertexSet().iterator();
113
114         while (vertexIter.hasNext()) {
115             Object JavaDoc vertex = vertexIter.next();
116
117             if (vertex == startVertex) {
118                 assertEquals(0, g.inDegreeOf(vertex));
119                 assertEquals(1, g.outDegreeOf(vertex));
120
121                 continue;
122             }
123
124             if (vertex == endVertex) {
125                 assertEquals(1, g.inDegreeOf(vertex));
126                 assertEquals(0, g.outDegreeOf(vertex));
127
128                 continue;
129             }
130
131             assertEquals(1, g.inDegreeOf(vertex));
132             assertEquals(1, g.outDegreeOf(vertex));
133         }
134     }
135
136     /**
137      * .
138      */
139     public void testRingGraphGenerator()
140     {
141         GraphGenerator<Object JavaDoc, DefaultEdge, Object JavaDoc> gen =
142             new RingGraphGenerator<Object JavaDoc, DefaultEdge>(SIZE);
143         DirectedGraph<Object JavaDoc, DefaultEdge> g =
144             new DefaultDirectedGraph<Object JavaDoc, DefaultEdge>(DefaultEdge.class);
145         Map<String JavaDoc, Object JavaDoc> resultMap = new HashMap<String JavaDoc, Object JavaDoc>();
146         gen.generateGraph(g, vertexFactory, resultMap);
147         assertEquals(SIZE, g.vertexSet().size());
148         assertEquals(SIZE, g.edgeSet().size());
149
150         Object JavaDoc startVertex = g.vertexSet().iterator().next();
151         assertEquals(1, g.outDegreeOf(startVertex));
152
153         Object JavaDoc nextVertex = startVertex;
154         Set<Object JavaDoc> seen = new HashSet<Object JavaDoc>();
155
156         for (int i = 0; i < SIZE; ++i) {
157             DefaultEdge nextEdge =
158                 g.outgoingEdgesOf(nextVertex).iterator().next();
159             nextVertex = g.getEdgeTarget(nextEdge);
160             assertEquals(1, g.inDegreeOf(nextVertex));
161             assertEquals(1, g.outDegreeOf(nextVertex));
162             assertTrue(!seen.contains(nextVertex));
163             seen.add(nextVertex);
164         }
165
166         // do you ever get the feeling you're going in circles?
167 assertTrue(nextVertex == startVertex);
168         assertTrue(resultMap.isEmpty());
169     }
170
171     // TODO: testWheelGraphGenerator
172 }
173
Popular Tags