32 /// It is not a polinomial time algorithm for counting the minimum cost |
32 /// It is not a polinomial time algorithm for counting the minimum cost |
33 /// maximal flow, since it counts the minimum cost flow for every value 0..M |
33 /// maximal flow, since it counts the minimum cost flow for every value 0..M |
34 /// where \c M is the value of the maximal flow. |
34 /// where \c M is the value of the maximal flow. |
35 /// |
35 /// |
36 ///\author Attila Bernath |
36 ///\author Attila Bernath |
37 template <typename Graph, typename LengthMap> |
37 template <typename Graph, typename LengthMap, typename CapacityMap> |
38 class MinCostFlows { |
38 class MinCostFlows { |
39 |
39 |
40 typedef typename LengthMap::ValueType Length; |
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 typedef typename Graph::Node Node; |
45 typedef typename Graph::Node Node; |
45 typedef typename Graph::NodeIt NodeIt; |
46 typedef typename Graph::NodeIt NodeIt; |
46 typedef typename Graph::Edge Edge; |
47 typedef typename Graph::Edge Edge; |
47 typedef typename Graph::OutEdgeIt OutEdgeIt; |
48 typedef typename Graph::OutEdgeIt OutEdgeIt; |
48 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
49 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
49 |
50 |
50 // typedef ConstMap<Edge,int> ConstMap; |
51 // typedef ConstMap<Edge,int> ConstMap; |
51 |
52 |
52 typedef ResGraphWrapper<const Graph,int,EdgeIntMap,EdgeIntMap> ResGraphType; |
53 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType; |
53 |
54 typedef typename ResGraphType::Edge ResGraphEdge; |
54 class ModLengthMap { |
55 class ModLengthMap { |
55 typedef typename ResGraphType::template NodeMap<Length> NodeMap; |
56 typedef typename ResGraphType::template NodeMap<Length> NodeMap; |
56 const ResGraphType& G; |
57 const ResGraphType& G; |
57 // const EdgeIntMap& rev; |
58 // const EdgeIntMap& rev; |
58 const LengthMap &ol; |
59 const LengthMap &ol; |
66 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
67 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
67 else |
68 else |
68 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
69 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
69 } |
70 } |
70 |
71 |
71 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
72 ModLengthMap(const ResGraphType& _G, |
72 const LengthMap &o, const NodeMap &p) : |
73 const LengthMap &o, const NodeMap &p) : |
73 G(_G), /*rev(_rev),*/ ol(o), pot(p){}; |
74 G(_G), /*rev(_rev),*/ ol(o), pot(p){}; |
74 };//ModLengthMap |
75 };//ModLengthMap |
75 |
76 |
76 |
77 |
77 |
78 |
78 //Input |
79 //Input |
79 const Graph& G; |
80 const Graph& G; |
80 const LengthMap& length; |
81 const LengthMap& length; |
81 const EdgeIntMap& capacity; |
82 const CapacityMap& capacity; |
82 |
83 |
83 //auxiliary variables |
84 //auxiliary variables |
84 |
85 |
85 //The value is 1 iff the edge is reversed. |
86 //The value is 1 iff the edge is reversed. |
86 //If the algorithm has finished, the edges of the seeked paths are |
87 //If the algorithm has finished, the edges of the seeked paths are |
96 Length total_length; |
97 Length total_length; |
97 |
98 |
98 public : |
99 public : |
99 |
100 |
100 |
101 |
101 MinLengthPaths(Graph& _G, LengthMap& _length, EdgeIntMap& _cap) : G(_G), |
102 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), |
102 length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ } |
103 length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ } |
103 |
104 |
104 |
105 |
105 ///Runs the algorithm. |
106 ///Runs the algorithm. |
106 |
107 |
107 ///Runs the algorithm. |
108 ///Runs the algorithm. |
108 ///Returns k if there are at least k edge-disjoint paths from s to t. |
109 ///Returns k if there are at least k edge-disjoint paths from s to t. |
109 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
110 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
110 int run(Node s, Node t, int k) { |
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 //We need a residual graph |
120 //We need a residual graph |
114 ResGraphType res_graph(G, capacity, flow); |
121 ResGraphType res_graph(G, capacity, flow); |
115 |
122 |
116 //Initialize the copy of the Dijkstra potential to zero |
123 //Initialize the copy of the Dijkstra potential to zero |
117 typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph); |
124 typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph); |
136 } |
143 } |
137 |
144 |
138 |
145 |
139 //Augmenting on the sortest path |
146 //Augmenting on the sortest path |
140 Node n=t; |
147 Node n=t; |
141 Edge e; |
148 ResGraphEdge e; |
142 while (n!=s){ |
149 while (n!=s){ |
143 e = dijkstra.pred(n); |
150 e = dijkstra.pred(n); |
144 n = dijkstra.predNode(n); |
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 |
148 |
160 |
149 } |
161 } |
150 |
162 |
151 /* |
|
152 ///\TODO To be implemented later |
|
153 |
|
154 //Let's find the paths |
|
155 //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 paths |
|
160 //in the member variable total_length |
|
161 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] = 1-reversed[e]; |
|
180 } |
|
181 |
|
182 } |
|
183 */ |
|
184 |
163 |
185 return i; |
164 return i; |
186 } |
165 } |
|
166 |
|
167 |
187 |
168 |
188 ///This function gives back the total length of the found paths. |
169 ///This function gives back the total length of the found paths. |
189 ///Assumes that \c run() has been run and nothing changed since then. |
170 ///Assumes that \c run() has been run and nothing changed since then. |
190 Length totalLength(){ |
171 Length totalLength(){ |
191 return total_length; |
172 return total_length; |
192 } |
173 } |
|
174 |
|
175 /* |
|
176 ///\todo To be implemented later |
193 |
177 |
194 ///This function gives back the \c j-th path in argument p. |
178 ///This function gives back the \c j-th path in argument p. |
195 ///Assumes that \c run() has been run and nothing changed since then. |
179 ///Assumes that \c run() has been run and nothing changed since then. |
196 /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path. |
180 /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path. |
197 template<typename DirPath> |
181 template<typename DirPath> |