Spaces:
Runtime error
Runtime error
File size: 6,474 Bytes
35b22df |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
"""
=========
Subgraphs
=========
Example of partitioning a directed graph with nodes labeled as
supported and unsupported nodes into a list of subgraphs
that contain only entirely supported or entirely unsupported nodes.
Adopted from
https://github.com/lobpcg/python_examples/blob/master/networkx_example.py
"""
import networkx as nx
import matplotlib.pyplot as plt
def graph_partitioning(G, plotting=True):
"""Partition a directed graph into a list of subgraphs that contain
only entirely supported or entirely unsupported nodes.
"""
# Categorize nodes by their node_type attribute
supported_nodes = {n for n, d in G.nodes(data="node_type") if d == "supported"}
unsupported_nodes = {n for n, d in G.nodes(data="node_type") if d == "unsupported"}
# Make a copy of the graph.
H = G.copy()
# Remove all edges connecting supported and unsupported nodes.
H.remove_edges_from(
(n, nbr, d)
for n, nbrs in G.adj.items()
if n in supported_nodes
for nbr, d in nbrs.items()
if nbr in unsupported_nodes
)
H.remove_edges_from(
(n, nbr, d)
for n, nbrs in G.adj.items()
if n in unsupported_nodes
for nbr, d in nbrs.items()
if nbr in supported_nodes
)
# Collect all removed edges for reconstruction.
G_minus_H = nx.DiGraph()
G_minus_H.add_edges_from(set(G.edges) - set(H.edges))
if plotting:
# Plot the stripped graph with the edges removed.
_node_colors = [c for _, c in H.nodes(data="node_color")]
_pos = nx.spring_layout(H)
plt.figure(figsize=(8, 8))
nx.draw_networkx_edges(H, _pos, alpha=0.3, edge_color="k")
nx.draw_networkx_nodes(H, _pos, node_color=_node_colors)
nx.draw_networkx_labels(H, _pos, font_size=14)
plt.axis("off")
plt.title("The stripped graph with the edges removed.")
plt.show()
# Plot the the edges removed.
_pos = nx.spring_layout(G_minus_H)
plt.figure(figsize=(8, 8))
ncl = [G.nodes[n]["node_color"] for n in G_minus_H.nodes]
nx.draw_networkx_edges(G_minus_H, _pos, alpha=0.3, edge_color="k")
nx.draw_networkx_nodes(G_minus_H, _pos, node_color=ncl)
nx.draw_networkx_labels(G_minus_H, _pos, font_size=14)
plt.axis("off")
plt.title("The removed edges.")
plt.show()
# Find the connected components in the stripped undirected graph.
# And use the sets, specifying the components, to partition
# the original directed graph into a list of directed subgraphs
# that contain only entirely supported or entirely unsupported nodes.
subgraphs = [
H.subgraph(c).copy() for c in nx.connected_components(H.to_undirected())
]
return subgraphs, G_minus_H
###############################################################################
# Create an example directed graph.
# ---------------------------------
#
# This directed graph has one input node labeled `in` and plotted in blue color
# and one output node labeled `out` and plotted in magenta color.
# The other six nodes are classified as four `supported` plotted in green color
# and two `unsupported` plotted in red color. The goal is computing a list
# of subgraphs that contain only entirely `supported` or `unsupported` nodes.
G_ex = nx.DiGraph()
G_ex.add_nodes_from(["In"], node_type="input", node_color="b")
G_ex.add_nodes_from(["A", "C", "E", "F"], node_type="supported", node_color="g")
G_ex.add_nodes_from(["B", "D"], node_type="unsupported", node_color="r")
G_ex.add_nodes_from(["Out"], node_type="output", node_color="m")
G_ex.add_edges_from(
[
("In", "A"),
("A", "B"),
("B", "C"),
("B", "D"),
("D", "E"),
("C", "F"),
("E", "F"),
("F", "Out"),
]
)
###############################################################################
# Plot the original graph.
# ------------------------
#
node_color_list = [nc for _, nc in G_ex.nodes(data="node_color")]
pos = nx.spectral_layout(G_ex)
plt.figure(figsize=(8, 8))
nx.draw_networkx_edges(G_ex, pos, alpha=0.3, edge_color="k")
nx.draw_networkx_nodes(G_ex, pos, alpha=0.8, node_color=node_color_list)
nx.draw_networkx_labels(G_ex, pos, font_size=14)
plt.axis("off")
plt.title("The original graph.")
plt.show()
###############################################################################
# Calculate the subgraphs with plotting all results of intemediate steps.
# -----------------------------------------------------------------------
#
subgraphs_of_G_ex, removed_edges = graph_partitioning(G_ex, plotting=True)
###############################################################################
# Plot the results: every subgraph in the list.
# ---------------------------------------------
#
for subgraph in subgraphs_of_G_ex:
_pos = nx.spring_layout(subgraph)
plt.figure(figsize=(8, 8))
nx.draw_networkx_edges(subgraph, _pos, alpha=0.3, edge_color="k")
node_color_list_c = [nc for _, nc in subgraph.nodes(data="node_color")]
nx.draw_networkx_nodes(subgraph, _pos, node_color=node_color_list_c)
nx.draw_networkx_labels(subgraph, _pos, font_size=14)
plt.axis("off")
plt.title("One of the subgraphs.")
plt.show()
###############################################################################
# Put the graph back from the list of subgraphs
# ---------------------------------------------
#
G_ex_r = nx.DiGraph()
# Composing all subgraphs.
for subgraph in subgraphs_of_G_ex:
G_ex_r = nx.compose(G_ex_r, subgraph)
# Adding the previously stored edges.
G_ex_r.add_edges_from(removed_edges.edges())
###############################################################################
# Check that the original graph and the reconstructed graphs are isomorphic.
# --------------------------------------------------------------------------
#
assert nx.is_isomorphic(G_ex, G_ex_r)
###############################################################################
# Plot the reconstructed graph.
# -----------------------------
#
node_color_list = [nc for _, nc in G_ex_r.nodes(data="node_color")]
pos = nx.spectral_layout(G_ex_r)
plt.figure(figsize=(8, 8))
nx.draw_networkx_edges(G_ex_r, pos, alpha=0.3, edge_color="k")
nx.draw_networkx_nodes(G_ex_r, pos, alpha=0.8, node_color=node_color_list)
nx.draw_networkx_labels(G_ex_r, pos, font_size=14)
plt.axis("off")
plt.title("The reconstructed graph.")
plt.show()
|