<jupyter_start><jupyter_text>メモpython で graph theory のグラフをどう描くか、試行錯誤。 実験参考1. networkx 本家 tutorial  https://networkx.org/documentation/stable/tutorial.html1. グラフ理論  Lecture 3: Graphs, Relations and a Matrix  http://schmidt.ucg.ie/cs4423/networks03.pdf1. sagemath での描き方 sage: g=graphs.GrotzschGraph()1. https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f <=qiita1. https://www.analyticsvidhya.com/blog/2018/09/introduction-graph-theory-applications-python/1. https://www.python-course.eu/networkx.php1. https://igraph.org/python/doc/tutorial/tutorial.html igraph tutorial1. plotly, pypi networkx で作ったグラフ理論のグラフを colab (jupyter) で表示するのに1. matplotlib.pyplot の show を使う方法1. networkx の draw を使う方法1. IPython.display の SVG と Image を使う方法1. pygraphviz を使う方法の 4通りある。基本的に matplotlib の show を使う。  networkx の draw は裏で matplotlib を使っているので、出力は同じと思われる。pygraphviz はツールのインストールが必要なので colab で使うのは現実的でない。SVG に変換する networkx の関数は裏で pygraphiviz を使っていて、pygraphviz のインストールが必要である。 なので同じ。<jupyter_code>import networkx as nx
nx.__version__
# 参考
# pygraphviz を使いたい場合次のようにすれば colab (jupyter) で描ける
# !apt install libgraphviz-dev
# !pip install pygraphviz
#
# としておいて別のコードセルで
#
# import pygraphviz
# import networkx as nx
# from IPython.display import Image
# G = nx.DiGraph()
# data_array = [1,2,3,4,5,6,7,8]
# nx.add_cycle(G, data_array)
# Image(nx.nx_agraph.view_pygraphviz(G, prog='fdp')[0])
#
# nx.nx_agraph.view_pygraphviz(G, prog='fdp') の結果が (png, object) のタプルなので [0] で png を取り出している
# png の表示方法に IPython.display のt Image を使ったがもっと一般的な方法があるかもしれない<jupyter_output><empty_output><jupyter_text>グラフを描く<jupyter_code># グラフを描く
import networkx as nx
G = nx.Graph()
data_array =['A','B','C']
nx.add_cycle(G, data_array)
nx.draw_networkx(G)
plt.show (G)
# 実験 数字と混ぜられるか
import networkx as nx
G = nx.Graph()
data_array =['A','B','C']
nx.add_cycle(G, data_array)
G.add_nodes_from([2, 3])
nx.draw_networkx(G)
plt.show (G)
# 実験 数字と混ぜられるか
import networkx as nx
G = nx.Graph()
data_array =['A','B','C',2,3]
nx.add_cycle(G, data_array)
nx.draw_networkx(G)
plt.show (G)<jupyter_output><empty_output><jupyter_text>有向グラフ DiGraph<jupyter_code>import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()  # 有向グラフ (Directed Graph)
data_array = [1,2,3,4,5,6,7,8]

nx.add_cycle(G, data_array)

nx.draw_networkx(G)
plt.show (G)
# 上のセルと同じものを SVG にしてから出力
# pygraphviz をインストールしないとエラーになる
# import networkx as nx
# from IPython.display import SVG

# G = nx.DiGraph()  # 有向グラフ (Directed Graph)
# data_array = [1,2,3,4,5,6,7,8]

# nx.add_cycle(G, data_array)

# display(SVG(nx.nx_agraph.to_agraph(G).draw(prog='fdp', format='svg')))
import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])
plt.show (nx.draw_networkx(G))

# 辺の追加 (頂点も必要に応じて追加される)
G.add_edge(1, 2)                                    
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])
plt.show (nx.draw_networkx(G))

# 辺の削除
G.remove_edge(3, 4)                    
G.remove_edges_from([(1, 3), (2, 5)])
plt.show (nx.draw_networkx(G))

# 頂点の削除 (削除された頂点に接続されている辺も削除される)
G.remove_node(5)
G.remove_nodes_from([3, 4])
plt.show (nx.draw_networkx(G))

# 指定したパス上の頂点と辺を追加
nx.add_path(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5
plt.show (nx.draw_networkx(G))

# 指定した閉路上の頂点と辺を追加
nx.add_cycle(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5 → 1
plt.show (nx.draw_networkx(G))

# 放射状に頂点と辺を追加
nx.add_star(G, [1, 2, 3, 4, 5])  # 1 → 2, 1 → 3, 1 → 4, 1 → 5
plt.show (nx.draw_networkx(G))

# 実験
import matplotlib.pyplot as plt
import networkx as nx

G = nx.DiGraph()
nx.add_path(G, [3, 5, 4, 1, 0, 2, 7, 8, 9, 6])
nx.add_path(G, [3, 0, 6, 4, 2, 7, 1, 9, 8, 5])

nx.draw_networkx(G)
plt.show()
# 実験 頂点の名前を変えるにはどうしたらよいか
# 以下の方法では変わらない
import matplotlib.pyplot as plt
import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 3)])

# G.nodes[頂点][属性キー] = 属性値
G.nodes[1]['a'] = 'Alice'
nx.draw_networkx(G)
plt.show()

# G.edges[辺][属性キー] = 属性値
G.edges[1, 2]['b'] = 'Bob'

# G.succ[始点][終点][属性キー] = 属性値
G.succ[2][3]['c'] = 'Carol'

