{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Dedensification\n\nExamples of dedensification of a graph. Dedensification retains the structural\npattern of the original graph and will only add compressor nodes when doing so\nwould result in fewer edges in the compressed graph.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\nimport networkx as nx\n\nplt.suptitle(\"Dedensification\")\n\noriginal_graph = nx.DiGraph()\nwhite_nodes = [\"1\", \"2\", \"3\", \"4\", \"5\", \"6\"]\nred_nodes = [\"A\", \"B\", \"C\"]\nnode_sizes = [250 for node in white_nodes + red_nodes]\nnode_colors = [\"white\" for n in white_nodes] + [\"red\" for n in red_nodes]\n\noriginal_graph.add_nodes_from(white_nodes + red_nodes)\noriginal_graph.add_edges_from(\n [\n (\"1\", \"C\"),\n (\"1\", \"B\"),\n (\"2\", \"C\"),\n (\"2\", \"B\"),\n (\"2\", \"A\"),\n (\"3\", \"B\"),\n (\"3\", \"A\"),\n (\"3\", \"6\"),\n (\"4\", \"C\"),\n (\"4\", \"B\"),\n (\"4\", \"A\"),\n (\"5\", \"B\"),\n (\"5\", \"A\"),\n (\"6\", \"5\"),\n (\"A\", \"6\"),\n ]\n)\nbase_options = {\"with_labels\": True, \"edgecolors\": \"black\"}\npos = {\n \"3\": (0, 1),\n \"2\": (0, 2),\n \"1\": (0, 3),\n \"6\": (1, 0),\n \"A\": (1, 1),\n \"B\": (1, 2),\n \"C\": (1, 3),\n \"4\": (2, 3),\n \"5\": (2, 1),\n}\nax1 = plt.subplot(1, 2, 1)\nplt.title(\"Original (%s edges)\" % original_graph.number_of_edges())\nnx.draw_networkx(original_graph, pos=pos, node_color=node_colors, **base_options)\n\nnonexp_graph, compression_nodes = nx.summarization.dedensify(\n original_graph, threshold=2, copy=False\n)\nnonexp_node_colors = list(node_colors)\nnonexp_node_sizes = list(node_sizes)\nfor node in compression_nodes:\n nonexp_node_colors.append(\"yellow\")\n nonexp_node_sizes.append(600)\nplt.subplot(1, 2, 2)\n\nplt.title(\"Dedensified (%s edges)\" % nonexp_graph.number_of_edges())\nnonexp_pos = {\n \"5\": (0, 0),\n \"B\": (0, 2),\n \"1\": (0, 3),\n \"6\": (1, 0.75),\n \"3\": (1.5, 1.5),\n \"A\": (2, 0),\n \"C\": (2, 3),\n \"4\": (3, 1.5),\n \"2\": (3, 2.5),\n}\nc_nodes = list(compression_nodes)\nc_nodes.sort()\nfor spot, node in enumerate(c_nodes):\n nonexp_pos[node] = (2, spot + 2)\nnx.draw_networkx(\n nonexp_graph,\n pos=nonexp_pos,\n node_color=nonexp_node_colors,\n node_size=nonexp_node_sizes,\n **base_options,\n)\n\nplt.tight_layout()\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:56:41 CEST 2026.