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