如何合并图中的节点？

Question

我想合并在我的应用程序中语义相同的节点。有没有我可以用来处理图形的工具或算法？

输入示例：节点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

Answer 1

Graphviz 中没有内置此类函数，但您可以借助不相交集数据结构来预处理图形