Win a copy of Murach's Java Programming this week in the Beginning Java forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

How to implement topological search on a graph of quest nodes?  RSS feed

 
Tom Daly
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, I am trying to implement topological sort for a quest prerequisite method i am try to write from the algorithm below and am having trouble implementing the last parts of the algorithm. I'm not sure how to implement it and the language in the pseudo code language is confusing me as to what i need to write. I will include the pseudocode and what i have so far, if any one can help me figure out how to finish the method that would be great as I am stuck on how to finish the method. Thanks!

pseudocode:


my code:
 
Knute Snortum
Sheriff
Posts: 3834
91
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch!  Here are a few things I see with this code:

Your pseudo code is ambiguous because there are no END WHILEs or END FORs in it.  Is the FOR loop inside the WHILE loop or not?

Don't write if (condition == true), just write if (condition) {

The variable names are poorly chosen.  Avoid signle-letter names except for temporary variables that are used within about three lines.  Choose names that mean something.

For the pseudo code:
while H is non - empty do remove a quest n from H
I would use an enhanced for loop:

That's a start.
 
Piet Souris
Rancher
Posts: 1915
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Tom,

welcome to the ranch!

A slight problem is that I do not know the classes that you have in your code. So, suppose we have the vertices 0, 1, ..., N-1 and we have an adjacency matrix adj[N][N].

The algorithm is then:

for every vertex I, if column I of the adjacency matrix contains only zero's, put I into H.

If H is empty, then we have an invalid graph.

Next:

The whole of the adjacency matrix should now contain only zero's.

You will have to translate this simple scheme to the classes that you have.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!