On 11/24/2011 02:43 PM, Matthias Ekman wrote:
Note that maximum matching on _directed_ graphs, as defined in your reference [2], can be mapped to the _undirected_ problem using an undirected bipartite graph [...]
Indeed, but as far as I know graph_tool doesn't offer any bipartite representations, right? Sorry, may be I am missing something trivial, both graph_tool and bipartite graphs are somehow new to me, ... or is it simple as creating a new adjacency matrix A', where an example graph A (n=3 vertices):
0 1 1 0 1 0 0 0 1
becomes:
A' with n' = n*2
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
vertices A'_i and A'_i+n represent the same vertex, but appear twice, once as starting- and once as ending vertex
A' could be than used as input for the maximum matching algorithm?
Yes, this idea is correct. But of course your augmented adjacency matrix A' is missing the lower diagonal terms, since it needs to be symmetric (the graph is undirected). Bipartite graphs are normal graphs, with the property that the vertices can be divided in two groups, such that there are no edges between members of the same group. Therefore graph_tool handles bipartite graphs just as any other type of graph... Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>