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 回答