Partial topological sorting

Topics: algorithm
Jul 31, 2008 at 9:52 AM
Edited Jul 31, 2008 at 9:53 AM

I have vertices that represent some steps in a process. There are dependencies between those steps. Step may depend on several other steps and all these steps should be done before doing the step. That's why TopologicalSorting algorithm is useful for me.
But I don't need to update vertices (steps) that are not in certain subgraph. If I sort all the graph topologically I can't skip redundant vertices. So how can I use QuickGraph for sorting the graph partially. May I somehow tell him where to start (from which vertex)?

Thank you.

Kindest regards, Gregory.
Jul 31, 2008 at 11:31 AM
Well, the only option to do this is to derive TopologicalSortAlgorithm from RootedAlgorithmBase and not from AlgorithmBase as today. In addition we must pass the RootVertex property value to the DFS algorithm (which is already derived from RootedAlgorithmBase). In addition we must provide some mehanism that will allow searching only in connected component (DFS will produce only one tree instead of forest). This must be done in the InternalCompute where Visit() method is invoked for each vertex.

I may change the source. Is it useful for anyone?
Jul 31, 2008 at 1:46 PM
I've done all the changes to code and it works great. The code is so clear and understandable!

Everything is working fine!

If somebody needs the feature, no problem. Write here and I'll get a notification to my email address.

P.S. Naturally I don't talk to myself all the time :)
Aug 25, 2008 at 9:05 AM
Glad to see to that you could figure it out yourself :)
Aug 26, 2008 at 6:58 AM
Yeap :)

Nice code, pelikhan!