Possible bug in flow?

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. :frowning: 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,

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. :frowning: 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
Boost users' mailing page: Re: [Boost-users] BGL: Undirected graphs and max flow).

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

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.

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