blog.monophile.net

コンピュータのこととかのメモ。

Takaaki Yamamoto

東京工業大学において計算機科学と応用数学を学び、 情報科学芸術大学院大学[IAMAS] においてメディア表現を専攻し修了。 現在は digitiminimi Inc. において、インフラエンジニアとして生計をたててている。

work

各種システム構築と管理を承ります。

Cloud PlatformOpenstack, GCP, AWS, Azure, ...
Openstackkeystone, glance, cinder, swift, neutron, nova, ...
VirtualizationQEMU+KVM, LXD/LXC, Docker, ...
OSDebian GNU/Linux, Ubuntu, CentOS, ...
NetworksIPSec, L2TP, VXLAN, WirelessAP, ...
WebAppsWordPress, GitLab, Redmine, ...
Configuration ManagementAnsible, Terraform, ...
MonitoringNagios, Munin, ...

posts

グラフの連結性判定

いきさつ

離散グラフ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