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