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