# Source code for networkx.algorithms.bipartite.extendability

```""" Provides a function for computing the extendability of a graph which is
undirected, simple, connected and bipartite and contains at least one perfect matching."""

import networkx as nx
from networkx.utils import not_implemented_for

__all__ = ["maximal_extendability"]

[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def maximal_extendability(G):
"""Computes the extendability of a graph.

The extendability of a graph is defined as the maximum \$k\$ for which `G`
is \$k\$-extendable. Graph `G` is \$k\$-extendable if and only if `G` has a
perfect matching and every set of \$k\$ independent edges can be extended
to a perfect matching in `G`.

Parameters
----------
G : NetworkX Graph
A fully-connected bipartite graph without self-loops

Returns
-------
extendability : int

Raises
------
NetworkXError
If the graph `G` is disconnected.
If the graph `G` is not bipartite.
If the graph `G` does not contain a perfect matching.
If the residual graph of `G` is not strongly connected.

Notes
-----
Definition:
Let `G` be a simple, connected, undirected and bipartite graph with a perfect
matching M and bipartition (U,V). The residual graph of `G`, denoted by \$G_M\$,
is the graph obtained from G by directing the edges of M from V to U and the
edges that do not belong to M from U to V.

Lemma [1]_ :
Let M be a perfect matching of `G`. `G` is \$k\$-extendable if and only if its residual
graph \$G_M\$ is strongly connected and there are \$k\$ vertex-disjoint directed
paths between every vertex of U and every vertex of V.

Assuming that input graph `G` is undirected, simple, connected, bipartite and contains
a perfect matching M, this function constructs the residual graph \$G_M\$ of G and
returns the minimum value among the maximum vertex-disjoint directed paths between
every vertex of U and every vertex of V in \$G_M\$. By combining the definitions
and the lemma, this value represents the extendability of the graph `G`.

Time complexity O(\$n^3\$ \$m^2\$)) where \$n\$ is the number of vertices
and \$m\$ is the number of edges.

References
----------
.. [1] "A polynomial algorithm for the extendability problem in bipartite graphs",
J. Lakhal, L. Litzler, Information Processing Letters, 1998.
.. [2] "On n-extendible graphs", M. D. Plummer, Discrete Mathematics, 31:201–210, 1980
https://doi.org/10.1016/0012-365X(80)90037-0

"""
if not nx.is_connected(G):
raise nx.NetworkXError("Graph G is not connected")

if not nx.bipartite.is_bipartite(G):
raise nx.NetworkXError("Graph G is not bipartite")

U, V = nx.bipartite.sets(G)

maximum_matching = nx.bipartite.hopcroft_karp_matching(G)

if not nx.is_perfect_matching(G, maximum_matching):
raise nx.NetworkXError("Graph G does not contain a perfect matching")

# list of edges in perfect matching, directed from V to U
pm = [(node, maximum_matching[node]) for node in V & maximum_matching.keys()]

# Direct all the edges of G, from V to U if in matching, else from U to V
directed_edges = [
(x, y) if (x in V and (x, y) in pm) or (x in U and (y, x) not in pm) else (y, x)
for x, y in G.edges
]

# Construct the residual graph of G
residual_G = nx.DiGraph()

if not nx.is_strongly_connected(residual_G):
raise nx.NetworkXError("The residual graph of G is not strongly connected")

# For node-pairs between V & U, keep min of max number of node-disjoint paths
# Variable \$k\$ stands for the extendability of graph G
k = float("inf")
for u in U:
for v in V:
num_paths = sum(1 for _ in nx.node_disjoint_paths(residual_G, u, v))
k = k if k < num_paths else num_paths
return k

```