topological sort

[Denis Yuzvyk]

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.

    
------------------MyData.java------------------
 
public class MyData {
    public String job;
public String [] others;
public MyData(String job, String [] other) {
this.job = job;
this.others = other;
}
}
 
---------------TopSort.java-------------------
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Iterator;
 
public class TopSort {
 
public static String[] topologicalSort(MyData[] data) throws Exception {
/*
 * Q ? Set of all nodes with no incoming edges while Q is non-empty do
 * remove a node n from Q output n for each node m with an edge e from n
 * to m do remove edge e from the graph if m has no other incoming edges
 * then insert m into Q if graph has edges then output error message
 * (graph has a cycle)
 */
int n = data.length;
Map graph = new HashMap();
Queue q = new LinkedList();
String[] sorted = new String[n];
// Graph construction
for (int i = 0; i < data.length; i++) {
// for each statistic name s
graph.put(data[i].job, new HashSet());
String[] requiredJobs = data[i].others;
for (int j = 0; j < requiredJobs.length; j++) {
// for each String si in requiredStats
((Set) graph.get(data[i].job)).add(requiredJobs[j]);
}
// Initial nodes in q
if (((Set) graph.get(data[i].job)).size() == 0)
q.add(data[i].job);
}
 
// Getting the nodes in sorted order
int index = 0;
while (q.size() > 0) {
String s = (String) q.remove();
sorted[index++] = s;
Iterator iter = graph.keySet().iterator();
while (iter.hasNext()) {
// for each key in graph
// check if node is not already removed
Object key = iter.next();
if (((Set) graph.get(key)).size() != 0) {
((Set) graph.get(key)).remove(s);
// if this node now has zero incoming edges
if (((Set) graph.get(key)).size() == 0) {
q.add(key);
}
}
}
}
 
if(index<n)
  throw new Exception("Cycle detected, exiting ....");
 
return sorted;
}
 
public static void main(String[] args) throws Exception {
MyData d1 = new MyData("job1",new String [] {"job3","job5","job4"});
MyData d2 = new MyData("job3",new String [] {"job5","job6"});
MyData d3 = new MyData("job4",new String [] {"job2","job7"});
MyData d4 = new MyData("job7",new String [] {"job1","job2","job4"});
String [] sorted = TopSort.topologicalSort(new MyData [] {d1,d2,d3,d4});
for (int i = 0; i < sorted.length; i++) {
System.out.println(sorted[i]);
}
 

}
 
}

[Steve Fahlbusch]

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]

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]

Why don't you just use the test data (ie: the graph) in the wiki page you referenced in your first post?

[Denis Yuzvyk]

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:

MyData d1 = new MyData("7",new String [] {"11","8"});
MyData d2 = new MyData("5",new String [] {"11"});
MyData d3 = new MyData("3",new String [] {"8","10"});
MyData d4 = new MyData("11",new String [] {"2","9","10"});
MyData d5 = new MyData("8",new String [] {"9"});
MyData d6 = new MyData("2",new String [] {});
MyData d7 = new MyData("9",new String [] {});
MyData d8 = new MyData("10",new String [] {});
String [] sorted = TopSort.topologicalSort(new MyData [] {d1,d2,d3,d4,d5,d6,d7,d8});

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]

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]

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]

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]

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!