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.flow; |
23 | |
|
24 | |
import junit.framework.TestCase; |
25 | |
import net.sourceforge.combean.graph.containers.doubleval.EdgeMapAsDoubleEdgeMap; |
26 | |
import net.sourceforge.combean.graph.containers.doubleval.NodeMapAsDoubleNodeMap; |
27 | |
import net.sourceforge.combean.graph.prop.statics.ConstructableNumberedGraphBuilder; |
28 | |
import net.sourceforge.combean.interfaces.graph.alg.flow.MinCostFlowAlg; |
29 | |
import net.sourceforge.combean.interfaces.graph.containers.doubleval.DoubleEdgeMap; |
30 | |
import net.sourceforge.combean.interfaces.graph.containers.doubleval.DoubleNodeMap; |
31 | |
import net.sourceforge.combean.interfaces.graph.prop.ConstructableNumberedGraphProp; |
32 | |
import net.sourceforge.combean.test.helpers.checks.CheckGraph; |
33 | |
import net.sourceforge.combean.test.helpers.factories.GraphFixtureFactory; |
34 | |
|
35 | |
|
36 | |
|
37 | |
|
38 | |
|
39 | |
public abstract class AbstractTestMinCostFlowAlg extends TestCase { |
40 | |
|
41 | 9 | private MinCostFlowAlg minCostAlg = null; |
42 | |
|
43 | 9 | private ConstructableNumberedGraphProp constructG = null; |
44 | |
|
45 | 3 | private static int[][] edges = { |
46 | |
{0, 1}, |
47 | |
{0, 2}, |
48 | |
{2, 1}, |
49 | |
{1, 3}, |
50 | |
{2, 3} |
51 | |
}; |
52 | |
|
53 | 3 | private static final double[] inflow = {10, 0, 0, -10}; |
54 | 3 | private static final double[] edgeWeights = {0.0, 2.0, 5.0, 1.0, 10.0}; |
55 | 3 | private static final double[] edgeCapacities = |
56 | |
{2.0, 100.0, 200.0, 5.0, 50.0}; |
57 | 3 | private static final double[] expectedFlow = {2.0, 8.0, 3.0, 5.0, 5.0}; |
58 | |
private static final double flowCost = 2*0 + 8*2 + 3*5 + 5*1 + 5*10; |
59 | |
|
60 | 9 | private DoubleNodeMap inflowMap = null; |
61 | 9 | private DoubleEdgeMap capacityMap = null; |
62 | 9 | private DoubleEdgeMap weightMap = null; |
63 | |
|
64 | |
|
65 | |
|
66 | |
|
67 | |
protected void setUp() throws Exception { |
68 | 9 | super.setUp(); |
69 | |
|
70 | 9 | this.constructG = GraphFixtureFactory.createConstructableNumberedGraph(); |
71 | |
|
72 | 9 | ConstructableNumberedGraphBuilder builder = |
73 | |
new ConstructableNumberedGraphBuilder(this.constructG); |
74 | |
|
75 | 9 | builder.addNodes(inflow.length); |
76 | 9 | builder.addEdges(edges); |
77 | |
|
78 | 9 | this.inflowMap = new NodeMapAsDoubleNodeMap(); |
79 | 9 | builder.fillDoubleNodeMap(this.inflowMap, inflow); |
80 | |
|
81 | 9 | this.capacityMap = new EdgeMapAsDoubleEdgeMap(); |
82 | 9 | builder.fillDoubleEdgeMap(this.capacityMap, edgeCapacities); |
83 | 9 | this.weightMap = new EdgeMapAsDoubleEdgeMap(); |
84 | 9 | builder.fillDoubleEdgeMap(this.weightMap, edgeWeights); |
85 | |
|
86 | 9 | this.minCostAlg = createMinCostFlowAlg(); |
87 | |
|
88 | 9 | this.minCostAlg.setGraph(this.constructG); |
89 | 9 | } |
90 | |
|
91 | |
|
92 | |
|
93 | |
|
94 | |
protected void tearDown() throws Exception { |
95 | 9 | super.tearDown(); |
96 | 9 | } |
97 | |
|
98 | |
|
99 | |
|
100 | |
|
101 | |
|
102 | |
public AbstractTestMinCostFlowAlg(String name) { |
103 | 9 | super(name); |
104 | 9 | } |
105 | |
|
106 | |
protected abstract MinCostFlowAlg createMinCostFlowAlg(); |
107 | |
|
108 | |
public void testInfeasibleFlowDueToMissingCapacities() { |
109 | |
|
110 | 3 | this.capacityMap.putDouble(this.constructG.getEdge(4), 2.0); |
111 | |
|
112 | 3 | this.minCostAlg.setInflowMap(this.inflowMap); |
113 | 3 | this.minCostAlg.setEdgeCapacityMap(this.capacityMap); |
114 | 3 | this.minCostAlg.setEdgeWeightsMap(this.weightMap); |
115 | |
|
116 | 3 | this.minCostAlg.run(); |
117 | |
|
118 | 3 | assertFalse(this.minCostAlg.isFeasible()); |
119 | 3 | } |
120 | |
|
121 | |
public final void testInfeasibleFlowDueToUnbalancedInflow() { |
122 | 3 | this.inflowMap.putDouble(this.constructG.getNode(0), 5.0); |
123 | |
|
124 | 3 | this.minCostAlg.setInflowMap(this.inflowMap); |
125 | 3 | this.minCostAlg.setEdgeCapacityMap(this.capacityMap); |
126 | 3 | this.minCostAlg.setEdgeWeightsMap(this.weightMap); |
127 | |
|
128 | 3 | this.minCostAlg.run(); |
129 | |
|
130 | 3 | assertFalse(this.minCostAlg.isFeasible()); |
131 | 3 | } |
132 | |
|
133 | |
public final void testFeasibleFlow() { |
134 | 3 | this.minCostAlg.setInflowMap(this.inflowMap); |
135 | 3 | this.minCostAlg.setEdgeCapacityMap(this.capacityMap); |
136 | 3 | this.minCostAlg.setEdgeWeightsMap(this.weightMap); |
137 | |
|
138 | 3 | this.minCostAlg.run(); |
139 | |
|
140 | 3 | assertTrue(this.minCostAlg.isFeasible()); |
141 | 3 | assertEquals(flowCost, this.minCostAlg.getTotalCost(), 0.0); |
142 | 3 | CheckGraph.checkDoubleEdgeMap(this.constructG, |
143 | |
this.minCostAlg.getFlowMap(), |
144 | |
expectedFlow, 0.0 ); |
145 | 3 | } |
146 | |
} |