I was wondering if the max_cardinality_matching functions is defined for /directed/ graphs as suggested by the documentation example [0]? I am asking, because the linked boost reference [1] describes the matching only for /undirected/ graphs.
The algorithm is only defined for undirected graphs, and if one passes a directed graph, as in the documentation, the direction of the edges is ignored.
alright, thanks for clearing that up!
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?
Best, Matthias
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
Thanks Tiago, for your answer and your amazing graph package! Your comment was of great help.
-
Matthias Ekman -
Tiago de Paula Peixoto