hopcroftKarp

Takes as input a bipartite graph and produces as output a maximum cardinality matching – a set of as many edges as possible with the property that no two edges share an endpoint.

Calling this function with a non-bipartite graph results in undefined behaviour.

count_t hopcroftKarp(nodes_u_it U, nodes_v_it V, adjacency_t adjacency)
count_t
hopcroftKarp
(
count_t = size_t
nodes_u_it
nodes_v_it
adjacency_t
)
(
nodes_u_it U
,
nodes_v_it V
,
adjacency_t adjacency
)
if (
isForwardRange!nodes_u_it &&
isForwardRange!nodes_v_it
&&
is(ElementType!nodes_u_it == ElementType!nodes_v_it)
&&
isIntegral!(ElementType!nodes_u_it)
&&
isUnsigned!(ElementType!nodes_u_it)
&&
isRandomAccessRange!adjacency_t
&&
isForwardRange!(ElementType!adjacency_t)
&&
is(ElementType!(ElementType!adjacency_t) == ElementType!nodes_u_it)
&&
isIntegral!count_t
&&
isUnsigned!count_t
)
count_t hopcroftKarp(nodes_u_it U, nodes_v_it V, adjacency_t adjacency, node_t[node_t] pairU, node_t[node_t] pairV)

Examples

Example

//            ____
//           /    \.
// 0   1   2 | 3   4
// |  / \ /| | |\  |
// | /   X | / | \ |
// |/   / \|/  |  \|
// 5   6   7   8   9
//
uint[][] adjacency;
adjacency.length = 10;

alias connect = (from, uint[] neighbors...) {
    adjacency[from] ~= neighbors;
};

connect(0u,  5u);
connect(1u,  5u, 7u);
connect(2u,  6u, 7u);
connect(3u,  8u, 9u);
connect(4u,  7u, 9u);
connect(5u,  0u, 1u);
connect(6u,  2u);
connect(7u,  2u, 4u);
connect(8u,  3u);
connect(9u,  3u, 4u);

auto count = hopcroftKarp(iota(5u), iota(5u, 10u), adjacency);

assert(count == 5);

hopcroftKarp

Examples

Meta

Source