36 ///\author Attila Bernath |
36 ///\author Attila Bernath |
37 template <typename Graph, typename LengthMap> |
37 template <typename Graph, typename LengthMap> |
38 class MinCostFlows { |
38 class MinCostFlows { |
39 |
39 |
40 typedef typename LengthMap::ValueType Length; |
40 typedef typename LengthMap::ValueType Length; |
|
41 |
|
42 typedef typename LengthMap::ValueType Length; |
41 |
43 |
42 typedef typename Graph::Node Node; |
44 typedef typename Graph::Node Node; |
43 typedef typename Graph::NodeIt NodeIt; |
45 typedef typename Graph::NodeIt NodeIt; |
44 typedef typename Graph::Edge Edge; |
46 typedef typename Graph::Edge Edge; |
45 typedef typename Graph::OutEdgeIt OutEdgeIt; |
47 typedef typename Graph::OutEdgeIt OutEdgeIt; |
46 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
48 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
47 |
49 |
48 typedef ConstMap<Edge,int> ConstMap; |
50 // typedef ConstMap<Edge,int> ConstMap; |
49 |
51 |
50 typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType; |
52 typedef ResGraphWrapper<const Graph,int,EdgeIntMap,EdgeIntMap> ResGraphType; |
51 |
53 |
52 class ModLengthMap { |
54 class ModLengthMap { |
53 typedef typename ResGraphType::template NodeMap<Length> NodeMap; |
55 typedef typename ResGraphType::template NodeMap<Length> NodeMap; |
54 const ResGraphType& G; |
56 const ResGraphType& G; |
55 const EdgeIntMap& rev; |
57 // const EdgeIntMap& rev; |
56 const LengthMap &ol; |
58 const LengthMap &ol; |
57 const NodeMap &pot; |
59 const NodeMap &pot; |
58 public : |
60 public : |
59 typedef typename LengthMap::KeyType KeyType; |
61 typedef typename LengthMap::KeyType KeyType; |
60 typedef typename LengthMap::ValueType ValueType; |
62 typedef typename LengthMap::ValueType ValueType; |
61 |
63 |
62 ValueType operator[](typename ResGraphType::Edge e) const { |
64 ValueType operator[](typename ResGraphType::Edge e) const { |
63 //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){ |
65 if (G.forward(e)) |
64 // std::cout<<"Negative length!!"<<std::endl; |
66 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
65 //} |
67 else |
66 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
68 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
67 } |
69 } |
68 |
70 |
69 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
71 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
70 const LengthMap &o, const NodeMap &p) : |
72 const LengthMap &o, const NodeMap &p) : |
71 G(_G), rev(_rev), ol(o), pot(p){}; |
73 G(_G), /*rev(_rev),*/ ol(o), pot(p){}; |
72 };//ModLengthMap |
74 };//ModLengthMap |
73 |
75 |
74 |
76 |
75 |
77 |
76 |
78 //Input |
77 const Graph& G; |
79 const Graph& G; |
78 const LengthMap& length; |
80 const LengthMap& length; |
|
81 const EdgeIntMap& capacity; |
79 |
82 |
80 //auxiliary variables |
83 //auxiliary variables |
81 |
84 |
82 //The value is 1 iff the edge is reversed. |
85 //The value is 1 iff the edge is reversed. |
83 //If the algorithm has finished, the edges of the seeked paths are |
86 //If the algorithm has finished, the edges of the seeked paths are |
84 //exactly those that are reversed |
87 //exactly those that are reversed |
85 EdgeIntMap reversed; |
88 EdgeIntMap flow; |
86 |
89 |
87 //Container to store found paths |
90 //Container to store found paths |
88 std::vector< std::vector<Edge> > paths; |
91 std::vector< std::vector<Edge> > paths; |
89 //typedef DirPath<Graph> DPath; |
92 //typedef DirPath<Graph> DPath; |
90 //DPath paths; |
93 //DPath paths; |
93 Length total_length; |
96 Length total_length; |
94 |
97 |
95 public : |
98 public : |
96 |
99 |
97 |
100 |
98 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), |
101 MinLengthPaths(Graph& _G, LengthMap& _length, EdgeIntMap& _cap) : G(_G), |
99 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ } |
102 length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ } |
100 |
103 |
101 |
104 |
102 ///Runs the algorithm. |
105 ///Runs the algorithm. |
103 |
106 |
104 ///Runs the algorithm. |
107 ///Runs the algorithm. |
105 ///Returns k if there are at least k edge-disjoint paths from s to t. |
108 ///Returns k if there are at least k edge-disjoint paths from s to t. |
106 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
109 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
107 int run(Node s, Node t, int k) { |
110 int run(Node s, Node t, int k) { |
108 ConstMap const1map(1); |
111 |
109 |
112 |
110 |
113 //We need a residual graph |
111 //We need a residual graph, in which some of the edges are reversed |
114 ResGraphType res_graph(G, capacity, flow); |
112 ResGraphType res_graph(G, const1map, reversed); |
|
113 |
115 |
114 //Initialize the copy of the Dijkstra potential to zero |
116 //Initialize the copy of the Dijkstra potential to zero |
115 typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph); |
117 typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph); |
116 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
118 ModLengthMap mod_length(res_graph, length, dijkstra_dist); |
117 |
119 |
118 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
120 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
119 |
121 |
120 int i; |
122 int i; |
121 for (i=0; i<k; ++i){ |
123 for (i=0; i<k; ++i){ |
132 dijkstra_dist[n] += dijkstra.distMap()[n]; |
134 dijkstra_dist[n] += dijkstra.distMap()[n]; |
133 } |
135 } |
134 } |
136 } |
135 |
137 |
136 |
138 |
137 //Reversing the sortest path |
139 //Augmenting on the sortest path |
138 Node n=t; |
140 Node n=t; |
139 Edge e; |
141 Edge e; |
140 while (n!=s){ |
142 while (n!=s){ |
141 e = dijkstra.pred(n); |
143 e = dijkstra.pred(n); |
142 n = dijkstra.predNode(n); |
144 n = dijkstra.predNode(n); |
143 reversed[e] = 1-reversed[e]; |
145 G.augment(e,1); |
144 } |
146 } |
145 |
147 |
146 |
148 |
147 } |
149 } |
148 |
150 |
|
151 /* |
|
152 ///\TODO To be implemented later |
|
153 |
149 //Let's find the paths |
154 //Let's find the paths |
150 //We put the paths into stl vectors (as an inner representation). |
155 //We put the paths into stl vectors (as an inner representation). |
151 //In the meantime we lose the information stored in 'reversed'. |
156 //In the meantime we lose the information stored in 'reversed'. |
152 //We suppose the lengths to be positive now. |
157 //We suppose the lengths to be positive now. |
153 |
158 |