1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
/*
* SonarQube, open source software quality management tool.
* Copyright (C) 2008-2012 SonarSource
* mailto:contact AT sonarsource DOT com
*
* SonarQube is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 3 of the License, or (at your option) any later version.
*
* SonarQube is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with Sonar; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02
*/
package org.sonar.graph;
import java.util.Set;
import org.junit.Test;
import static org.hamcrest.Matchers.is;
import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertTrue;
public class MinimumFeedbackEdgeSetSolverTest {
@Test
public void testGetFeedbackEdgesOnSimpleLoop() {
DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph();
dcg.addEdge("A", "B", 3).addEdge("B", "A", 1);
CycleDetector<String> cycleDetector = new CycleDetector<String>(dcg);
cycleDetector.detectCycles();
MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles());
Set<Edge> feedbackEdges = solver.getEdges();
assertThat(feedbackEdges.size(), is(1));
}
@Test
public void testFlagFeedbackEdgesOnSimpleLoop() {
DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph();
dcg.addEdge("A", "B", 3).addEdge("B", "A", 1);
CycleDetector<String> cycleDetector = new CycleDetector<String>(dcg);
cycleDetector.detectCycles();
MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles());
Set<Edge> feedbackEdges = solver.getEdges();
assertTrue(feedbackEdges.contains(dcg.getEdge("B", "A")));
}
@Test
public void testGetFeedbackEdgesOnComplexGraph() {
DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph();
dcg.addEdge("A", "B", 7).addEdge("B", "C", 3).addEdge("C", "D", 1).addEdge("D", "A", 3);
dcg.addEdge("B", "A", 12);
CycleDetector<String> cycleDetector = new CycleDetector<String>(dcg);
cycleDetector.detectCycles();
MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles());
Set<Edge> feedbackEdges = solver.getEdges();
assertThat(feedbackEdges.size(), is(1));
assertTrue(feedbackEdges.contains(dcg.getEdge("A", "B")));
}
@Test
public void testFlagFeedbackEdgesOnUnrelatedCycles() {
DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph();
dcg.addEdge("A", "B", 7).addEdge("B", "C", 3).addEdge("C", "A", 2);
dcg.addEdge("D", "E", 3).addEdge("E", "D", 5);
dcg.addEdge("F", "G", 1).addEdge("G", "H", 4).addEdge("H", "F", 7);
CycleDetector<String> cycleDetector = new CycleDetector<String>(dcg);
cycleDetector.detectCycles();
MinimumFeedbackEdgeSetSolver solver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles());
Set<Edge> feedbackEdges = solver.getEdges();
assertThat(feedbackEdges.size(), is(3));
assertTrue(feedbackEdges.contains(dcg.getEdge("C", "A")));
assertTrue(feedbackEdges.contains(dcg.getEdge("D", "E")));
assertTrue(feedbackEdges.contains(dcg.getEdge("F", "G")));
}
@Test
public void testApproximateMinimumFeedbackEdges() {
DirectedGraph<String, StringEdge> dcg = DirectedGraph.createStringDirectedGraph();
dcg.addEdge("A", "B", 5).addEdge("B", "C", 9).addEdge("C", "A", 1);
dcg.addEdge("D", "B", 5).addEdge("C", "D", 7);
dcg.addEdge("F", "B", 5).addEdge("C", "F", 4);
CycleDetector<String> cycleDetector = new CycleDetector<String>(dcg);
cycleDetector.detectCycles();
MinimumFeedbackEdgeSetSolver minimumSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles());
assertThat(minimumSolver.getEdges().size(), is(1));
assertTrue(minimumSolver.getEdges().contains(dcg.getEdge("B", "C")));
MinimumFeedbackEdgeSetSolver approximateSolver = new MinimumFeedbackEdgeSetSolver(cycleDetector.getCycles(), 2);
assertThat(approximateSolver.getEdges().size(), is(2));
assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("B", "C")));
assertTrue(approximateSolver.getEdges().contains(dcg.getEdge("C", "A")));
}
}
|
