[Python] 隣接リストを用いてグラフを表現

下記の記事の続きです。

Python で隣接リストを用いてグラフを表現します。

隣接リスト

隣接リスト（英: adjacency list）は、グラフ理論でのグラフにある頂点または辺を全てリスト（一覧）で表現したものである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

辺の重みをもつ無向グラフを考えます。

wiki には、「各頂点とその隣接する頂点群の配列をハッシュテーブルで関連づける方法」と、「頂点の番号をインデックスとする配列に各頂点の隣接する頂点群の片方向リストへの参照を格納する方法」の2つがデータ構造として挙げられています。

ここでは、ハッシュテーブル、Python で言うところの辞書による実装を行います。

前回と同じ下のようなグラフを考えます。

辞書での実装

class Vertex(object):
    def __init__(self, id):
        self.id = id
        self.adjacent = {}

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight
    
    def get_neighbors(self):
        return self.adjacent

    def get_connections(self):
        return self.adjacent.keys()  

    def get_vertex_id(self):
        return self.id

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]


class Graph(object):
    def __init__(self):
        self.vertex_dict = {}
        self.num_vertex = 0

    def add_vertex(self, id):
        self.num_vertex = self.num_vertex + 1
        new_vertex = Vertex(id)
        self.vertex_dict[id] = new_vertex
        return new_vertex

    def get_vertex(self, id):
        if id in self.vertex_dict:
            return self.vertex_dict[id]
        else:
            return None

    def add_edge(self, frm, to, weight=0):
        if frm not in self.vertex_dict:
            self.add_vertex(frm)
        if to not in self.vertex_dict:
            self.add_vertex(to)
        self.vertex_dict[frm].add_neighbor(self.vertex_dict[to], weight)
        # 有向グラフの場合は別
        self.vertex_dict[to].add_neighbor(self.vertex_dict[frm], weight)

    def get_vertices(self):
        return self.vertex_dict.keys()

    def get_edges(self):
        edges = []
        for v in self.vertex_dict.values():
            for w in v.get_connections():
                vid = v.get_vertex_id()
                wid = w.get_vertex_id()
                edges.append((vid, wid, v.get_weight(w)))
        return edges
    
if __name__ == '__main__':

    graph = Graph()
    graph.add_vertex('a')
    graph.add_vertex('b')
    graph.add_vertex('c')
    graph.add_vertex('d')
    graph.add_vertex('e')
    print('ノード')
    print(graph.get_vertices())
    print('エッジ')
    print(graph.get_edges())
    print('-----------------------')
    # ノード
    # dict_keys(['a', 'b', 'c', 'd', 'e'])
    # エッジ
    # []
    # -----------------------

    graph.add_edge('a', 'e', 10)  
    graph.add_edge('a', 'c', 20)
    graph.add_edge('c', 'b', 30)
    graph.add_edge('b', 'e', 40)
    graph.add_edge('e', 'd', 50)
    print('ノード')
    print(graph.get_vertices())
    print('エッジ')
    print(graph.get_edges())
    print('-----------------------')
    # ノード
    # dict_keys(['a', 'b', 'c', 'd', 'e'])
    # エッジ
    # [('a', 'e', 10), ('a', 'c', 20), ('b', 'c', 30), ('b', 'e', 40), ('c', 'a', 20), ('c', 'b', 30), ('d', 'e', 50), ('e', 'a', 10), ('e', 'b', 40), ('e', 'd', 50)]
    # -----------------------

想定通りの結果を得ることができました。