Changeset 941:186aa53d2802 in lemon-0.x for src/lemon/suurballe.h
- Timestamp:
- 10/08/04 15:07:51 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1283
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/suurballe.h
r921 r941 69 69 typedef ConstMap<Edge,int> ConstMap; 70 70 71 //Input72 71 const Graph& G; 72 73 Node s; 74 Node t; 73 75 74 76 //Auxiliary variables … … 76 78 ConstMap const1map; 77 79 //This MinCostFlow instance will actually solve the problem 78 MinCostFlow<Graph, LengthMap, ConstMap> min cost_flow;80 MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow; 79 81 80 82 //Container to store found paths … … 84 86 85 87 86 /// The constructor of the class. 87 88 ///\param _G The directed graph the algorithm runs on. 89 ///\param _length The length (weight or cost) of the edges. 90 Suurballe(Graph& _G, LengthMap& _length) : G(_G), 91 const1map(1), mincost_flow(_G, _length, const1map){} 88 /*! \brief The constructor of the class. 89 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. 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 99 ///Runs the algorithm. … … 95 101 ///Runs the algorithm. 96 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 106 ///\param k How many paths are we looking for? 102 107 /// 103 int run(Node s, Node t, int k) { 104 105 int i = mincost_flow.run(s,t,k); 106 108 int run(int k) { 109 int i = min_cost_flow.run(k); 107 110 108 111 //Let's find the paths … … 111 114 //We suppose the lengths to be positive now. 112 115 113 //We don't want to change the flow of min cost_flow, so we make a copy116 //We don't want to change the flow of min_cost_flow, so we make a copy 114 117 //The name here suggests that the flow has only 0/1 values. 115 118 EdgeIntMap reversed(G); 116 119 117 120 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) 118 reversed[e] = min cost_flow.getFlow()[e];121 reversed[e] = min_cost_flow.getFlow()[e]; 119 122 120 123 paths.clear(); … … 144 147 145 148 146 ///Returns the total length of the paths 149 ///Returns the total length of the paths. 147 150 148 151 ///This function gives back the total length of the found paths. 149 ///\pre \ref run() must150 ///be called before using this function.151 152 Length totalLength(){ 152 return min cost_flow.totalLength();153 return min_cost_flow.totalLength(); 153 154 } 154 155 … … 156 157 157 158 ///This function returns a const reference to the EdgeMap \c flow. 158 ///\pre \ref run() must 159 ///be called before using this function. 160 const EdgeIntMap &getFlow() const { return mincost_flow.flow;} 159 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;} 161 160 162 161 /// Returns the optimal dual solution … … 164 163 ///This function returns a const reference to the NodeMap 165 164 ///\c potential (the dual solution). 166 /// \pre \ref run() must be called before using this function. 167 const EdgeIntMap &getPotential() const { return mincost_flow.potential;} 165 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;} 168 166 169 167 ///Checks whether the complementary slackness holds. 170 168 171 169 ///This function checks, whether the given solution is optimal. 172 ///It should return true after calling \ref run()173 170 ///Currently this function only checks optimality, 174 171 ///doesn't bother with feasibility 175 172 ///It is meant for testing purposes. 176 ///177 173 bool checkComplementarySlackness(){ 178 return min cost_flow.checkComplementarySlackness();174 return min_cost_flow.checkComplementarySlackness(); 179 175 } 180 176
Note: See TracChangeset
for help on using the changeset viewer.