1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Atlas\n\nAtlas of all connected graphs with up to 6 nodes.\n\nThis example uses Graphviz via PyGraphviz.\n\nThe image should show 142 graphs.\nWe don't plot the empty graph nor the single node graph.\n(142 is the sum of values 2 to n=6 in sequence oeis.org/A001349).\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import random\n\nimport matplotlib.pyplot as plt\nimport networkx as nx\n\n\nGraphMatcher = nx.isomorphism.vf2userfunc.GraphMatcher\n\n\ndef atlas6():\n \"\"\"Return the atlas of all connected graphs with at most 6 nodes\"\"\"\n\n Atlas = nx.graph_atlas_g()[3:209] # 0, 1, 2 => no edges. 208 is last 6 node graph\n U = nx.Graph() # graph for union of all graphs in atlas\n for G in Atlas:\n # check if connected\n if nx.number_connected_components(G) == 1:\n # check if isomorphic to a previous graph\n if not GraphMatcher(U, G).subgraph_is_isomorphic():\n U = nx.disjoint_union(U, G)\n return U\n\n\nG = atlas6()\n\nprint(G)\nprint(nx.number_connected_components(G), \"connected components\")\n\nplt.figure(1, figsize=(8, 8))\n# layout graphs with positions using graphviz neato\npos = nx.nx_agraph.graphviz_layout(G, prog=\"neato\")\n# color nodes the same in each connected subgraph\nC = (G.subgraph(c) for c in nx.connected_components(G))\nfor g in C:\n c = [random.random()] * nx.number_of_nodes(g) # random color...\n nx.draw(g, pos, node_size=40, node_color=c, vmin=0.0, vmax=1.0, with_labels=False)\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.9.15"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
|
