最小全域木

本稿では NetworkX の提供する機能を利用して、与えられたグラフの最小全域木 (Minimum Spanning Tree, MST) を計算する手順について記す。正直に言って面白い例が思い浮かばないので、出来合いの問題を失敬して解くだけに留める。イラストすらない貧相なノートになる。

問題の背景

例えばあなたがある街の建物間に電話線を敷設することになった電話会社の担当者だとする。営利を追求する企業の構成員としては、この敷設費用を極小化するネットワーク敷設計画を立てねばならない。これを MST 問題の一例として考えてみよう。

対象となるグラフは電話線ネットワークであり、ノード、エッジはそれぞれ建物、電話線だ。そしてエッジの重みは建物同士を結ぶ電線の敷設費用とみなすことができる。あなたが求めるものは「全ノードを含む部分グラフで、エッジの重みの総和が最小となるもの」だ。

リアルな数値を用意してここにサンプルコードを示したいのだが、叶わなかったので、 この問題 を解いていくことにする。

サンプルコードを小出しにしながら解説する。まずはプログラムの処理手順だ。

#!/usr/bin/env python
"""mst.py: demonstrate NetworkX (minimum_spanning_tree)

This code solves the problem #2, presented by:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp
"""
import networkx as nx

# CSV of source-node destination-node weight.
GRAPH_TEXT = """\
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6
"""

def main():
    """The main function.

    Returns:
      None
    """

    G = setup_graph()
    print_spanning(G)

所定の条件からグラフを構築する処理を示す。

def setup_graph():
    """Create a graph to demonstrate MST.

    Returns:
      (Graph): A simple undirected graph.
    """
    G = nx.Graph()

    for i in GRAPH_TEXT.splitlines():
        source, destination, cost = (int(j) for j in i.split())
        G.add_edge(source, destination, weight=cost)

    return G

テキスト処理程度しか行っていないが、注意点がひとつ。グラフに add_edge するときにコストをしっかりと指示することを忘れてはならない。このテキストがエッジ始点、エッジ終点、エッジコストを示している。我々の例では建物と電線の敷設費用に相当するデータだ。

関数 nx.minimum_spanning_tree の実行およびデータの取得

入力が NetworkX のグラフオブジェクトになったので、MST を求めるとしよう。

def print_spanning(G):
    """Compute MST and print the result.

    Args:
      G (Graph): A simple undirected graph.

    Returns:
      None
    """

    print('size of G:', G.size(weight='weight'))
    T = nx.minimum_spanning_tree(G)

    print('size of MST:', T.size(weight='weight'))
    print('spanning edges:')
    for i in sorted(T.edges(data=True)):
        print(i)

最初に入力グラフのエッジ全体のコストを出力する。ポイントは G.size メソッドのキーワード引数 weight の明示的な指示だ。これにより、各エッジに付加済みの weight 値を考慮したグラフのサイズを計算させる。

続いてただちに関数 nx.minimum_spanning_tree を実行する。戻り値の G の部分グラフ T が求めるもののすべてだ。

最後に MST の weight 値を考慮したグラフのサイズと、エッジリストの出力を行う。 edges メソッドの data 引数に注意。これにより個々のエッジの重みも得られる。それは次のようなものになる。

size of G: 24.0
size of MST: 5.0
spanning edges:
(0, 1, {'weight': 1})
(1, 2, {'weight': 1})
(2, 4, {'weight': 1})
(3, 4, {'weight': 1})
(3, 5, {'weight': 1})

このように、元データがしっかり定義されていれば、比較的少量のコードで MST が得られることが理解できたと思う。