bipartite_matching

A bipartite graph is a graph in which we can divide nodes into two independent sets, such that every relationship connects nodes between these sets. No connection can be established within the set. Matching in bipartite graphs (bipartite matching) is described as a set of relationships that are picked in a way to not share an endpoint. Furthermore, maximum matching is such matching of maximum cardinality of the chosen relationships set. The algorithm runs in O(VE)\mathcal{O}(|V|*|E|) time where VV represents a set of vertices (nodes) and EE represents a set of edges (relationships).

TraitValue
Module typealgorithm
ImplementationC++
Graph directionundirected
Edge weightsunweighted
Parallelismsequential

Procedures

max()

The procedure divide nodes into two independent sets, such that every relationship connects nodes between these sets.

Output:

  • maximum_bipartite_matching: integer ➡ Maximum bipartite matching, the cardinality of maximum matching relationship subset. If graph is not bipartite, returned value is zero(0).

Usage:

To divide nodes into two independent sets, use the following query:

CALL bipartite_matching.max()
YIELD maximum_bipartite_matching;

Example

Database state

The database contains the following data:

Created with the following Cypher queries:

MERGE (a:Node {id: 0}) MERGE (b:Node {id: 3}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 0}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 3}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 2}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);

Get maximung biparte matching

Get the values using the following query:

CALL bipartite_matching.max()
YIELD maximum_bipartite_matching
RETURN maximum_bipartite_matching;

Results:

+----------------------------+
| maximum_bipartite_matching |
+----------------------------+
| 3                          |
+----------------------------+