最大流問題

最大流問題は、与えられたグラフにおいて、ある2つの頂点を指定して、それらの間に最大量の流れを流す問題です。

以下は、NetworkXを使用して最大流問題を解く例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import networkx as nx

# グラフを作成
G = nx.DiGraph()

G.add_nodes_from(['S', 'A', 'B', 'C', 'D', 'T'])

G.add_edges_from([('S', 'A', {'capacity': 10}),
                  ('S', 'C', {'capacity': 5}),
                  ('A', 'B', {'capacity': 9}),
                  ('A', 'D', {'capacity': 4}),
                  ('B', 'T', {'capacity': 8}),
                  ('C', 'D', {'capacity': 3}),
                  ('C', 'T', {'capacity': 7}),
                  ('D', 'B', {'capacity': 6}),
                  ('D', 'T', {'capacity': 9})])

# 最大流を求める
max_flow_value, flow_dict = nx.maximum_flow(G, 'S', 'T', capacity='capacity')

# 結果を表示する
print('Maximum Flow Value:', max_flow_value)
print('Flow Dictionary:', flow_dict)

上記の例では、6つの頂点を持つグラフが与えられています。

SとTはそれぞれ始点と終点を表し、他の頂点は中間点として機能します。

各辺は容量を持ち、それが最大流を制限するものです。

maximum_flow関数は、グラフ、始点、終点、容量属性を受け取り、最大流量とフローの辞書を返します。

capacity引数は、各辺の容量を指定する属性名を表します。

実行結果は以下のようになります。

[実行結果]

Maximum Flow Value: 15
Flow Dictionary: {'S': {'A': 10, 'C': 5}, 'A': {'B': 8, 'D': 2}, 'B': {'T': 8}, 'C': {'D': 0, 'T': 5}, 'D': {'B': 0, 'T': 2}, 'T': {}}

この結果により、グラフの始点から終点に15の最大流量が流れることがわかります。

また、各辺のフローも辞書として表示されます。

ループ検出

ループ検出の例題として、以下のような有向グラフを考えてみましょう。

A -> B -> C -> D -> E

このグラフにはループが含まれていません。

しかし、次のようなグラフを考えてみましょう。

A -> B -> C -> D -> E -> A

このグラフには、ノードAからノードEに至るループが含まれています。

このグラフでループを検出するには、NetworkXのsimple_cycles関数を使用することができます。

以下は、コード例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import networkx as nx

# グラフを作成する
G = nx.DiGraph()
nodes = "ABCDE"
for i in range(len(nodes)):
    G.add_node(nodes[i])
    if i < len(nodes) - 1:
        G.add_edge(nodes[i], nodes[i+1])
G.add_edge(nodes[-1], nodes[0])

# ループを検出する
loops = list(nx.simple_cycles(G))
if len(loops) > 0:
    print("ループを検出しました:")
    print(loops)
else:
    print("ループは検出されませんでした。")

出力結果は以下のようになります。

[実行結果]

ループを検出しました:
[['D', 'E', 'A', 'B', 'C']]

このように、simple_cycles関数を使用することで、グラフ上のループを検出することができます。

次数

グラフ理論において、頂点の次数とは、その頂点に接続された辺の本数のことを指します。

グラフ理論では、次数は頂点の重要な特徴量の1つであり、グラフの性質を表すために用いられます。

例えば、無向グラフにおいて全ての頂点の次数が偶数である場合、オイラー路と呼ばれる全ての辺を1度だけ通るパスが存在することが知られています。

問題

以下のグラフの各頂点の次数を求めて下さい。

   1---2---3
      /    |
     /     |
   4-------5

ソースコード

以下のようにPythonコードを書くことができます。

1
2
3
4
5
6
7
8
9

import networkx as nx

# グラフを作成する
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5), (5, 3)])

# 各頂点の次数を計算する
degrees = dict(G.degree())
print(degrees)

実行すると、以下のような出力が得られます。

[実行結果]

{1: 1, 2: 3, 3: 2, 4: 2, 5: 2}

これは、頂点1の次数が1、頂点2の次数が3、頂点3の次数が2、頂点4の次数が2、頂点5の次数が2であることを示しています。

クラスタリング問題

クラスタリング問題とは、データセットをグループに分割する問題です。

