Hi,
I'm looking to use graph-tool for some work involving percolation theory. So far it is a clear preference over the alternatives (networkx, etc).
BUT, I have just tried to use the max flow algorithms with the following result:
File "/usr/lib/python2.7/site-packages/graph_tool/flow/__init__.py", line 238, in push_relabel_max_flow _prop("e", g, residual)) RuntimeError: No static implementation was found for the desired routine. This is a graph_tool bug. :-( Please follow but report instructions at http://graph-tool.skewed.de. What follows is debug information.
Graph view: boost::UndirectedAdaptor<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::property<boost::edge_index_t, unsigned long, boost::no_property>, boost::no_property, boost::listS>, boost::keep_all, graph_tool::detail::MaskFilter<boost::unchecked_vector_property_map<unsigned char, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> >
Action: boost::_bi::bind_t<void, get_push_relabel_max_flow, boost::_bi::list7<boost::arg<1>, boost::_bi::value<boost::adj_list_edge_property_map<boost::bidirectional_tag, unsigned long, unsigned long&, unsigned long, boost::property<boost::edge_index_t, unsigned long, boost::no_property>, boost::edge_index_t> >, boost::_bi::value<unsigned long>, boost::_bi::value<unsigned long>, boost::_bi::value<unsigned long>, boost::arg<2>, boost::arg<3> > >
Arg 1: boost::checked_vector_property_map<double, boost::adj_list_edge_property_map<boost::bidirectional_tag, unsigned long, unsigned long&, unsigned long, boost::property<boost::edge_index_t, unsigned long, boost::no_property>, boost::edge_index_t> >
Arg 2: boost::checked_vector_property_map<double, boost::adj_list_edge_property_map<boost::bidirectional_tag, unsigned long, unsigned long&, unsigned long, boost::property<boost::edge_index_t, unsigned long, boost::no_property>, boost::edge_index_t> >
All of the max flow methods return this exception. Is there something wrong with my set-up? Or is this a genuine bug? Max flow is critical to my project and I would prefer not to sacrifice speed and use networkx.
Thanks, Jeremy
Hi Jeremy,
On 01/12/2011 10:48 PM, jeremy wrote:
I'm looking to use graph-tool for some work involving percolation theory. So far it is a clear preference over the alternatives (networkx, etc).
BUT, I have just tried to use the max flow algorithms with the following result:
File "/usr/lib/python2.7/site-packages/graph_tool/flow/__init__.py", line 238, in push_relabel_max_flow _prop("e", g, residual)) RuntimeError: No static implementation was found for the desired routine. This is a graph_tool bug. :-( Please follow but report instructions at http://graph-tool.skewed.de. What follows is debug information.
Graph view: boost::UndirectedAdaptor<boost::filtered_graph<boost::adjacency_list<boost::vecS,
[...]
All of the max flow methods return this exception. Is there something wrong with my set-up? Or is this a genuine bug? Max flow is critical to my project and I would prefer not to sacrifice speed and use networkx.
Oops, this is indeed a bug. It seems I have restricted the C++ code to directed graphs only, and forgot to add a check in the python side of things. I'll do this shortly.
Note however that you cannot use the max-flow algorithms in graph-tool (which come from the BGL) to calculate the max-flow of undirected graphs, since they are all formulated for directed graphs only (see http://lists.boost.org/boost-users/2005/03/10724.php).
If you are really sure you want to do this for undirected graphs (the max-flow problem is usually posed for directed graphs), I guess your best option is to transform it into a directed graph with duplicated edges going in both directions...
Cheers, Tiago
-- Tiago de Paula Peixoto tiago@skewed.de
Thanks for the info Tiago, your suggestion appears to be working, although still evaluating whether the results are meaningful. I'm pretty much a newbie in the art of graph analysis so I appreciate your support.
I've found the push_relabel method to be unreliable, failing more often than not. But, the kolmogorov method seems to work every time. As this method is now showing as deprecated in the boost library will you be updating graph_tool to use the boykov_kolmogorov method?
Cheers, Jeremy.
On 01/13/2011 02:40 PM, jeremy wrote:
Thanks for the info Tiago, your suggestion appears to be working, although still evaluating whether the results are meaningful. I'm pretty much a newbie in the art of graph analysis so I appreciate your support.
I've committed a fixed for the directed check in the git version. I also modified the graph augmentation code which should make things faster for the kolmogorov method, since reversed edges which already exist are now detected and used.
I've found the push_relabel method to be unreliable, failing more often than not. But, the kolmogorov method seems to work every time.
This is interesting... Could you perhaps give me a short example where the push_relabel method fails and the kolmogorov method doesn't?
As this method is now showing as deprecated in the boost library will you be updating graph_tool to use the boykov_kolmogorov method?
Only the name of the method changed, not the algorithm itself... But now I also changed the name of the function to boykov_kolmogorov_max_flow() in graph-tool to reflect the change in boost (and also to be fair to Boykov :-).
Cheers, Tiago
-- Tiago de Paula Peixoto tiago@skewed.de
-
jeremy -
Tiago de Paula Peixoto