Hi,
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.
I am trying to get the "driver nodes" of a network as described by [2]. The authors showed, that the amount of "driver nodes needed to maintain full control of the network is determined by the ‘maximum matching’ in the network". May be even anyone has seen an implementation of this approach somewhere?
[0] http://projects.skewed.de/graph-tool/doc/flow.html#graph_tool.flow.max_cardi... [1] http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/maximum_matching.html [2] Liu, Y.-Y., Slotine, J.-J., & Barabási, A.-L. (2011). Controllability of complex networks. *Nature*, *473*(7346), 167–173. doi:10.1038/nature10011
Thanks, Matthias
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
-
Matthias Ekman -
Tiago de Paula Peixoto