46 public : |
49 public : |
47 typedef typename LengthMap::KeyType KeyType; |
50 typedef typename LengthMap::KeyType KeyType; |
48 typedef typename LengthMap::ValueType ValueType; |
51 typedef typename LengthMap::ValueType ValueType; |
49 |
52 |
50 ValueType operator[](typename ResGraphType::Edge e) const { |
53 ValueType operator[](typename ResGraphType::Edge e) const { |
51 if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){ |
54 //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){ |
52 ///\TODO This has to be removed |
55 // std::cout<<"Negative length!!"<<std::endl; |
53 std::cout<<"Negative length!!"<<std::endl; |
56 //} |
54 } |
|
55 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
57 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
56 } |
58 } |
57 |
59 |
58 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
60 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
59 const LengthMap &o, const NodeMap &p) : |
61 const LengthMap &o, const NodeMap &p) : |
62 |
64 |
63 |
65 |
64 const Graph& G; |
66 const Graph& G; |
65 const LengthMap& length; |
67 const LengthMap& length; |
66 |
68 |
67 //auxiliry variable |
69 //auxiliry variables |
|
70 |
68 //The value is 1 iff the edge is reversed. |
71 //The value is 1 iff the edge is reversed. |
69 //If the algorithm has finished, the edges of the seeked paths are |
72 //If the algorithm has finished, the edges of the seeked paths are |
70 //exactly those that are reversed |
73 //exactly those that are reversed |
71 EdgeIntMap reversed; |
74 EdgeIntMap reversed; |
72 |
75 |
|
76 //Container to store found paths |
|
77 std::vector< std::vector<Edge> > paths; |
|
78 |
73 public : |
79 public : |
74 |
80 |
75 |
81 |
76 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), |
82 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), |
77 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ } |
83 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ } |
78 |
84 |
79 ///Runs the algorithm |
|
80 |
85 |
81 ///Runs the algorithm |
86 ///Runs the algorithm |
82 ///Returns k if there are at least k edge-disjoint paths from s to t. |
87 ///Returns k if there are at least k edge-disjoint paths from s to t. |
83 ///Otherwise it returns the number of edge-disjoint paths from s to t. |
88 ///Otherwise it returns the number of edge-disjoint paths from s to t. |
84 int run(Node s, Node t, int k) { |
89 int run(Node s, Node t, int k) { |
90 //Initialize the copy of the Dijkstra potential to zero |
95 //Initialize the copy of the Dijkstra potential to zero |
91 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph); |
96 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph); |
92 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
97 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
93 |
98 |
94 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
99 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
95 |
100 |
96 for (int i=0; i<k; ++i){ |
101 int i; |
|
102 for (i=0; i<k; ++i){ |
97 dijkstra.run(s); |
103 dijkstra.run(s); |
98 if (!dijkstra.reached(t)){ |
104 if (!dijkstra.reached(t)){ |
99 //There are no k paths from s to t |
105 //There are no k paths from s to t |
100 return i; |
106 break; |
101 }; |
107 }; |
102 |
108 |
103 { |
109 { |
104 //We have to copy the potential |
110 //We have to copy the potential |
105 typename ResGraphType::NodeIt n; |
111 typename ResGraphType::NodeIt n; |
118 reversed[e] = 1-reversed[e]; |
124 reversed[e] = 1-reversed[e]; |
119 } |
125 } |
120 |
126 |
121 |
127 |
122 } |
128 } |
123 return k; |
129 |
124 } |
130 //Let's find the paths |
|
131 //We put the paths into vectors (just for now). In the meantime we lose |
|
132 //the information stored in 'reversed' |
|
133 //We suppose the lengths to be positive now. |
|
134 paths.clear(); |
|
135 paths.resize(k); |
|
136 for (int j=0; j<i; ++j){ |
|
137 Node n=s; |
|
138 OutEdgeIt e; |
|
139 |
|
140 while (n!=t){ |
125 |
141 |
126 |
142 |
|
143 G.first(e,n); |
|
144 |
|
145 while (!reversed[e]){ |
|
146 G.next(e); |
|
147 } |
|
148 n = G.head(e); |
|
149 paths[j].push_back(e); |
|
150 reversed[e] = 1-reversed[e]; |
|
151 } |
|
152 |
|
153 } |
127 |
154 |
|
155 return i; |
|
156 } |
128 |
157 |
129 |
158 |
130 }; //class MinLengthPaths |
159 }; //class MinLengthPaths |
131 |
160 |
132 |
161 |