Hi Matthias, On 11/23/2011 12:41 PM, Matthias Ekman wrote: > 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. 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 constructed as follows. Each vertex is cloned into two versions: An "input" vertex, and an "output" vertex. A given input vertex is connected to output vertices according to the directed edges present in the original graph. The resulting graph is undirected and bipartite, and finding the maximum matching on it is equivalent to the maximum matching on the directed graph, as defined in ref. [2]. Cheers, Tiago -- Tiago de Paula Peixoto <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
