Integrating edmond's algorithm in boost graph with graph_tool


I am trying to integrate a boost graph implementation
<; of Tarjan's optimal branching
algorithm with graph_tool

The code is in pure C++ and I want to wrap it using boost python.

The ultimate goal is I can pass in a `graph_tool.Graph` instance to the
wrapped function directly.

For example:

from graph_tool.generation import complete_graph
from pyedmond import optimal_branching  # suppose I made it already,
pyedmond is the name of the module after  wrapping

g = complete_graph(1000, directed=True)
optimal_branching(g) # it runs and give the correct result.

attachment.html (2 KB)

You have to use the C++ representation of the graph that is used internally
by graph-tool, but this is not documented. You have to look in source code,
e.g. as is done for k-core:

I have written some simple documentation to explain how to add simple extensions, and
I will be adding it to the main documentation soon.


PS. If you want Edmonds algorithm implemented in graph-tool, the most useful
work is to change the code in so that it
works for the sparse case. The dense algorithm used there is too slow for
big networks, but it can be changed by using priority queues.

Sounds good. Thanks!

attachment.html (2.34 KB)