blog.monophile.net

Takaaki Yamamoto

東京工業大学において計算機科学と応用数学を学び、情報科学芸術大学院大学[IAMAS]においてメディア表現を専攻し修了。 現在は digitiminimi Inc. において、インフラエンジニアとして生計をたててている。 また、計算を主題に制作を行い、現代音楽作品や公共インスタレーション作品など技術提供を行う。 三輪眞弘に師事する。

List

グラフの連結性判定

いきさつ

離散グラフG(V,E)が連結かどうかを判定する必要があったので、 判定するためのプログラムを書きました。 今回は無向グラフを対象としています。 コードの見やすさ重視で書いたので速くないと思います。 入力のデータはnumpyの行列形式です。

code

import numpy as np

def is_connected(npmat):
    mat = np.copy(npmat)
    dim = mat.shape[0]
    for i in range(dim):
        mat[i][i] = 0
    accessible = set([0])
    queue = [0]
    while len(queue) > 0:
        i = queue.pop()
        js = filter(lambda x:x[1], enumerate(mat[i] > 0))
        for j, bool in js:
            if not j in accessible:
                accessible.add(j)
                if len(accessible) == dim :
                    return True
                queue.append(j)
    return len(accessible) == dim

if __name__ == "__main__":
    dim = 10
    identity = np.identity(dim, dtype=np.float)
    ones = np.ones((dim, dim) , dtype=np.float)
    print is_connected(identity)
    print is_connected(ones)

output

False # identity matrix
True # ones