# G.pred[終点][始点][属性キー] = 属性値
G.pred[3][1]['d'] = 'Dave'

print(dict(G.nodes))
# {1: {'a': 'Alice'}, 2: {}, 3: {}}

print(dict(G.edges))
# {(1, 2): {'b': 'Bob'}, (1, 3): {'d': 'Dave'}, (2, 3): {'c': 'Carol'}}

print(G.succ)
# {1: {2: {'b': 'Bob'}, 3: {'d': 'Dave'}}, 2: {3: {'c': 'Carol'}}, 3: {}}

print(G.pred)
# {1: {2: {'b': 'Bob'}, 3: {'d': 'Dave'}}, 2: {3: {'c': 'Carol'}}, 3: {}}
nx.draw_networkx(G)
plt.show()
# 実験 node の名前が長かった場合
import networkx as nx
G = nx.Graph()
G.add_node("Allways at the Center")
nx.draw_networkx(G)
plt.show (G)
# node だけを追加する
import networkx as nx
G = nx.Graph()
G.add_node("A")
G.add_nodes_from([2, 3])
nx.draw_networkx(G)
plt.show (G)
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_node("A")
G.add_nodes_from([2, 3])
G.add_nodes_from([
    (4, {"node_color": "red"}), # ここで色を指定しても反映しない
    (5, {"color": "green"}),
])
nx.draw_networkx(G, node_color='grey')
plt.show (G)

# node の属性はどうしたら反映されるか。 とりあえず色が変わらない。
# 2つのグラフの node を足す
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_node("A")
G.add_node("B")
H = nx.path_graph(10)
nx.draw_networkx(H)
plt.show (H)

G.add_nodes_from(H)

nx.draw_networkx(G)
plt.show (G)

# 辺を追加する add_edge(,), add_edges_from([()])
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_edge(1, 2)
e = (2, 3)
G.add_edge(*e)  # unpack edge tuple*
G.add_edges_from([(4,1),(4,2)])
nx.draw_networkx(G)
plt.show (G)<jupyter_output><empty_output><jupyter_text>グラフ理論と線形代数と集合論graph theory , linear algebra, matrix multiplication , set theory<jupyter_code>import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
G = nx.Graph(["AB","BC","BD","CD","DE"])
opts = {"with_labels": True, "node_color": 'yellow'}
nx.draw(G, **opts)
nx.draw_networkx(G, node_color='red')
plt.show(G)<jupyter_output><empty_output><jupyter_text>隣接行列 adjacency matrixグラフ理論および計算機科学において、隣接行列は、有限グラフを表わすために使われる正方行列である。 $A = \begin{pmatrix}0 & 1 & 0 & 0 & 0\\1 & 0 & 1 & 1 & 0\\0 & 1 & 0 & 1 & 0\\0 & 1 & 1 & 0 & 1\\0 & 0 & 0 & 1 & 0\end{pmatrix}$ 行と列はグラフの頂点に対応し、対応する頂点がエッジで結合されているかどうかに関係なく、行と列がある。 行や列が頂点に対応し、その中のエントリが繋がりを表すことによってエッジを示す。グラフ G の隣接行列 A は```A=nx.adjacency_matrix(G)```で算出される。<jupyter_code>import networkx as nx
from sympy import *
init_printing()
G = nx.Graph(["AB","BC","BD","CD","DE"])
A=nx.adjacency_matrix(G)
print(A)
print(type(A))
print(type(A.toarray()))
print(A.toarray())
display(Matrix(A.toarray()))
print(latex(Matrix(A.toarray())))<jupyter_output>(0, 1)	1
  (1, 0)	1
  (1, 2)	1
  (1, 3)	1
  (2, 1)	1
  (2, 3)	1
  (3, 1)	1
  (3, 2)	1
  (3, 4)	1
  (4, 3)	1
<class 'scipy.sparse.csr.csr_matrix'>
<class 'numpy.ndarray'>
[[0 1 0 0 0]
 [1 0 1 1 0]
 [0 1 0 1 0]
 [0 1 1 0 1]
 [0 0 0 1 0]]<jupyter_text>この行列 $A=(a_ij)$ は対角線について対称である。すべての $i,j$ について $a_ij = a_ji$ である。頂点からそれ自身への辺 loop を許容しない場合、対角要素は全て 0 になる。頂点のラベル名を無視すれば、隣接行列からグラフを再現できる。<jupyter_code>import matplotlib.pyplot as plt
# H=nx.from_numpy_matrix(A.toarray())
H=nx.from_numpy_array(A.toarray())
opts = {"with_labels": True, "node_color": 'green'}
nx.draw(H, **opts)
opts = {"with_labels": True, "node_color": 'red'}
nx.draw_networkx(H, **opts)
plt.show (H)
print((A**0).toarray())
print((A*A).toarray())
print((A.toarray()**0))
print((A.toarray()*A.toarray()))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18474993167532114, 'fraction_numerical': 0.03853511888494124, 'mean_word_length': 5.063794531897266, 'pattern_counts': {'":': 8, '<': 27, '<?xml version=': 0, '>': 26, 'https://': 5, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '83182', 'license': 'MIT', 'n_tokens_mistral': 4160, 'n_tokens_neox': 3892, 'n_words': 722, 'path': 'python_graphtheory.ipynb', 'repo_name': 'kalz2q/myjupyternotebooks', 'size': '7318'}