| """ |
| ========================== |
| Bipartite Graph Algorithms |
| ========================== |
| """ |
|
|
| import networkx as nx |
| from networkx.algorithms.components import connected_components |
| from networkx.exception import AmbiguousSolution |
|
|
| __all__ = [ |
| "is_bipartite", |
| "is_bipartite_node_set", |
| "color", |
| "sets", |
| "density", |
| "degrees", |
| ] |
|
|
|
|
| @nx._dispatchable |
| def color(G): |
| """Returns a two-coloring of the graph. |
| |
| Raises an exception if the graph is not bipartite. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| |
| Returns |
| ------- |
| color : dictionary |
| A dictionary keyed by node with a 1 or 0 as data for each node color. |
| |
| Raises |
| ------ |
| NetworkXError |
| If the graph is not two-colorable. |
| |
| Examples |
| -------- |
| >>> from networkx.algorithms import bipartite |
| >>> G = nx.path_graph(4) |
| >>> c = bipartite.color(G) |
| >>> print(c) |
| {0: 1, 1: 0, 2: 1, 3: 0} |
| |
| You can use this to set a node attribute indicating the bipartite set: |
| |
| >>> nx.set_node_attributes(G, c, "bipartite") |
| >>> print(G.nodes[0]["bipartite"]) |
| 1 |
| >>> print(G.nodes[1]["bipartite"]) |
| 0 |
| """ |
| if G.is_directed(): |
| import itertools |
|
|
| def neighbors(v): |
| return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)]) |
|
|
| else: |
| neighbors = G.neighbors |
|
|
| color = {} |
| for n in G: |
| if n in color or len(G[n]) == 0: |
| continue |
| queue = [n] |
| color[n] = 1 |
| while queue: |
| v = queue.pop() |
| c = 1 - color[v] |
| for w in neighbors(v): |
| if w in color: |
| if color[w] == color[v]: |
| raise nx.NetworkXError("Graph is not bipartite.") |
| else: |
| color[w] = c |
| queue.append(w) |
| |
| color.update(dict.fromkeys(nx.isolates(G), 0)) |
| return color |
|
|
|
|
| @nx._dispatchable |
| def is_bipartite(G): |
| """Returns True if graph G is bipartite, False if not. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| |
| Examples |
| -------- |
| >>> from networkx.algorithms import bipartite |
| >>> G = nx.path_graph(4) |
| >>> print(bipartite.is_bipartite(G)) |
| True |
| |
| See Also |
| -------- |
| color, is_bipartite_node_set |
| """ |
| try: |
| color(G) |
| return True |
| except nx.NetworkXError: |
| return False |
|
|
|
|
| @nx._dispatchable |
| def is_bipartite_node_set(G, nodes): |
| """Returns True if nodes and G/nodes are a bipartition of G. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| |
| nodes: list or container |
| Check if nodes are a one of a bipartite set. |
| |
| Examples |
| -------- |
| >>> from networkx.algorithms import bipartite |
| >>> G = nx.path_graph(4) |
| >>> X = set([1, 3]) |
| >>> bipartite.is_bipartite_node_set(G, X) |
| True |
| |
| Notes |
| ----- |
| An exception is raised if the input nodes are not distinct, because in this |
| case some bipartite algorithms will yield incorrect results. |
| For connected graphs the bipartite sets are unique. This function handles |
| disconnected graphs. |
| """ |
| S = set(nodes) |
|
|
| if len(S) < len(nodes): |
| |
| raise AmbiguousSolution( |
| "The input node set contains duplicates.\n" |
| "This may lead to incorrect results when using it in bipartite algorithms.\n" |
| "Consider using set(nodes) as the input" |
| ) |
|
|
| for CC in (G.subgraph(c).copy() for c in connected_components(G)): |
| X, Y = sets(CC) |
| if not ( |
| (X.issubset(S) and Y.isdisjoint(S)) or (Y.issubset(S) and X.isdisjoint(S)) |
| ): |
| return False |
| return True |
|
|
|
|
| @nx._dispatchable |
| def sets(G, top_nodes=None): |
| """Returns bipartite node sets of graph G. |
| |
| Raises an exception if the graph is not bipartite or if the input |
| graph is disconnected and thus more than one valid solution exists. |
| See :mod:`bipartite documentation <networkx.algorithms.bipartite>` |
| for further details on how bipartite graphs are handled in NetworkX. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| |
| top_nodes : container, optional |
| Container with all nodes in one bipartite node set. If not supplied |
| it will be computed. But if more than one solution exists an exception |
| will be raised. |
| |
| Returns |
| ------- |
| X : set |
| Nodes from one side of the bipartite graph. |
| Y : set |
| Nodes from the other side. |
| |
| Raises |
| ------ |
| AmbiguousSolution |
| Raised if the input bipartite graph is disconnected and no container |
| with all nodes in one bipartite set is provided. When determining |
| the nodes in each bipartite set more than one valid solution is |
| possible if the input graph is disconnected. |
| NetworkXError |
| Raised if the input graph is not bipartite. |
| |
| Examples |
| -------- |
| >>> from networkx.algorithms import bipartite |
| >>> G = nx.path_graph(4) |
| >>> X, Y = bipartite.sets(G) |
| >>> list(X) |
| [0, 2] |
| >>> list(Y) |
| [1, 3] |
| |
| See Also |
| -------- |
| color |
| |
| """ |
| if G.is_directed(): |
| is_connected = nx.is_weakly_connected |
| else: |
| is_connected = nx.is_connected |
| if top_nodes is not None: |
| X = set(top_nodes) |
| Y = set(G) - X |
| else: |
| if not is_connected(G): |
| msg = "Disconnected graph: Ambiguous solution for bipartite sets." |
| raise nx.AmbiguousSolution(msg) |
| c = color(G) |
| X = {n for n, is_top in c.items() if is_top} |
| Y = {n for n, is_top in c.items() if not is_top} |
| return (X, Y) |
|
|
|
|
| @nx._dispatchable(graphs="B") |
| def density(B, nodes): |
| """Returns density of bipartite graph B. |
| |
| Parameters |
| ---------- |
| B : NetworkX graph |
| |
| nodes: list or container |
| Nodes in one node set of the bipartite graph. |
| |
| Returns |
| ------- |
| d : float |
| The bipartite density |
| |
| Examples |
| -------- |
| >>> from networkx.algorithms import bipartite |
| >>> G = nx.complete_bipartite_graph(3, 2) |
| >>> X = set([0, 1, 2]) |
| >>> bipartite.density(G, X) |
| 1.0 |
| >>> Y = set([3, 4]) |
| >>> bipartite.density(G, Y) |
| 1.0 |
| |
| Notes |
| ----- |
| The container of nodes passed as argument must contain all nodes |
| in one of the two bipartite node sets to avoid ambiguity in the |
| case of disconnected graphs. |
| See :mod:`bipartite documentation <networkx.algorithms.bipartite>` |
| for further details on how bipartite graphs are handled in NetworkX. |
| |
| See Also |
| -------- |
| color |
| """ |
| n = len(B) |
| m = nx.number_of_edges(B) |
| nb = len(nodes) |
| nt = n - nb |
| if m == 0: |
| d = 0.0 |
| else: |
| if B.is_directed(): |
| d = m / (2 * nb * nt) |
| else: |
| d = m / (nb * nt) |
| return d |
|
|
|
|
| @nx._dispatchable(graphs="B", edge_attrs="weight") |
| def degrees(B, nodes, weight=None): |
| """Returns the degrees of the two node sets in the bipartite graph B. |
| |
| Parameters |
| ---------- |
| B : NetworkX graph |
| |
| nodes: list or container |
| Nodes in one node set of the bipartite graph. |
| |
| weight : string or None, optional (default=None) |
| The edge attribute that holds the numerical value used as a weight. |
| If None, then each edge has weight 1. |
| The degree is the sum of the edge weights adjacent to the node. |
| |
| Returns |
| ------- |
| (degX,degY) : tuple of dictionaries |
| The degrees of the two bipartite sets as dictionaries keyed by node. |
| |
| Examples |
| -------- |
| >>> from networkx.algorithms import bipartite |
| >>> G = nx.complete_bipartite_graph(3, 2) |
| >>> Y = set([3, 4]) |
| >>> degX, degY = bipartite.degrees(G, Y) |
| >>> dict(degX) |
| {0: 2, 1: 2, 2: 2} |
| |
| Notes |
| ----- |
| The container of nodes passed as argument must contain all nodes |
| in one of the two bipartite node sets to avoid ambiguity in the |
| case of disconnected graphs. |
| See :mod:`bipartite documentation <networkx.algorithms.bipartite>` |
| for further details on how bipartite graphs are handled in NetworkX. |
| |
| See Also |
| -------- |
| color, density |
| """ |
| bottom = set(nodes) |
| top = set(B) - bottom |
| return (B.degree(top, weight), B.degree(bottom, weight)) |
|
|
