{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Subgraphs\nExample of partitioning a directed graph with nodes labeled as\nsupported and unsupported nodes into a list of subgraphs\nthat contain only entirely supported or entirely unsupported nodes.\nAdopted from \nhttps://github.com/lobpcg/python_examples/blob/master/networkx_example.py\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import networkx as nx\nimport matplotlib.pyplot as plt\n\n\ndef graph_partitioning(G, plotting=True):\n \"\"\"Partition a directed graph into a list of subgraphs that contain\n only entirely supported or entirely unsupported nodes.\n \"\"\"\n # Categorize nodes by their node_type attribute\n supported_nodes = {n for n, d in G.nodes(data=\"node_type\") if d == \"supported\"}\n unsupported_nodes = {n for n, d in G.nodes(data=\"node_type\") if d == \"unsupported\"}\n\n # Make a copy of the graph.\n H = G.copy()\n # Remove all edges connecting supported and unsupported nodes.\n H.remove_edges_from(\n (n, nbr, d)\n for n, nbrs in G.adj.items()\n if n in supported_nodes\n for nbr, d in nbrs.items()\n if nbr in unsupported_nodes\n )\n H.remove_edges_from(\n (n, nbr, d)\n for n, nbrs in G.adj.items()\n if n in unsupported_nodes\n for nbr, d in nbrs.items()\n if nbr in supported_nodes\n )\n\n # Collect all removed edges for reconstruction.\n G_minus_H = nx.DiGraph()\n G_minus_H.add_edges_from(set(G.edges) - set(H.edges))\n\n if plotting:\n # Plot the stripped graph with the edges removed.\n _node_colors = [c for _, c in H.nodes(data=\"node_color\")]\n _pos = nx.spring_layout(H)\n plt.figure(figsize=(8, 8))\n nx.draw_networkx_edges(H, _pos, alpha=0.3, edge_color=\"k\")\n nx.draw_networkx_nodes(H, _pos, node_color=_node_colors)\n nx.draw_networkx_labels(H, _pos, font_size=14)\n plt.axis(\"off\")\n plt.title(\"The stripped graph with the edges removed.\")\n plt.show()\n # Plot the edges removed.\n _pos = nx.spring_layout(G_minus_H)\n plt.figure(figsize=(8, 8))\n ncl = [G.nodes[n][\"node_color\"] for n in G_minus_H.nodes]\n nx.draw_networkx_edges(G_minus_H, _pos, alpha=0.3, edge_color=\"k\")\n nx.draw_networkx_nodes(G_minus_H, _pos, node_color=ncl)\n nx.draw_networkx_labels(G_minus_H, _pos, font_size=14)\n plt.axis(\"off\")\n plt.title(\"The removed edges.\")\n plt.show()\n\n # Find the connected components in the stripped undirected graph.\n # And use the sets, specifying the components, to partition\n # the original directed graph into a list of directed subgraphs\n # that contain only entirely supported or entirely unsupported nodes.\n subgraphs = [\n H.subgraph(c).copy() for c in nx.connected_components(H.to_undirected())\n ]\n\n return subgraphs, G_minus_H"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Create an example directed graph.\n\nThis directed graph has one input node labeled `in` and plotted in blue color\nand one output node labeled `out` and plotted in magenta color.\nThe other six nodes are classified as four `supported` plotted in green color\nand two `unsupported` plotted in red color. The goal is computing a list\nof subgraphs that contain only entirely `supported` or `unsupported` nodes.\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"G_ex = nx.DiGraph()\nG_ex.add_nodes_from([\"In\"], node_type=\"input\", node_color=\"b\")\nG_ex.add_nodes_from([\"A\", \"C\", \"E\", \"F\"], node_type=\"supported\", node_color=\"g\")\nG_ex.add_nodes_from([\"B\", \"D\"], node_type=\"unsupported\", node_color=\"r\")\nG_ex.add_nodes_from([\"Out\"], node_type=\"output\", node_color=\"m\")\nG_ex.add_edges_from(\n [\n (\"In\", \"A\"),\n (\"A\", \"B\"),\n (\"B\", \"C\"),\n (\"B\", \"D\"),\n (\"D\", \"E\"),\n (\"C\", \"F\"),\n (\"E\", \"F\"),\n (\"F\", \"Out\"),\n ]\n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Plot the original graph.\n\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"node_color_list = [nc for _, nc in G_ex.nodes(data=\"node_color\")]\npos = nx.spectral_layout(G_ex)\nplt.figure(figsize=(8, 8))\nnx.draw_networkx_edges(G_ex, pos, alpha=0.3, edge_color=\"k\")\nnx.draw_networkx_nodes(G_ex, pos, alpha=0.8, node_color=node_color_list)\nnx.draw_networkx_labels(G_ex, pos, font_size=14)\nplt.axis(\"off\")\nplt.title(\"The original graph.\")\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Calculate the subgraphs with plotting all results of intermediate steps.\n\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"subgraphs_of_G_ex, removed_edges = graph_partitioning(G_ex, plotting=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Plot the results: every subgraph in the list.\n\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for subgraph in subgraphs_of_G_ex:\n _pos = nx.spring_layout(subgraph)\n plt.figure(figsize=(8, 8))\n nx.draw_networkx_edges(subgraph, _pos, alpha=0.3, edge_color=\"k\")\n node_color_list_c = [nc for _, nc in subgraph.nodes(data=\"node_color\")]\n nx.draw_networkx_nodes(subgraph, _pos, node_color=node_color_list_c)\n nx.draw_networkx_labels(subgraph, _pos, font_size=14)\n plt.axis(\"off\")\n plt.title(\"One of the subgraphs.\")\n plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Put the graph back from the list of subgraphs\n\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"G_ex_r = nx.DiGraph()\n# Composing all subgraphs.\nfor subgraph in subgraphs_of_G_ex:\n G_ex_r = nx.compose(G_ex_r, subgraph)\n# Adding the previously stored edges.\nG_ex_r.add_edges_from(removed_edges.edges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Check that the original graph and the reconstructed graphs are isomorphic.\n\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"assert nx.is_isomorphic(G_ex, G_ex_r)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Plot the reconstructed graph.\n\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"node_color_list = [nc for _, nc in G_ex_r.nodes(data=\"node_color\")]\npos = nx.spectral_layout(G_ex_r)\nplt.figure(figsize=(8, 8))\nnx.draw_networkx_edges(G_ex_r, pos, alpha=0.3, edge_color=\"k\")\nnx.draw_networkx_nodes(G_ex_r, pos, alpha=0.8, node_color=node_color_list)\nnx.draw_networkx_labels(G_ex_r, pos, font_size=14)\nplt.axis(\"off\")\nplt.title(\"The reconstructed graph.\")\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.7"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Generated by dwww version 1.16 on Wed Apr 8 10:57:29 CEST 2026.