java: implementation of topological sort, from a reputable source

views:

524

answers:

java: implementation of topological sort, from a reputable source

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?

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 2009-09-28 15:55:35

thanks but java2s isn't a reputable source unless what it cites comes from a reputable source.

Jason S 2009-09-28 16:27:26

@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 2009-09-28 17:27:11

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 2009-09-28 17:37:54

@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 2009-09-28 20:21:16

"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 2009-09-28 23:42:11

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

This book might be of use to you.

2009-09-28 17:33:51

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 2009-09-28 17:44:07

ansaurus

tags:

views:

answers:

java: implementation of topological sort, from a reputable source

related questions