40

グラフで推移簡約を実行するアルゴリズムを探していましたが、成功しませんでした。私のアルゴリズムの聖書には何もありません（Cormenらによるアルゴリズムの紹介）。推移閉包の擬似コードをたくさん見ましたが、削減のために何も追跡できませんでした。私が持っている最も近いものは、Volker Turau（ISBN：978-3-486-59057-9）の「AlgorithmischeGraphentheorie」にあるものですが、残念ながら私はこの本にアクセスできません！ウィキペディアは役に立たず、グーグルはまだ何も発表していません。：^（

推移簡約を実行するためのアルゴリズムを知っている人はいますか？

4

7 に答える 7

18

ハリー・シューを参照してください。「ダイグラフの最小等価グラフを見つけるためのアルゴリズム。」、Journal of the ACM、22(1):11-16、1975 年 1 月。以下の単純な 3 次アルゴリズム (N x N パス行列を使用) は、DAG には十分です。しかし、スーはそれを巡回グラフに一般化します。

// reflexive reduction
for (int i = 0; i < N; ++i)
  m[i][i] = false;

// transitive reduction
for (int j = 0; j < N; ++j)
  for (int i = 0; i < N; ++i)
    if (m[i][j])
      for (int k = 0; k < N; ++k)
        if (m[j][k])
          m[i][k] = false;
于 2011-07-15T02:47:57.843 に答える
7

私が使った推移還元アルゴリズムの基本的な要点は


foreach x in graph.vertices
   foreach y in graph.vertices
      foreach z in graph.vertices
         delete edge xz if edges xy and yz exist

同じスクリプトで使用した推移閉包アルゴリズムは非常に似ていますが、最後の行は


         add edge xz if edges xy and yz OR edge xz exist
于 2010-03-03T14:49:42.797 に答える
4

ウィキペディアの推移還元に関する記事は、GraphViz (オープン ソース) 内での実装を示しています。正確には疑似コードではありませんが、どこかから始めるべきでしょうか?

LEDA には、推移的な縮小アルゴリズムが含まれています。私はもうLEDA の本を持っていません。この機能は本が出版された後に追加されたのかもしれません。しかし、そこにある場合は、アルゴリズムの適切な説明があります。

Googleは、誰かが Boost に含めることを提案したアルゴリズムを指摘しています。読んでいないので間違っているかも？

また、これは一見の価値があるかもしれません。

于 2009-11-07T15:42:18.057 に答える
3

"girlwithglasses" のアルゴリズムは、冗長エッジが 3 つのエッジのチェーンにまたがる可能性があることを忘れています。修正するには、Q = R x R+ (R+ は推移閉包) を計算し、Q に表示される R からすべてのエッジを削除します。ウィキペディアの記事も参照してください。

于 2010-12-08T19:42:06.237 に答える
2

疑似 python の深さ優先アルゴリズム:

for vertex0 in vertices:
    done = set()
    for child in vertex0.children:
        df(edges, vertex0, child, done)

df = function(edges, vertex0, child0, done)
    if child0 in done:
        return
    for child in child0.children:
        edge.discard((vertex0, child))
        df(edges, vertex0, child, done)
    done.add(child0)

このアルゴリズムは最適ではありませんが、以前のソリューションのマルチ エッジ スパンの問題を処理します。結果は、graphviz からの tred が生成するものと非常によく似ています。

于 2012-06-28T02:04:07.727 に答える