No subject

[Henry Cejtin]

Ah  yes, a greedy algorithm.  So, for each edge, you attach a weight which is
the number of edges that will be eliminated  if  you  merge  the  source  and
target  nodes.   Note, this is NOT always 1.  It can be more than one because
of the directed nature (so merging A with B will eliminate both the A->B  and
any  B->A  edge).   More importantly, it can be more than 1 because merging A
with B will also eliminate any A->C for which there is also a  B->C  and  any
C->A for which there is also a C->B.

So you just look at the edges, compute the weight and then merge the heaviest
one you can, re-computing the weights.  Pretty fast and I claim not bad.

I still like the idea of keeping the directed graph, but if you  insist,  you
can go to the undirected version.