NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/suurballe.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_SUURBALLE_H
18 #define LEMON_SUURBALLE_H
22 ///\brief An algorithm for finding k paths of minimal total length.
25 #include <lemon/maps.h>
27 #include <lemon/min_cost_flow.h>
31 /// \addtogroup flowalgs
34 ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
35 /// of minimal total length
37 /// The class \ref lemon::Suurballe implements
38 /// an algorithm for finding k edge-disjoint paths
39 /// from a given source node to a given target node in an
40 /// edge-weighted directed graph having minimal total weight (length).
42 ///\warning Length values should be nonnegative!
44 ///\param Graph The directed graph type the algorithm runs on.
45 ///\param LengthMap The type of the length map (values should be nonnegative).
47 ///\note It it questionable whether it is correct to call this method after
48 ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm
49 ///for finding minimum cost flows. In fact, this implementation just
50 ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and
51 ///Edmonds-Karp published in 1972, therefore it is possibly right to
52 ///state that they are
53 ///independent results. Most frequently this special case is referred as
54 ///%Suurballe method in the literature, especially in communication
56 ///\author Attila Bernath
57 template <typename Graph, typename LengthMap>
61 typedef typename LengthMap::Value Length;
63 typedef typename Graph::Node Node;
64 typedef typename Graph::NodeIt NodeIt;
65 typedef typename Graph::Edge Edge;
66 typedef typename Graph::OutEdgeIt OutEdgeIt;
67 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
69 typedef ConstMap<Edge,int> ConstMap;
77 //This is the capacity map for the mincostflow problem
79 //This MinCostFlow instance will actually solve the problem
80 MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
82 //Container to store found paths
83 std::vector< std::vector<Edge> > paths;
88 /*! \brief The constructor of the class.
90 \param _G The directed graph the algorithm runs on.
91 \param _length The length (weight or cost) of the edges.
92 \param _s Source node.
93 \param _t Target node.
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) { }
99 ///Runs the algorithm.
101 ///Runs the algorithm.
102 ///Returns k if there are at least k edge-disjoint paths from s to t.
103 ///Otherwise it returns the number of edge-disjoint paths found
106 ///\param k How many paths are we looking for?
109 int i = min_cost_flow.run(k);
111 //Let's find the paths
112 //We put the paths into stl vectors (as an inner representation).
113 //In the meantime we lose the information stored in 'reversed'.
114 //We suppose the lengths to be positive now.
116 //We don't want to change the flow of min_cost_flow, so we make a copy
117 //The name here suggests that the flow has only 0/1 values.
118 EdgeIntMap reversed(G);
120 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
121 reversed[e] = min_cost_flow.getFlow()[e];
125 for (int j=0; j<i; ++j){
132 while (!reversed[e]){
136 paths[j].push_back(e);
137 reversed[e] = 1-reversed[e];
145 ///Returns the total length of the paths.
147 ///This function gives back the total length of the found paths.
148 Length totalLength(){
149 return min_cost_flow.totalLength();
152 ///Returns the found flow.
154 ///This function returns a const reference to the EdgeMap \c flow.
155 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
157 /// Returns the optimal dual solution
159 ///This function returns a const reference to the NodeMap
160 ///\c potential (the dual solution).
161 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
163 ///Checks whether the complementary slackness holds.
165 ///This function checks, whether the given solution is optimal.
166 ///Currently this function only checks optimality,
167 ///doesn't bother with feasibility.
168 ///It is meant for testing purposes.
169 bool checkComplementarySlackness(){
170 return min_cost_flow.checkComplementarySlackness();
173 ///Read the found paths.
175 ///This function gives back the \c j-th path in argument p.
176 ///Assumes that \c run() has been run and nothing has changed since then.
177 /// \warning It is assumed that \c p is constructed to
178 ///be a path of graph \c G.
179 ///If \c j is not less than the result of previous \c run,
180 ///then the result here will be an empty path (\c j can be 0 as well).
182 ///\param Path The type of the path structure to put the result to (must meet lemon path concept).
183 ///\param p The path to put the result to.
184 ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively).
185 template<typename Path>
186 void getPath(Path& p, size_t j){
189 if (j>paths.size()-1){
192 typename Path::Builder B(p);
193 for(typename std::vector<Edge>::iterator i=paths[j].begin();
194 i!=paths[j].end(); ++i ){
207 #endif //LEMON_SUURBALLE_H