programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Devaka Cooray
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• paul wheaton
• Henry Wong
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Tim Moores
• Carey Brown
• Mikalai Zaikin
Bartenders:
• Lou Hamers
• Piet Souris
• Frits Walraven

# topological sort

Greenhorn
Posts: 22
• Number of slices to send:
Optional 'thank-you' note:
Hello,
I need implement topological sort.
http://en.wikipedia.org/wiki/Topological_sort
I write something like (code below).
But I can't test it .
According to wiki I get error that my graph is not a DAG, so a topological sort is impossible
My code below, Please with what input test it.
Thanks.

Bartender
Posts: 612
7
• Number of slices to send:
Optional 'thank-you' note:
Well what i see from your data is that you do indeed have cyclic data like job4 -> job7 -> job4.

I suggest that either you eliminate the cyclic data or move on to an approach that will allow cyclic data

Denis Yuzvyk
Greenhorn
Posts: 22
• Number of slices to send:
Optional 'thank-you' note:
can you please give test data?
all my attempts failed : (
may be there is bug?

May be someone can point me to implementation of this algo?

Thanks.

Steve Fahlbusch
Bartender
Posts: 612
7
• Number of slices to send:
Optional 'thank-you' note:
Why don't you just use the test data (ie: the graph) in the wiki page you referenced in your first post?

Denis Yuzvyk
Greenhorn
Posts: 22
• Number of slices to send:
Optional 'thank-you' note:
for this grapth, i created following input:

I found such vertex and edges:
7 -> 11,8
5 -> 11
3 -> 8,10
11 -> 2,9,10
8 -> 9

so input:

but result is:
2,9,10,8,11,3,5,7
but it's wrong, coz on wiki page correct result must be

The graph shown to the left has many valid topological sorts, including:

* 7,5,3,11,8,2,9,10
* 7,5,11,2,3,10,8,9
* 3,7,8,5,11,10,9,2

Steve Fahlbusch
Bartender
Posts: 612
7
• Number of slices to send:
Optional 'thank-you' note:
Look at your output - it is in reverse order!

If you reverse your output youv'e got a correct solution :-) (congrats)

Now just work through your algorithm (like how you are adding and removing from the queue) and how you are building your solution and you should see where you have it backwards.
[ January 19, 2007: Message edited by: Steve Fahlbusch ]

Denis Yuzvyk
Greenhorn
Posts: 22
• Number of slices to send:
Optional 'thank-you' note:
but it is wrong too:

2,9,10,8,11,3,5,7
reverted:
7,5,3,11,8,10,9,2
from wiki:
7,5,3,11,8,2,9,10

Steve Fahlbusch
Bartender
Posts: 612
7
• Number of slices to send:
Optional 'thank-you' note:
Are you sure?

If you look at the wiki page it says that there are many solutions. And your reversed looks to me like it is correct.

Why would 7,5,3,11,8,10,9,2 not be a correct answer?

Denis Yuzvyk
Greenhorn
Posts: 22
• Number of slices to send:
Optional 'thank-you' note:
Oh! you are right!
at wiki says that:
The graph shown to the left has many valid topological sorts, including:

so all ok now!

Thanks!

 So I left, I came home, and I ate some pie. And then I read this tiny ad: We need your help - Coderanch server fundraiser https://coderanch.com/wiki/782867/Coderanch-server-fundraiser