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.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);


        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);

            theNode2.inDeg += 1;

        Iterator i1 = Vertices.iterator();
        while (i1.hasNext()) {
            node theNode = (node);
            if (theNode.inDeg == 0) {
                Iterator i2 = theNode.out.iterator();
                while (i2.hasNext()) {
                    node outNode = (node);
                    outNode.inDeg -= 1;
                i1 = Vertices.iterator();

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!)

This article has been dead for over six months. Start a new discussion instead.