1

Suppose I have a directed graph with a single source and sink, say a and z. Suppose that the graph is a->b->c->d->e->z, a->f->g->h->z.

What I want to do is maintain the identity of the 'sub groups' b->c->d->e and f->g->h in the result of the topological sort.

My idea is to first scan the graph looking for groups of more than one linked vertex all with a single entry point and a single exit point, replacing each of them with a 'super vertex' labelled 'A', then 'B' etc.

So I would get a result of a->A->B->z or a->B->A->z. Either is acceptable.

When I have found all the super vertices, I would do my topological sort, and then replace the super vertices with the original sequenced vertices.

So my final result will be a->b->c->d->e>f->g->h->z, or a->f->g->h->b->c->d->e->z.

I need an algorithm - pseudo code is fine - to do this. I'll implement in perl if I can.

The graph exists as a dot file, if that helps.

Many thanks - this is my first question on SO, so be gentle!

Roger

1 Answer 1

0

First do a depth-first search, and record the order in which the nodes are encountered.

Then, when choosing what node to add to the topological order next, pick the one that comes earlier in the DFS order.

So in your case the DFS order would be abcdezfgh, and the topological sort would be abcdefghz.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.