如何合併圖形中的節點？

Question

我想在我的應用程序中合併語義相同的節點。有沒有可用於處理圖形的工具或算法？

輸入示例：節點一個和b應該合併。使用dot圖形的

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

圖片：

輸出示例：節點一個和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沒有這樣的功能，但你可以預先處理你的圖形與一個援助disjoint set data structure

Answer 2

有一種工具：它叫gvpr，它代表圖形圖案掃描和處理語言。

從鏈接的PDF：

gvpr是由AWK啓發的曲線流編輯器。它將輸入圖形複製到其輸出，可能轉換其結構和屬性，創建新圖形或打印任意信息。

我相信你可以通過創建一個gvpr程序來實現你所需要的。

我沒有時間創建工作解決方案，但是您可以參考this answer查看示例gvpr程序和其他信息。