max_cardinality_matching for directed graphs and "controllability"

graph-tool
1

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_cardinality_matching
[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

attachment.html (1.51 KB)

2

Hi Matthias,

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