blob: 40f90513bfab5a989731fa0483eb90feb390f1bd [file] [log] [blame]
Thomas Vachuska24c849c2014-10-27 09:53:05 -07001/*
Thomas Vachuska4f1a60c2014-10-28 13:39:07 -07002 * Copyright 2014 Open Networking Laboratory
Thomas Vachuska24c849c2014-10-27 09:53:05 -07003 *
Thomas Vachuska4f1a60c2014-10-28 13:39:07 -07004 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
Thomas Vachuska24c849c2014-10-27 09:53:05 -07007 *
Thomas Vachuska4f1a60c2014-10-28 13:39:07 -07008 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
Thomas Vachuska24c849c2014-10-27 09:53:05 -070015 */
tom0633d682014-09-10 12:10:03 -070016package org.onlab.graph;
17
18import org.junit.Test;
19
20import static com.google.common.collect.ImmutableSet.of;
21import static org.junit.Assert.assertEquals;
Jonathan Hartd9df7bd2015-11-10 17:10:25 -080022import static org.onlab.graph.TarjanGraphSearch.SccResult;
tom0633d682014-09-10 12:10:03 -070023
24/**
25 * Tarjan graph search tests.
26 */
27public class TarjanGraphSearchTest extends GraphTest {
28
Jonathan Hartd9df7bd2015-11-10 17:10:25 -080029 private void validate(SccResult<TestVertex, TestEdge> result, int cc) {
tom0633d682014-09-10 12:10:03 -070030 System.out.println("Cluster count: " + result.clusterVertexes().size());
31 System.out.println("Clusters: " + result.clusterVertexes());
32 assertEquals("incorrect cluster count", cc, result.clusterCount());
33 }
34
Jonathan Hartd9df7bd2015-11-10 17:10:25 -080035 private void validate(SccResult<TestVertex, TestEdge> result,
tom0633d682014-09-10 12:10:03 -070036 int i, int vc, int ec) {
37 assertEquals("incorrect cluster count", vc, result.clusterVertexes().get(i).size());
38 assertEquals("incorrect edge count", ec, result.clusterEdges().get(i).size());
39 }
40
41 @Test
42 public void basic() {
43 graph = new AdjacencyListsGraph<>(vertexes(), edges());
44 TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
Jonathan Hartd9df7bd2015-11-10 17:10:25 -080045 SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
tom0633d682014-09-10 12:10:03 -070046 validate(result, 6);
47 }
48
49 @Test
50 public void singleCluster() {
51 graph = new AdjacencyListsGraph<>(vertexes(),
52 of(new TestEdge(A, B, 1),
53 new TestEdge(B, C, 1),
54 new TestEdge(C, D, 1),
55 new TestEdge(D, E, 1),
56 new TestEdge(E, F, 1),
57 new TestEdge(F, G, 1),
58 new TestEdge(G, H, 1),
59 new TestEdge(H, A, 1)));
60
61 TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
Jonathan Hartd9df7bd2015-11-10 17:10:25 -080062 SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
tom0633d682014-09-10 12:10:03 -070063 validate(result, 1);
64 validate(result, 0, 8, 8);
65 }
66
67 @Test
68 public void twoUnconnectedCluster() {
69 graph = new AdjacencyListsGraph<>(vertexes(),
70 of(new TestEdge(A, B, 1),
71 new TestEdge(B, C, 1),
72 new TestEdge(C, D, 1),
73 new TestEdge(D, A, 1),
74 new TestEdge(E, F, 1),
75 new TestEdge(F, G, 1),
76 new TestEdge(G, H, 1),
77 new TestEdge(H, E, 1)));
78 TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
Jonathan Hartd9df7bd2015-11-10 17:10:25 -080079 SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
tom0633d682014-09-10 12:10:03 -070080 validate(result, 2);
81 validate(result, 0, 4, 4);
82 validate(result, 1, 4, 4);
83 }
84
85 @Test
86 public void twoWeaklyConnectedClusters() {
87 graph = new AdjacencyListsGraph<>(vertexes(),
88 of(new TestEdge(A, B, 1),
89 new TestEdge(B, C, 1),
90 new TestEdge(C, D, 1),
91 new TestEdge(D, A, 1),
92 new TestEdge(E, F, 1),
93 new TestEdge(F, G, 1),
94 new TestEdge(G, H, 1),
95 new TestEdge(H, E, 1),
96 new TestEdge(B, E, 1)));
97 TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
Jonathan Hartd9df7bd2015-11-10 17:10:25 -080098 SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
tom0633d682014-09-10 12:10:03 -070099 validate(result, 2);
100 validate(result, 0, 4, 4);
101 validate(result, 1, 4, 4);
102 }
103
104 @Test
105 public void twoClustersConnectedWithIgnoredEdges() {
106 graph = new AdjacencyListsGraph<>(vertexes(),
107 of(new TestEdge(A, B, 1),
108 new TestEdge(B, C, 1),
109 new TestEdge(C, D, 1),
110 new TestEdge(D, A, 1),
111 new TestEdge(E, F, 1),
112 new TestEdge(F, G, 1),
113 new TestEdge(G, H, 1),
114 new TestEdge(H, E, 1),
115 new TestEdge(B, E, -1),
116 new TestEdge(E, B, -1)));
117
118 TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
Jonathan Hartd9df7bd2015-11-10 17:10:25 -0800119 SccResult<TestVertex, TestEdge> result = gs.search(graph, weight);
tom0633d682014-09-10 12:10:03 -0700120 validate(result, 2);
121 validate(result, 0, 4, 4);
122 validate(result, 1, 4, 4);
123 }
124
125}