グループ内のデータは互いに似ており、異なるグループのデータとは異なる特徴を持っています。

この問題は、機械学習やデータマイニング、ネットワーク解析などの分野でよく用いられます。

クラスタリングによって得られたグループは、同じグループ内のデータが似ているため、そのグループに属するデータの特徴をより深く理解することができます。

また、異なるグループのデータの違いを明確にすることができます。

クラスタリングは、顧客分類、マーケティング分析、医療診断、画像処理、自然言語処理などの分野で幅広く使用されています。

例題

クラスタリング問題の例を１つ挙げます。

Zachary’s karate clubとして知られる、34人のメンバーとそのつながりを示すグラフを用いて、クラスタリングを行います。

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

import networkx as nx
import matplotlib.pyplot as plt
from networkx.algorithms import community

# グラフの読み込み
G = nx.karate_club_graph()

# グラフの可視化
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
plt.show()

# クラスタリング
communities = community.greedy_modularity_communities(G)

# クラスタリング結果の表示
for i, c in enumerate(communities):
    print("Cluster ", i+1, ": ", c)

# クラスタリング結果をグラフに反映
color_map = []
for node in G:
    for i, c in enumerate(communities):
        if node in c:
            color_map.append(i)
nx.draw(G, pos, node_color=color_map, with_labels=True)
plt.show()

このコードでは、まずグラフを読み込み、可視化します。

次に、community.greedy_modularity_communities()を使用して、グラフをクラスタリングします。

最後に、クラスタリング結果をグラフに反映し、色分けして表示します。

この例では、Zachary’s karate clubグラフは3つのクラスターに分割されます。

各クラスターは、それぞれのメンバーのつながりを考慮して形成されていることがわかります。

[実行結果]

自然災害問題

自然災害に関する問題の一つとして、道路ネットワーク上での交通渋滞の発生があります。

以下のようなシナリオを考えてみましょう：

🔹ある地域において、地震が発生し、複数の道路が通行不能になった。
🔹この地域には複数の車両が存在し、それぞれの車両が目的地に到達するために、どのルートを取るかを決定しなければならない。
🔹通行可能なルートは限られており、道路の通行状況は車両数に応じて変化する。
🔹車両が選択するルートによって、交通渋滞が発生する可能性がある。

このような問題を解くために、以下のような手順でNetworkXを使用することができます。

1. 道路ネットワークのグラフを作成する。
   グラフのノードは交差点や道路の始点・終点とし、エッジは道路とし、エッジの重みはその道路の通行可能度合いとする。
2. 車両の現在地と目的地をノードとして指定する。
3. NetworkXの最短経路アルゴリズムを使用して、車両が最短時間で目的地に到達できる経路を計算する。
4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する。

解法・ソースコード

交通渋滞の発生確率を評価する上記の例題をnetworkxを用いて実装します。

具体的には、以下の手順でグラフを作成し、最短経路を計算して、最短経路上での交通渋滞の発生確率を評価しています。

1. グラフを作成する

1
2

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

まず、NetworkXを用いてグラフを作成します。ここでは、4つのノードと4つのエッジを持つグラフを作成しています。

2. エッジに重みを付ける

1
2

for (u, v) in G.edges():
    G[u][v]['weight'] = random.uniform(0.1, 1.0)

次に、各エッジにランダムな重みを付けます。

ここでは、0.1から1.0の範囲の乱数を用いて重みを設定しています。

3. ノード1からノード5への最短経路を計算する

1
2

path = nx.shortest_path(G, source=1, target=5, weight='weight')
print(f"Shortest path: {path}")

nx.shortest_path関数を用いて、ノード1からノード5までの最短経路を計算します。

weight引数には、エッジの重みを指定しています。

計算された最短経路をpath変数に格納し、print関数を用いて表示しています。

4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する

1
2
3
4
5
6
7
8

prob = 1.0
for i in range(len(path) - 1):
    u = path[i]
    v = path[i + 1]
    weight = G[u][v]['weight'] + random.uniform(-0.1, 0.1)
    G[u][v]['weight'] = max(weight - 0.1, 0)  # 通行可能度合いを減少させる
    prob *= weight  # 経路上のエッジの通行可能度合いの積を計算する
