1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/min_cost_flows.h Wed Sep 22 07:32:57 2004 +0000
1.3 @@ -0,0 +1,241 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_MINCOSTFLOWS_H
1.6 +#define HUGO_MINCOSTFLOWS_H
1.7 +
1.8 +///\ingroup flowalgs
1.9 +///\file
1.10 +///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost
1.11 +
1.12 +
1.13 +#include <hugo/dijkstra.h>
1.14 +#include <hugo/graph_wrapper.h>
1.15 +#include <hugo/maps.h>
1.16 +#include <vector>
1.17 +
1.18 +namespace hugo {
1.19 +
1.20 +/// \addtogroup flowalgs
1.21 +/// @{
1.22 +
1.23 + ///\brief Implementation of an algorithm for finding a flow of value \c k
1.24 + ///(for small values of \c k) having minimal total cost between 2 nodes
1.25 + ///
1.26 + ///
1.27 + /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
1.28 + /// an algorithm for finding a flow of value \c k
1.29 + /// having minimal total cost
1.30 + /// from a given source node to a given target node in an
1.31 + /// edge-weighted directed graph. To this end,
1.32 + /// the edge-capacities and edge-weitghs have to be nonnegative.
1.33 + /// The edge-capacities should be integers, but the edge-weights can be
1.34 + /// integers, reals or of other comparable numeric type.
1.35 + /// This algorithm is intended to use only for small values of \c k,
1.36 + /// since it is only polynomial in k,
1.37 + /// not in the length of k (which is log k).
1.38 + /// In order to find the minimum cost flow of value \c k it
1.39 + /// finds the minimum cost flow of value \c i for every
1.40 + /// \c i between 0 and \c k.
1.41 + ///
1.42 + ///\param Graph The directed graph type the algorithm runs on.
1.43 + ///\param LengthMap The type of the length map.
1.44 + ///\param CapacityMap The capacity map type.
1.45 + ///
1.46 + ///\author Attila Bernath
1.47 + template <typename Graph, typename LengthMap, typename CapacityMap>
1.48 + class MinCostFlows {
1.49 +
1.50 + typedef typename LengthMap::ValueType Length;
1.51 +
1.52 + //Warning: this should be integer type
1.53 + typedef typename CapacityMap::ValueType Capacity;
1.54 +
1.55 + typedef typename Graph::Node Node;
1.56 + typedef typename Graph::NodeIt NodeIt;
1.57 + typedef typename Graph::Edge Edge;
1.58 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.59 + typedef typename Graph::template EdgeMap<int> EdgeIntMap;
1.60 +
1.61 +
1.62 + typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
1.63 + typedef typename ResGraphType::Edge ResGraphEdge;
1.64 +
1.65 + class ModLengthMap {
1.66 + typedef typename Graph::template NodeMap<Length> NodeMap;
1.67 + const ResGraphType& G;
1.68 + const LengthMap &ol;
1.69 + const NodeMap &pot;
1.70 + public :
1.71 + typedef typename LengthMap::KeyType KeyType;
1.72 + typedef typename LengthMap::ValueType ValueType;
1.73 +
1.74 + ValueType operator[](typename ResGraphType::Edge e) const {
1.75 + if (G.forward(e))
1.76 + return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
1.77 + else
1.78 + return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
1.79 + }
1.80 +
1.81 + ModLengthMap(const ResGraphType& _G,
1.82 + const LengthMap &o, const NodeMap &p) :
1.83 + G(_G), /*rev(_rev),*/ ol(o), pot(p){};
1.84 + };//ModLengthMap
1.85 +
1.86 +
1.87 + protected:
1.88 +
1.89 + //Input
1.90 + const Graph& G;
1.91 + const LengthMap& length;
1.92 + const CapacityMap& capacity;
1.93 +
1.94 +
1.95 + //auxiliary variables
1.96 +
1.97 + //To store the flow
1.98 + EdgeIntMap flow;
1.99 + //To store the potential (dual variables)
1.100 + typedef typename Graph::template NodeMap<Length> PotentialMap;
1.101 + PotentialMap potential;
1.102 +
1.103 +
1.104 + Length total_length;
1.105 +
1.106 +
1.107 + public :
1.108 +
1.109 + /// The constructor of the class.
1.110 +
1.111 + ///\param _G The directed graph the algorithm runs on.
1.112 + ///\param _length The length (weight or cost) of the edges.
1.113 + ///\param _cap The capacity of the edges.
1.114 + MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
1.115 + length(_length), capacity(_cap), flow(_G), potential(_G){ }
1.116 +
1.117 +
1.118 + ///Runs the algorithm.
1.119 +
1.120 + ///Runs the algorithm.
1.121 + ///Returns k if there is a flow of value at least k edge-disjoint
1.122 + ///from s to t.
1.123 + ///Otherwise it returns the maximum value of a flow from s to t.
1.124 + ///
1.125 + ///\param s The source node.
1.126 + ///\param t The target node.
1.127 + ///\param k The value of the flow we are looking for.
1.128 + ///
1.129 + ///\todo May be it does make sense to be able to start with a nonzero
1.130 + /// feasible primal-dual solution pair as well.
1.131 + int run(Node s, Node t, int k) {
1.132 +
1.133 + //Resetting variables from previous runs
1.134 + total_length = 0;
1.135 +
1.136 + for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
1.137 +
1.138 + //Initialize the potential to zero
1.139 + for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
1.140 +
1.141 +
1.142 + //We need a residual graph
1.143 + ResGraphType res_graph(G, capacity, flow);
1.144 +
1.145 +
1.146 + ModLengthMap mod_length(res_graph, length, potential);
1.147 +
1.148 + Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
1.149 +
1.150 + int i;
1.151 + for (i=0; i<k; ++i){
1.152 + dijkstra.run(s);
1.153 + if (!dijkstra.reached(t)){
1.154 + //There are no flow of value k from s to t
1.155 + break;
1.156 + };
1.157 +
1.158 + //We have to change the potential
1.159 + for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n)
1.160 + potential[n] += dijkstra.distMap()[n];
1.161 +
1.162 +
1.163 + //Augmenting on the sortest path
1.164 + Node n=t;
1.165 + ResGraphEdge e;
1.166 + while (n!=s){
1.167 + e = dijkstra.pred(n);
1.168 + n = dijkstra.predNode(n);
1.169 + res_graph.augment(e,1);
1.170 + //Let's update the total length
1.171 + if (res_graph.forward(e))
1.172 + total_length += length[e];
1.173 + else
1.174 + total_length -= length[e];
1.175 + }
1.176 +
1.177 +
1.178 + }
1.179 +
1.180 +
1.181 + return i;
1.182 + }
1.183 +
1.184 +
1.185 +
1.186 + /// Gives back the total weight of the found flow.
1.187 +
1.188 + ///This function gives back the total weight of the found flow.
1.189 + ///Assumes that \c run() has been run and nothing changed since then.
1.190 + Length totalLength(){
1.191 + return total_length;
1.192 + }
1.193 +
1.194 + ///Returns a const reference to the EdgeMap \c flow.
1.195 +
1.196 + ///Returns a const reference to the EdgeMap \c flow.
1.197 + ///\pre \ref run() must
1.198 + ///be called before using this function.
1.199 + const EdgeIntMap &getFlow() const { return flow;}
1.200 +
1.201 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.202 +
1.203 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.204 + /// \pre \ref run() must be called before using this function.
1.205 + const PotentialMap &getPotential() const { return potential;}
1.206 +
1.207 + /// Checking the complementary slackness optimality criteria
1.208 +
1.209 + ///This function checks, whether the given solution is optimal
1.210 + ///If executed after the call of \c run() then it should return with true.
1.211 + ///This function only checks optimality, doesn't bother with feasibility.
1.212 + ///It is meant for testing purposes.
1.213 + ///
1.214 + bool checkComplementarySlackness(){
1.215 + Length mod_pot;
1.216 + Length fl_e;
1.217 + for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
1.218 + //C^{\Pi}_{i,j}
1.219 + mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
1.220 + fl_e = flow[e];
1.221 + if (0<fl_e && fl_e<capacity[e]) {
1.222 + /// \todo better comparison is needed for real types, moreover,
1.223 + /// this comparison here is superfluous.
1.224 + if (mod_pot != 0)
1.225 + return false;
1.226 + }
1.227 + else {
1.228 + if (mod_pot > 0 && fl_e != 0)
1.229 + return false;
1.230 + if (mod_pot < 0 && fl_e != capacity[e])
1.231 + return false;
1.232 + }
1.233 + }
1.234 + return true;
1.235 + }
1.236 +
1.237 +
1.238 + }; //class MinCostFlows
1.239 +
1.240 + ///@}
1.241 +
1.242 +} //namespace hugo
1.243 +
1.244 +#endif //HUGO_MINCOSTFLOWS_H
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/hugo/min_length_paths.h Wed Sep 22 07:32:57 2004 +0000
2.3 @@ -0,0 +1,191 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_MINLENGTHPATHS_H
2.6 +#define HUGO_MINLENGTHPATHS_H
2.7 +
2.8 +///\ingroup flowalgs
2.9 +///\file
2.10 +///\brief An algorithm for finding k paths of minimal total length.
2.11 +
2.12 +
2.13 +#include <hugo/maps.h>
2.14 +#include <vector>
2.15 +#include <hugo/min_cost_flows.h>
2.16 +
2.17 +namespace hugo {
2.18 +
2.19 +/// \addtogroup flowalgs
2.20 +/// @{
2.21 +
2.22 + ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
2.23 + /// of minimal total length
2.24 + ///
2.25 + /// The class \ref hugo::MinLengthPaths implements
2.26 + /// an algorithm for finding k edge-disjoint paths
2.27 + /// from a given source node to a given target node in an
2.28 + /// edge-weighted directed graph having minimal total weight (length).
2.29 + ///
2.30 + ///\warning Length values should be nonnegative.
2.31 + ///
2.32 + ///\param Graph The directed graph type the algorithm runs on.
2.33 + ///\param LengthMap The type of the length map (values should be nonnegative).
2.34 + ///
2.35 + ///\author Attila Bernath
2.36 + template <typename Graph, typename LengthMap>
2.37 + class MinLengthPaths{
2.38 +
2.39 +
2.40 + typedef typename LengthMap::ValueType Length;
2.41 +
2.42 + typedef typename Graph::Node Node;
2.43 + typedef typename Graph::NodeIt NodeIt;
2.44 + typedef typename Graph::Edge Edge;
2.45 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.46 + typedef typename Graph::template EdgeMap<int> EdgeIntMap;
2.47 +
2.48 + typedef ConstMap<Edge,int> ConstMap;
2.49 +
2.50 + //Input
2.51 + const Graph& G;
2.52 +
2.53 + //Auxiliary variables
2.54 + //This is the capacity map for the mincostflow problem
2.55 + ConstMap const1map;
2.56 + //This MinCostFlows instance will actually solve the problem
2.57 + MinCostFlows<Graph, LengthMap, ConstMap> mincost_flow;
2.58 +
2.59 + //Container to store found paths
2.60 + std::vector< std::vector<Edge> > paths;
2.61 +
2.62 + public :
2.63 +
2.64 +
2.65 + /// The constructor of the class.
2.66 +
2.67 + ///\param _G The directed graph the algorithm runs on.
2.68 + ///\param _length The length (weight or cost) of the edges.
2.69 + MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
2.70 + const1map(1), mincost_flow(_G, _length, const1map){}
2.71 +
2.72 + ///Runs the algorithm.
2.73 +
2.74 + ///Runs the algorithm.
2.75 + ///Returns k if there are at least k edge-disjoint paths from s to t.
2.76 + ///Otherwise it returns the number of found edge-disjoint paths from s to t.
2.77 + ///
2.78 + ///\param s The source node.
2.79 + ///\param t The target node.
2.80 + ///\param k How many paths are we looking for?
2.81 + ///
2.82 + int run(Node s, Node t, int k) {
2.83 +
2.84 + int i = mincost_flow.run(s,t,k);
2.85 +
2.86 +
2.87 + //Let's find the paths
2.88 + //We put the paths into stl vectors (as an inner representation).
2.89 + //In the meantime we lose the information stored in 'reversed'.
2.90 + //We suppose the lengths to be positive now.
2.91 +
2.92 + //We don't want to change the flow of mincost_flow, so we make a copy
2.93 + //The name here suggests that the flow has only 0/1 values.
2.94 + EdgeIntMap reversed(G);
2.95 +
2.96 + for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
2.97 + reversed[e] = mincost_flow.getFlow()[e];
2.98 +
2.99 + paths.clear();
2.100 + //total_length=0;
2.101 + paths.resize(k);
2.102 + for (int j=0; j<i; ++j){
2.103 + Node n=s;
2.104 + OutEdgeIt e;
2.105 +
2.106 + while (n!=t){
2.107 +
2.108 +
2.109 + G.first(e,n);
2.110 +
2.111 + while (!reversed[e]){
2.112 + ++e;
2.113 + }
2.114 + n = G.head(e);
2.115 + paths[j].push_back(e);
2.116 + //total_length += length[e];
2.117 + reversed[e] = 1-reversed[e];
2.118 + }
2.119 +
2.120 + }
2.121 + return i;
2.122 + }
2.123 +
2.124 +
2.125 + ///Returns the total length of the paths
2.126 +
2.127 + ///This function gives back the total length of the found paths.
2.128 + ///\pre \ref run() must
2.129 + ///be called before using this function.
2.130 + Length totalLength(){
2.131 + return mincost_flow.totalLength();
2.132 + }
2.133 +
2.134 + ///Returns the found flow.
2.135 +
2.136 + ///This function returns a const reference to the EdgeMap \c flow.
2.137 + ///\pre \ref run() must
2.138 + ///be called before using this function.
2.139 + const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
2.140 +
2.141 + /// Returns the optimal dual solution
2.142 +
2.143 + ///This function returns a const reference to the NodeMap
2.144 + ///\c potential (the dual solution).
2.145 + /// \pre \ref run() must be called before using this function.
2.146 + const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
2.147 +
2.148 + ///Checks whether the complementary slackness holds.
2.149 +
2.150 + ///This function checks, whether the given solution is optimal.
2.151 + ///It should return true after calling \ref run()
2.152 + ///Currently this function only checks optimality,
2.153 + ///doesn't bother with feasibility
2.154 + ///It is meant for testing purposes.
2.155 + ///
2.156 + bool checkComplementarySlackness(){
2.157 + return mincost_flow.checkComplementarySlackness();
2.158 + }
2.159 +
2.160 + ///Read the found paths.
2.161 +
2.162 + ///This function gives back the \c j-th path in argument p.
2.163 + ///Assumes that \c run() has been run and nothing changed since then.
2.164 + /// \warning It is assumed that \c p is constructed to
2.165 + ///be a path of graph \c G.
2.166 + ///If \c j is not less than the result of previous \c run,
2.167 + ///then the result here will be an empty path (\c j can be 0 as well).
2.168 + ///
2.169 + ///\param Path The type of the path structure to put the result to (must meet hugo path concept).
2.170 + ///\param p The path to put the result to
2.171 + ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
2.172 + template<typename Path>
2.173 + void getPath(Path& p, size_t j){
2.174 +
2.175 + p.clear();
2.176 + if (j>paths.size()-1){
2.177 + return;
2.178 + }
2.179 + typename Path::Builder B(p);
2.180 + for(typename std::vector<Edge>::iterator i=paths[j].begin();
2.181 + i!=paths[j].end(); ++i ){
2.182 + B.pushBack(*i);
2.183 + }
2.184 +
2.185 + B.commit();
2.186 + }
2.187 +
2.188 + }; //class MinLengthPaths
2.189 +
2.190 + ///@}
2.191 +
2.192 +} //namespace hugo
2.193 +
2.194 +#endif //HUGO_MINLENGTHPATHS_H
3.1 --- a/src/hugo/mincostflows.h Wed Sep 22 07:22:34 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/minlengthpaths.h Wed Sep 22 07:22:34 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/mincostflows.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 --- a/src/test/Makefile.am Wed Sep 22 07:22:34 2004 +0000
5.2 +++ b/src/test/Makefile.am Wed Sep 22 07:32:57 2004 +0000
5.3 @@ -11,8 +11,8 @@
5.4 graph_test \
5.5 graph_wrapper_test \
5.6 kruskal_test \
5.7 - mincostflows_test \
5.8 - minlengthpaths_test \
5.9 + min_cost_flows_test \
5.10 + min_length_paths_test \
5.11 path_test \
5.12 preflow_test \
5.13 test_tools_fail \
5.14 @@ -30,8 +30,8 @@
5.15 graph_test_SOURCES = graph_test.cc
5.16 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
5.17 kruskal_test_SOURCES = kruskal_test.cc
5.18 -mincostflows_test_SOURCES = mincostflows_test.cc
5.19 -minlengthpaths_test_SOURCES = minlengthpaths_test.cc
5.20 +min_cost_flows_test_SOURCES = min_cost_flows_test.cc
5.21 +min_length_paths_test_SOURCES = min_length_paths_test.cc
5.22 path_test_SOURCES = path_test.cc
5.23 preflow_test_SOURCES = preflow_test.cc
5.24 time_measure_test_SOURCES = time_measure_test.cc
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/test/min_cost_flows_test.cc Wed Sep 22 07:32:57 2004 +0000
6.3 @@ -0,0 +1,107 @@
6.4 +#include <iostream>
6.5 +#include "test_tools.h"
6.6 +#include <hugo/list_graph.h>
6.7 +#include <hugo/min_cost_flows.h>
6.8 +//#include <path.h>
6.9 +//#include <maps.h>
6.10 +
6.11 +using namespace std;
6.12 +using namespace hugo;
6.13 +
6.14 +
6.15 +
6.16 +bool passed = true;
6.17 +/*
6.18 +void check(bool rc, char *msg="") {
6.19 + passed = passed && rc;
6.20 + if(!rc) {
6.21 + std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
6.22 +
6.23 +
6.24 + }
6.25 +}
6.26 +*/
6.27 +
6.28 +
6.29 +int main()
6.30 +{
6.31 +
6.32 + typedef ListGraph::Node Node;
6.33 + typedef ListGraph::Edge Edge;
6.34 +
6.35 + ListGraph graph;
6.36 +
6.37 + //Ahuja könyv példája
6.38 +
6.39 + Node s=graph.addNode();
6.40 + Node v1=graph.addNode();
6.41 + Node v2=graph.addNode();
6.42 + Node v3=graph.addNode();
6.43 + Node v4=graph.addNode();
6.44 + Node v5=graph.addNode();
6.45 + Node t=graph.addNode();
6.46 +
6.47 + Edge s_v1=graph.addEdge(s, v1);
6.48 + Edge v1_v2=graph.addEdge(v1, v2);
6.49 + Edge s_v3=graph.addEdge(s, v3);
6.50 + Edge v2_v4=graph.addEdge(v2, v4);
6.51 + Edge v2_v5=graph.addEdge(v2, v5);
6.52 + Edge v3_v5=graph.addEdge(v3, v5);
6.53 + Edge v4_t=graph.addEdge(v4, t);
6.54 + Edge v5_t=graph.addEdge(v5, t);
6.55 +
6.56 +
6.57 + ListGraph::EdgeMap<int> length(graph);
6.58 +
6.59 + length.set(s_v1, 6);
6.60 + length.set(v1_v2, 4);
6.61 + length.set(s_v3, 10);
6.62 + length.set(v2_v4, 5);
6.63 + length.set(v2_v5, 1);
6.64 + length.set(v3_v5, 4);
6.65 + length.set(v4_t, 8);
6.66 + length.set(v5_t, 8);
6.67 +
6.68 + ListGraph::EdgeMap<int> capacity(graph);
6.69 +
6.70 + capacity.set(s_v1, 2);
6.71 + capacity.set(v1_v2, 2);
6.72 + capacity.set(s_v3, 1);
6.73 + capacity.set(v2_v4, 1);
6.74 + capacity.set(v2_v5, 1);
6.75 + capacity.set(v3_v5, 1);
6.76 + capacity.set(v4_t, 1);
6.77 + capacity.set(v5_t, 2);
6.78 +
6.79 + // ConstMap<Edge, int> const1map(1);
6.80 + std::cout << "Mincostflows algorithm test..." << std::endl;
6.81 +
6.82 + MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
6.83 + surb_test(graph, length, capacity);
6.84 +
6.85 + int k=1;
6.86 +
6.87 + check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
6.88 +
6.89 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
6.90 +
6.91 + k=2;
6.92 +
6.93 + check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
6.94 +
6.95 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
6.96 +
6.97 +
6.98 + k=4;
6.99 +
6.100 + check( surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
6.101 +
6.102 + check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
6.103 +
6.104 +
6.105 + cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
6.106 + << endl;
6.107 +
6.108 + return passed ? 0 : 1;
6.109 +
6.110 +}
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/test/min_length_paths_test.cc Wed Sep 22 07:32:57 2004 +0000
7.3 @@ -0,0 +1,94 @@
7.4 +#include <iostream>
7.5 +#include <hugo/list_graph.h>
7.6 +#include <hugo/min_length_paths.h>
7.7 +//#include <path.h>
7.8 +#include "test_tools.h"
7.9 +
7.10 +using namespace std;
7.11 +using namespace hugo;
7.12 +
7.13 +
7.14 +
7.15 +bool passed = true;
7.16 +
7.17 +
7.18 +int main()
7.19 +{
7.20 +
7.21 + typedef ListGraph::Node Node;
7.22 + typedef ListGraph::Edge Edge;
7.23 +
7.24 + ListGraph graph;
7.25 +
7.26 + //Ahuja könyv példája
7.27 +
7.28 + Node s=graph.addNode();
7.29 + Node v1=graph.addNode();
7.30 + Node v2=graph.addNode();
7.31 + Node v3=graph.addNode();
7.32 + Node v4=graph.addNode();
7.33 + Node v5=graph.addNode();
7.34 + Node t=graph.addNode();
7.35 +
7.36 + Edge s_v1=graph.addEdge(s, v1);
7.37 + Edge v1_v2=graph.addEdge(v1, v2);
7.38 + Edge s_v3=graph.addEdge(s, v3);
7.39 + Edge v2_v4=graph.addEdge(v2, v4);
7.40 + Edge v2_v5=graph.addEdge(v2, v5);
7.41 + Edge v3_v5=graph.addEdge(v3, v5);
7.42 + Edge v4_t=graph.addEdge(v4, t);
7.43 + Edge v5_t=graph.addEdge(v5, t);
7.44 +
7.45 +
7.46 + ListGraph::EdgeMap<int> length(graph);
7.47 +
7.48 + length.set(s_v1, 6);
7.49 + length.set(v1_v2, 4);
7.50 + length.set(s_v3, 10);
7.51 + length.set(v2_v4, 5);
7.52 + length.set(v2_v5, 1);
7.53 + length.set(v3_v5, 5);
7.54 + length.set(v4_t, 8);
7.55 + length.set(v5_t, 8);
7.56 +
7.57 + std::cout << "Minlengthpaths algorithm test..." << std::endl;
7.58 +
7.59 +
7.60 + int k=3;
7.61 + MinLengthPaths< ListGraph, ListGraph::EdgeMap<int> >
7.62 + surb_test(graph, length);
7.63 +
7.64 + check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
7.65 + "Two paths, total length should be 46");
7.66 +
7.67 + check( surb_test.checkComplementarySlackness(),
7.68 + "Complementary slackness conditions are not met.");
7.69 +
7.70 + // typedef DirPath<ListGraph> DPath;
7.71 + // DPath P(graph);
7.72 +
7.73 + /*
7.74 + surb_test.getPath(P,0);
7.75 + check(P.length() == 4, "First path should contain 4 edges.");
7.76 + cout<<P.length()<<endl;
7.77 + surb_test.getPath(P,1);
7.78 + check(P.length() == 3, "Second path: 3 edges.");
7.79 + cout<<P.length()<<endl;
7.80 + */
7.81 +
7.82 + k=1;
7.83 + check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
7.84 + "One path, total length should be 19");
7.85 +
7.86 + check( surb_test.checkComplementarySlackness(),
7.87 + "Complementary slackness conditions are not met.");
7.88 +
7.89 + // surb_test.getPath(P,0);
7.90 + // check(P.length() == 4, "First path should contain 4 edges.");
7.91 +
7.92 + cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
7.93 + << endl;
7.94 +
7.95 + return passed ? 0 : 1;
7.96 +
7.97 +}
8.1 --- a/src/test/mincostflows_test.cc Wed Sep 22 07:22:34 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/mincostflows.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/minlengthpaths_test.cc Wed Sep 22 07:22:34 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/minlengthpaths.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 --- a/src/test/old_path_test.cc Wed Sep 22 07:22:34 2004 +0000
10.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
10.3 @@ -1,175 +0,0 @@
10.4 -#include <string>
10.5 -#include <iostream>
10.6 -//#include <hugo/skeletons/path.h>
10.7 -#include <hugo/path.h>
10.8 -#include <hugo/list_graph.h>
10.9 -
10.10 -using namespace std;
10.11 -using namespace hugo;
10.12 -#ifdef HUGO_SKELETON_PATH_H
10.13 -using namespace skeleton;
10.14 -#endif
10.15 -
10.16 -bool passed = true;
10.17 -
10.18 -void check(bool rc) {
10.19 - passed = passed && rc;
10.20 - if(!rc) {
10.21 - cout << "Test failed!" << endl;
10.22 - }
10.23 -}
10.24 -
10.25 -#ifdef DEBUG
10.26 -const bool debug = true;
10.27 -#else
10.28 -const bool debug = false;
10.29 -#endif
10.30 -
10.31 -
10.32 -int main() {
10.33 -
10.34 - try {
10.35 -
10.36 - typedef ListGraph::Node Node;
10.37 - typedef ListGraph::Edge Edge;
10.38 -
10.39 - ListGraph G;
10.40 -
10.41 - Node s=G.addNode();
10.42 - Node v1=G.addNode();
10.43 - Node v2=G.addNode();
10.44 - Node v3=G.addNode();
10.45 - Node v4=G.addNode();
10.46 - Node t=G.addNode();
10.47 -
10.48 - Edge e1 = G.addEdge(s, v1);
10.49 - Edge e2 = G.addEdge(s, v2);
10.50 - Edge e3 = G.addEdge(v1, v2);
10.51 - Edge e4 = G.addEdge(v2, v1);
10.52 - Edge e5 = G.addEdge(v1, v3);
10.53 - Edge e6 = G.addEdge(v3, v2);
10.54 - Edge e7 = G.addEdge(v2, v4);
10.55 - Edge e8 = G.addEdge(v4, v3);
10.56 - Edge e9 = G.addEdge(v3, t);
10.57 - Edge e10 = G.addEdge(v4, t);
10.58 -
10.59 -#ifdef DEBUG
10.60 - bool rc;
10.61 -#endif
10.62 -
10.63 - {
10.64 - cout << "\n\n\nDirPath tesztelese...\n";
10.65 -
10.66 -
10.67 - cout << "Ures path letrehozasa" << endl;
10.68 -
10.69 -#ifndef HUGO_SKELETON_PATH_H
10.70 - typedef DirPath<ListGraph> DPath;
10.71 -#else
10.72 - typedef Path<ListGraph> DPath;
10.73 -#endif
10.74 -
10.75 - DPath P(G);
10.76 -
10.77 - cout << "P.length() == " << P.length() << endl;
10.78 - check(P.length() == 0);
10.79 -
10.80 - cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl;
10.81 - check(! (P.tail()!=INVALID));
10.82 - {
10.83 - cout << "Builder objektum letrehozasa" << endl;
10.84 - DPath::Builder B(P);
10.85 -
10.86 - cout << "Hozzaadunk az elejehez ket elet..." << endl;
10.87 - B.pushFront(e6);
10.88 - B.pushFront(e5);
10.89 - cout << "P.length() == " << P.length() << endl;
10.90 - check(P.length() == 0);
10.91 -
10.92 - cout << "Commitolunk..." << endl;
10.93 - B.commit();
10.94 -
10.95 - cout << "P.length() == " << P.length() << endl;
10.96 - check(P.length() == 2);
10.97 -
10.98 - cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl;
10.99 - check(P.tail()!=INVALID);
10.100 - cout << "P.tail()==v1 ? " << (P.tail()==v1) << endl;
10.101 - check(P.tail() == v1);
10.102 -
10.103 - // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
10.104 - // de legalabb valami:
10.105 -#ifdef DEBUG
10.106 - cout << "Hozzaadunk az elejehez egy nem illeszkedo elet..." << endl;
10.107 - rc = false;
10.108 - try {
10.109 - B.pushFront(e3);
10.110 - }
10.111 - catch(const Exception &e) {
10.112 - cout << "E: " << e.what() << endl;
10.113 - rc = true;
10.114 - }
10.115 - check(rc);
10.116 -#endif
10.117 -
10.118 - cout << "Hozzaadunk a vegehez ket elet..." << endl;
10.119 - B.pushBack(e7);
10.120 - B.pushBack(e8);
10.121 - cout << "P.length() == " << P.length() << endl;
10.122 - check(P.length() == 2);
10.123 -
10.124 - cout << "Es commitolunk...\n";
10.125 - B.commit();
10.126 - }
10.127 - cout << "P.length() == " << P.length() << endl;
10.128 - check(P.length() == 4);
10.129 -
10.130 - cout << "P.head()==v3 ? " << (P.head()==v3) << endl;
10.131 - check(P.head() == v3);
10.132 -
10.133 -#ifndef HUGO_SKELETON_PATH_H
10.134 - cout << "Vegigiteralunk az eleken." << endl;
10.135 - typedef DPath::NodeIt NodeIt;
10.136 - typedef DPath::EdgeIt EdgeIt;
10.137 - EdgeIt e;
10.138 - int i=1;
10.139 - for(P.first(e); e!=INVALID; ++e, ++i) {
10.140 - cout << i << ". el: " <</* e << */endl;
10.141 - }
10.142 -#endif
10.143 -
10.144 - // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
10.145 - // de legalabb valami:
10.146 -
10.147 -#ifdef DEBUG
10.148 - rc = false;
10.149 - try {
10.150 - cout << "Setting an edgeiter to a nonexistant edge." << endl;
10.151 - //P.nth(e,134);
10.152 - rc = !debug;
10.153 - }
10.154 - catch(const Exception &e) {
10.155 - cout << "E: " << e.what() << endl;
10.156 - rc = debug;
10.157 - }
10.158 - check(rc);
10.159 -#endif
10.160 - }
10.161 -
10.162 - }
10.163 - catch(const std::exception &e) {
10.164 - cout << "Uncaught exception: " << e.what() << endl;
10.165 - return 1;
10.166 - }
10.167 - catch(...) {
10.168 - cout << "Something horrible happened: an exception which isn't "
10.169 - << "std::exception" << endl;
10.170 - return 2;
10.171 - }
10.172 -
10.173 -
10.174 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
10.175 - << endl;
10.176 -
10.177 - return passed ? 0 : 1;
10.178 -}