views:

524

answers:

3

I'm looking for a reputable Java implementation of a topological sort, given a directed graph of dependencies (node #7 depends on node #2, node #2 depends on note #4, etc.), that will detect the presence of a cycle so I can report an error if a cycle occurs.

I assume Apache ant has to do this so I'm hoping I could just make use of it, but if not then I'm sure there's something else out there. Otherwise I suppose I could implement one of the algorithms in the Wikipedia page, but I am somewhat error prone so would rather not reinvent the wheel.

any suggestions?

A: 

Google is your friend. As it happens I have implemented topological sort in Java, but unfortunately I can't publish the code. I haven't tested the code in the linked-to page but on the basis of a cursory glance, the algorithm looks OK (not sure it's optimized, though). It should be a reasonable basis for you to build on.

Vinay Sajip
thanks but java2s isn't a reputable source unless what it cites comes from a reputable source.
Jason S
@Jason, define "reputable source" -- there's obviously no universally accepted definition for what that means and it's useless for us to try and guess what you'd consider as such and what you wouldn't.
Alex Martelli
Why would you need a reputable source for an algorithm that has a publically known (and not even very difficult) proof? It's like asking a reputable source for mergesort.
Joren
@Joren, this reminds me of Knuth's quote "I have only proved it correct, not tried it.". Seems that not even as reputable a source as the JDK is infallible: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Ants Aasma
"It is not sufficient merely to prove a program correct; you have to test it too." That's nonsense. What ridiculous definition of 'proof' do they use that allows being incorrect? If your algorithm doesn't work with the datatypes you're using, then it's obviously impossible to prove its correctness. If you instead prove that it's correct if your integers aren't vulnerable to overflow, then it's the fault of the implementer who tries to apply a proof to a situation where the premises of the proof don't hold.
Joren
A: 

Ant's toposort is not in any way general purpose.

This book might be of use to you.

A: 

Maven has such an implementation as described in the Aggregation (or Multi-Module) section:

You do not need to consider the inter-module dependencies yourself when listing the modules, i.e. the ordering of the modules given by the POM is not important. Maven will topologically sort the modules such that dependencies are always build before dependent modules.

Pascal Thivent