5

アプリケーションで意味的に同じであるノードをマージしたいと思います。グラフの処理に使用できるツールまたはアルゴリズムはありますか？

入力例：ノードaとbをマージする必要があります。

digraph g {                                                                     
  a -> {b;c;d;e};                                                               
  b -> {a;c;d;e};                                                               
}

を使用したグラフの画像dot：

ノードaとbをマージする必要があります

出力例：ノードaとbがノードabにマージされました。

digraph g {                                                                     
  ab -> {c;d;e};                                                                
}

ここに画像の説明を入力してください

ラフスケッチアルゴリズム：

# XE = a set of nodes, represent a directed edge (x,_)
# YE = a set of nodes, representing a directed edge (y,_)
# XE \ y = XE except y
# YE \ x = YE except x

For each pair of nodes x,y
  If (edges (x,y) and (y,x) exists) AND (XE \ y == YE \ x)
    create new node xy -> xedges\y
    delete nodes x and y and their edges
4

2 に答える 2

2

ツールがあります。これは、グラフ パターン スキャンおよび処理言語gvprを表すと呼ばれます。

リンクされたpdfから：

gvprはawkに触発されたグラフ ストリーム エディターです。入力グラフを出力にコピーし、構造と属性を変換したり、新しいグラフを作成したり、任意の情報を出力したりします。

gvpr プログラムを作成することで、必要なことを達成できると確信しています。

実用的なソリューションを作成する時間はありませんが、gvpr プログラムの例と追加情報については、この回答をご覧ください。

于 2013-02-19T21:46:26.153 に答える
1

Graphviz にはそのような機能は組み込まれていませんが、素集合のデータ構造を使用してグラフを前処理できる場合があります。

于 2013-02-19T20:55:59.833 に答える