|
|
""" |
|
|
========================== |
|
|
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._dispatch |
|
|
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._dispatch |
|
|
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._dispatch |
|
|
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._dispatch |
|
|
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._dispatch(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._dispatch(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)) |
|
|
|
