1 | |
|
2 | |
|
3 | |
|
4 | |
|
5 | |
|
6 | |
|
7 | |
|
8 | |
|
9 | |
|
10 | |
|
11 | |
|
12 | |
|
13 | |
|
14 | |
|
15 | |
|
16 | |
|
17 | |
|
18 | |
|
19 | |
|
20 | |
|
21 | |
|
22 | |
package net.sourceforge.combean.test.graph.alg.spath; |
23 | |
|
24 | |
import net.sourceforge.combean.interfaces.graph.NodeIterator; |
25 | |
import net.sourceforge.combean.interfaces.graph.alg.spath.SingleSourceShortestPathWithNegCycleDetectionAlg; |
26 | |
import net.sourceforge.combean.interfaces.graph.containers.FixedPath; |
27 | |
|
28 | |
|
29 | |
|
30 | |
|
31 | |
|
32 | |
public class GraphWithNegativeCycleFixture |
33 | |
extends AbstractGraphWithEdgeWeightsFixture { |
34 | |
|
35 | |
|
36 | |
|
37 | |
|
38 | |
|
39 | |
|
40 | |
|
41 | |
|
42 | |
|
43 | |
|
44 | |
|
45 | |
|
46 | |
|
47 | |
|
48 | |
|
49 | |
|
50 | |
|
51 | 3 | private static int[][] edgesWithWeights = { |
52 | |
{0, 2, 4}, |
53 | |
{0, 1, 6}, |
54 | |
{1, 2, 2}, |
55 | |
{1, 3, 2}, |
56 | |
{3, 2,-4}, |
57 | |
{2, 4, 2}, |
58 | |
{3, 5, 7}, |
59 | |
{4, 3, 1}, |
60 | |
{4, 5, 3} |
61 | |
}; |
62 | |
|
63 | 3 | private static int[] cycleNodes = {2,4,3,2,4,3}; |
64 | |
|
65 | |
|
66 | |
|
67 | |
|
68 | |
public GraphWithNegativeCycleFixture() throws Exception { |
69 | 21 | super(6, edgesWithWeights); |
70 | 21 | } |
71 | |
|
72 | |
public final void checkNegativeCycleDetection( |
73 | |
SingleSourceShortestPathWithNegCycleDetectionAlg<Double> alg) { |
74 | 3 | runShortestPathAlg(alg); |
75 | |
|
76 | 3 | boolean negCycleFound = alg.hasNegativeCycle(); |
77 | 3 | assertTrue(negCycleFound); |
78 | |
|
79 | 3 | FixedPath cycle = alg.getNegativeCycle(); |
80 | 3 | assertNotNull(cycle); |
81 | |
|
82 | 3 | int idxOfFirstNodeInCycle = |
83 | |
this.constructG.getNodeNumber(cycle.getFirstNode()); |
84 | 3 | int startNodeIdx = -1; |
85 | 6 | for (int i = 0; i < 3; i++) { |
86 | 6 | if (cycleNodes[i] == idxOfFirstNodeInCycle) { |
87 | 3 | startNodeIdx = i; |
88 | 3 | break; |
89 | |
} |
90 | |
} |
91 | 3 | assertTrue("first node of cycle with number " + idxOfFirstNodeInCycle + |
92 | |
" must belong to cyclenodes array", |
93 | |
-1 != startNodeIdx); |
94 | |
|
95 | 3 | NodeIterator itCycle = cycle.getNodeIterator(); |
96 | 15 | for (int i = 0; i < 4; i++) { |
97 | 12 | assertTrue("cycle may not end prematurely", itCycle.hasNext()); |
98 | 12 | int currNodeNum = this.constructG.getNodeNumber(itCycle.next()); |
99 | 12 | assertEquals(cycleNodes[startNodeIdx + i], currNodeNum); |
100 | |
} |
101 | 3 | assertFalse("cycle may not have additional nodes", itCycle.hasNext()); |
102 | 3 | } |
103 | |
} |