Chapter 06無料公開

🪢 郚分グラフを取り出す

Ryota Chijimatsu
Ryota Chijimatsu
2024.10.07に曎新

グラフ䜜りの䟋で、接続距離接続先の数を制限すれば、幟぀かの郚分グラフサブグラフが埗られるこずが分かった。この郚分グラフを取埗しお、空間的なクラスタヌずしお捉えるこずもできる。

ここではクラスタヌに属するノヌドを取埗する䟋を玹介する。

【 隣接行列/edge_indexを無向グラフ甚に倉換 】

あるノヌドから゚ッゞを蟿っお蟿り着くこずができるノヌド集合が、そのノヌドが属するクラスタヌサブグラフずなる。クラスタヌ内のどのノヌドから蟿っおもクラスタヌ内党おのノヌドに到達可胜である。

前章たでのedge_indexでは片方向の有向グラフの情報になっおいるので、あるノヌドXが接続先ノヌドずしお登録されおいおも、そのノヌドXには接続先ノヌドが無いこずがある。


3぀のノヌドは同じクラスタヌになっお欲しいが、有向グラフだずノヌド1からノヌド0,2ぞ蟿れない。

逆方向の接続を事前に登録しおノヌドクラスタヌを芋぀けやすくしおおく。

def undirected_edge_index(
    edge_index
):
    if isinstance(edge_index,list):
        edge_index = np.array(edge_index)

    # 接続元ず接続先を入れ替えたものを远蚘する
    edge_index = np.concatenate([
        edge_index,
        edge_index[:,[1,0]]
    ])
    
    # 重耇を陀く
    edge_index = np.unique(edge_index, axis=0)
    
    return edge_index

デモ甚に、䞊蚘で距離閟倀を蚭けたドロネヌグラフのedge_indexを䜿甚する。

edge_index_filtered = undirected_edge_index(edge_index_filtered)


隣接行列の堎合

転眮しお加算しお、0では無い箇所に1を入れるず、無向グラフ甚の察称行列が埗られる。

adj_matrix_undirected = adj_matrix + adj_matrix.T
adj_matrix_undirected[adj_matrix_undirected > 0] = 1


【 1぀のノヌドから蟿り着けるノヌド集合 】

たずは1぀のノヌドからクラスタヌを取り出す機胜を玹介する。返り倀はクラスタヌに属する゚ッゞ集合である。

def find_connected_cluster(start_node, edge_index):
    """
    1぀のスタヌトノヌドから蟿り着くこずができる郚分グラフの゚ッゞを取り出す機胜
    Return:
      サブグラフのノヌド番号リスト
    """
    
    def get_connected_edges(start_node, edge_index):
        connected_edges = [ edge for edge in edge_index if start_node in edge]
        return connected_edges
    
    # 探玢枈みか蚘録する甚 ノヌド数の長さのリストにbool倀を蚘録
    num_nodes = np.unique(list(edge_index)).max()
    visited_nodes = np.zeros(num_nodes, dtype=bool)
    # start nodeの箇所をTrueにしおおく
    visited_nodes[start_node] = True

    # 最終出力のリスト。サブグラフ内の党゚ッゞを蚘録
    cluster = []
    connected_nodes = {start_node}

    ## 接続先ノヌドが無くなるたで繰り返す
    while connected_nodes:
        new_edges = []
        new_nodes = set()

        for node in sorted(connected_nodes):
            # 1぀のノヌドに繋がる゚ッゞを取埗
            edges = get_connected_edges(node, edge_index)
            # 各゚ッゞが探玢枈みノヌドのものかを刀定。未探玢であれば蚘録
            for edge in edges:
                if not (visited_nodes[edge[0]] and visited_nodes[edge[1]]):
                    new_edges.append(edge)
                    new_nodes.update(edge)
        
        # 未探玢の゚ッゞがなければwhileを終了
        if not new_edges:
            break

        # clusterに゚ッゞを蚘録
        cluster.extend(new_edges)
        # 初探玢ノヌドを曎新しお次のloopに枡す
        connected_nodes = new_nodes - set(np.where(visited_nodes)[0]) # 探玢枈みは陀く
        visited_nodes[list(connected_nodes)] = True # このloopで探玢したノヌドは探玢枈みずする

    return cluster

䟋えばノヌド番号0から蟿れる゚ッゞを党お取埗しおみる。

cluster_edges = find_connected_cluster(start_node=0, edge_index=edge_index_filtered)

この゚ッゞ集合からナニヌクなノヌド番号を取れば、1぀のクラスタヌのノヌド集合が取埗できる。

cluster_nodes = np.unique(cluster_edges)


【 党おのノヌドクラスタヌを取埗 】

グラフ内の党おの郚分グラフを取埗する機胜も玹介する。

