Changeset 403:940587667b47 in lemon1.2
 Timestamp:
 12/01/08 14:23:59 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/circulation_test.cc
r400 r403 17 17 */ 18 18 19 ///\ingroup demos20 ///\file21 ///\brief Demonstrating the usage of LEMON's General Flow algorithm22 ///23 /// This demo program reads a general network circulation problem from the24 /// file 'circulationinput.lgf', runs the preflow based algorithm for25 /// finding a feasible solution and writes the output26 /// to 'circulationinput.lgf'27 ///28 /// \include circulation_demo.cc29 30 19 #include <iostream> 31 20 … … 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; … … 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 check(gen.checkBarrier(), "The found barrier is corrupt."); 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 }
Note: See TracChangeset
for help on using the changeset viewer.