Topological sorting

[w0rk4holic]

how do i generate all the topological ordering of (directed acyclic graph), i have written a program that can find 1 topological ordering, the problem is once i am finished i am left with a empty linked list as my algorithm involves deleting the traversed nodes which is crucial for the algorithm to work

[A picture is worth a thousand words]

here is the code:

package topological_sort;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;


public class Topological_Sort {

    public static class node {

        int inDeg, number;
        LinkedList<node> out;

        public node(int number) {
            this.number = number;
            this.inDeg = 0;
            this.out = new LinkedList();
        }
    }

    public static void main(String[] args) throws FileNotFoundException, IOException {
        BufferedReader fin = new BufferedReader(new FileReader("topo1.txt"));

        int nNodes, i, node1, node2;
        String edges;
        Scanner input;
        LinkedList<node> Vertices = new LinkedList();

        input = new Scanner(fin.readLine());
        nNodes = input.nextInt();

        for (i = 0; i < nNodes; i++) {
            node theNode = new node(i);
            Vertices.add(theNode);
        }

        input.reset();

        while ((edges = fin.readLine()) != null) {
            input = new Scanner(edges);
            node1 = input.nextInt();
            node2 = input.nextInt();

            node theNode1 = Vertices.get(node1);
            node theNode2 = Vertices.get(node2);

            theNode1.out.add(theNode2);
            theNode2.inDeg += 1;
        }

        Iterator i1 = Vertices.iterator();
        while (i1.hasNext()) {
            node theNode = (node) i1.next();
            if (theNode.inDeg == 0) {
                Iterator i2 = theNode.out.iterator();
                while (i2.hasNext()) {
                    node outNode = (node) i2.next();
                    outNode.inDeg -= 1;
                }
                Vertices.remove(theNode);
                i1 = Vertices.iterator();
                System.out.println(theNode.number);
            }
        }
    }
}

thanks !

(maybe this forum is not the right place for posting this but i could not find anywhere else to post, if you know of a forum that could help, please let me know, thanks!)

[ericklesterbran]

fuckoff