隣接行列の実装

Introduction

sorry, this page is Japanese only. 

ここでは隣接行列の実装を行っていきます。Python3を使っています。OSはwindows10です。隣接行列の説明は以下の記事の下の方をご覧ください。

グラフ理論の基礎

実装例

扱うグラフ

コマンドでの結果

Code
defファイル

import numpy as np

class directed_Gragh():
    def __init__(self,E,V,gragh_map):
        self.edge = E;
        self.vertex = V;
        self.map = gragh_map;

    def Adjacency_matrix(self):
        adjacency_matrix = np.zeros((self.vertex.shape[0],self.vertex.shape[0]))
        for ed in self.edge:
            P_ = self.map(ed)
            start = P_[0]
            end = P_[1]
            row = np.where(self.vertex == start)
            column = np.where(self.vertex == end)
            adjacency_matrix[row,column] = 1
            adjacency_matrix[column,row] = 1
        return adjacency_matrix

mainファイル

import numpy as np
from Gragh_def import directed_Gragh

def main():

    vertex = np.array(['house','station','school','hospital'])
    edge = np.array([1,2,3,4])

    def gragh_map(edge):
        if edge == 1:
            vertexs = np.array(['house','school'])
        elif edge == 2:
            vertexs = np.array(['school','station'])
        elif edge == 3:
            vertexs = np.array(['house','station'])
        else:
            vertexs = np.array(['station','hospital'])
        return vertexs

    test_gragh = directed_Gragh(edge,vertex,gragh_map)
    print('vertex is %s \n'%test_gragh.vertex)

    adjacency_matrix = test_gragh.Adjacency_matrix()

    print('adjacency_matrix = \n %s \n'%adjacency_matrix)

if __name__ == '__main__':
        main()

References
https://ja.wikipedia.org/wiki/グラフ理論