print(f"Probability of traffic congestion: {1 - prob:.3f}")

最後に、計算された最短経路上での交通渋滞の発生確率を評価します。

prob変数には、経路上のエッジの通行可能度合いの積を格納します。

forループで、最短経路上の各エッジについて、エッジの通行可能度合いをランダムに減少させ、prob変数にそのエッジの通行可能度合いを乗じます。

最後に、1 - probを計算することで、交通渋滞の発生確率を評価します。

なお、エッジの通行可能度合いの減少幅は、0から0.1の範囲の乱数を用いて決定しています。

以上の手順で、最短経路上での交通渋滞の発生確率を評価することができます。

[実行結果（例）]

Shortest path: [1, 2, 4, 5]
Probability of traffic congestion: 0.953

ノード1からノード5への最短経路は[1, 2, 4, 5]となりました。

そして、この経路上のエッジの通行可能度合いの積を計算することで、交通渋滞の発生確率を評価しました。

結果として、この経路上で交通渋滞が発生する確率は0.953となりました。

最小全域木問題

最小全域木問題 (Minimum Spanning Tree Problem) とは、グラフ理論において、与えられた重みつき無向グラフに対して、そのグラフの全ての頂点を含む木（連結かつ閉路を持たないグラフ）のうち、辺の重みの和が最小になるような木を求める問題です。

問題

以下の図のグラフにおいて、全ての頂点を繋ぐ最小コストの辺集合を求めてください。

     2     3
 A ----- B ----- C
 |   4 / |   5 / |
 |   /   |   /   |
 1 /     4 /     | 1
 | /     | /     |
 |/      |/      |
 D ----- E ----- F
     5     4

解法・ソースコード

最初に、networkxライブラリをnxという名前でインポートします。

次に、空のグラフを作成し、add_weighted_edges_from()メソッドで、頂点間の辺を加えます。

ここで、(‘A’, ‘B’, 2)というように、3つ目の引数で辺の重みを指定しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import networkx as nx

# グラフを作成
G = nx.Graph()
G.add_weighted_edges_from([
    ('A', 'B', 2),
    ('A', 'D', 1),
    ('B', 'C', 3),
    ('B', 'E', 4),
    ('B', 'D', 4),
    ('C', 'E', 5),
    ('C', 'F', 1),
    ('D', 'E', 5),
    ('E', 'F', 4)
])

次に、minimum_spanning_tree()メソッドを使って、最小全域木を求めます。

このメソッドは、引数にグラフを取り、最小全域木を構成する辺集合を返します。

最後に、print()関数を使って、最小全域木を構成する辺集合を表示しています。

edges()メソッドを使うことで、辺集合を取得できます。

1
2
3
4
5

# 最小全域木を求める
mst = nx.minimum_spanning_tree(G)

# 結果を表示
print(mst.edges())

実行すると、以下のように最小全域木を構成する辺集合が表示されます。

[実行結果]

[('A', 'D'), ('A', 'B'), ('B', 'C'), ('B', 'E'), ('E', 'F')]

影響力の分析

影響力の分析についての例題として、Twitter上でのフォロー関係から、影響力の高いユーザーを分析することを考えてみます。

以下のようなツイッターユーザー間のフォロー関係があるとします。

A follows B
A follows C
B follows C
B follows D
C follows A
C follows B
C follows D
D follows A
D follows C

このグラフをNetworkXで表現し、pagerankアルゴリズムを用いて、各ユーザーの影響力を計算するPythonコードを以下に示します。

pagerankアルゴリズムとは、Webページの重要度を計算するアルゴリズムです。

Webページのリンク構造を解析して、そのページが他の多くのページからどの程度の重要度を持つかを計算します。

これを、フォロワー関係からの影響力を分析するのに使ってみます。

[ソースコード]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import networkx as nx

# ツイッターユーザーのフォロー関係を表現するグラフを作成する
G = nx.DiGraph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'C')])

# pagerankアルゴリズムを用いて、各ユーザーの影響力を計算する
pagerank = nx.pagerank(G)

# 影響力が高い順にユーザーを並び替える
sorted_pagerank = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)

# 結果を表示する
for user, score in sorted_pagerank:
    print(f'{user}: {score}')

実行すると、以下のような結果が得られます。

