9

次のような 3 つのオブジェクト (Vertex、Edge、Graph) と 1 つの関数 (topo_sort) を持つ軽量のグラフ ライブラリを作成しました。

class DAGError(Exception): pass

def topo_sort(graph):
    sorted_list = []
    def visit(vertex):
        nonlocal sorted_list
        if vertex.idle:
            raise DAGError('Graph has at least one cycle.')
        if not vertex.done:
            vertex.idle = True
            for neighbor in vertex.vertices():
                visit(neighbor)
            vertex.done = True
            vertex.idle = False
            sorted_list.insert(0, vertex)
    queue = [vertex for vertex in graph.vertices() if not vertex.done]
    while queue:
        visit(queue.pop(0))
    return iter(sorted_list)

フラットな DAG を使用している場合、これは正常に機能しています。しかし、私が達成したいのは、私が描いたこの図でわかるように、メイン グラフにサブグラフ(またはネストされたグラフ)を追加することです。

ネストされた/サブ グラフの図

これはまだ DAG なので、これで関数を実行すると、通常の topo_sort出力は次のようになります。

V0, V3, V1, V5, V4, V8, V7, V12, V11, V13, V14, V2, V6, V10, V9, V15, V17, V16

ただし、サブグラフの頂点が処理される前に、サブグラフが依存するすべての頂点が「処理」される場合、私の好ましい出力は次のようになります。

V0, V1, V8,        # vertices of maingraph
V3, V5, V4, V12    # vertices of subgraph_0
V7, V11, V13,      # vertices of subgraph_1
V14                # vertex   of subgraph_0
V2                 # vertex   of maingraph
V6, V10, V9, V15   # vertices of subgraph_2
V16, V17           # vertices of maingraph

しかし、次のリソースは見つかりませんでした。

  • サブグラフの一部としてグラフの頂点を「マーク」または「保存」する方法は?
  • サブグラフの依存関係に基づいて頂点をソートする方法（上記の例のように）？
  • サブグラフを独立したグラフとして取得または処理する方法は?

私の問題を十分に詳しく説明できればと思いますが、何か不足している場合はお知らせください。不足している部分について質問を広げます。

前もって感謝します！

編集：

私はこれ（Boost Graph Library、BGL）を見つけましたが、私が抱えている非常によく似た（またはまったく同じ？）問題を解決しているように見えますが、C ++に慣れていないので、それがどのようになっているのかわかりません動作していて、正確には何をしているのか--しかし、私はこれをここに入れました。多分誰かが私の質問に答えるのに役立つと思うでしょう..

編集2：

Pythonだけでなく疑似コードも受け付けます！もちろん、既存のpythonライブラリがこれを知っていれば興味がありますが、graph-toolsたとえば、私はそのような巨大なライブラリを使用したくありません.

4

2 に答える 2

2

あなたにとっては少し遅いかもしれませんが、同様の問題を抱えている他の人にとっては：

サブグラフの一部としてグラフの頂点を「マーク」または「保存」する方法は?

subgraph頂点オブジェクトに、頂点が属するサブグラフにラベル付けする整数または文字列を保持する属性を与えないのはなぜですか? (NetworkX を使用する場合は、ノード属性ディクショナリを使用します) この方法で、ソート アルゴリズムでこのサブグラフ属性を確認できます。

サブグラフの依存関係に基づいて頂点をソートする方法 (>上記の例のように)?

私はトポロジーソートの専門家ではありませんが、すべての頂点がそれが属するサブグラフを「知っている」と仮定すると、これが私が思いついたものです (NetworkX を使用しますが、私が使用した部分を自分のライブラリで簡単に実装できます):以下のコードは、説明したすべての「依存関係」(現在の頂点の前に来る必要があるすべての頂点) を収集します。この情報を使用して topol_sort() 関数を変更し、依存関係のすべての頂点がまだリストにない場合にのみ、現在の頂点をリストに追加することができます。

import networkx as nx

# define the graph and the subgraphs suitable for NetworkX
G = ...
subgraphs = ...

for subgraph in subgraphs:
    # find all vertices that the current subgraph depends on
    dependencies = set()
    for vertex in subgraph:
        anc = nx.ancestors(G, vertex) # anc is the set of all vertices having a path to 'vertex'
        dependencies.union(anc)
    dependencies -= subgraph.nodes()
    # store these dependencies under every vertex of the current subgraph
    for vertex in subgraph:
        G[vertex].node['depends'] = dependencies

# run modified topological sorting
topo_sort_mod(G)

サブグラフを独立したグラフとして取得または処理する方法は?

ここであなたが正確に何を望んでいるのかわかりません。たぶん、これが役立つかもしれません（これもNetworkXを使用しています）、特にこの部分：

エッジ/ノード属性の独自のコピーを持つサブグラフを作成するには、次を使用します: nx.Graph(G.subgraph(nbunch))

エッジ属性がコンテナの場合、次を使用してディープ コピーを取得できます: G.subgraph(nbunch).copy()

これが誰かに役立つことを願っています... :)

于 2015-02-26T11:01:03.193 に答える