r418:940587667b47
Mon, 01 Dec 2008 14:23:59
[Not Reviewed]
0 comments (0 inline)
0
1
0
118
80
| ... | ... |
@@ -16,103 +16,141 @@ |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 |
///\ingroup demos |
|
| 20 |
///\file |
|
| 21 |
///\brief Demonstrating the usage of LEMON's General Flow algorithm |
|
| 22 |
/// |
|
| 23 |
/// This demo program reads a general network circulation problem from the |
|
| 24 |
/// file 'circulation-input.lgf', runs the preflow based algorithm for |
|
| 25 |
/// finding a feasible solution and writes the output |
|
| 26 |
/// to 'circulation-input.lgf' |
|
| 27 |
/// |
|
| 28 |
/// \include circulation_demo.cc |
|
| 29 |
|
|
| 30 | 19 |
#include <iostream> |
| 31 | 20 |
|
| 32 | 21 |
#include "test_tools.h" |
| 33 | 22 |
#include <lemon/list_graph.h> |
| 34 | 23 |
#include <lemon/circulation.h> |
| 35 | 24 |
#include <lemon/lgf_reader.h> |
| 25 |
#include <lemon/concepts/digraph.h> |
|
| 26 |
#include <lemon/concepts/maps.h> |
|
| 36 | 27 |
|
| 37 | 28 |
using namespace lemon; |
| 38 | 29 |
|
| 39 | 30 |
char test_lgf[] = |
| 40 | 31 |
"@nodes\n" |
| 41 |
"label delta\n" |
|
| 42 |
"0 0\n" |
|
| 43 |
"1 13\n" |
|
| 44 |
"2 0\n" |
|
| 45 |
"3 0\n" |
|
| 46 |
"4 0\n" |
|
| 47 |
"5 0\n" |
|
| 48 |
"6 0\n" |
|
| 49 |
"7 0\n" |
|
| 50 |
"8 -13\n" |
|
| 51 |
"9 0\n" |
|
| 52 |
"@edges\n" |
|
| 53 |
" label lo_cap up_cap\n" |
|
| 54 |
"0 1 0 0 20\n" |
|
| 55 |
"0 2 1 0 0\n" |
|
| 56 |
"1 1 2 0 3\n" |
|
| 57 |
"1 2 3 0 8\n" |
|
| 58 |
"1 3 4 0 8\n" |
|
| 59 |
"2 5 5 0 5\n" |
|
| 60 |
"3 2 6 0 5\n" |
|
| 61 |
"3 5 7 0 5\n" |
|
| 62 |
"3 6 8 0 5\n" |
|
| 63 |
"4 3 9 0 3\n" |
|
| 64 |
"5 7 10 0 3\n" |
|
| 65 |
"5 6 11 0 10\n" |
|
| 66 |
"5 8 12 0 10\n" |
|
| 67 |
"6 8 13 0 8\n" |
|
| 68 |
"8 9 14 0 20\n" |
|
| 69 |
"8 1 15 0 5\n" |
|
| 70 |
"9 5 16 0 5\n" |
|
| 32 |
"label\n" |
|
| 33 |
"0\n" |
|
| 34 |
"1\n" |
|
| 35 |
"2\n" |
|
| 36 |
"3\n" |
|
| 37 |
"4\n" |
|
| 38 |
"5\n" |
|
| 39 |
"@arcs\n" |
|
| 40 |
" lcap ucap\n" |
|
| 41 |
"0 1 2 10\n" |
|
| 42 |
"0 2 2 6\n" |
|
| 43 |
"1 3 4 7\n" |
|
| 44 |
"1 4 0 5\n" |
|
| 45 |
"2 4 1 3\n" |
|
| 46 |
"3 5 3 8\n" |
|
| 47 |
"4 5 3 7\n" |
|
| 71 | 48 |
"@attributes\n" |
| 72 |
"source 1\n" |
|
| 73 |
"sink 8\n"; |
|
| 49 |
"source 0\n" |
|
| 50 |
"sink 5\n"; |
|
| 51 |
|
|
| 52 |
void checkCirculationCompile() |
|
| 53 |
{
|
|
| 54 |
typedef int VType; |
|
| 55 |
typedef concepts::Digraph Digraph; |
|
| 56 |
|
|
| 57 |
typedef Digraph::Node Node; |
|
| 58 |
typedef Digraph::Arc Arc; |
|
| 59 |
typedef concepts::ReadMap<Arc,VType> CapMap; |
|
| 60 |
typedef concepts::ReadMap<Node,VType> DeltaMap; |
|
| 61 |
typedef concepts::ReadWriteMap<Arc,VType> FlowMap; |
|
| 62 |
typedef concepts::WriteMap<Node,bool> BarrierMap; |
|
| 63 |
|
|
| 64 |
typedef Elevator<Digraph, Digraph::Node> Elev; |
|
| 65 |
typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev; |
|
| 66 |
|
|
| 67 |
Digraph g; |
|
| 68 |
Node n; |
|
| 69 |
Arc a; |
|
| 70 |
CapMap lcap, ucap; |
|
| 71 |
DeltaMap delta; |
|
| 72 |
FlowMap flow; |
|
| 73 |
BarrierMap bar; |
|
| 74 |
|
|
| 75 |
Circulation<Digraph, CapMap, CapMap, DeltaMap> |
|
| 76 |
::SetFlowMap<FlowMap> |
|
| 77 |
::SetElevator<Elev> |
|
| 78 |
::SetStandardElevator<LinkedElev> |
|
| 79 |
::Create circ_test(g,lcap,ucap,delta); |
|
| 80 |
|
|
| 81 |
circ_test.lowerCapMap(lcap); |
|
| 82 |
circ_test.upperCapMap(ucap); |
|
| 83 |
circ_test.deltaMap(delta); |
|
| 84 |
flow = circ_test.flowMap(); |
|
| 85 |
circ_test.flowMap(flow); |
|
| 86 |
|
|
| 87 |
circ_test.init(); |
|
| 88 |
circ_test.greedyInit(); |
|
| 89 |
circ_test.start(); |
|
| 90 |
circ_test.run(); |
|
| 91 |
|
|
| 92 |
circ_test.barrier(n); |
|
| 93 |
circ_test.barrierMap(bar); |
|
| 94 |
circ_test.flow(a); |
|
| 95 |
} |
|
| 96 |
|
|
| 97 |
template <class G, class LM, class UM, class DM> |
|
| 98 |
void checkCirculation(const G& g, const LM& lm, const UM& um, |
|
| 99 |
const DM& dm, bool find) |
|
| 100 |
{
|
|
| 101 |
Circulation<G, LM, UM, DM> circ(g, lm, um, dm); |
|
| 102 |
bool ret = circ.run(); |
|
| 103 |
if (find) {
|
|
| 104 |
check(ret, "A feasible solution should have been found."); |
|
| 105 |
check(circ.checkFlow(), "The found flow is corrupt."); |
|
| 106 |
check(!circ.checkBarrier(), "A barrier should not have been found."); |
|
| 107 |
} else {
|
|
| 108 |
check(!ret, "A feasible solution should not have been found."); |
|
| 109 |
check(circ.checkBarrier(), "The found barrier is corrupt."); |
|
| 110 |
} |
|
| 111 |
} |
|
| 74 | 112 |
|
| 75 | 113 |
int main (int, char*[]) |
| 76 | 114 |
{
|
| 115 |
typedef ListDigraph Digraph; |
|
| 116 |
DIGRAPH_TYPEDEFS(Digraph); |
|
| 77 | 117 |
|
| 78 |
typedef ListDigraph Digraph; |
|
| 79 |
typedef Digraph::Node Node; |
|
| 80 |
typedef Digraph::NodeIt NodeIt; |
|
| 81 |
typedef Digraph::Arc Arc; |
|
| 82 |
typedef Digraph::ArcIt ArcIt; |
|
| 83 |
typedef Digraph::ArcMap<int> ArcMap; |
|
| 84 |
typedef Digraph::NodeMap<int> NodeMap; |
|
| 85 |
typedef Digraph::NodeMap<double> DNodeMap; |
|
| 118 |
Digraph g; |
|
| 119 |
IntArcMap lo(g), up(g); |
|
| 120 |
IntNodeMap delta(g, 0); |
|
| 121 |
Node s, t; |
|
| 86 | 122 |
|
| 87 |
Digraph g; |
|
| 88 |
ArcMap lo(g); |
|
| 89 |
ArcMap up(g); |
|
| 90 |
NodeMap delta(g); |
|
| 91 |
NodeMap nid(g); |
|
| 92 |
ArcMap eid(g); |
|
| 93 |
Node source, sink; |
|
| 94 |
|
|
| 95 |
std::istringstream input(test_lgf); |
|
| 96 |
DigraphReader<Digraph>(g,input). |
|
| 97 |
arcMap("lo_cap", lo).
|
|
| 98 |
arcMap("up_cap", up).
|
|
| 99 |
nodeMap("delta", delta).
|
|
| 100 |
arcMap("label", eid).
|
|
| 101 |
nodeMap("label", nid).
|
|
| 102 |
node("source",source).
|
|
| 103 |
node("sink",sink).
|
|
| 104 |
run(); |
|
| 123 |
std::istringstream input(test_lgf); |
|
| 124 |
DigraphReader<Digraph>(g,input). |
|
| 125 |
arcMap("lcap", lo).
|
|
| 126 |
arcMap("ucap", up).
|
|
| 127 |
node("source",s).
|
|
| 128 |
node("sink",t).
|
|
| 129 |
run(); |
|
| 105 | 130 |
|
| 106 |
Circulation<Digraph> gen(g,lo,up,delta); |
|
| 107 |
bool ret=gen.run(); |
|
| 108 |
check(ret,"A feasible solution should have been found."); |
|
| 109 |
check(gen.checkFlow(), "The found flow is corrupt."); |
|
| 110 |
|
|
| 111 |
delta[source]=14; |
|
| 112 |
delta[sink]=-14; |
|
| 113 |
|
|
| 114 |
bool ret2=gen.run(); |
|
| 115 |
check(!ret2,"A feasible solution should not have been found."); |
|
| 116 |
|
|
| 131 |
delta[s] = 7; delta[t] = -7; |
|
| 132 |
checkCirculation(g, lo, up, delta, true); |
|
| 117 | 133 |
|
| 134 |
delta[s] = 13; delta[t] = -13; |
|
| 135 |
checkCirculation(g, lo, up, delta, true); |
|
| 136 |
|
|
| 137 |
delta[s] = 6; delta[t] = -6; |
|
| 138 |
checkCirculation(g, lo, up, delta, false); |
|
| 139 |
|
|
| 140 |
delta[s] = 14; delta[t] = -14; |
|
| 141 |
checkCirculation(g, lo, up, delta, false); |
|
| 142 |
|
|
| 143 |
delta[s] = 7; delta[t] = -13; |
|
| 144 |
checkCirculation(g, lo, up, delta, true); |
|
| 145 |
|
|
| 146 |
delta[s] = 5; delta[t] = -15; |
|
| 147 |
checkCirculation(g, lo, up, delta, true); |
|
| 148 |
|
|
| 149 |
delta[s] = 10; delta[t] = -11; |
|
| 150 |
checkCirculation(g, lo, up, delta, true); |
|
| 151 |
|
|
| 152 |
delta[s] = 11; delta[t] = -10; |
|
| 153 |
checkCirculation(g, lo, up, delta, false); |
|
| 154 |
|
|
| 155 |
return 0; |
|
| 118 | 156 |
} |
0 comments (0 inline)