Integrating edmond's algorithm in boost graph with graph_tool
Hi, I am trying to integrate a boost graph implementation <https://github.com/atofigh/edmonds-alg> 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. ``` ----------------- My attempt (with code example <https://github.com/xiaohan2012/pyedmond>): instead of using `graph_tool.Graph`, I created another graph type using boost graph (in C++), say the name is `MyGraph`. Then I pass the edges and weights in `graph_tool.Graph` (in Python) to `MyGraph` (in C++) via boost python so that a new MyGraph is created. Last I pass in the MyGraph instance to the optimal branching function in C++. I do this "graph copying" because `graph_tool.Graph` does not match the signature of the optimal branching function, which requires: ``` boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> ``` ---------------- My question is: Can I circumvent the graph copying procedure? -- Best Han
On 20.09.2017 20:49, 肖晗 wrote:
Can I circumvent the graph copying procedure?
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: https://git.skewed.de/count0/graph-tool/blob/master/src/graph/topology/graph... https://git.skewed.de/count0/graph-tool/blob/master/src/graph/topology/graph... I have written some simple documentation to explain how to add simple extensions, and I will be adding it to the main documentation soon. Best, Tiago PS. If you want Edmonds algorithm implemented in graph-tool, the most useful work is to change the code in http://edmonds-alg.sourceforge.net/ 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. -- Tiago de Paula Peixoto <tiago@skewed.de>
Sounds good. Thanks! On Wed, Sep 20, 2017 at 11:26 PM, Tiago de Paula Peixoto <tiago@skewed.de> wrote:
On 20.09.2017 20:49, 肖晗 wrote:
Can I circumvent the graph copying procedure?
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:
https://git.skewed.de/count0/graph-tool/blob/master/src/ graph/topology/graph_kcore.hh https://git.skewed.de/count0/graph-tool/blob/master/src/ graph/topology/graph_kcore.cc
I have written some simple documentation to explain how to add simple extensions, and I will be adding it to the main documentation soon.
Best, Tiago
PS. If you want Edmonds algorithm implemented in graph-tool, the most useful work is to change the code in http://edmonds-alg.sourceforge.net/ 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.
-- Tiago de Paula Peixoto <tiago@skewed.de> _______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
-- Best Han
participants (2)
-
Tiago de Paula Peixoto -
肖晗