# 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
$\mathcal{O}(|V|*|E|)$ time where $V$ represents a set of vertices (nodes) and $E$ represents a
set of edges (relationships).

| Trait               | Value      |
| ------------------- | ---------- |
| **Module type**     | algorithm  |
| **Implementation**  | C++        |
| **Graph direction** | undirected |
| **Edge weights**    | unweighted |
| **Parallelism**     | sequential |

## Procedures

> **Info**
>
> You can execute this algorithm on [graph projections, subgraphs or portions of the graph](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph).

### `max()`

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

#### Input:

- `subgraph: Graph` (**OPTIONAL**) ➡ A specific subgraph, which is an [object of type Graph](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph) returned by the `project()` function, on which the algorithm is run. 
If subgraph is not specified, the algorithm is computed on the entire graph by default.

#### 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:

```cypher
CALL bipartite_matching.max()
YIELD maximum_bipartite_matching;
```

## Example

### Database state
 

The database contains the following data: 

![](https://memgraph.com/docs/pages/advanced-algorithms/available-algorithms/bipartite_matching/bipartite-matching-1.png)

Created with the following Cypher queries:

```cypher
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 maximum bipartite matching
 

Get the values using the following query:

```cypher
CALL bipartite_matching.max()
YIELD maximum_bipartite_matching
RETURN maximum_bipartite_matching;
```

Results:

```plaintext
+----------------------------+
| maximum_bipartite_matching |
+----------------------------+
| 3                          |
+----------------------------+
```