How can I merge nodes in a graph?

Question

I would like to merge nodes which are semantically identically in my application. Is there a tool or algorithm I can use to process my graph?

Input Example: nodes a and b should be merged.

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

Image of graph using dot:

Output Example: nodes a and b have been merged into a node ab.

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's called gvpr which stands for graph pattern scanning and processing language.

From the linked pdf:

gvpr is a graph stream editor inspired by awk. It copies input graphs to its output, possibly transforming their structure and attributes, creating new graphs, or printing arbitrary information.

I'm sure you can achieve what you need by creating a gvpr program.

I don't have the time to create a working solution, but you may take a look at this answer for an example gvpr program and additional information.

Answer 2

There is no such function built into Graphviz, but you may be able to pre-process your graph with the aid of a disjoint set data structure