1 25 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 55 public class BronKerboschCliqueFinderTest 56 extends TestCase 57 { 58 59 61 private static final String V1 = "v1"; 62 private static final String V2 = "v2"; 63 private static final String V3 = "v3"; 64 private static final String V4 = "v4"; 65 private static final String V5 = "v5"; 66 private static final String V6 = "v6"; 67 private static final String V7 = "v7"; 68 private static final String V8 = "v8"; 69 70 72 77 public void createGraph(Graph<String , 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 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 g.addEdge(V5, V6); 98 g.addEdge(V5, V7); 99 g.addEdge(V6, V7); 100 101 g.addEdge(V3, V5); 103 g.addEdge(V4, V5); 104 105 g.addEdge(V7, V8); 107 } 108 109 public void testFindBiggest() 110 { 111 SimpleGraph<String , DefaultEdge> g = 112 new SimpleGraph<String , DefaultEdge>(DefaultEdge.class); 113 createGraph(g); 114 115 BronKerboschCliqueFinder<String , DefaultEdge> finder = 116 new BronKerboschCliqueFinder<String , DefaultEdge>(g); 117 118 Collection<Set<String >> cliques = finder.getBiggestMaximalCliques(); 119 120 assertEquals(1, cliques.size()); 121 122 Set<String > expected = new HashSet<String >(); 123 expected.add(V1); 124 expected.add(V2); 125 expected.add(V3); 126 expected.add(V4); 127 128 Set<String > actual = cliques.iterator().next(); 129 130 assertEquals(expected, actual); 131 } 132 133 public void testFindAll() 134 { 135 SimpleGraph<String , DefaultEdge> g = 136 new SimpleGraph<String , DefaultEdge>(DefaultEdge.class); 137 createGraph(g); 138 139 BronKerboschCliqueFinder<String , DefaultEdge> finder = 140 new BronKerboschCliqueFinder<String , DefaultEdge>(g); 141 142 Collection<Set<String >> cliques = finder.getAllMaximalCliques(); 143 144 assertEquals(4, cliques.size()); 145 146 Set<Set<String >> expected = new HashSet<Set<String >>(); 147 148 Set<String > set = new HashSet<String >(); 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 >(); 156 set.add(V5); 157 set.add(V6); 158 set.add(V7); 159 expected.add(set); 160 161 set = new HashSet<String >(); 162 set.add(V3); 163 set.add(V4); 164 set.add(V5); 165 expected.add(set); 166 167 set = new HashSet<String >(); 168 set.add(V7); 169 set.add(V8); 170 expected.add(set); 171 172 Set<Set<String >> actual = new HashSet<Set<String >>(cliques); 175 176 assertEquals(expected, actual); 177 } 178 } 179 180 | Popular Tags |