diff options
| author | Ross Barnowski <rossbar@berkeley.edu> | 2021-12-17 08:03:44 -0800 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-12-17 08:03:44 -0800 |
| commit | 0f5ec4228b04700a612cddf7e181f385e2f2c679 (patch) | |
| tree | f52b42781cf1c6b68815df2eb7032ab153cfed38 /examples/algorithms | |
| parent | f2debbc61a39edbf4c094b82d250a675a7159837 (diff) | |
| download | networkx-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.py | 130 |
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() |
