2

有向非巡回グラフが有向エッジと無向エッジで構成されている場合、このグラフをチェーンコンポーネントの有向グラフ（チェーンコンポーネント内の各ノードは無向エッジでのみ相互に接続されます）とその順序に分解したいと思います。

最初にすべての有向エッジをトポロジカルソートしてから、チェーンコンポーネントとして無向エッジをハントする必要があるのか​​、それともすべての無向エッジを調べてグループIDを指定し、それらのコンポーネントを接続するための有向エッジを見つける必要があるのか​​、混乱しています。

グラフは非循環的であるため、番号の小さいコンポーネントから番号の大きいコンポーネントに並べ替えることは可能だと思いますが、確実な答えを出すことはできませんでした。

4

3 に答える 3

1

チェーンコンポーネントを定義する同値関係は、Drton 2009によって次のようになります。2つの頂点v_0を定義v_kし、チェーングラフGで、すべての0≤i≤k−1に対してGにパスが存在する場合に同等になるように(v_0,..., v_k)定義しv_i − v_{i+1}ます。

この同値関係の下の同値類は、Gのチェーンコンポーネントです。大まかに言えば、これは、チェーングラフの無向エッジから作成されたグラフのすべての連結成分、および有向エッジのみで入射するすべてのノード、および隣人がまったくいない、これはピーターの答えに相当します

これは、Cowell 2005、Probabilistic Networks、および...、pで与えられたチェーングラフCH-Asiaを正しく分解する関数です。110図6.1。これは、私が趣味のプロジェクトとして開発しているグラフィカルモデルライブラリの一部です。

カスタムデータ構造を使用しますが、グラフィカルモデルを含む他のコードベースに適応するのはそれほど難しくありません。

def get_chain_components(self) -> Set[Set[Node]]:
    """!
    """
    # filter out undirected edges
    edges = set()
    for e in self.edges():
        if e.type() == EdgeType.UNDIRECTED:
            edges.add(e)

    # make a graph from undirected edges
    undi = UndiGraph.from_graph(Graph.from_edge_node_set(edges, self.nodes()))
    return undi.get_components_as_node_set()
于 2021-01-29T02:05:38.030 に答える
0

どちらの方法でもうまくいくと思います。

私の考えでは、2番目の方法はより自然に思えます。

networkxでこれを行っている場合は、次の方法で2番目のメソッドを実装します。

  1. すべての頂点を含むが、無向エッジのみを含む新しいグラフHを作成します。

  2. Hでconnected_componentsを呼び出して、チェーンコンポーネントを抽出し、各コンポーネントに異なるグループIDを割り当てます。

  3. グループIDごとに1つのノードを持つ新しいグラフFを作成します。Fのグループを、元のグラフの有向エッジに基づいて有向エッジに接続します。

  4. Fでtopological_sortを呼び出して、グループIDの順序を計算します。

于 2013-01-25T09:08:20.777 に答える
0

あなたが説明するような混合グラフもまた有向グラフです。方向性のない各エッジを、反対方向を指す2つの方向性のあるエッジに置き換えるだけです。

また、無向エッジを持つ非巡回グラフを作成することはできません。少なくとも長さ2のサイクルが常に存在するので、これが何を意味するのかわかりません。

このグラフで強く接続されたコンポーネントを探しているようですので、それらを見つけるためにタージャンのアルゴリズムを使用することをお勧めします。

于 2013-01-25T09:15:53.693 に答える