# How to get all the solutions of topological sorting

Hi everyone I was trying to solve this problem http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=813 and I realized that it wants to get all the solutions of topological sorting problem, I know how to get only one possible solution and this is my code http://ideone.com/IiQxiu

```static ArrayList<Integer> [] arr;
static int visited [];
static Stack<Integer> a = new Stack<Integer>();
static boolean flag=false;

public static void graphcheck(int node){  //method to check if there is a cycle in the graph
visited[node] = 2;
for(int i=0;i<arr[node].size();i++){
int u =arr[node].get(i);
if(visited[u]==0){
graphcheck(u);
}else if(visited[u]==2){
flag=true;
return;
}
}
visited[node] = 1;
}

public static void dfs2(int node){            //method to get one possible topological sort which I want to extend to get all posibilites
visited[node] = 1;
for(int i=0;i<arr[node].size();i++){
int u =arr[node].get(i);
if(visited[u]==0){
dfs2(u);
}
}
a.push(node);
}

public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for(int k=0;k<tc;k++){
br.readLine();

String h[]= br.readLine().split(" ");
int n= h.length;
arr=new ArrayList[n];
visited = new int[n];
for( int i = 0; i < n; i++) {
arr[ i] = new ArrayList<Integer>();
}
String q[]=br.readLine().split(" ");
int y=q.length;
for(int i=0;i<y;i++){
int x=0;
int z=0;
for(int j=0;j<n;j++){
if(q[i].charAt(0)==h[j].charAt(0)){
x=j;
}else if(q[i].charAt(2)==h[j].charAt(0)){
z=j;
}
}
if(q[i].charAt(1)=='<'){
arr[x].add(z);
}
}
for(int i=0;i<n;i++){
if(visited[i]==0)
graphcheck(i);
}
if(flag){
System.out.println("NO");
}else{
a.clear();
Arrays.fill(visited, 0);
for(int i=0;i<n;i++){
if(visited[i]==0){
dfs2(i);
}
}
int z= a.size();
for(int i=0;i<z;i++){
int x =a.pop();
System.out.print(h[x]+" ");
}
System.out.println();
}

}
}
```

## Answer

A potential way would be to modify the algorithm specified by Khan, (1962), in which a topological sort is calculated using the following algorithm:

L ← Empty list that will contain the sorted elements

S ← Set of all nodes with no incoming edges

while S is non-empty do

```   remove a node n from S

insert n into L

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 S
```

if graph has edges then

```   return error (graph has at least one cycle)
```

else

```   return L (a topologically sorted order)
```

This calculates one topological sort, in order to generate all possible sorts. To get all possible sorts, you could think of the result as a tree, where the root is the first node, and each child of a node is one of the next values. Given a graph:

```    1 -> 3 -> 8
|    |    |
|    v    |
|    7    |
|        |
|      _ v
+--> 5 -> 9
```

The tree might look like:

```        1
/
3   5
/|  |
7 8 9 9
| |
9 9
```

However, after re-reading your problem:

Given a list of variable constraints of the form A < B, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the contraints A < B and A < C there are two orderings of the variables A, B and C that are consistent with these constraints: ABC and ACB.

I don’t believe this solution will provide you with the answers you are looking for, but you are more than welcome to try and implement it.

Also check out this algorithm.

Note:

I was going to refrain from posting this after re-reading your problem, however I decided against it, as this information may be useful to you.

Good luck.