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() residual_G.add_nodes_from(G) residual_G.add_edges_from(directed_edges) 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