KickJava   Java API By Example, From Geeks To Geeks.

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


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  * BronKerboschCliqueFinderTest.java
27  * ------------------------------
28  * (C) Copyright 2005-2006, by John V. Sichi and Contributors.
29  *
30  * Original Author: John V. Sichi
31  * Contributor(s): -
32  *
33  * $Id: BronKerboschCliqueFinderTest.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 26-July-2005 : 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 BronKerboschCliqueFinderTest
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     private static final String JavaDoc V7 = "v7";
68     private static final String JavaDoc V8 = "v8";
69
70     //~ Methods ---------------------------------------------------------------
71

72     /**
73      * .
74      *
75      * @param g
76      */

77     public void createGraph(Graph<String JavaDoc, DefaultEdge> g)
78     {
79         g.addVertex(V1);
80         g.addVertex(V2);
81         g.addVertex(V3);
82         g.addVertex(V4);
83         g.addVertex(V5);
84         g.addVertex(V6);
85         g.addVertex(V7);
86         g.addVertex(V8);
87
88         // biggest clique: { V1, V2, V3, V4 }
89
g.addEdge(V1, V2);
90         g.addEdge(V1, V3);
91         g.addEdge(V1, V4);
92         g.addEdge(V2, V3);
93         g.addEdge(V2, V4);
94         g.addEdge(V3, V4);
95
96         // smaller clique: { V5, V6, V7 }
97
g.addEdge(V5, V6);
98         g.addEdge(V5, V7);
99         g.addEdge(V6, V7);
100
101         // for fun, add an overlapping clique { V3, V4, V5 }
102
g.addEdge(V3, V5);
103         g.addEdge(V4, V5);
104
105         // make V8 less lonely
106
g.addEdge(V7, V8);
107     }
108
109     public void testFindBiggest()
110     {
111         SimpleGraph<String JavaDoc, DefaultEdge> g =
112             new SimpleGraph<String JavaDoc, DefaultEdge>(DefaultEdge.class);
113         createGraph(g);
114
115         BronKerboschCliqueFinder<String JavaDoc, DefaultEdge> finder =
116             new BronKerboschCliqueFinder<String JavaDoc, DefaultEdge>(g);
117
118         Collection<Set<String JavaDoc>> cliques = finder.getBiggestMaximalCliques();
119
120         assertEquals(1, cliques.size());
121
122         Set<String JavaDoc> expected = new HashSet<String JavaDoc>();
123         expected.add(V1);
124         expected.add(V2);
125         expected.add(V3);
126         expected.add(V4);
127
128         Set<String JavaDoc> actual = cliques.iterator().next();
129
130         assertEquals(expected, actual);
131     }
132
133     public void testFindAll()
134     {
135         SimpleGraph<String JavaDoc, DefaultEdge> g =
136             new SimpleGraph<String JavaDoc, DefaultEdge>(DefaultEdge.class);
137         createGraph(g);
138
139         BronKerboschCliqueFinder<String JavaDoc, DefaultEdge> finder =
140             new BronKerboschCliqueFinder<String JavaDoc, DefaultEdge>(g);
141
142         Collection<Set<String JavaDoc>> cliques = finder.getAllMaximalCliques();
143
144         assertEquals(4, cliques.size());
145
146         Set<Set<String JavaDoc>> expected = new HashSet<Set<String JavaDoc>>();
147
148         Set<String JavaDoc> set = new HashSet<String JavaDoc>();
149         set.add(V1);
150         set.add(V2);
151         set.add(V3);
152         set.add(V4);
153         expected.add(set);
154
155         set = new HashSet<String JavaDoc>();
156         set.add(V5);
157         set.add(V6);
158         set.add(V7);
159         expected.add(set);
160
161         set = new HashSet<String JavaDoc>();
162         set.add(V3);
163         set.add(V4);
164         set.add(V5);
165         expected.add(set);
166
167         set = new HashSet<String JavaDoc>();
168         set.add(V7);
169         set.add(V8);
170         expected.add(set);
171
172         // convert result from Collection to Set because we don't want
173
// order to be significant
174
Set<Set<String JavaDoc>> actual = new HashSet<Set<String JavaDoc>>(cliques);
175
176         assertEquals(expected, actual);
177     }
178 }
179
180 // End BronKerboschCliqueFinderTest.java
181
Popular Tags