[実行結果]

C: 0.3245609358176832
A: 0.2251463547274389
B: 0.2251463547274389
D: 0.2251463547274389

この結果から、ユーザーCが最も影響力が高いことが分かりました。

問題

以下のグラフにおいて、頂点Aと頂点Eの間にパスが存在するかどうかを判定してください。

  A --- B --- C
  |     |     |
  |     |     |
  D --- E --- F

解法・ソースコード

この問題を解くためには、以下の手順に従います。

1. NetworkXを用いてグラフを作成します。

1
2
3
4
5

import networkx as nx

G = nx.Graph()

G.add_edges_from([('A', 'B'), ('A', 'D'), ('B', 'C'), ('B', 'E'), ('C', 'F'), ('D', 'E'), ('E', 'F')])

2. 頂点Aと頂点Eの間にパスが存在するかどうかを判定します。

NetworkXのhas_path関数を使います。

1
2
3
4

if nx.has_path(G, 'A', 'E'):
    print("頂点Aと頂点Eの間にパスが存在します。")
else:
    print("頂点Aと頂点Eの間にパスは存在しません。")

実行結果は、「頂点Aと頂点Eの間にパスが存在します。」となります。

以上の手順で、グラフにおいて2つの頂点間にパスが存在するかどうかを判定することができました。

最長経路問題

NetworkXを使って簡単な最長路問題を解いてみましょう。

[単純なグラフ]

まず、networkxをインストールして、次のようにインポートします。

1

import networkx as nx

次に、グラフを作成します。ここでは、有向グラフを作成します。

1

G = nx.DiGraph()

グラフにノードを追加します。

1

G.add_nodes_from([1, 2, 3, 4, 5])

ノード間のエッジを追加します。各エッジには、重みがあると仮定します。

1

G.add_weighted_edges_from([(1, 2, 3), (1, 3, 4), (2, 3, 1), (2, 4, 6), (3, 4, 2), (3, 5, 7), (4, 5, 8)])

これでグラフが完成しました。

最長経路問題を解くには、NetworkXのlongest_path関数を使用します。

1
2

longest_path = nx.dag_longest_path(G)
print(longest_path)

これで、最長経路が求められます。

最長経路の出力は、最初のノードから最後のノードまでの最長経路上のノードのリストです。

注意：

この方法は、有向非巡回グラフ（DAG）にのみ適用されます。

循環がある場合は、longest_path関数はエラーを返します。

全ソースコードと結果

上記のコードをまとめると以下のようになります。

[全ソースコード]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import networkx as nx

# ①グラフの作成
G = nx.DiGraph()

# ②ノードの追加
G.add_nodes_from([1, 2, 3, 4, 5])

# ③エッジの追加
G.add_weighted_edges_from([(1, 2, 3), (1, 3, 4), (2, 3, 1), (2, 4, 6), (3, 4, 2), (3, 5, 7), (4, 5, 8)])

# ④最長経路の計算
longest_path = nx.dag_longest_path(G)

# ⑤結果の出力
print("最長経路: ", longest_path)

実行結果は次の通りです

[実行結果]

最長経路:  [1, 2, 4, 5]

1 ⇒ 2 ⇒ 4 ⇒ 5という最長経路を求めることができました

最短経路問題

NetworkXを使って簡単な最短路問題を解いてみましょう。

例えば、以下のようなグラフがあるとします。

[単純なグラフ]

このグラフにおいて、ノードAからノードDまでの最短経路を求めるソースコードは以下のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12

import networkx as nx

# グラフを定義する
G = nx.Graph()
G.add_edge('A', 'B', weight=5)
G.add_edge('A', 'C', weight=3)
G.add_edge('B', 'D', weight=2)
G.add_edge('C', 'D', weight=3)

# ノードAからノードDまでの最短経路を求める
path = nx.shortest_path(G, 'A', 'D', weight='weight')
print(path)  # 結果：['A', 'C', 'D']

最短経路を求めるために、NetworkXのshortest_path関数を使っています。

またweightパラメータには、辺の重み（コストや所要時間など）を指定しています。

[実行結果]

['A', 'C', 'D']

‘A’ ⇒ ‘C’ ⇒ ‘D’という最短経路を求めることができました