今回は、さまざまなグラフ操作の方法について説明します。グラフは、頂点と辺で構成される非線形データ構造です。都市間の地図、ユーザーのソーシャルメディア上のつながり、ウェブページのつながりなどを表現するのに使われます。
グラフ操作の作業
グラフの実装について勉強したことがない方は、Pythonのグラフの実装についての記事を読むことを検討してみてください。さて、前置きはこのくらいにして、ここからはさまざまなグラフの操作について説明します。
1. 隣接表が与えられているときにグラフの頂点を表示する
次のようなグラフの例を考えてみましょう。
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
|
このグラフの隣接リスト表現が次のように与えられたとします。
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
|
結果を出力すると、以下の様になります。
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
vertices=set(graph.keys())
print("The vertices of the graph are:")
print(vertices)
|
隣接リストを表す辞書のキーがグラフの頂点を表していることがわかるので、以下のように辞書のkeys()メソッドを使ってキーを抽出すれば、グラフの頂点を表示することができる。
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
The vertices of the graph are:{0, 1, 2, 3, 4, 5}
|
を結果を出力すると、以下の様になります。
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
E = list()
for u in graph.keys():
for v in graph[u]:
edge = {u, v}
if edge not in E:
E.append(edge)
print("The edges of the graph are:")
print(E)
|
2. 隣接リストのとき、グラフの辺を表示する
グラフの辺を表示するために、グラフの各頂点(u)を走査し、各頂点に関連する隣接頂点のリストを走査して、頂点uに接続している各頂点(v)を見ることになる。各頂点uとvについて、辺の集合に順序のないペア(u,v)を追加することにします。
頂点vがuの隣接リストにあれば、uはvの隣接リストにも存在します。このため、隣接リストには各辺が2回含まれる。グラフの辺を表示するのは、少し難しい。
そこで、頂点uとvを結ぶ辺を表す非順序集合{u,v}を作り、各辺{u,v}を含む辺を表すリストEを作成します。
これにより、{u,v}が既に辺のリストに含まれている場合、{v,u}と{u,v}は同一とみなされるため、{v,u}をセットから除外することができる。
その後、E内の各ペアをグラフのエッジを表すタプルに変換します。こうすることで、重複を避け、以下のようにエッジを表現することができる。
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
The edges of the graph are:[{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}]
|
結果を出力すると、以下の様になります。
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
# adding vertex '6' to graphgraph.update({6: []})
print("The new vertices of the graph are:")
print(set(graph.keys()))
|
3. グラフへの頂点の追加
グラフに頂点を追加するには、グラフを表す辞書に、次のように別のキーとそれに関連する隣接リストとして空のリストを追加するだけでよい。
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
The new vertices of the graph are:{0, 1, 2, 3, 4, 5, 6}
|
結果を出力すると、以下の様になります。
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2],6:[]}
print("The adjacency List representing the graph is:")
print(graph)
# adding edges (5,6) and (4,6) to graphnew_edges = [(5, 6), (4, 6)]
for edge in new_edges:
u=edge[0]
v=edge[1]
graph[u].append(v)
graph[v].append(u)
#display new edgesE = list()
for u in graph.keys():
for v in graph[u]:
edge = {u, v}
if edge not in E:
E.append(edge)
print("The new edges of the graph are:")
print(E)
|
4. グラフに辺を追加する
グラフにエッジ(u,v)を追加するには、まずエッジ「u」と「v」の両方がグラフに存在するかどうかを確認します。どちらかが存在しない場合は、処理を中断します。
uとvの両方が存在する場合は、uをvの隣接リストに追加し、vをuの隣接リストに追加します。
これは次のように行うことができる。
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
The new edges of the graph are:[{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}, {4, 6}, {5, 6}]
|
結果を出力すると、以下の様になります。
まとめ
今回は、グラフに頂点や辺を追加したり、グラフの辺や頂点を表示するなど、グラフに対してさまざまな操作を行う方法についてご紹介しました。今後も有益な記事をお届けします。
それでは、よいお年を