{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Lowest Common Ancestors\n\nCompute and visualize LCA for node pairs\n\nIn a randomly generated directed tree, the lowest common \nancestors are computed for certain node pairs. These node \npairs and their LCA are then visualized with a chosen \ncolor scheme.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import networkx as nx\nimport matplotlib.pyplot as plt\n\n# Generate a random tree with its node positions\nG = nx.random_tree(14, seed=100, create_using=nx.DiGraph)\npos = nx.nx_agraph.graphviz_layout(G, prog=\"dot\")\n\n# Compute lowest-common ancestors for certain node pairs\nancestors = list(nx.all_pairs_lowest_common_ancestor(G, ((1, 3), (4, 9), (13, 10))))\n\n# Create node color and edge color lists\nnode_color_map = []\nedge_color_map = []\nfor i in range(14):\n node_color_map.append(\"#D5D7D8\")\n edge_color_map.append(\"None\")\ntemplate = [\"#FFE799\", \"#FFD23F\", \"#CEB6E2\", \"#A77CCB\", \"#88DFE7\", \"#45CDD9\"]\nx = 0\nfor i in ancestors:\n for j in i[0]:\n node_color_map[j] = template[x]\n x += 1\n node_color_map[i[1]] = template[x]\n edge_color_map[i[1]] = \"black\"\n x += 1\n\n# Plot tree\nplt.figure(figsize=(15, 15))\nplt.title(\"Visualize Lowest Common Ancestors of node pairs\")\nnx.draw_networkx_nodes(\n G, pos, node_color=node_color_map, node_size=2000, edgecolors=edge_color_map\n)\nnx.draw_networkx_edges(G, pos)\nnx.draw_networkx_labels(G, pos, font_size=15)\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:27 CEST 2026.