50 |
50 |
51 // typedef ConstMap<Edge,int> ConstMap; |
51 // typedef ConstMap<Edge,int> ConstMap; |
52 |
52 |
53 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType; |
53 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType; |
54 typedef typename ResGraphType::Edge ResGraphEdge; |
54 typedef typename ResGraphType::Edge ResGraphEdge; |
|
55 |
55 class ModLengthMap { |
56 class ModLengthMap { |
56 typedef typename ResGraphType::template NodeMap<Length> NodeMap; |
57 //typedef typename ResGraphType::template NodeMap<Length> NodeMap; |
|
58 typedef typename Graph::template NodeMap<Length> NodeMap; |
57 const ResGraphType& G; |
59 const ResGraphType& G; |
58 // const EdgeIntMap& rev; |
60 // const EdgeIntMap& rev; |
59 const LengthMap &ol; |
61 const LengthMap &ol; |
60 const NodeMap &pot; |
62 const NodeMap &pot; |
61 public : |
63 public : |
85 |
87 |
86 //The value is 1 iff the edge is reversed. |
88 //The value is 1 iff the edge is reversed. |
87 //If the algorithm has finished, the edges of the seeked paths are |
89 //If the algorithm has finished, the edges of the seeked paths are |
88 //exactly those that are reversed |
90 //exactly those that are reversed |
89 EdgeIntMap flow; |
91 EdgeIntMap flow; |
|
92 typename Graph::template NodeMap<Length> potential; |
90 |
93 |
91 //Container to store found paths |
94 //Container to store found paths |
92 std::vector< std::vector<Edge> > paths; |
95 std::vector< std::vector<Edge> > paths; |
93 //typedef DirPath<Graph> DPath; |
96 //typedef DirPath<Graph> DPath; |
94 //DPath paths; |
97 //DPath paths; |
98 |
101 |
99 public : |
102 public : |
100 |
103 |
101 |
104 |
102 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), |
105 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), |
103 length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ } |
106 length(_length), capacity(_cap), flow(_G), potential(_G){ } |
104 |
107 |
105 |
108 |
106 ///Runs the algorithm. |
109 ///Runs the algorithm. |
107 |
110 |
108 ///Runs the algorithm. |
111 ///Runs the algorithm. |
110 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
113 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
111 int run(Node s, Node t, int k) { |
114 int run(Node s, Node t, int k) { |
112 |
115 |
113 //Resetting variables from previous runs |
116 //Resetting variables from previous runs |
114 total_length = 0; |
117 total_length = 0; |
|
118 |
115 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ |
119 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ |
116 flow.set(e,0); |
120 flow.set(e,0); |
117 } |
121 } |
|
122 |
|
123 FOR_EACH_LOC(typename Graph::NodeIt, n, G){ |
|
124 //cout << potential[n]<<endl; |
|
125 potential.set(n,0); |
|
126 } |
|
127 |
118 |
128 |
119 |
129 |
120 //We need a residual graph |
130 //We need a residual graph |
121 ResGraphType res_graph(G, capacity, flow); |
131 ResGraphType res_graph(G, capacity, flow); |
122 |
132 |
123 //Initialize the copy of the Dijkstra potential to zero |
133 //Initialize the copy of the Dijkstra potential to zero |
124 typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph); |
134 |
125 ModLengthMap mod_length(res_graph, length, dijkstra_dist); |
135 //typename ResGraphType::template NodeMap<Length> potential(res_graph); |
|
136 |
|
137 |
|
138 ModLengthMap mod_length(res_graph, length, potential); |
126 |
139 |
127 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
140 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
128 |
141 |
129 int i; |
142 int i; |
130 for (i=0; i<k; ++i){ |
143 for (i=0; i<k; ++i){ |
136 |
149 |
137 { |
150 { |
138 //We have to copy the potential |
151 //We have to copy the potential |
139 typename ResGraphType::NodeIt n; |
152 typename ResGraphType::NodeIt n; |
140 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { |
153 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { |
141 dijkstra_dist[n] += dijkstra.distMap()[n]; |
154 potential[n] += dijkstra.distMap()[n]; |
142 } |
155 } |
143 } |
156 } |
144 |
157 |
145 |
158 |
146 //Augmenting on the sortest path |
159 //Augmenting on the sortest path |