• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2014 The Guava Authors
3  *
4  * 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
7  *
8  * 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.
15  */
16 
17 package com.google.common.graph;
18 
19 import static com.google.common.graph.Graphs.hasCycle;
20 import static com.google.common.truth.Truth.assertThat;
21 
22 import com.google.common.collect.ImmutableList;
23 import org.junit.Before;
24 import org.junit.Test;
25 import org.junit.runner.RunWith;
26 import org.junit.runners.JUnit4;
27 
28 /** Tests for {@link Graphs#hasCycle(Graph)} and {@link Graphs#hasCycle(Network)}. */
29 // TODO(user): Consider moving this to GraphsTest.
30 @RunWith(JUnit4.class)
31 public class GraphPropertiesTest {
32   ImmutableList<MutableGraph<Integer>> graphsToTest;
33   Graph<Integer> directedGraph;
34   Graph<Integer> undirectedGraph;
35 
36   ImmutableList<MutableNetwork<Integer, String>> networksToTest;
37   Network<Integer, String> directedNetwork;
38   Network<Integer, String> undirectedNetwork;
39 
40   @Before
init()41   public void init() {
42     MutableGraph<Integer> mutableDirectedGraph =
43         GraphBuilder.directed().allowsSelfLoops(true).build();
44     MutableGraph<Integer> mutableUndirectedGraph =
45         GraphBuilder.undirected().allowsSelfLoops(true).build();
46     graphsToTest = ImmutableList.of(mutableDirectedGraph, mutableUndirectedGraph);
47     directedGraph = mutableDirectedGraph;
48     undirectedGraph = mutableUndirectedGraph;
49 
50     MutableNetwork<Integer, String> mutableDirectedNetwork =
51         NetworkBuilder.directed().allowsParallelEdges(true).allowsSelfLoops(true).build();
52     MutableNetwork<Integer, String> mutableUndirectedNetwork =
53         NetworkBuilder.undirected().allowsParallelEdges(true).allowsSelfLoops(true).build();
54     networksToTest = ImmutableList.of(mutableDirectedNetwork, mutableUndirectedNetwork);
55     directedNetwork = mutableDirectedNetwork;
56     undirectedNetwork = mutableUndirectedNetwork;
57   }
58 
59   @Test
hasCycle_emptyGraph()60   public void hasCycle_emptyGraph() {
61     assertThat(hasCycle(directedGraph)).isFalse();
62     assertThat(hasCycle(undirectedGraph)).isFalse();
63   }
64 
65   @Test
hasCycle_isolatedNodes()66   public void hasCycle_isolatedNodes() {
67     for (MutableGraph<Integer> graph : graphsToTest) {
68       graph.addNode(1);
69       graph.addNode(2);
70     }
71     assertThat(hasCycle(directedGraph)).isFalse();
72     assertThat(hasCycle(undirectedGraph)).isFalse();
73   }
74 
75   @Test
hasCycle_oneEdge()76   public void hasCycle_oneEdge() {
77     for (MutableGraph<Integer> graph : graphsToTest) {
78       graph.putEdge(1, 2);
79     }
80     assertThat(hasCycle(directedGraph)).isFalse();
81     assertThat(hasCycle(undirectedGraph)).isFalse();
82   }
83 
84   @Test
hasCycle_selfLoopEdge()85   public void hasCycle_selfLoopEdge() {
86     for (MutableGraph<Integer> graph : graphsToTest) {
87       graph.putEdge(1, 1);
88     }
89     assertThat(hasCycle(directedGraph)).isTrue();
90     assertThat(hasCycle(undirectedGraph)).isTrue();
91   }
92 
93   @Test
hasCycle_twoAcyclicEdges()94   public void hasCycle_twoAcyclicEdges() {
95     for (MutableGraph<Integer> graph : graphsToTest) {
96       graph.putEdge(1, 2);
97       graph.putEdge(1, 3);
98     }
99     assertThat(hasCycle(directedGraph)).isFalse();
100     assertThat(hasCycle(undirectedGraph)).isFalse();
101   }
102 
103   @Test
hasCycle_twoCyclicEdges()104   public void hasCycle_twoCyclicEdges() {
105     for (MutableGraph<Integer> graph : graphsToTest) {
106       graph.putEdge(1, 2);
107       graph.putEdge(2, 1); // no-op in undirected case
108     }
109     assertThat(hasCycle(directedGraph)).isTrue();
110     assertThat(hasCycle(undirectedGraph)).isFalse();
111   }
112 
113   @Test
hasCycle_threeAcyclicEdges()114   public void hasCycle_threeAcyclicEdges() {
115     for (MutableGraph<Integer> graph : graphsToTest) {
116       graph.putEdge(1, 2);
117       graph.putEdge(2, 3);
118       graph.putEdge(1, 3);
119     }
120     assertThat(hasCycle(directedGraph)).isFalse();
121     assertThat(hasCycle(undirectedGraph)).isTrue(); // cyclic in undirected case
122   }
123 
124   @Test
hasCycle_threeCyclicEdges()125   public void hasCycle_threeCyclicEdges() {
126     for (MutableGraph<Integer> graph : graphsToTest) {
127       graph.putEdge(1, 2);
128       graph.putEdge(2, 3);
129       graph.putEdge(3, 1);
130     }
131     assertThat(hasCycle(directedGraph)).isTrue();
132     assertThat(hasCycle(undirectedGraph)).isTrue();
133   }
134 
135   @Test
hasCycle_disconnectedCyclicGraph()136   public void hasCycle_disconnectedCyclicGraph() {
137     for (MutableGraph<Integer> graph : graphsToTest) {
138       graph.putEdge(1, 2);
139       graph.putEdge(2, 1); // no-op in undirected case
140       graph.addNode(3);
141     }
142     assertThat(hasCycle(directedGraph)).isTrue();
143     assertThat(hasCycle(undirectedGraph)).isFalse();
144   }
145 
146   @Test
hasCycle_multipleCycles()147   public void hasCycle_multipleCycles() {
148     for (MutableGraph<Integer> graph : graphsToTest) {
149       graph.putEdge(1, 2);
150       graph.putEdge(2, 1);
151       graph.putEdge(2, 3);
152       graph.putEdge(3, 1);
153     }
154     assertThat(hasCycle(directedGraph)).isTrue();
155     assertThat(hasCycle(undirectedGraph)).isTrue();
156   }
157 
158   @Test
hasCycle_twoParallelEdges()159   public void hasCycle_twoParallelEdges() {
160     for (MutableNetwork<Integer, String> network : networksToTest) {
161       network.addEdge(1, 2, "1-2a");
162       network.addEdge(1, 2, "1-2b");
163     }
164     assertThat(hasCycle(directedNetwork)).isFalse();
165     assertThat(hasCycle(undirectedNetwork)).isTrue(); // cyclic in undirected case
166   }
167 
168   @Test
hasCycle_cyclicMultigraph()169   public void hasCycle_cyclicMultigraph() {
170     for (MutableNetwork<Integer, String> network : networksToTest) {
171       network.addEdge(1, 2, "1-2a");
172       network.addEdge(1, 2, "1-2b");
173       network.addEdge(2, 3, "2-3");
174       network.addEdge(3, 1, "3-1");
175     }
176     assertThat(hasCycle(directedNetwork)).isTrue();
177     assertThat(hasCycle(undirectedNetwork)).isTrue();
178   }
179 }
180