Changeset 530:d9c06ac0b3a3 in lemon0.x
 Timestamp:
 05/04/04 18:52:15 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@696
 Location:
 src/work/athos
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/mincostflows.h
r527 r530 12 12 #include <maps.h> 13 13 #include <vector.h> 14 14 #include <for_each_macros.h> 15 15 16 16 namespace hugo { … … 35 35 /// 36 36 ///\author Attila Bernath 37 template <typename Graph, typename LengthMap >37 template <typename Graph, typename LengthMap, typename CapacityMap> 38 38 class MinCostFlows { 39 39 40 40 typedef typename LengthMap::ValueType Length; 41 41 42 typedef typename LengthMap::ValueType Length; 42 //Warning: this should be integer type 43 typedef typename CapacityMap::ValueType Capacity; 43 44 44 45 typedef typename Graph::Node Node; … … 50 51 // typedef ConstMap<Edge,int> ConstMap; 51 52 52 typedef ResGraphWrapper<const Graph,int, EdgeIntMap,EdgeIntMap> ResGraphType;53 53 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType; 54 typedef typename ResGraphType::Edge ResGraphEdge; 54 55 class ModLengthMap { 55 56 typedef typename ResGraphType::template NodeMap<Length> NodeMap; … … 69 70 } 70 71 71 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,72 ModLengthMap(const ResGraphType& _G, 72 73 const LengthMap &o, const NodeMap &p) : 73 74 G(_G), /*rev(_rev),*/ ol(o), pot(p){}; … … 79 80 const Graph& G; 80 81 const LengthMap& length; 81 const EdgeIntMap& capacity;82 const CapacityMap& capacity; 82 83 83 84 //auxiliary variables … … 99 100 100 101 101 Min LengthPaths(Graph& _G, LengthMap& _length, EdgeIntMap& _cap) : G(_G),102 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), 102 103 length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ } 103 104 … … 110 111 int run(Node s, Node t, int k) { 111 112 112 113 //Resetting variables from previous runs 114 total_length = 0; 115 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ 116 flow.set(e,0); 117 } 118 119 113 120 //We need a residual graph 114 121 ResGraphType res_graph(G, capacity, flow); … … 139 146 //Augmenting on the sortest path 140 147 Node n=t; 141 Edge e;148 ResGraphEdge e; 142 149 while (n!=s){ 143 150 e = dijkstra.pred(n); 144 151 n = dijkstra.predNode(n); 145 G.augment(e,1); 152 res_graph.augment(e,1); 153 //Let's update the total length 154 if (res_graph.forward(e)) 155 total_length += length[e]; 156 else 157 total_length = length[e]; 146 158 } 147 159 … … 149 161 } 150 162 151 /*152 ///\TODO To be implemented later153 154 //Let's find the paths155 //We put the paths into stl vectors (as an inner representation).156 //In the meantime we lose the information stored in 'reversed'.157 //We suppose the lengths to be positive now.158 159 //Meanwhile we put the total length of the found paths160 //in the member variable total_length161 paths.clear();162 total_length=0;163 paths.resize(k);164 for (int j=0; j<i; ++j){165 Node n=s;166 OutEdgeIt e;167 168 while (n!=t){169 170 171 G.first(e,n);172 173 while (!reversed[e]){174 G.next(e);175 }176 n = G.head(e);177 paths[j].push_back(e);178 total_length += length[e];179 reversed[e] = 1reversed[e];180 }181 182 }183 */184 163 185 164 return i; 186 165 } 166 167 187 168 188 169 ///This function gives back the total length of the found paths. … … 191 172 return total_length; 192 173 } 174 175 /* 176 ///\todo To be implemented later 193 177 194 178 ///This function gives back the \c jth path in argument p. … … 207 191 } 208 192 209 }; //class MinLengthPaths 193 */ 194 195 }; //class MinCostFlows 210 196 211 197 ///@} 
src/work/athos/mincostflows_test.cc
r527 r530 62 62 length.set(v5_t, 8); 63 63 64 ConstMap const1map(1);65 std::cout << "Min lengthpaths algorithm test..." << std::endl;64 ConstMap<Edge, int> const1map(1); 65 std::cout << "Mincostflows algorithm test..." << std::endl; 66 66 67 67 68 68 int k=3; 69 MinCostFlows< ListGraph, ListGraph::EdgeMap<int> >69 MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> > 70 70 surb_test(graph, length, const1map); 71 71 72 72 check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46"); 73 73 74 k=1; 75 check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19"); 76 77 //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl; 78 /* 74 79 typedef DirPath<ListGraph> DPath; 75 80 DPath P(graph); … … 86 91 surb_test.getPath(P,0); 87 92 check(P.length() == 4, "First path should contain 4 edges."); 88 93 */ 89 94 cout << (passed ? "All tests passed." : "Some of the tests failed!!!") 90 95 << endl;
Note: See TracChangeset
for help on using the changeset viewer.