Changeset 860:3577b3db6089 in lemon-0.x for src
- Timestamp:
- 09/16/04 12:26:14 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1160
- Location:
- src/hugo
- Files:
-
- 2 edited
-
mincostflows.h (modified) (8 diffs)
-
minlengthpaths.h (modified) (9 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/mincostflows.h
r788 r860 24 24 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements 25 25 /// an algorithm for finding a flow of value \c k 26 /// (for small values of \c k)having minimal total cost26 /// having minimal total cost 27 27 /// from a given source node to a given target node in an 28 28 /// edge-weighted directed graph having nonnegative integer capacities. 29 /// The range of the length (weight) function is nonnegative reals but 30 /// the range of capacity function is the set of nonnegative integers. 31 /// It is not a polinomial time algorithm for counting the minimum cost 32 /// maximal flow, since it counts the minimum cost flow for every value 0..M 33 /// where \c M is the value of the maximal flow. 29 /// The range of the length (weight or cost) function can be nonnegative reals but 30 /// the range of the capacity function has to be the set of nonnegative integers. 31 /// This algorithm is intended to use only for for small values of \c k, since /// it is not a polinomial time algorithm for finding the minimum cost 32 /// maximal flow (in order to find the minimum cost flow of value \c k it 33 /// finds the minimum cost flow of value \c i for every 34 /// \c i between 0 and \c k). 35 /// 36 ///\param Graph The directed graph type the algorithm runs on. 37 ///\param LengthMap The type of the length map. 38 ///\param CapacityMap The capacity map type. 34 39 /// 35 40 ///\author Attila Bernath 36 41 template <typename Graph, typename LengthMap, typename CapacityMap> 37 42 class MinCostFlows { 43 44 38 45 39 46 typedef typename LengthMap::ValueType Length; … … 48 55 typedef typename Graph::template EdgeMap<int> EdgeIntMap; 49 56 50 // typedef ConstMap<Edge,int> ConstMap;51 57 52 58 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType; … … 54 60 55 61 class ModLengthMap { 56 //typedef typename ResGraphType::template NodeMap<Length> NodeMap;57 62 typedef typename Graph::template NodeMap<Length> NodeMap; 58 63 const ResGraphType& G; 59 // const EdgeIntMap& rev;60 64 const LengthMap &ol; 61 65 const NodeMap &pot; … … 99 103 public : 100 104 101 105 /// The constructor of the class. 106 107 ///\param _G The directed graph the algorithm runs on. 108 ///\param _length The length (weight or cost) of the edges. 109 ///\param _cap The capacity of the edges. 102 110 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), 103 111 length(_length), capacity(_cap), flow(_G), potential(_G){ } … … 105 113 106 114 ///Runs the algorithm. 107 115 108 116 ///Runs the algorithm. 109 ///Returns k if there are at least k edge-disjoint paths from s to t. 110 ///Otherwise it returns the number of found edge-disjoint paths from s to t. 117 ///Returns k if there is a flow of value at least k edge-disjoint 118 ///from s to t. 119 ///Otherwise it returns the maximum value of a flow from s to t. 120 /// 121 ///\param s The source node. 122 ///\param t The target node. 123 ///\param k The value of the flow we are looking for. 124 /// 111 125 ///\todo May be it does make sense to be able to start with a nonzero 112 126 /// feasible primal-dual solution pair as well. … … 134 148 dijkstra.run(s); 135 149 if (!dijkstra.reached(t)){ 136 //There are no k pathsfrom s to t150 //There are no flow of value k from s to t 137 151 break; 138 152 }; … … 166 180 167 181 168 169 ///This function gives back the total length of the found paths. 182 /// Gives back the total weight of the found flow. 183 184 ///This function gives back the total weight of the found flow. 170 185 ///Assumes that \c run() has been run and nothing changed since then. 171 186 Length totalLength(){ … … 173 188 } 174 189 175 ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must 190 ///Returns a const reference to the EdgeMap \c flow. 191 192 ///Returns a const reference to the EdgeMap \c flow. 193 ///\pre \ref run() must 176 194 ///be called before using this function. 177 195 const EdgeIntMap &getFlow() const { return flow;} 178 196 179 ///Returns a const reference to the NodeMap \c potential (the dual solution). 197 ///Returns a const reference to the NodeMap \c potential (the dual solution). 198 199 ///Returns a const reference to the NodeMap \c potential (the dual solution). 180 200 /// \pre \ref run() must be called before using this function. 181 201 const PotentialMap &getPotential() const { return potential;} 182 202 203 /// Checking the complementary slackness optimality criteria 204 183 205 ///This function checks, whether the given solution is optimal 184 ///Running after a \c run() should return with true 185 ///In this "state of the art" this only check optimality, doesn't bother with feasibility 206 ///If executed after the call of \c run() then it should return with true. 207 ///This function only checks optimality, doesn't bother with feasibility. 208 ///It is meant for testing purposes. 186 209 /// 187 ///\todo Is this OK here?188 210 bool checkComplementarySlackness(){ 189 211 Length mod_pot; -
src/hugo/minlengthpaths.h
r853 r860 8 8 9 9 10 //#include <hugo/dijkstra.h>11 //#include <hugo/graph_wrapper.h>12 10 #include <hugo/maps.h> 13 11 #include <vector> … … 19 17 /// @{ 20 18 21 ///\brief Implementation of an algorithm for finding k paths between 2 nodes19 ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes 22 20 /// of minimal total length 23 21 /// 24 /// The class \ref hugo::MinLengthPaths "MinLengthPaths"implements22 /// The class \ref hugo::MinLengthPaths implements 25 23 /// an algorithm for finding k edge-disjoint paths 26 24 /// from a given source node to a given target node in an 27 /// edge-weighted directed graph having minimal total weig th(length).25 /// edge-weighted directed graph having minimal total weight (length). 28 26 /// 29 ///\warning It is assumed that the lengths are positive, since the 30 /// general flow-decomposition is not implemented yet. 27 ///\warning Length values should be nonnegative. 28 /// 29 ///\param Graph The directed graph type the algorithm runs on. 30 ///\param LengthMap The type of the length map (values should be nonnegative). 31 31 /// 32 32 ///\author Attila Bernath … … 60 60 61 61 62 /// The constructor of the class. 63 64 ///\param _G The directed graph the algorithm runs on. 65 ///\param _length The length (weight or cost) of the edges. 62 66 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 63 67 const1map(1), mincost_flow(_G, _length, const1map){} … … 68 72 ///Returns k if there are at least k edge-disjoint paths from s to t. 69 73 ///Otherwise it returns the number of found edge-disjoint paths from s to t. 74 /// 75 ///\param s The source node. 76 ///\param t The target node. 77 ///\param k How many paths are we looking for? 78 /// 70 79 int run(Node s, Node t, int k) { 71 80 72 81 int i = mincost_flow.run(s,t,k); 73 74 82 75 83 76 84 //Let's find the paths … … 112 120 113 121 114 /// Total length of the paths122 ///Returns the total length of the paths 115 123 116 124 ///This function gives back the total length of the found paths. … … 121 129 } 122 130 123 ///Return the found flow.131 ///Returns the found flow. 124 132 125 133 ///This function returns a const reference to the EdgeMap \c flow. … … 128 136 const EdgeIntMap &getFlow() const { return mincost_flow.flow;} 129 137 130 /// Return the optimal dual solution138 /// Returns the optimal dual solution 131 139 132 140 ///This function returns a const reference to the NodeMap … … 137 145 ///Checks whether the complementary slackness holds. 138 146 139 ///This function checks, whether the given solution is optimal 140 /// Running after a \c run() should return with true147 ///This function checks, whether the given solution is optimal. 148 ///It should return true after calling \ref run() 141 149 ///Currently this function only checks optimality, 142 150 ///doesn't bother with feasibility 151 ///It is meant for testing purposes. 143 152 /// 144 ///\todo Is this OK here?145 153 bool checkComplementarySlackness(){ 146 154 return mincost_flow.checkComplementarySlackness(); … … 155 163 ///If \c j is not less than the result of previous \c run, 156 164 ///then the result here will be an empty path (\c j can be 0 as well). 165 /// 166 ///\param Path The type of the path structure to put the result to (must meet hugo path concept). 167 ///\param p The path to put the result to 168 ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively) 157 169 template<typename Path> 158 170 void getPath(Path& p, size_t j){ 159 171 160 172 p.clear(); 161 173 if (j>paths.size()-1){
Note: See TracChangeset
for help on using the changeset viewer.
