How can I combine nodes in a graph?

Question

I would like to combine nodes that are semantically identical in my application. Is there a tool or algorithm that I can use to process my chart?

Input example: nodes a and b must be combined.

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

Graph image using dot :

Output example: nodes a and b were merged into node ab .. p>

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

Rough Sketch Algorithm:

 # 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

There is a tool: it is called gvpr , which stands for the language for scanning and processing a graphic template.

From the linked pdf:

gvpr is an awk- inspired graph flow editor. He copies input charts to his output, possibly transforming their structure and attributes, creating new charts, or printing arbitrary information.

I am sure that you can achieve what you need by creating the gvpr program.

I don’t have time to create a working solution, but you can see this answer for an example gvpr program and additional information.

Answer 2

Graphviz doesn’t have such a function, but you can pre-process your graph using the disjoint dataset structure