1.1 --- a/src/hugo/Makefile.am Wed Sep 22 08:54:53 2004 +0000
1.2 +++ b/src/hugo/Makefile.am Wed Sep 22 09:55:41 2004 +0000
1.3 @@ -18,8 +18,8 @@
1.4 map_registry.h \
1.5 map_bits.h \
1.6 maps.h \
1.7 - min_cost_flows.h \
1.8 - min_length_paths.h \
1.9 + min_cost_flow.h \
1.10 + suurballe.h \
1.11 preflow.h \
1.12 path.h \
1.13 smart_graph.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/hugo/min_cost_flow.h Wed Sep 22 09:55:41 2004 +0000
2.3 @@ -0,0 +1,241 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_MINCOSTFLOWS_H
2.6 +#define HUGO_MINCOSTFLOWS_H
2.7 +
2.8 +///\ingroup flowalgs
2.9 +///\file
2.10 +///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost
2.11 +
2.12 +
2.13 +#include <hugo/dijkstra.h>
2.14 +#include <hugo/graph_wrapper.h>
2.15 +#include <hugo/maps.h>
2.16 +#include <vector>
2.17 +
2.18 +namespace hugo {
2.19 +
2.20 +/// \addtogroup flowalgs
2.21 +/// @{
2.22 +
2.23 + ///\brief Implementation of an algorithm for finding a flow of value \c k
2.24 + ///(for small values of \c k) having minimal total cost between 2 nodes
2.25 + ///
2.26 + ///
2.27 + /// The class \ref hugo::MinCostFlow "MinCostFlow" implements
2.28 + /// an algorithm for finding a flow of value \c k
2.29 + /// having minimal total cost
2.30 + /// from a given source node to a given target node in an
2.31 + /// edge-weighted directed graph. To this end,
2.32 + /// the edge-capacities and edge-weitghs have to be nonnegative.
2.33 + /// The edge-capacities should be integers, but the edge-weights can be
2.34 + /// integers, reals or of other comparable numeric type.
2.35 + /// This algorithm is intended to use only for small values of \c k,
2.36 + /// since it is only polynomial in k,
2.37 + /// not in the length of k (which is log k).
2.38 + /// In order to find the minimum cost flow of value \c k it
2.39 + /// finds the minimum cost flow of value \c i for every
2.40 + /// \c i between 0 and \c k.
2.41 + ///
2.42 + ///\param Graph The directed graph type the algorithm runs on.
2.43 + ///\param LengthMap The type of the length map.
2.44 + ///\param CapacityMap The capacity map type.
2.45 + ///
2.46 + ///\author Attila Bernath
2.47 + template <typename Graph, typename LengthMap, typename CapacityMap>
2.48 + class MinCostFlow {
2.49 +
2.50 + typedef typename LengthMap::ValueType Length;
2.51 +
2.52 + //Warning: this should be integer type
2.53 + typedef typename CapacityMap::ValueType Capacity;
2.54 +
2.55 + typedef typename Graph::Node Node;
2.56 + typedef typename Graph::NodeIt NodeIt;
2.57 + typedef typename Graph::Edge Edge;
2.58 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.59 + typedef typename Graph::template EdgeMap<int> EdgeIntMap;
2.60 +
2.61 +
2.62 + typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
2.63 + typedef typename ResGraphType::Edge ResGraphEdge;
2.64 +
2.65 + class ModLengthMap {
2.66 + typedef typename Graph::template NodeMap<Length> NodeMap;
2.67 + const ResGraphType& G;
2.68 + const LengthMap &ol;
2.69 + const NodeMap &pot;
2.70 + public :
2.71 + typedef typename LengthMap::KeyType KeyType;
2.72 + typedef typename LengthMap::ValueType ValueType;
2.73 +
2.74 + ValueType operator[](typename ResGraphType::Edge e) const {
2.75 + if (G.forward(e))
2.76 + return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
2.77 + else
2.78 + return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
2.79 + }
2.80 +
2.81 + ModLengthMap(const ResGraphType& _G,
2.82 + const LengthMap &o, const NodeMap &p) :
2.83 + G(_G), /*rev(_rev),*/ ol(o), pot(p){};
2.84 + };//ModLengthMap
2.85 +
2.86 +
2.87 + protected:
2.88 +
2.89 + //Input
2.90 + const Graph& G;
2.91 + const LengthMap& length;
2.92 + const CapacityMap& capacity;
2.93 +
2.94 +
2.95 + //auxiliary variables
2.96 +
2.97 + //To store the flow
2.98 + EdgeIntMap flow;
2.99 + //To store the potential (dual variables)
2.100 + typedef typename Graph::template NodeMap<Length> PotentialMap;
2.101 + PotentialMap potential;
2.102 +
2.103 +
2.104 + Length total_length;
2.105 +
2.106 +
2.107 + public :
2.108 +
2.109 + /// The constructor of the class.
2.110 +
2.111 + ///\param _G The directed graph the algorithm runs on.
2.112 + ///\param _length The length (weight or cost) of the edges.
2.113 + ///\param _cap The capacity of the edges.
2.114 + MinCostFlow(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
2.115 + length(_length), capacity(_cap), flow(_G), potential(_G){ }
2.116 +
2.117 +
2.118 + ///Runs the algorithm.
2.119 +
2.120 + ///Runs the algorithm.
2.121 + ///Returns k if there is a flow of value at least k edge-disjoint
2.122 + ///from s to t.
2.123 + ///Otherwise it returns the maximum value of a flow from s to t.
2.124 + ///
2.125 + ///\param s The source node.
2.126 + ///\param t The target node.
2.127 + ///\param k The value of the flow we are looking for.
2.128 + ///
2.129 + ///\todo May be it does make sense to be able to start with a nonzero
2.130 + /// feasible primal-dual solution pair as well.
2.131 + int run(Node s, Node t, int k) {
2.132 +
2.133 + //Resetting variables from previous runs
2.134 + total_length = 0;
2.135 +
2.136 + for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
2.137 +
2.138 + //Initialize the potential to zero
2.139 + for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
2.140 +
2.141 +
2.142 + //We need a residual graph
2.143 + ResGraphType res_graph(G, capacity, flow);
2.144 +
2.145 +
2.146 + ModLengthMap mod_length(res_graph, length, potential);
2.147 +
2.148 + Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
2.149 +
2.150 + int i;
2.151 + for (i=0; i<k; ++i){
2.152 + dijkstra.run(s);
2.153 + if (!dijkstra.reached(t)){
2.154 + //There are no flow of value k from s to t
2.155 + break;
2.156 + };
2.157 +
2.158 + //We have to change the potential
2.159 + for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n)
2.160 + potential[n] += dijkstra.distMap()[n];
2.161 +
2.162 +
2.163 + //Augmenting on the sortest path
2.164 + Node n=t;
2.165 + ResGraphEdge e;
2.166 + while (n!=s){
2.167 + e = dijkstra.pred(n);
2.168 + n = dijkstra.predNode(n);
2.169 + res_graph.augment(e,1);
2.170 + //Let's update the total length
2.171 + if (res_graph.forward(e))
2.172 + total_length += length[e];
2.173 + else
2.174 + total_length -= length[e];
2.175 + }
2.176 +
2.177 +
2.178 + }
2.179 +
2.180 +
2.181 + return i;
2.182 + }
2.183 +
2.184 +
2.185 +
2.186 + /// Gives back the total weight of the found flow.
2.187 +
2.188 + ///This function gives back the total weight of the found flow.
2.189 + ///Assumes that \c run() has been run and nothing changed since then.
2.190 + Length totalLength(){
2.191 + return total_length;
2.192 + }
2.193 +
2.194 + ///Returns a const reference to the EdgeMap \c flow.
2.195 +
2.196 + ///Returns a const reference to the EdgeMap \c flow.
2.197 + ///\pre \ref run() must
2.198 + ///be called before using this function.
2.199 + const EdgeIntMap &getFlow() const { return flow;}
2.200 +
2.201 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
2.202 +
2.203 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
2.204 + /// \pre \ref run() must be called before using this function.
2.205 + const PotentialMap &getPotential() const { return potential;}
2.206 +
2.207 + /// Checking the complementary slackness optimality criteria
2.208 +
2.209 + ///This function checks, whether the given solution is optimal
2.210 + ///If executed after the call of \c run() then it should return with true.
2.211 + ///This function only checks optimality, doesn't bother with feasibility.
2.212 + ///It is meant for testing purposes.
2.213 + ///
2.214 + bool checkComplementarySlackness(){
2.215 + Length mod_pot;
2.216 + Length fl_e;
2.217 + for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
2.218 + //C^{\Pi}_{i,j}
2.219 + mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
2.220 + fl_e = flow[e];
2.221 + if (0<fl_e && fl_e<capacity[e]) {
2.222 + /// \todo better comparison is needed for real types, moreover,
2.223 + /// this comparison here is superfluous.
2.224 + if (mod_pot != 0)
2.225 + return false;
2.226 + }
2.227 + else {
2.228 + if (mod_pot > 0 && fl_e != 0)
2.229 + return false;
2.230 + if (mod_pot < 0 && fl_e != capacity[e])
2.231 + return false;
2.232 + }
2.233 + }
2.234 + return true;
2.235 + }
2.236 +
2.237 +
2.238 + }; //class MinCostFlow
2.239 +
2.240 + ///@}
2.241 +
2.242 +} //namespace hugo
2.243 +
2.244 +#endif //HUGO_MINCOSTFLOWS_H
3.1 --- a/src/hugo/min_cost_flows.h Wed Sep 22 08:54:53 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,241 +0,0 @@
3.4 -// -*- c++ -*-
3.5 -#ifndef HUGO_MINCOSTFLOWS_H
3.6 -#define HUGO_MINCOSTFLOWS_H
3.7 -
3.8 -///\ingroup flowalgs
3.9 -///\file
3.10 -///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost
3.11 -
3.12 -
3.13 -#include <hugo/dijkstra.h>
3.14 -#include <hugo/graph_wrapper.h>
3.15 -#include <hugo/maps.h>
3.16 -#include <vector>
3.17 -
3.18 -namespace hugo {
3.19 -
3.20 -/// \addtogroup flowalgs
3.21 -/// @{
3.22 -
3.23 - ///\brief Implementation of an algorithm for finding a flow of value \c k
3.24 - ///(for small values of \c k) having minimal total cost between 2 nodes
3.25 - ///
3.26 - ///
3.27 - /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
3.28 - /// an algorithm for finding a flow of value \c k
3.29 - /// having minimal total cost
3.30 - /// from a given source node to a given target node in an
3.31 - /// edge-weighted directed graph. To this end,
3.32 - /// the edge-capacities and edge-weitghs have to be nonnegative.
3.33 - /// The edge-capacities should be integers, but the edge-weights can be
3.34 - /// integers, reals or of other comparable numeric type.
3.35 - /// This algorithm is intended to use only for small values of \c k,
3.36 - /// since it is only polynomial in k,
3.37 - /// not in the length of k (which is log k).
3.38 - /// In order to find the minimum cost flow of value \c k it
3.39 - /// finds the minimum cost flow of value \c i for every
3.40 - /// \c i between 0 and \c k.
3.41 - ///
3.42 - ///\param Graph The directed graph type the algorithm runs on.
3.43 - ///\param LengthMap The type of the length map.
3.44 - ///\param CapacityMap The capacity map type.
3.45 - ///
3.46 - ///\author Attila Bernath
3.47 - template <typename Graph, typename LengthMap, typename CapacityMap>
3.48 - class MinCostFlows {
3.49 -
3.50 - typedef typename LengthMap::ValueType Length;
3.51 -
3.52 - //Warning: this should be integer type
3.53 - typedef typename CapacityMap::ValueType Capacity;
3.54 -
3.55 - typedef typename Graph::Node Node;
3.56 - typedef typename Graph::NodeIt NodeIt;
3.57 - typedef typename Graph::Edge Edge;
3.58 - typedef typename Graph::OutEdgeIt OutEdgeIt;
3.59 - typedef typename Graph::template EdgeMap<int> EdgeIntMap;
3.60 -
3.61 -
3.62 - typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
3.63 - typedef typename ResGraphType::Edge ResGraphEdge;
3.64 -
3.65 - class ModLengthMap {
3.66 - typedef typename Graph::template NodeMap<Length> NodeMap;
3.67 - const ResGraphType& G;
3.68 - const LengthMap &ol;
3.69 - const NodeMap &pot;
3.70 - public :
3.71 - typedef typename LengthMap::KeyType KeyType;
3.72 - typedef typename LengthMap::ValueType ValueType;
3.73 -
3.74 - ValueType operator[](typename ResGraphType::Edge e) const {
3.75 - if (G.forward(e))
3.76 - return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
3.77 - else
3.78 - return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
3.79 - }
3.80 -
3.81 - ModLengthMap(const ResGraphType& _G,
3.82 - const LengthMap &o, const NodeMap &p) :
3.83 - G(_G), /*rev(_rev),*/ ol(o), pot(p){};
3.84 - };//ModLengthMap
3.85 -
3.86 -
3.87 - protected:
3.88 -
3.89 - //Input
3.90 - const Graph& G;
3.91 - const LengthMap& length;
3.92 - const CapacityMap& capacity;
3.93 -
3.94 -
3.95 - //auxiliary variables
3.96 -
3.97 - //To store the flow
3.98 - EdgeIntMap flow;
3.99 - //To store the potential (dual variables)
3.100 - typedef typename Graph::template NodeMap<Length> PotentialMap;
3.101 - PotentialMap potential;
3.102 -
3.103 -
3.104 - Length total_length;
3.105 -
3.106 -
3.107 - public :
3.108 -
3.109 - /// The constructor of the class.
3.110 -
3.111 - ///\param _G The directed graph the algorithm runs on.
3.112 - ///\param _length The length (weight or cost) of the edges.
3.113 - ///\param _cap The capacity of the edges.
3.114 - MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
3.115 - length(_length), capacity(_cap), flow(_G), potential(_G){ }
3.116 -
3.117 -
3.118 - ///Runs the algorithm.
3.119 -
3.120 - ///Runs the algorithm.
3.121 - ///Returns k if there is a flow of value at least k edge-disjoint
3.122 - ///from s to t.
3.123 - ///Otherwise it returns the maximum value of a flow from s to t.
3.124 - ///
3.125 - ///\param s The source node.
3.126 - ///\param t The target node.
3.127 - ///\param k The value of the flow we are looking for.
3.128 - ///
3.129 - ///\todo May be it does make sense to be able to start with a nonzero
3.130 - /// feasible primal-dual solution pair as well.
3.131 - int run(Node s, Node t, int k) {
3.132 -
3.133 - //Resetting variables from previous runs
3.134 - total_length = 0;
3.135 -
3.136 - for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
3.137 -
3.138 - //Initialize the potential to zero
3.139 - for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
3.140 -
3.141 -
3.142 - //We need a residual graph
3.143 - ResGraphType res_graph(G, capacity, flow);
3.144 -
3.145 -
3.146 - ModLengthMap mod_length(res_graph, length, potential);
3.147 -
3.148 - Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
3.149 -
3.150 - int i;
3.151 - for (i=0; i<k; ++i){
3.152 - dijkstra.run(s);
3.153 - if (!dijkstra.reached(t)){
3.154 - //There are no flow of value k from s to t
3.155 - break;
3.156 - };
3.157 -
3.158 - //We have to change the potential
3.159 - for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n)
3.160 - potential[n] += dijkstra.distMap()[n];
3.161 -
3.162 -
3.163 - //Augmenting on the sortest path
3.164 - Node n=t;
3.165 - ResGraphEdge e;
3.166 - while (n!=s){
3.167 - e = dijkstra.pred(n);
3.168 - n = dijkstra.predNode(n);
3.169 - res_graph.augment(e,1);
3.170 - //Let's update the total length
3.171 - if (res_graph.forward(e))
3.172 - total_length += length[e];
3.173 - else
3.174 - total_length -= length[e];
3.175 - }
3.176 -
3.177 -
3.178 - }
3.179 -
3.180 -
3.181 - return i;
3.182 - }
3.183 -
3.184 -
3.185 -
3.186 - /// Gives back the total weight of the found flow.
3.187 -
3.188 - ///This function gives back the total weight of the found flow.
3.189 - ///Assumes that \c run() has been run and nothing changed since then.
3.190 - Length totalLength(){
3.191 - return total_length;
3.192 - }
3.193 -
3.194 - ///Returns a const reference to the EdgeMap \c flow.
3.195 -
3.196 - ///Returns a const reference to the EdgeMap \c flow.
3.197 - ///\pre \ref run() must
3.198 - ///be called before using this function.
3.199 - const EdgeIntMap &getFlow() const { return flow;}
3.200 -
3.201 - ///Returns a const reference to the NodeMap \c potential (the dual solution).
3.202 -
3.203 - ///Returns a const reference to the NodeMap \c potential (the dual solution).
3.204 - /// \pre \ref run() must be called before using this function.
3.205 - const PotentialMap &getPotential() const { return potential;}
3.206 -
3.207 - /// Checking the complementary slackness optimality criteria
3.208 -
3.209 - ///This function checks, whether the given solution is optimal
3.210 - ///If executed after the call of \c run() then it should return with true.
3.211 - ///This function only checks optimality, doesn't bother with feasibility.
3.212 - ///It is meant for testing purposes.
3.213 - ///
3.214 - bool checkComplementarySlackness(){
3.215 - Length mod_pot;
3.216 - Length fl_e;
3.217 - for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
3.218 - //C^{\Pi}_{i,j}
3.219 - mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
3.220 - fl_e = flow[e];
3.221 - if (0<fl_e && fl_e<capacity[e]) {
3.222 - /// \todo better comparison is needed for real types, moreover,
3.223 - /// this comparison here is superfluous.
3.224 - if (mod_pot != 0)
3.225 - return false;
3.226 - }
3.227 - else {
3.228 - if (mod_pot > 0 && fl_e != 0)
3.229 - return false;
3.230 - if (mod_pot < 0 && fl_e != capacity[e])
3.231 - return false;
3.232 - }
3.233 - }
3.234 - return true;
3.235 - }
3.236 -
3.237 -
3.238 - }; //class MinCostFlows
3.239 -
3.240 - ///@}
3.241 -
3.242 -} //namespace hugo
3.243 -
3.244 -#endif //HUGO_MINCOSTFLOWS_H
4.1 --- a/src/hugo/min_length_paths.h Wed Sep 22 08:54:53 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,191 +0,0 @@
4.4 -// -*- c++ -*-
4.5 -#ifndef HUGO_MINLENGTHPATHS_H
4.6 -#define HUGO_MINLENGTHPATHS_H
4.7 -
4.8 -///\ingroup flowalgs
4.9 -///\file
4.10 -///\brief An algorithm for finding k paths of minimal total length.
4.11 -
4.12 -
4.13 -#include <hugo/maps.h>
4.14 -#include <vector>
4.15 -#include <hugo/min_cost_flows.h>
4.16 -
4.17 -namespace hugo {
4.18 -
4.19 -/// \addtogroup flowalgs
4.20 -/// @{
4.21 -
4.22 - ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
4.23 - /// of minimal total length
4.24 - ///
4.25 - /// The class \ref hugo::MinLengthPaths implements
4.26 - /// an algorithm for finding k edge-disjoint paths
4.27 - /// from a given source node to a given target node in an
4.28 - /// edge-weighted directed graph having minimal total weight (length).
4.29 - ///
4.30 - ///\warning Length values should be nonnegative.
4.31 - ///
4.32 - ///\param Graph The directed graph type the algorithm runs on.
4.33 - ///\param LengthMap The type of the length map (values should be nonnegative).
4.34 - ///
4.35 - ///\author Attila Bernath
4.36 - template <typename Graph, typename LengthMap>
4.37 - class MinLengthPaths{
4.38 -
4.39 -
4.40 - typedef typename LengthMap::ValueType Length;
4.41 -
4.42 - typedef typename Graph::Node Node;
4.43 - typedef typename Graph::NodeIt NodeIt;
4.44 - typedef typename Graph::Edge Edge;
4.45 - typedef typename Graph::OutEdgeIt OutEdgeIt;
4.46 - typedef typename Graph::template EdgeMap<int> EdgeIntMap;
4.47 -
4.48 - typedef ConstMap<Edge,int> ConstMap;
4.49 -
4.50 - //Input
4.51 - const Graph& G;
4.52 -
4.53 - //Auxiliary variables
4.54 - //This is the capacity map for the mincostflow problem
4.55 - ConstMap const1map;
4.56 - //This MinCostFlows instance will actually solve the problem
4.57 - MinCostFlows<Graph, LengthMap, ConstMap> mincost_flow;
4.58 -
4.59 - //Container to store found paths
4.60 - std::vector< std::vector<Edge> > paths;
4.61 -
4.62 - public :
4.63 -
4.64 -
4.65 - /// The constructor of the class.
4.66 -
4.67 - ///\param _G The directed graph the algorithm runs on.
4.68 - ///\param _length The length (weight or cost) of the edges.
4.69 - MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
4.70 - const1map(1), mincost_flow(_G, _length, const1map){}
4.71 -
4.72 - ///Runs the algorithm.
4.73 -
4.74 - ///Runs the algorithm.
4.75 - ///Returns k if there are at least k edge-disjoint paths from s to t.
4.76 - ///Otherwise it returns the number of found edge-disjoint paths from s to t.
4.77 - ///
4.78 - ///\param s The source node.
4.79 - ///\param t The target node.
4.80 - ///\param k How many paths are we looking for?
4.81 - ///
4.82 - int run(Node s, Node t, int k) {
4.83 -
4.84 - int i = mincost_flow.run(s,t,k);
4.85 -
4.86 -
4.87 - //Let's find the paths
4.88 - //We put the paths into stl vectors (as an inner representation).
4.89 - //In the meantime we lose the information stored in 'reversed'.
4.90 - //We suppose the lengths to be positive now.
4.91 -
4.92 - //We don't want to change the flow of mincost_flow, so we make a copy
4.93 - //The name here suggests that the flow has only 0/1 values.
4.94 - EdgeIntMap reversed(G);
4.95 -
4.96 - for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
4.97 - reversed[e] = mincost_flow.getFlow()[e];
4.98 -
4.99 - paths.clear();
4.100 - //total_length=0;
4.101 - paths.resize(k);
4.102 - for (int j=0; j<i; ++j){
4.103 - Node n=s;
4.104 - OutEdgeIt e;
4.105 -
4.106 - while (n!=t){
4.107 -
4.108 -
4.109 - G.first(e,n);
4.110 -
4.111 - while (!reversed[e]){
4.112 - ++e;
4.113 - }
4.114 - n = G.head(e);
4.115 - paths[j].push_back(e);
4.116 - //total_length += length[e];
4.117 - reversed[e] = 1-reversed[e];
4.118 - }
4.119 -
4.120 - }
4.121 - return i;
4.122 - }
4.123 -
4.124 -
4.125 - ///Returns the total length of the paths
4.126 -
4.127 - ///This function gives back the total length of the found paths.
4.128 - ///\pre \ref run() must
4.129 - ///be called before using this function.
4.130 - Length totalLength(){
4.131 - return mincost_flow.totalLength();
4.132 - }
4.133 -
4.134 - ///Returns the found flow.
4.135 -
4.136 - ///This function returns a const reference to the EdgeMap \c flow.
4.137 - ///\pre \ref run() must
4.138 - ///be called before using this function.
4.139 - const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
4.140 -
4.141 - /// Returns the optimal dual solution
4.142 -
4.143 - ///This function returns a const reference to the NodeMap
4.144 - ///\c potential (the dual solution).
4.145 - /// \pre \ref run() must be called before using this function.
4.146 - const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
4.147 -
4.148 - ///Checks whether the complementary slackness holds.
4.149 -
4.150 - ///This function checks, whether the given solution is optimal.
4.151 - ///It should return true after calling \ref run()
4.152 - ///Currently this function only checks optimality,
4.153 - ///doesn't bother with feasibility
4.154 - ///It is meant for testing purposes.
4.155 - ///
4.156 - bool checkComplementarySlackness(){
4.157 - return mincost_flow.checkComplementarySlackness();
4.158 - }
4.159 -
4.160 - ///Read the found paths.
4.161 -
4.162 - ///This function gives back the \c j-th path in argument p.
4.163 - ///Assumes that \c run() has been run and nothing changed since then.
4.164 - /// \warning It is assumed that \c p is constructed to
4.165 - ///be a path of graph \c G.
4.166 - ///If \c j is not less than the result of previous \c run,
4.167 - ///then the result here will be an empty path (\c j can be 0 as well).
4.168 - ///
4.169 - ///\param Path The type of the path structure to put the result to (must meet hugo path concept).
4.170 - ///\param p The path to put the result to
4.171 - ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
4.172 - template<typename Path>
4.173 - void getPath(Path& p, size_t j){
4.174 -
4.175 - p.clear();
4.176 - if (j>paths.size()-1){
4.177 - return;
4.178 - }
4.179 - typename Path::Builder B(p);
4.180 - for(typename std::vector<Edge>::iterator i=paths[j].begin();
4.181 - i!=paths[j].end(); ++i ){
4.182 - B.pushBack(*i);
4.183 - }
4.184 -
4.185 - B.commit();
4.186 - }
4.187 -
4.188 - }; //class MinLengthPaths
4.189 -
4.190 - ///@}
4.191 -
4.192 -} //namespace hugo
4.193 -
4.194 -#endif //HUGO_MINLENGTHPATHS_H
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/hugo/suurballe.h Wed Sep 22 09:55:41 2004 +0000
5.3 @@ -0,0 +1,200 @@
5.4 +// -*- c++ -*-
5.5 +#ifndef HUGO_MINLENGTHPATHS_H
5.6 +#define HUGO_MINLENGTHPATHS_H
5.7 +
5.8 +///\ingroup flowalgs
5.9 +///\file
5.10 +///\brief An algorithm for finding k paths of minimal total length.
5.11 +
5.12 +
5.13 +#include <hugo/maps.h>
5.14 +#include <vector>
5.15 +#include <hugo/min_cost_flow.h>
5.16 +
5.17 +namespace hugo {
5.18 +
5.19 +/// \addtogroup flowalgs
5.20 +/// @{
5.21 +
5.22 + ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
5.23 + /// of minimal total length
5.24 + ///
5.25 + /// The class \ref hugo::Suurballe implements
5.26 + /// an algorithm for finding k edge-disjoint paths
5.27 + /// from a given source node to a given target node in an
5.28 + /// edge-weighted directed graph having minimal total weight (length).
5.29 + ///
5.30 + ///\warning Length values should be nonnegative.
5.31 + ///
5.32 + ///\param Graph The directed graph type the algorithm runs on.
5.33 + ///\param LengthMap The type of the length map (values should be nonnegative).
5.34 + ///
5.35 + ///\note It it questionable if it is correct to call this method after
5.36 + ///%Suurballe for it is just a special case of Edmond's and Karp's algorithm
5.37 + ///for finding minimum cost flows. In fact, this implementation is just
5.38 + ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and
5.39 + ///Edmonds-Karp published in 1972, therefore it is possibly right to
5.40 + ///state that they are
5.41 + ///independent results. Most frequently this special case is referred as
5.42 + ///%Suurballe method in the literature, especially in communication
5.43 + ///network context.
5.44 + ///\author Attila Bernath
5.45 + template <typename Graph, typename LengthMap>
5.46 + class Suurballe{
5.47 +
5.48 +
5.49 + typedef typename LengthMap::ValueType Length;
5.50 +
5.51 + typedef typename Graph::Node Node;
5.52 + typedef typename Graph::NodeIt NodeIt;
5.53 + typedef typename Graph::Edge Edge;
5.54 + typedef typename Graph::OutEdgeIt OutEdgeIt;
5.55 + typedef typename Graph::template EdgeMap<int> EdgeIntMap;
5.56 +
5.57 + typedef ConstMap<Edge,int> ConstMap;
5.58 +
5.59 + //Input
5.60 + const Graph& G;
5.61 +
5.62 + //Auxiliary variables
5.63 + //This is the capacity map for the mincostflow problem
5.64 + ConstMap const1map;
5.65 + //This MinCostFlow instance will actually solve the problem
5.66 + MinCostFlow<Graph, LengthMap, ConstMap> mincost_flow;
5.67 +
5.68 + //Container to store found paths
5.69 + std::vector< std::vector<Edge> > paths;
5.70 +
5.71 + public :
5.72 +
5.73 +
5.74 + /// The constructor of the class.
5.75 +
5.76 + ///\param _G The directed graph the algorithm runs on.
5.77 + ///\param _length The length (weight or cost) of the edges.
5.78 + Suurballe(Graph& _G, LengthMap& _length) : G(_G),
5.79 + const1map(1), mincost_flow(_G, _length, const1map){}
5.80 +
5.81 + ///Runs the algorithm.
5.82 +
5.83 + ///Runs the algorithm.
5.84 + ///Returns k if there are at least k edge-disjoint paths from s to t.
5.85 + ///Otherwise it returns the number of found edge-disjoint paths from s to t.
5.86 + ///
5.87 + ///\param s The source node.
5.88 + ///\param t The target node.
5.89 + ///\param k How many paths are we looking for?
5.90 + ///
5.91 + int run(Node s, Node t, int k) {
5.92 +
5.93 + int i = mincost_flow.run(s,t,k);
5.94 +
5.95 +
5.96 + //Let's find the paths
5.97 + //We put the paths into stl vectors (as an inner representation).
5.98 + //In the meantime we lose the information stored in 'reversed'.
5.99 + //We suppose the lengths to be positive now.
5.100 +
5.101 + //We don't want to change the flow of mincost_flow, so we make a copy
5.102 + //The name here suggests that the flow has only 0/1 values.
5.103 + EdgeIntMap reversed(G);
5.104 +
5.105 + for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
5.106 + reversed[e] = mincost_flow.getFlow()[e];
5.107 +
5.108 + paths.clear();
5.109 + //total_length=0;
5.110 + paths.resize(k);
5.111 + for (int j=0; j<i; ++j){
5.112 + Node n=s;
5.113 + OutEdgeIt e;
5.114 +
5.115 + while (n!=t){
5.116 +
5.117 +
5.118 + G.first(e,n);
5.119 +
5.120 + while (!reversed[e]){
5.121 + ++e;
5.122 + }
5.123 + n = G.head(e);
5.124 + paths[j].push_back(e);
5.125 + //total_length += length[e];
5.126 + reversed[e] = 1-reversed[e];
5.127 + }
5.128 +
5.129 + }
5.130 + return i;
5.131 + }
5.132 +
5.133 +
5.134 + ///Returns the total length of the paths
5.135 +
5.136 + ///This function gives back the total length of the found paths.
5.137 + ///\pre \ref run() must
5.138 + ///be called before using this function.
5.139 + Length totalLength(){
5.140 + return mincost_flow.totalLength();
5.141 + }
5.142 +
5.143 + ///Returns the found flow.
5.144 +
5.145 + ///This function returns a const reference to the EdgeMap \c flow.
5.146 + ///\pre \ref run() must
5.147 + ///be called before using this function.
5.148 + const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
5.149 +
5.150 + /// Returns the optimal dual solution
5.151 +
5.152 + ///This function returns a const reference to the NodeMap
5.153 + ///\c potential (the dual solution).
5.154 + /// \pre \ref run() must be called before using this function.
5.155 + const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
5.156 +
5.157 + ///Checks whether the complementary slackness holds.
5.158 +
5.159 + ///This function checks, whether the given solution is optimal.
5.160 + ///It should return true after calling \ref run()
5.161 + ///Currently this function only checks optimality,
5.162 + ///doesn't bother with feasibility
5.163 + ///It is meant for testing purposes.
5.164 + ///
5.165 + bool checkComplementarySlackness(){
5.166 + return mincost_flow.checkComplementarySlackness();
5.167 + }
5.168 +
5.169 + ///Read the found paths.
5.170 +
5.171 + ///This function gives back the \c j-th path in argument p.
5.172 + ///Assumes that \c run() has been run and nothing changed since then.
5.173 + /// \warning It is assumed that \c p is constructed to
5.174 + ///be a path of graph \c G.
5.175 + ///If \c j is not less than the result of previous \c run,
5.176 + ///then the result here will be an empty path (\c j can be 0 as well).
5.177 + ///
5.178 + ///\param Path The type of the path structure to put the result to (must meet hugo path concept).
5.179 + ///\param p The path to put the result to
5.180 + ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
5.181 + template<typename Path>
5.182 + void getPath(Path& p, size_t j){
5.183 +
5.184 + p.clear();
5.185 + if (j>paths.size()-1){
5.186 + return;
5.187 + }
5.188 + typename Path::Builder B(p);
5.189 + for(typename std::vector<Edge>::iterator i=paths[j].begin();
5.190 + i!=paths[j].end(); ++i ){
5.191 + B.pushBack(*i);
5.192 + }
5.193 +
5.194 + B.commit();
5.195 + }
5.196 +
5.197 + }; //class Suurballe
5.198 +
5.199 + ///@}
5.200 +
5.201 +} //namespace hugo
5.202 +
5.203 +#endif //HUGO_MINLENGTHPATHS_H
6.1 --- a/src/test/Makefile.am Wed Sep 22 08:54:53 2004 +0000
6.2 +++ b/src/test/Makefile.am Wed Sep 22 09:55:41 2004 +0000
6.3 @@ -11,8 +11,8 @@
6.4 graph_test \
6.5 graph_wrapper_test \
6.6 kruskal_test \
6.7 - min_cost_flows_test \
6.8 - min_length_paths_test \
6.9 + min_cost_flow_test \
6.10 + suurballe_test \
6.11 path_test \
6.12 preflow_test \
6.13 test_tools_fail \
6.14 @@ -30,8 +30,8 @@
6.15 graph_test_SOURCES = graph_test.cc
6.16 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
6.17 kruskal_test_SOURCES = kruskal_test.cc
6.18 -min_cost_flows_test_SOURCES = min_cost_flows_test.cc
6.19 -min_length_paths_test_SOURCES = min_length_paths_test.cc
6.20 +min_cost_flow_test_SOURCES = min_cost_flow_test.cc
6.21 +suurballe_test_SOURCES = suurballe_test.cc
6.22 path_test_SOURCES = path_test.cc
6.23 preflow_test_SOURCES = preflow_test.cc
6.24 time_measure_test_SOURCES = time_measure_test.cc
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/test/min_cost_flow_test.cc Wed Sep 22 09:55:41 2004 +0000
7.3 @@ -0,0 +1,107 @@
7.4 +#include <iostream>
7.5 +#include "test_tools.h"
7.6 +#include <hugo/list_graph.h>
7.7 +#include <hugo/min_cost_flow.h>
7.8 +//#include <path.h>
7.9 +//#include <maps.h>
7.10 +
7.11 +using namespace std;
7.12 +using namespace hugo;
7.13 +
7.14 +
7.15 +
7.16 +bool passed = true;
7.17 +/*
7.18 +void check(bool rc, char *msg="") {
7.19 + passed = passed && rc;
7.20 + if(!rc) {
7.21 + std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
7.22 +
7.23 +
7.24 + }
7.25 +}
7.26 +*/
7.27 +
7.28 +
7.29 +int main()
7.30 +{
7.31 +
7.32 + typedef ListGraph::Node Node;
7.33 + typedef ListGraph::Edge Edge;
7.34 +
7.35 + ListGraph graph;
7.36 +
7.37 + //Ahuja könyv példája
7.38 +
7.39 + Node s=graph.addNode();
7.40 + Node v1=graph.addNode();
7.41 + Node v2=graph.addNode();
7.42 + Node v3=graph.addNode();
7.43 + Node v4=graph.addNode();
7.44 + Node v5=graph.addNode();
7.45 + Node t=graph.addNode();
7.46 +
7.47 + Edge s_v1=graph.addEdge(s, v1);
7.48 + Edge v1_v2=graph.addEdge(v1, v2);
7.49 + Edge s_v3=graph.addEdge(s, v3);
7.50 + Edge v2_v4=graph.addEdge(v2, v4);
7.51 + Edge v2_v5=graph.addEdge(v2, v5);
7.52 + Edge v3_v5=graph.addEdge(v3, v5);
7.53 + Edge v4_t=graph.addEdge(v4, t);
7.54 + Edge v5_t=graph.addEdge(v5, t);
7.55 +
7.56 +
7.57 + ListGraph::EdgeMap<int> length(graph);
7.58 +
7.59 + length.set(s_v1, 6);
7.60 + length.set(v1_v2, 4);
7.61 + length.set(s_v3, 10);
7.62 + length.set(v2_v4, 5);
7.63 + length.set(v2_v5, 1);
7.64 + length.set(v3_v5, 4);
7.65 + length.set(v4_t, 8);
7.66 + length.set(v5_t, 8);
7.67 +
7.68 + ListGraph::EdgeMap<int> capacity(graph);
7.69 +
7.70 + capacity.set(s_v1, 2);
7.71 + capacity.set(v1_v2, 2);
7.72 + capacity.set(s_v3, 1);
7.73 + capacity.set(v2_v4, 1);
7.74 + capacity.set(v2_v5, 1);
7.75 + capacity.set(v3_v5, 1);
7.76 + capacity.set(v4_t, 1);
7.77 + capacity.set(v5_t, 2);
7.78 +
7.79 + // ConstMap<Edge, int> const1map(1);
7.80 + std::cout << "Mincostflows algorithm test..." << std::endl;
7.81 +
7.82 + MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
7.83 + surb_test(graph, length, capacity);
7.84 +
7.85 + int k=1;
7.86 +
7.87 + check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
7.88 +
7.89 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
7.90 +
7.91 + k=2;
7.92 +
7.93 + check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
7.94 +
7.95 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
7.96 +
7.97 +
7.98 + k=4;
7.99 +
7.100 + check( surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
7.101 +
7.102 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
7.103 +
7.104 +
7.105 + cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
7.106 + << endl;
7.107 +
7.108 + return passed ? 0 : 1;
7.109 +
7.110 +}
8.1 --- a/src/test/min_cost_flows_test.cc Wed Sep 22 08:54:53 2004 +0000
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,107 +0,0 @@
8.4 -#include <iostream>
8.5 -#include "test_tools.h"
8.6 -#include <hugo/list_graph.h>
8.7 -#include <hugo/min_cost_flows.h>
8.8 -//#include <path.h>
8.9 -//#include <maps.h>
8.10 -
8.11 -using namespace std;
8.12 -using namespace hugo;
8.13 -
8.14 -
8.15 -
8.16 -bool passed = true;
8.17 -/*
8.18 -void check(bool rc, char *msg="") {
8.19 - passed = passed && rc;
8.20 - if(!rc) {
8.21 - std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
8.22 -
8.23 -
8.24 - }
8.25 -}
8.26 -*/
8.27 -
8.28 -
8.29 -int main()
8.30 -{
8.31 -
8.32 - typedef ListGraph::Node Node;
8.33 - typedef ListGraph::Edge Edge;
8.34 -
8.35 - ListGraph graph;
8.36 -
8.37 - //Ahuja könyv példája
8.38 -
8.39 - Node s=graph.addNode();
8.40 - Node v1=graph.addNode();
8.41 - Node v2=graph.addNode();
8.42 - Node v3=graph.addNode();
8.43 - Node v4=graph.addNode();
8.44 - Node v5=graph.addNode();
8.45 - Node t=graph.addNode();
8.46 -
8.47 - Edge s_v1=graph.addEdge(s, v1);
8.48 - Edge v1_v2=graph.addEdge(v1, v2);
8.49 - Edge s_v3=graph.addEdge(s, v3);
8.50 - Edge v2_v4=graph.addEdge(v2, v4);
8.51 - Edge v2_v5=graph.addEdge(v2, v5);
8.52 - Edge v3_v5=graph.addEdge(v3, v5);
8.53 - Edge v4_t=graph.addEdge(v4, t);
8.54 - Edge v5_t=graph.addEdge(v5, t);
8.55 -
8.56 -
8.57 - ListGraph::EdgeMap<int> length(graph);
8.58 -
8.59 - length.set(s_v1, 6);
8.60 - length.set(v1_v2, 4);
8.61 - length.set(s_v3, 10);
8.62 - length.set(v2_v4, 5);
8.63 - length.set(v2_v5, 1);
8.64 - length.set(v3_v5, 4);
8.65 - length.set(v4_t, 8);
8.66 - length.set(v5_t, 8);
8.67 -
8.68 - ListGraph::EdgeMap<int> capacity(graph);
8.69 -
8.70 - capacity.set(s_v1, 2);
8.71 - capacity.set(v1_v2, 2);
8.72 - capacity.set(s_v3, 1);
8.73 - capacity.set(v2_v4, 1);
8.74 - capacity.set(v2_v5, 1);
8.75 - capacity.set(v3_v5, 1);
8.76 - capacity.set(v4_t, 1);
8.77 - capacity.set(v5_t, 2);
8.78 -
8.79 - // ConstMap<Edge, int> const1map(1);
8.80 - std::cout << "Mincostflows algorithm test..." << std::endl;
8.81 -
8.82 - MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
8.83 - surb_test(graph, length, capacity);
8.84 -
8.85 - int k=1;
8.86 -
8.87 - check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
8.88 -
8.89 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
8.90 -
8.91 - k=2;
8.92 -
8.93 - check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
8.94 -
8.95 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
8.96 -
8.97 -
8.98 - k=4;
8.99 -
8.100 - check( surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
8.101 -
8.102 - check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
8.103 -
8.104 -
8.105 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
8.106 - << endl;
8.107 -
8.108 - return passed ? 0 : 1;
8.109 -
8.110 -}
9.1 --- a/src/test/min_length_paths_test.cc Wed Sep 22 08:54:53 2004 +0000
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,94 +0,0 @@
9.4 -#include <iostream>
9.5 -#include <hugo/list_graph.h>
9.6 -#include <hugo/min_length_paths.h>
9.7 -//#include <path.h>
9.8 -#include "test_tools.h"
9.9 -
9.10 -using namespace std;
9.11 -using namespace hugo;
9.12 -
9.13 -
9.14 -
9.15 -bool passed = true;
9.16 -
9.17 -
9.18 -int main()
9.19 -{
9.20 -
9.21 - typedef ListGraph::Node Node;
9.22 - typedef ListGraph::Edge Edge;
9.23 -
9.24 - ListGraph graph;
9.25 -
9.26 - //Ahuja könyv példája
9.27 -
9.28 - Node s=graph.addNode();
9.29 - Node v1=graph.addNode();
9.30 - Node v2=graph.addNode();
9.31 - Node v3=graph.addNode();
9.32 - Node v4=graph.addNode();
9.33 - Node v5=graph.addNode();
9.34 - Node t=graph.addNode();
9.35 -
9.36 - Edge s_v1=graph.addEdge(s, v1);
9.37 - Edge v1_v2=graph.addEdge(v1, v2);
9.38 - Edge s_v3=graph.addEdge(s, v3);
9.39 - Edge v2_v4=graph.addEdge(v2, v4);
9.40 - Edge v2_v5=graph.addEdge(v2, v5);
9.41 - Edge v3_v5=graph.addEdge(v3, v5);
9.42 - Edge v4_t=graph.addEdge(v4, t);
9.43 - Edge v5_t=graph.addEdge(v5, t);
9.44 -
9.45 -
9.46 - ListGraph::EdgeMap<int> length(graph);
9.47 -
9.48 - length.set(s_v1, 6);
9.49 - length.set(v1_v2, 4);
9.50 - length.set(s_v3, 10);
9.51 - length.set(v2_v4, 5);
9.52 - length.set(v2_v5, 1);
9.53 - length.set(v3_v5, 5);
9.54 - length.set(v4_t, 8);
9.55 - length.set(v5_t, 8);
9.56 -
9.57 - std::cout << "Minlengthpaths algorithm test..." << std::endl;
9.58 -
9.59 -
9.60 - int k=3;
9.61 - MinLengthPaths< ListGraph, ListGraph::EdgeMap<int> >
9.62 - surb_test(graph, length);
9.63 -
9.64 - check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
9.65 - "Two paths, total length should be 46");
9.66 -
9.67 - check( surb_test.checkComplementarySlackness(),
9.68 - "Complementary slackness conditions are not met.");
9.69 -
9.70 - // typedef DirPath<ListGraph> DPath;
9.71 - // DPath P(graph);
9.72 -
9.73 - /*
9.74 - surb_test.getPath(P,0);
9.75 - check(P.length() == 4, "First path should contain 4 edges.");
9.76 - cout<<P.length()<<endl;
9.77 - surb_test.getPath(P,1);
9.78 - check(P.length() == 3, "Second path: 3 edges.");
9.79 - cout<<P.length()<<endl;
9.80 - */
9.81 -
9.82 - k=1;
9.83 - check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
9.84 - "One path, total length should be 19");
9.85 -
9.86 - check( surb_test.checkComplementarySlackness(),
9.87 - "Complementary slackness conditions are not met.");
9.88 -
9.89 - // surb_test.getPath(P,0);
9.90 - // check(P.length() == 4, "First path should contain 4 edges.");
9.91 -
9.92 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
9.93 - << endl;
9.94 -
9.95 - return passed ? 0 : 1;
9.96 -
9.97 -}
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/src/test/suurballe_test.cc Wed Sep 22 09:55:41 2004 +0000
10.3 @@ -0,0 +1,94 @@
10.4 +#include <iostream>
10.5 +#include <hugo/list_graph.h>
10.6 +#include <hugo/suurballe.h>
10.7 +//#include <path.h>
10.8 +#include "test_tools.h"
10.9 +
10.10 +using namespace std;
10.11 +using namespace hugo;
10.12 +
10.13 +
10.14 +
10.15 +bool passed = true;
10.16 +
10.17 +
10.18 +int main()
10.19 +{
10.20 +
10.21 + typedef ListGraph::Node Node;
10.22 + typedef ListGraph::Edge Edge;
10.23 +
10.24 + ListGraph graph;
10.25 +
10.26 + //Ahuja könyv példája
10.27 +
10.28 + Node s=graph.addNode();
10.29 + Node v1=graph.addNode();
10.30 + Node v2=graph.addNode();
10.31 + Node v3=graph.addNode();
10.32 + Node v4=graph.addNode();
10.33 + Node v5=graph.addNode();
10.34 + Node t=graph.addNode();
10.35 +
10.36 + Edge s_v1=graph.addEdge(s, v1);
10.37 + Edge v1_v2=graph.addEdge(v1, v2);
10.38 + Edge s_v3=graph.addEdge(s, v3);
10.39 + Edge v2_v4=graph.addEdge(v2, v4);
10.40 + Edge v2_v5=graph.addEdge(v2, v5);
10.41 + Edge v3_v5=graph.addEdge(v3, v5);
10.42 + Edge v4_t=graph.addEdge(v4, t);
10.43 + Edge v5_t=graph.addEdge(v5, t);
10.44 +
10.45 +
10.46 + ListGraph::EdgeMap<int> length(graph);
10.47 +
10.48 + length.set(s_v1, 6);
10.49 + length.set(v1_v2, 4);
10.50 + length.set(s_v3, 10);
10.51 + length.set(v2_v4, 5);
10.52 + length.set(v2_v5, 1);
10.53 + length.set(v3_v5, 5);
10.54 + length.set(v4_t, 8);
10.55 + length.set(v5_t, 8);
10.56 +
10.57 + std::cout << "Minlengthpaths algorithm test..." << std::endl;
10.58 +
10.59 +
10.60 + int k=3;
10.61 + Suurballe< ListGraph, ListGraph::EdgeMap<int> >
10.62 + surb_test(graph, length);
10.63 +
10.64 + check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
10.65 + "Two paths, total length should be 46");
10.66 +
10.67 + check( surb_test.checkComplementarySlackness(),
10.68 + "Complementary slackness conditions are not met.");
10.69 +
10.70 + // typedef DirPath<ListGraph> DPath;
10.71 + // DPath P(graph);
10.72 +
10.73 + /*
10.74 + surb_test.getPath(P,0);
10.75 + check(P.length() == 4, "First path should contain 4 edges.");
10.76 + cout<<P.length()<<endl;
10.77 + surb_test.getPath(P,1);
10.78 + check(P.length() == 3, "Second path: 3 edges.");
10.79 + cout<<P.length()<<endl;
10.80 + */
10.81 +
10.82 + k=1;
10.83 + check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
10.84 + "One path, total length should be 19");
10.85 +
10.86 + check( surb_test.checkComplementarySlackness(),
10.87 + "Complementary slackness conditions are not met.");
10.88 +
10.89 + // surb_test.getPath(P,0);
10.90 + // check(P.length() == 4, "First path should contain 4 edges.");
10.91 +
10.92 + cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
10.93 + << endl;
10.94 +
10.95 + return passed ? 0 : 1;
10.96 +
10.97 +}