graph-tool Digest, Vol 46, Issue 4

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

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


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...


Thanks Tiago, for your answer and your amazing graph package! Your comment
was of great help.

attachment.html (93 Bytes)