66 typedef typename Graph::OutEdgeIt OutEdgeIt; |
66 typedef typename Graph::OutEdgeIt OutEdgeIt; |
67 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
67 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
68 |
68 |
69 typedef ConstMap<Edge,int> ConstMap; |
69 typedef ConstMap<Edge,int> ConstMap; |
70 |
70 |
71 //Input |
|
72 const Graph& G; |
71 const Graph& G; |
|
72 |
|
73 Node s; |
|
74 Node t; |
73 |
75 |
74 //Auxiliary variables |
76 //Auxiliary variables |
75 //This is the capacity map for the mincostflow problem |
77 //This is the capacity map for the mincostflow problem |
76 ConstMap const1map; |
78 ConstMap const1map; |
77 //This MinCostFlow instance will actually solve the problem |
79 //This MinCostFlow instance will actually solve the problem |
78 MinCostFlow<Graph, LengthMap, ConstMap> mincost_flow; |
80 MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow; |
79 |
81 |
80 //Container to store found paths |
82 //Container to store found paths |
81 std::vector< std::vector<Edge> > paths; |
83 std::vector< std::vector<Edge> > paths; |
82 |
84 |
83 public : |
85 public : |
84 |
86 |
85 |
87 |
86 /// The constructor of the class. |
88 /*! \brief The constructor of the class. |
87 |
89 |
88 ///\param _G The directed graph the algorithm runs on. |
90 \param _G The directed graph the algorithm runs on. |
89 ///\param _length The length (weight or cost) of the edges. |
91 \param _length The length (weight or cost) of the edges. |
90 Suurballe(Graph& _G, LengthMap& _length) : G(_G), |
92 \param _s Source node. |
91 const1map(1), mincost_flow(_G, _length, const1map){} |
93 \param _t Target node. |
|
94 */ |
|
95 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) : |
|
96 G(_G), s(_s), t(_t), const1map(1), |
|
97 min_cost_flow(_G, _length, const1map, _s, _t) { } |
92 |
98 |
93 ///Runs the algorithm. |
99 ///Runs the algorithm. |
94 |
100 |
95 ///Runs the algorithm. |
101 ///Runs the algorithm. |
96 ///Returns k if there are at least k edge-disjoint paths from s to t. |
102 ///Returns k if there are at least k edge-disjoint paths from s to t. |
97 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
103 ///Otherwise it returns the number of edge-disjoint paths found |
|
104 ///from s to t. |
98 /// |
105 /// |
99 ///\param s The source node. |
|
100 ///\param t The target node. |
|
101 ///\param k How many paths are we looking for? |
106 ///\param k How many paths are we looking for? |
102 /// |
107 /// |
103 int run(Node s, Node t, int k) { |
108 int run(int k) { |
104 |
109 int i = min_cost_flow.run(k); |
105 int i = mincost_flow.run(s,t,k); |
|
106 |
|
107 |
110 |
108 //Let's find the paths |
111 //Let's find the paths |
109 //We put the paths into stl vectors (as an inner representation). |
112 //We put the paths into stl vectors (as an inner representation). |
110 //In the meantime we lose the information stored in 'reversed'. |
113 //In the meantime we lose the information stored in 'reversed'. |
111 //We suppose the lengths to be positive now. |
114 //We suppose the lengths to be positive now. |
112 |
115 |
113 //We don't want to change the flow of mincost_flow, so we make a copy |
116 //We don't want to change the flow of min_cost_flow, so we make a copy |
114 //The name here suggests that the flow has only 0/1 values. |
117 //The name here suggests that the flow has only 0/1 values. |
115 EdgeIntMap reversed(G); |
118 EdgeIntMap reversed(G); |
116 |
119 |
117 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) |
120 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) |
118 reversed[e] = mincost_flow.getFlow()[e]; |
121 reversed[e] = min_cost_flow.getFlow()[e]; |
119 |
122 |
120 paths.clear(); |
123 paths.clear(); |
121 //total_length=0; |
124 //total_length=0; |
122 paths.resize(k); |
125 paths.resize(k); |
123 for (int j=0; j<i; ++j){ |
126 for (int j=0; j<i; ++j){ |
141 } |
144 } |
142 return i; |
145 return i; |
143 } |
146 } |
144 |
147 |
145 |
148 |
146 ///Returns the total length of the paths |
149 ///Returns the total length of the paths. |
147 |
150 |
148 ///This function gives back the total length of the found paths. |
151 ///This function gives back the total length of the found paths. |
149 ///\pre \ref run() must |
|
150 ///be called before using this function. |
|
151 Length totalLength(){ |
152 Length totalLength(){ |
152 return mincost_flow.totalLength(); |
153 return min_cost_flow.totalLength(); |
153 } |
154 } |
154 |
155 |
155 ///Returns the found flow. |
156 ///Returns the found flow. |
156 |
157 |
157 ///This function returns a const reference to the EdgeMap \c flow. |
158 ///This function returns a const reference to the EdgeMap \c flow. |
158 ///\pre \ref run() must |
159 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;} |
159 ///be called before using this function. |
|
160 const EdgeIntMap &getFlow() const { return mincost_flow.flow;} |
|
161 |
160 |
162 /// Returns the optimal dual solution |
161 /// Returns the optimal dual solution |
163 |
162 |
164 ///This function returns a const reference to the NodeMap |
163 ///This function returns a const reference to the NodeMap |
165 ///\c potential (the dual solution). |
164 ///\c potential (the dual solution). |
166 /// \pre \ref run() must be called before using this function. |
165 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;} |
167 const EdgeIntMap &getPotential() const { return mincost_flow.potential;} |
|
168 |
166 |
169 ///Checks whether the complementary slackness holds. |
167 ///Checks whether the complementary slackness holds. |
170 |
168 |
171 ///This function checks, whether the given solution is optimal. |
169 ///This function checks, whether the given solution is optimal. |
172 ///It should return true after calling \ref run() |
|
173 ///Currently this function only checks optimality, |
170 ///Currently this function only checks optimality, |
174 ///doesn't bother with feasibility |
171 ///doesn't bother with feasibility |
175 ///It is meant for testing purposes. |
172 ///It is meant for testing purposes. |
176 /// |
|
177 bool checkComplementarySlackness(){ |
173 bool checkComplementarySlackness(){ |
178 return mincost_flow.checkComplementarySlackness(); |
174 return min_cost_flow.checkComplementarySlackness(); |
179 } |
175 } |
180 |
176 |
181 ///Read the found paths. |
177 ///Read the found paths. |
182 |
178 |
183 ///This function gives back the \c j-th path in argument p. |
179 ///This function gives back the \c j-th path in argument p. |