// -*- c++ -*- #ifndef HUGO_MINLENGTHPATHS_H #define HUGO_MINLENGTHPATHS_H ///\ingroup galgs ///\file ///\brief An algorithm for finding k paths of minimal total length. //#include //#include #include #include #include #include namespace hugo { /// \addtogroup galgs /// @{ ///\brief Implementation of an algorithm for finding k paths between 2 nodes /// of minimal total length /// /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements /// an algorithm for finding k edge-disjoint paths /// from a given source node to a given target node in an /// edge-weighted directed graph having minimal total weigth (length). /// ///\warning It is assumed that the lengths are positive, since the /// general flow-decomposition is not implemented yet. /// ///\author Attila Bernath template class MinLengthPaths{ typedef typename LengthMap::ValueType Length; typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::OutEdgeIt OutEdgeIt; typedef typename Graph::template EdgeMap EdgeIntMap; typedef ConstMap ConstMap; //Input const Graph& G; //Auxiliary variables //This is the capacity map for the mincostflow problem ConstMap const1map; //This MinCostFlows instance will actually solve the problem MinCostFlows mincost_flow; //Container to store found paths std::vector< std::vector > paths; public : MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), const1map(1), mincost_flow(_G, _length, const1map){} ///Runs the algorithm. ///Runs the algorithm. ///Returns k if there are at least k edge-disjoint paths from s to t. ///Otherwise it returns the number of found edge-disjoint paths from s to t. int run(Node s, Node t, int k) { int i = mincost_flow.run(s,t,k); //Let's find the paths //We put the paths into stl vectors (as an inner representation). //In the meantime we lose the information stored in 'reversed'. //We suppose the lengths to be positive now. //We don't want to change the flow of mincost_flow, so we make a copy //The name here suggests that the flow has only 0/1 values. EdgeIntMap reversed(G); FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ reversed[e] = mincost_flow.getFlow()[e]; } paths.clear(); //total_length=0; paths.resize(k); for (int j=0; j void getPath(DirPath& p, size_t j){ p.clear(); if (j>paths.size()-1){ return; } typename DirPath::Builder B(p); for(typename std::vector::iterator i=paths[j].begin(); i!=paths[j].end(); ++i ){ B.pushBack(*i); } B.commit(); } }; //class MinLengthPaths ///@} } //namespace hugo #endif //HUGO_MINLENGTHPATHS_H