// -*- 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 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 which finds 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). /// ///\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; typedef ResGraphWrapper ResGraphType; class ModLengthMap { typedef typename ResGraphType::template NodeMap NodeMap; const ResGraphType& G; const EdgeIntMap& rev; const LengthMap &ol; const NodeMap &pot; public : typedef typename LengthMap::KeyType KeyType; typedef typename LengthMap::ValueType ValueType; ValueType operator[](typename ResGraphType::Edge e) const { //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){ // std::cout<<"Negative length!!"< > paths; //typedef DirPath DPath; //DPath paths; Length total_length; public : MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ } ///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) { ConstMap const1map(1); //We need a residual graph, in which some of the edges are reversed ResGraphType res_graph(G, const1map, reversed); //Initialize the copy of the Dijkstra potential to zero typename ResGraphType::template NodeMap dijkstra_dist(res_graph); ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); Dijkstra dijkstra(res_graph, mod_length); int i; for (i=0; i void getPath(DirPath& p, int j){ p.clear(); typename DirPath::Builder B(p); for(typename std::vector::iterator i=paths[j].begin(); i!=paths[j].end(); ++i ){ B.pushBack(*j); } B.commit(); } }; //class MinLengthPaths ///@} } //namespace hugo #endif //HUGO_MINLENGTHPATHS_H