Pynote

Python、機械学習、画像処理について

グラフ理論 - networkx で点、辺を追加、削除する方法

グラフを Jupyter Notebook で描画するヘルパー関数

from IPython.display import Image, display

def draw_graph(G):
    A = nx.nx_agraph.to_agraph(G)
    A.node_attr.update(fixedsize=True, width=0.4, height=0.4)
    png = A.draw(format='png', prog='dot')
    display(Image(png))

networkx での点、辺の扱い

networkx では点は hashable なオブジェクトであれば、なんでもよい。

# int
G = nx.Graph([(1, 2), (2, 3), (3, 1)])
draw_graph(G)


# float
G = nx.Graph([(1.3, 2.6), (2.6, 3.9), (3.9, 1.3)])
draw_graph(G)


# str
G = nx.Graph([('A', 'B'), ('B', 'C'), ('C', 'A')])
draw_graph(G)


2つの点のタプル (点, 点) として表される。

属性

点や辺に任意の名前の属性を付加することができる。

G = nx.Graph()
G.add_node(1, size=10)
G.add_edge(1, 2, weight=20, capacity=10)

1つの点または辺に属性は複数付加でき、{属性名: 値, 属性名: 値, ...} という dict で管理される。

networkx のグラフの種類

networkx には、グラフの種類に応じて、4つのクラスが存在する。

種類 向きつけ ループ 多重辺
Graph 無向
DiGraph 有向
MultiGraph 無向
MultiDiGraph 有向

Graph

Graph は無向で多重辺が許されないグラフを表す。

import networkx as nx

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


  • 頂点集合 V(G) = \{1, 2, 3, 4\}
  • 辺集合 E(G) = \{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{2, 4\}\}

DiGraph

DiGraph は有向で多重辺が許されないグラフを表す。

import networkx as nx

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


  • 頂点集合 V(G) = \{1, 2, 3, 4\}
  • 辺集合 E(G) = \{(1, 2), (1, 3), (2, 3), (2, 4)\}

MultiGraph

MultiGraph は無向で多重辺が許されるグラフを表す。

import networkx as nx

G = nx.MultiGraph()
G.add_edges_from([[1, 2], [1, 2], [1, 3], [2, 3], [2, 4]])
draw_graph(G)


MultiDiGraph

MultiDiGraph は有向で多重辺が許されるグラフを表す。

import networkx as nx

G = nx.MultiDiGraph()  # 有向多重グラフ
G.add_edges_from([[1, 2], [1, 2], [1, 3], [2, 3], [2, 4]])
draw_graph(G)

コンストラク

関数名 Graph DiGraph MultiGraph MultiDiGraph
__init__

空グラフを作成する。

G = nx.Graph()

辺のリストからグラフを作成する。

[(点, 点), (点, 点), ...]
G = nx.Graph([(1, 2), (2, 3), (3, 4)])

[隣接リスト] リストの辞書 (dict of lists) からグラフを作成する。

{点: [点, 点, ...],
 点: [点, 点, ...],
 ...}
e = {1: [2, 3],
     2: [3, 4]}
G = nx.Graph(e)
draw_graph(G)


[隣接リスト] 辞書の辞書 (dict of dicts) からグラフを作成する。

{点: {点: 属性, 点: 属性, ...},
 点: {点: 属性, 点: 属性, ...},
 ...}
e = {1: {2: {'weight': 1}, 3: {'weight': 2}},
     2: {3: {'weight': 2}, 4: {'weight': 3}}}
G = nx.Graph(e)
draw_graph(G)

[隣接行列] numpy 配列 からグラフを作成する。

# 隣接行列
A = np.array([[0, 1, 2, 0],
              [1, 0, 2, 3],
              [2, 2, 0, 0],
              [0, 3, 0, 0]])
G = nx.Graph(A)
draw_graph(G)


G と同じグラフを作成する。

G2 = nx.Graph(G)

AGraph (pygraphviz のグラフオブジェクト) からグラフを作成する。

from pygraphviz import AGraph

