Hierarchical Index

00001 #ifndef SCIL_CUTTREE_H
00002 #define SCIL_CUTTREE_H
00003 /* 
00004  * Implementation of the Cut Tree algorithm by Gusfield
00005  */
00006 #include<vector>
00007 #include<map>
00008 #include<boost/graph/graph_traits.hpp>
00009 
00010 namespace SCIL{
00011 
00012 /* Given a undirected, capacitated Graph, this function computes an equivalent flow tree T
00013    The edges of T are pairs (i,p[i]), i>0 
00014    such an edge has value fl[i]. 
00015    See:
00016    Dan Gusfield, "VERY SIMPLE METHODS FOR ALL PAIRS NETWORK FLOW ANALYSIS" 1990
00017 */
00018 template< typename Graph >
00019 void computeCutTree(Graph& G, 
00020                     std::map<typename boost::graph_traits<Graph>::edge_descriptor, double> cap,
00021                     std::map<typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor>& p, 
00022                     std::map<typename boost::graph_traits<Graph>::vertex_descriptor, double>& fl );
00023 }
00024 
00025 // Load implementation
00026 #include <../src/core/cutTree.cc>
00027 
00028 #endif  /* SCIL_CUTTREE_H */
cutTree.h
