summaryrefslogtreecommitdiff
path: root/examples/algorithms
diff options
context:
space:
mode:
authorRoss Barnowski <rossbar@berkeley.edu>2021-12-17 08:03:44 -0800
committerGitHub <noreply@github.com>2021-12-17 08:03:44 -0800
commit0f5ec4228b04700a612cddf7e181f385e2f2c679 (patch)
treef52b42781cf1c6b68815df2eb7032ab153cfed38 /examples/algorithms
parentf2debbc61a39edbf4c094b82d250a675a7159837 (diff)
downloadnetworkx-0f5ec4228b04700a612cddf7e181f385e2f2c679.tar.gz
Touchups and suggestions for subgraph gallery example (#5225)
* Simplify construction of G with edges rm'd * Rm unused graph attribute. * Shorten categorization by node type. * Simplify node coloring. * Simplify isomorphism check. * Rm unit test. * Rm redundant plotting of each subgraph.
Diffstat (limited to 'examples/algorithms')
-rw-r--r--examples/algorithms/plot_subgraphs.py130
1 files changed, 21 insertions, 109 deletions
diff --git a/examples/algorithms/plot_subgraphs.py b/examples/algorithms/plot_subgraphs.py
index 41d18859..08127028 100644
--- a/examples/algorithms/plot_subgraphs.py
+++ b/examples/algorithms/plot_subgraphs.py
@@ -17,14 +17,9 @@ def graph_partitioning(G, plotting=True):
"""Partition a directed graph into a list of subgraphs that contain
only entirely supported or entirely unsupported nodes.
"""
- # Determine indexes of all supported and unsupported nodes.
- node_supported_index = []
- node_unsupported_index = []
- for v in G.nodes(data=True):
- if v[1]["node_type"] == "supported":
- node_supported_index.append(v[0])
- if v[1]["node_type"] == "unsupported":
- node_unsupported_index.append(v[0])
+ # 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()
@@ -32,44 +27,29 @@ def graph_partitioning(G, plotting=True):
H.remove_edges_from(
(n, nbr, d)
for n, nbrs in G.adj.items()
- if n in node_supported_index
+ if n in supported_nodes
for nbr, d in nbrs.items()
- if nbr in node_unsupported_index
+ if nbr in unsupported_nodes
)
H.remove_edges_from(
(n, nbr, d)
for n, nbrs in G.adj.items()
- if n in node_unsupported_index
+ if n in unsupported_nodes
for nbr, d in nbrs.items()
- if nbr in node_supported_index
+ if nbr in supported_nodes
)
- H.graph.update(G.graph)
- G_minus_H = nx.DiGraph()
# Collect all removed edges for reconstruction.
- G_minus_H.add_edges_from(
- (n, nbr, d)
- for n, nbrs in G.adj.items()
- if n in node_supported_index
- for nbr, d in nbrs.items()
- if nbr in node_unsupported_index
- )
- G_minus_H.add_edges_from(
- (n, nbr, d)
- for n, nbrs in G.adj.items()
- if n in node_unsupported_index
- for nbr, d in nbrs.items()
- if nbr in node_supported_index
- )
- G_minus_H.graph.update(G.graph)
+ 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_color_list = [v[1]["node_color"] for v in H.nodes(data=True)]
+ _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_color_list)
+ 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.")
@@ -77,36 +57,21 @@ def graph_partitioning(G, plotting=True):
# 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")
- Gn = G.nodes(data=True)
- Gmn = G_minus_H.nodes(data=True)
- nd = {v: dict(Gn[v]) for v in dict(Gn) if v in dict(Gmn)}
- ncl = [nd[v]["node_color"] for v in nd]
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 edges removed.")
+ plt.title("The removed edges.")
plt.show()
- # Find the connected componets in the stripped undirected graph.
+ # 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.
- # Plot the resulting subgraphs.
- subgraphs = []
- for c in nx.connected_components(H.to_undirected()):
- H_c = H.subgraph(c).copy()
- subgraphs.append(H_c)
- if plotting:
- _pos = nx.spring_layout(H_c)
- plt.figure(figsize=(8, 8))
- nx.draw_networkx_edges(H_c, _pos, alpha=0.3, edge_color="k")
- _node_color_list_c = [v[1]["node_color"] for v in H_c.nodes(data=True)]
- nx.draw_networkx_nodes(H_c, _pos, node_color=_node_color_list_c)
- nx.draw_networkx_labels(H_c, _pos, font_size=14)
- plt.axis("off")
- plt.title("One of the subgraphs.")
- plt.show()
+ subgraphs = [
+ H.subgraph(c).copy() for c in nx.connected_components(H.to_undirected())
+ ]
return subgraphs, G_minus_H
@@ -142,7 +107,7 @@ G_ex.add_edges_from(
# Plot the original graph.
# ------------------------
#
-node_color_list = [v[1]["node_color"] for v in G_ex.nodes(data=True)]
+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")
@@ -166,7 +131,7 @@ 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 = [v[1]["node_color"] for v in subgraph.nodes(data=True)]
+ 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")
@@ -188,14 +153,13 @@ G_ex_r.add_edges_from(removed_edges.edges())
# Check that the original graph and the reconstructed graphs are isomorphic.
# --------------------------------------------------------------------------
#
-check = nx.is_isomorphic(G_ex, G_ex_r)
-print("The reconstruction is", check)
+assert nx.is_isomorphic(G_ex, G_ex_r)
###############################################################################
# Plot the reconstructed graph.
# -----------------------------
#
-node_color_list = [v[1]["node_color"] for v in G_ex_r.nodes(data=True)]
+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")
@@ -204,55 +168,3 @@ nx.draw_networkx_labels(G_ex_r, pos, font_size=14)
plt.axis("off")
plt.title("The reconstructed graph.")
plt.show()
-
-
-###############################################################################
-# A unit test function for graph_partitioning.
-# --------------------------------------------
-#
-def test_graph_partitioning():
- """Unit test for graph partitioning."""
- # Unit test example generator.
- G_u = nx.DiGraph()
- G_u.add_nodes_from(["In"], node_type="input", node_color="b")
- G_u.add_nodes_from(["A"], node_type="supported", node_color="g")
- G_u.add_nodes_from(["B", "D"], node_type="unsupported", node_color="r")
- G_u.add_nodes_from(["Out"], node_type="output", node_color="m")
- G_u.add_edges_from([("In", "A"), ("A", "B"), ("B", "D"), ("D", "Out")])
-
- G_us = nx.DiGraph()
- G_us.add_nodes_from(["In"], node_type="input", node_color="b")
- G_us.add_nodes_from(["A"], node_type="supported", node_color="g")
- G_us.add_edges_from([("In", "A")])
-
- G_uu = nx.DiGraph()
- G_uu.add_nodes_from(["B", "D"], node_type="unsupported", node_color="r")
- G_uu.add_nodes_from(["Out"], node_type="output", node_color="m")
- G_uu.add_edges_from([("B", "D"), ("D", "Out")])
-
- subgraphs_of_G_u_true = [G_us, G_uu]
-
- subgraphs_of_G_u, _removed_edges = graph_partitioning(G_u, plotting=False)
-
- _check = nx.is_isomorphic(
- subgraphs_of_G_u[0], subgraphs_of_G_u_true[0]
- ) and nx.is_isomorphic(subgraphs_of_G_u[1], subgraphs_of_G_u_true[1])
-
- # Putting the graph back from the list of subgraphs
- G_u_r = nx.DiGraph()
- # Composing all subgraphs.
- for _subgraph in subgraphs_of_G_u:
- G_u_r = nx.compose(G_u_r, _subgraph)
- # Adding the previously stored edges.
- G_u_r.add_edges_from(_removed_edges.edges())
-
- _check = _check and nx.is_isomorphic(G_u, G_u_r)
-
- assert _check
-
-
-###############################################################################
-# Run the unit test function for graph_partitioning.
-# --------------------------------------------------
-#
-test_graph_partitioning()