# pygraphviz の AGraph を作成する。
e = {1: [2, 3],
     2: [3, 4]}
A = AGraph(e)

G = nx.Graph(A)

点、辺を追加、削除する関数一覧

関数名 Graph DiGraph MultiGraph MultiDiGraph
add_node
add_nodes_from
remove_node
remove_nodes_from
add_edge
add_edges_from
add_weighted_edges_from
remove_edge
remove_edges_from
clear
update

点を追加、削除する。

add_node: 1つの点を追加する。

G.add_node(1)  # 点1を追加する。

点を追加する際に、属性を付与できる。

G.add_node(1, size=10)  # 点1 (属性 size=10) を追加する。

add_nodes_from: 複数の点を追加する。

# 点の list
n = [1, 2]
G.add_nodes_from(n)

# 点の set
n = set([1, 2])
G.add_nodes_from(n)

# 点の dict {点: 属性, 点: 属性, ...}
n = {1: {'size': 3}, 2: {'size': 5}}
G.add_nodes_from(n)

# 各要素が (点, 属性) のタプルであるリスト
n = [(1, {'size': 3}), (2, {'size': 5}), 3]
G.add_nodes_from(n)

点を追加する際に、属性を付与できる。

n = [1, 2]
G.add_nodes_from(n, size=10)  # 点1、2 (属性 size=10) を追加する。

remove_node: 1つの点削除する。

G.remove_node(1)  # 点1を削除する。

remove_nodes_from: 複数の点を削除する。

G.remove_nodes_from([1, 2])  # 点1、2を削除する。

辺を追加、削除する。

add_edge: 1つの辺を追加する。

G.add_edge(1, 2)  # 辺 (1, 2) を追加する。

辺を追加する際に、属性を付与できる。

G.add_edge(1, 2, weight=10)  # 辺 (1, 2) (属性 weight=10) を追加する。

add_edges_from: 複数の辺を追加する。

# [(点, 点), (点, 点), ...]
e = [(1, 2), (2, 3), (3, 1)]
G.add_edges_from(e)

# [(点, 点, 属性), (点, 点, 属性), ...]
e = [(1, 2, {'weight': 3}), (2, 3, {'weight': 5}), (3, 1)]
G.add_edges_from(e)

add_weighted_edges_from: 複数の重み付きの辺を追加する。

# [(点, 点, 重み), (点, 点, 重み), ...]
e = [(1, 2, 3), (2, 3, 5)]
G.add_weighted_edges_from(e)  # 辺 (1, 2) 重み3、辺 (2, 3) 重み5を追加する。

remove_edge: 1つの辺を削除する。

G.remove_edge(1, 2)  # 辺 (1, 2) を削除する。

remove_edges_from: 複数の辺を削除する。

G.remove_edges_from([(1, 2), (2, 3)])  # 辺 (1, 2)、辺 (2, 3) を削除する。

その他

clear: グラフのすべての点及び辺を削除する。

G.clear()

update: グラフ、点、辺を追加する。

import networkx as nx

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

G.update(nodes=[5, 6])  # 点 5,6 を追加する。

G.update(edges=[(3, 4), (1, 4)])  # 辺 (3, 4), (1, 4) を追加する。
draw_graph(G)

第1引数にグラフオブジェクトを指定した場合、そのグラフの点及び辺を追加する。

import networkx as nx

G = nx.Graph([(1, 2), (1, 3), (2, 3), (2, 4)])

G.update(nodes=[5, 6])  # 点 5,6 を追加する。

G.update(edges=[(3, 4), (1, 4)])  # 辺 (3, 4), (1, 4) を追加する。

道、回路、星を追加する。

道 (path) を追加する。

G = nx.Graph()
G.add_path([1, 2, 3])
draw_graph(G)

回路 (cycle) を追加する。

G = nx.Graph()
G.add_cycle([1, 2, 3])
draw_graph(G)

星 (star) を追加する。

G = nx.Graph()
G.add_star([1, 2, 3, 4])
draw_graph(G)