• Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Devaka Cooray
  • Ron McLeod
  • paul wheaton
Saloon Keepers:
  • Tim Moores
  • Piet Souris
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Frits Walraven
  • Scott Selikoff

topological sort

 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello,
I need implement topological sort.
I found info about this type of sorting on
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
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
The knights of nee want a shrubbery. And a tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic