Topological order traversal

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Topological order traversal

Marden Neubert
Hi,

I found JGraphT while looking for a nice graph component
framework which I could plug into the system I am developing.

I need to implement a topological sort to execute a sequence
of steps with inter-dependencies, forming a directed acyclic
graph.

I found JGraphT very useful for representing the graph and in
a few minutes I could adapt the Graph class to an unit test
of mine (using a dummy DAG and an even simpler adaptor).

But I could not found a topological order traversal in
JGraphT's distribution. Then I implemented one using the
excellent infrastructure in the "traverse" package.

There is still some serious unit testing to implement and
lots of scenarios to validate, but I felt like submitting the
code to JGraphT's community and get some feedback.

One of the troubles I had when implementing the tests is that
the topological sort of a DAG is not unique, so it is kind of
hard to automate the tests. Other thing I could not
understand clearly is how to defend the code agains cyclic
graphs.

The code for the TopologicalOrderIterator is attached. If one
of the committers of the project finds it useful, I would be
glad to discuss some strategies to implement some unit tests
for it.

My congratulations to Barak and the others for the good work.

Best regards,
Marden Neubert.
 
__________________________________________________________________________
Acabe com aquelas janelinhas que pulam na sua tela.
AntiPop-up UOL - É grátis!
http://antipopup.uol.com.br/


=?iso-8859-1?Q?TopologicalOrderIterator.java?= (8K) Download Attachment