algorithm - グラフまたはツリーで冗長なエッジを見つけるためのアルゴリズム

Question

グラフ内の冗長エッジを見つけるための確立されたアルゴリズムはありますか?

たとえば、a->d と a->e が冗長であることを確認してから、次のように削除したいと思います。

=>

編集: Strilanc は、私の心を読んでくれるほど親切でした。上記の例では、a->b も a->c も冗長とは見なされませんが、a->d は冗長と見なされるため、「冗長」という言葉は強すぎます。

score 36 · Accepted Answer

頂点の到達可能性を維持する最小のグラフを計算したいと考えています。

これは、グラフの推移還元と呼ばれます。ウィキペディアの記事は、正しい道を歩み始めるのに役立ちます。

score 0 · Accepted Answer

私は同様の問題を抱えていて、この方法でそれを解決することになりました：

私のデータ構造はdependends、ノードIDからそれに依存するノードのリスト（つまり、DAG内のフォロワー）までの辞書で構成されています。有向非巡回グラフであるDAGに対してのみ機能することに注意してください。

私はそれの正確な複雑さを計算していませんが、それは一瞬で数千の私のグラフを飲み込みました。

_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]

score 0 · Accepted Answer

これを攻撃する方法はいくつかありますが、まず問題をもう少し正確に定義する必要があります。まず、ここにあるグラフは非巡回で有向です。これは常に真ですか?

次に、「冗長エッジ」の意味を定義する必要があります。この場合、2 つのパス a->c を持つグラフから開始します。1 つは b を経由し、もう 1 つは直接のパスです。このことから、「冗長」とは、このようなことを意味していると推測します。G=< V, E >をグラフとし、Vを頂点の集合、E ⊆ V×Vを辺の集合とします。v _iからv _jまでのすべてのエッジを、最長のエッジよりも短い「冗長」として定義しているように見えます。したがって、最も簡単な方法は、深さ優先検索を使用してパスを列挙し、より長い新しいパスを見つけたら、それを最良の候補として保存することです。

しかし、あなたがそれを何のために望んでいるのか想像できません。教えてくれますか？