Changeset 860:3577b3db6089 in lemon-0.x for src/hugo/minlengthpaths.h
- Timestamp:
- 09/16/04 12:26:14 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1160
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
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.