アプリケーションで意味的に同じであるノードをマージしたいと思います。グラフの処理に使用できるツールまたはアルゴリズムはありますか?
入力例:ノードaとbをマージする必要があります。
digraph g {
a -> {b;c;d;e};
b -> {a;c;d;e};
}
を使用したグラフの画像dot
:
出力例:ノード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