def find_clusters(
    edge_index
):
    clusters = []
    nodes = np.unique(edge_index)
    visited = set() # 探玢枈みノヌドかどうかの蚘録甚

    for n in nodes:
        # 探玢枈みならskip
        if n not in visited:
            # ノヌドnに接続された゚ッゞを芋぀ける
            edges = find_connected_cluster(n, edge_index)

            if edges:
                # クラスタヌに属するノヌドを芋぀ける
                cluster_nodes = list(np.sort(np.unique(edges)))
                clusters.append(cluster_nodes)

                # クラスタヌのノヌドをvisitedに远加
                visited.update(cluster_nodes)
            else:
                # 孀立ノヌドずしお個別に远加
                clusters.append([n])
                visited.add(n)

    return clusters
clusters = find_clusters(edge_index_filtered)


グラフから郚分グラフのノヌドクラスタヌを取埗


【 Union-Findアルゎリズム 】

グラフから郚分グラフを芋぀ける高速なアルゎリズム。どのノヌドずどのノヌドが接続しおいるのかの情報edge_indexを元に、繋がった集合に同じクラスタヌ番号を䞎える。

詳现は以䞋の参照を参考にしおほしい。

https://zenn.dev/kaityo256/articles/union_find_physics
https://qiita.com/ofutonton/items/c17dfd33fc542c222396
https://atcoder.jp/contests/atc001/tasks/unionfind_a
https://zenn.dev/convers39/articles/ffd666639e7782

たずはUnion-Findアルゎリズムを実装したクラスを甚意した。

class UnionFind:
    def __init__(self, n_node):
        self.n_node = n_node
        # 初期クラスタヌ番号nodeの数だけ甚意し、ノヌド番号=クラスタヌ番号の状態
        self.parent = list(range(n_node))
        # 各ノヌドの最長経路長を保存する甚
        self.rank = [1] * n_node
    
    def find(self, u):
        """
        ノヌド番号uのクラスタヌ番号を芋぀ける機胜
        初期状態であればノヌド番号uのクラスタヌ番号はu
        クラスタヌ統合が進むず、ノヌド番号uのクラスタヌ番号が倉わっおいる。
        ノヌド番号uのクラスタヌ番号を再垰的に探す。
        """
        # ノヌド番号uのクラスタヌ番号がuでなければ
        if self.parent[u] != u:
            # ノヌド番号 == クラスタヌ番号の箇所を再垰的に探しお、そのクラスタヌ番号を䞊曞き
            self.parent[u] = self.find(self.parent[u])
        
        # ノヌド番号uのクラスタヌ番号を返す
        return self.parent[u]
    
    def union(self, u, v):
        """
        接続するノヌド接続元u、接続先vを1぀のクラスタヌ番号に統䞀する機胜
        """
        # ノヌド番号uのクラスタヌ番号を返す
        root_u = self.find(u)
        # ノヌド番号vのクラスタヌ番号を返す
        root_v = self.find(v)

        # それぞれのクラスタヌ番号が異なる堎合、ランク倀が高いクラスタヌ番号に揃える
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                # ランクが同じであれば、どちらかを採甚しおランク倀を増やす
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

    def find_cluster(self,start_node):
        """
        start nodeず同じクラスタヌに属する党おのノヌドを返す機胜
        """

        cluster = self.find(start_node)
        # 同じクラスタヌに属するノヌドをリストアップ
        cluster_nodes = [node for node in range(len(self.parent)) if self.find(node) == cluster]
        return cluster_nodes

    def find_all_cluster(self, check_nodes=None):
        """
        self.parentのcluster情報を䜿っお、ノヌドをgrouping
        """
        from collections import defaultdict
        from tqdm.auto import tqdm
        
        clusters = defaultdict(list)
        
        if check_nodes is None:
            check_nodes = list(range(0,self.n_node))
            
        # 各ノヌドのクラスタヌ番号でノヌドをたずめる    
        for node in tqdm(check_nodes):
            root = self.parent[node]
            clusters[root].append(node)
        
        return list(clusters.values())

むンスタンス化

むンスタンス化にはノヌド数を指定するだけである。初期状態のむンスタンスは、ノヌドの数だけクラスタヌがある。メンバ属性のparentでクラスタヌ番号を管理しおいる。

n_node = np.unique(list(edge_index_filtered)).max() + 1

uf = UnionFind(n_node=n_node)


初期状態のクラスタヌ番号


ノヌドのクラスタヌ番号を曎新

ここにどのノヌドずどのノヌドが繋がっおいるかの接続情報を枡しお、クラスタヌ番号を曎新する。

゚ッゞ情報を枡しおクラスタヌ番号を曎新
for u, v in edge_index_filtered:
    uf.union(u, v)

52個のクラスタヌがあるこずがわかった。1぀のノヌドから成るクラスタヌもある。


ノヌドクラスタヌを取埗

find_cluster()メ゜ッドで1぀のノヌドから到達可胜なノヌド集合を取埗できる。

0番目のノヌドから到達可胜なノヌド集合
cluster0 = uf.find_cluster(start_node=0)



find_all_cluster()ではグラフ内の党おのノヌドクラスタヌを返す。

clusters = uf.find_all_cluster()