KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > CycleDetectorTest


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  * CycleDetectorTest.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: CycleDetectorTest.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 16-Sept-2004 : Initial revision (JVS);
38  *
39  */
40 package org.jgrapht.alg;
41
42 import java.util.*;
43
44 import junit.framework.*;
45
46 import org.jgrapht.*;
47 import org.jgrapht.graph.*;
48
49
50 /**
51  * .
52  *
53  * @author John V. Sichi
54  */
55 public class CycleDetectorTest
56     extends TestCase
57 {
58
59     //~ Static fields/initializers --------------------------------------------
60
61     private static final String JavaDoc V1 = "v1";
62     private static final String JavaDoc V2 = "v2";
63     private static final String JavaDoc V3 = "v3";
64     private static final String JavaDoc V4 = "v4";
65     private static final String JavaDoc V5 = "v5";
66     private static final String JavaDoc V6 = "v6";
67
68     //~ Methods ---------------------------------------------------------------
69
70     /**
71      * .
72      *
73      * @param g
74      */
75     public void createGraph(Graph<String JavaDoc, DefaultEdge> g)
76     {
77         g.addVertex(V1);
78         g.addVertex(V2);
79         g.addVertex(V3);
80         g.addVertex(V4);
81         g.addVertex(V5);
82         g.addVertex(V6);
83
84         g.addEdge(V1, V2);
85         g.addEdge(V2, V3);
86         g.addEdge(V3, V4);
87         g.addEdge(V4, V1);
88         g.addEdge(V4, V5);
89         g.addEdge(V5, V6);
90         g.addEdge(V1, V6);
91     }
92
93     /**
94      * .
95      */
96     public void testDirectedWithCycle()
97     {
98         DirectedGraph<String JavaDoc, DefaultEdge> g =
99             new DefaultDirectedGraph<String JavaDoc, DefaultEdge>(
100                 DefaultEdge.class);
101         createGraph(g);
102
103         Set<String JavaDoc> cyclicSet = new HashSet<String JavaDoc>();
104         cyclicSet.add(V1);
105         cyclicSet.add(V2);
106         cyclicSet.add(V3);
107         cyclicSet.add(V4);
108
109         Set<String JavaDoc> acyclicSet = new HashSet<String JavaDoc>();
110         acyclicSet.add(V5);
111         acyclicSet.add(V6);
112
113         runTest(g, cyclicSet, acyclicSet);
114     }
115
116     /**
117      * .
118      */
119     @SuppressWarnings JavaDoc("unchecked")
120     public void testDirectedWithoutCycle()
121     {
122         DirectedGraph<String JavaDoc, DefaultEdge> g =
123             new DefaultDirectedGraph<String JavaDoc, DefaultEdge>(
124                 DefaultEdge.class);
125         createGraph(g);
126         g.removeVertex(V2);
127
128         Set<String JavaDoc> cyclicSet = Collections.EMPTY_SET; // hb: I would like
129 // EMPTY_SET to be typed
130 // as well...
131 Set<String JavaDoc> acyclicSet = g.vertexSet();
132
133         runTest(g, cyclicSet, acyclicSet);
134     }
135
136     private void runTest(
137         DirectedGraph<String JavaDoc, DefaultEdge> g,
138         Set<String JavaDoc> cyclicSet,
139         Set<String JavaDoc> acyclicSet)
140     {
141         CycleDetector<String JavaDoc, DefaultEdge> detector =
142             new CycleDetector<String JavaDoc, DefaultEdge>(g);
143
144         Set emptySet = Collections.EMPTY_SET;
145
146         assertEquals(!cyclicSet.isEmpty(), detector.detectCycles());
147
148         assertEquals(cyclicSet, detector.findCycles());
149
150         for (String JavaDoc v : cyclicSet) {
151             assertEquals(true, detector.detectCyclesContainingVertex(v));
152             assertEquals(cyclicSet, detector.findCyclesContainingVertex(v));
153         }
154
155         for (String JavaDoc v : acyclicSet) {
156             assertEquals(false, detector.detectCyclesContainingVertex(v));
157             assertEquals(emptySet, detector.findCyclesContainingVertex(v));
158         }
159     }
160 }
161
Popular Tags