equal
deleted
inserted
replaced
62 |
62 |
63 |
63 |
64 const Graph& G; |
64 const Graph& G; |
65 const LengthMap& length; |
65 const LengthMap& length; |
66 |
66 |
67 //auxiliary variable |
67 //auxiliry variable |
68 //The value is 1 iff the edge is reversed |
68 //The value is 1 iff the edge is reversed. |
|
69 //If the algorithm has finished, the edges of the seeked paths are |
|
70 //exactly those that are reversed |
69 EdgeIntMap reversed; |
71 EdgeIntMap reversed; |
70 |
|
71 |
72 |
72 public : |
73 public : |
73 |
74 |
74 |
75 |
75 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), |
76 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), |
81 ///Returns k if there are at least k edge-disjoint paths from s to t. |
82 ///Returns k if there are at least k edge-disjoint paths from s to t. |
82 ///Otherwise it returns the number of edge-disjoint paths from s to t. |
83 ///Otherwise it returns the number of edge-disjoint paths from s to t. |
83 int run(Node s, Node t, int k) { |
84 int run(Node s, Node t, int k) { |
84 ConstMap const1map(1); |
85 ConstMap const1map(1); |
85 |
86 |
|
87 //We need a residual graph, in which some of the edges are reversed |
86 ResGraphType res_graph(G, reversed, const1map); |
88 ResGraphType res_graph(G, reversed, const1map); |
87 |
89 |
88 //Initialize the copy of the Dijkstra potential to zero |
90 //Initialize the copy of the Dijkstra potential to zero |
89 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph); |
91 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph); |
90 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
92 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
92 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
94 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
93 |
95 |
94 for (int i=0; i<k; ++i){ |
96 for (int i=0; i<k; ++i){ |
95 dijkstra.run(s); |
97 dijkstra.run(s); |
96 if (!dijkstra.reached(t)){ |
98 if (!dijkstra.reached(t)){ |
97 //There is no k path from s to t |
99 //There are no k paths from s to t |
98 /// \TODO mit keresett itt ez a ++? |
|
99 return i; |
100 return i; |
100 }; |
101 }; |
101 |
102 |
102 { |
103 { |
103 //We have to copy the potential |
104 //We have to copy the potential |