Topological sorting and cycles

Question

I've got some input files from my teacher wich we are supposed to test the program with. The task is to read from file, create a directed graph and print out the output. But if there is a cycle we are supposed to terminate the program.

I've got some files named house1 and house2. in the file house1 there isn't any cycles, but in house2 there is. But I can't figure out why my program can't find that cycle. Here I have all the code, and any help saying where I should be looking at is preciated :)

import java.util.*;
import java.io.*;
import java.lang.*;

class Input {

    public static void main(String[] args) {

    if (args.length == 0) {
        System.out.println("enter a filename!");
        System.exit(1);
    } else if (args.length == 1) {
        String fil = args[0]+".txt";
        LesFraFil(fil);
        //  skrivUt();
        topSort();
    } else {
        System.out.println("too many parameters, try again...");
    }
    }

    static int antTask;
    static Task[] ids;
    static int tTid;
    static void LesFraFil(String fil) {

    int i = 0;
    int j;
    try {

        String lest;

        Scanner in = new Scanner(new FileReader(fil));
        Edge til;

        int counter = 0;
        antTask = in.nextInt();
        ids = new Task[antTask];
        System.out.println(antTask);
        while (in.hasNextLine()) {

        lest = in.nextLine();
        // hvis tom linje, så hopper den over
        if(lest.trim().length() == 0) continue;

        String split[] = lest.split("\\s+");
        int id = Integer.parseInt(split[0]);
        String act = split[1];
        int tid = Integer.parseInt(split[2]);
        int staff = Integer.parseInt(split[3]);
        int depA = Integer.parseInt(split[4]);
        tTid += tid;
        ids[i] = new Task(id, act, tid, staff);
        j = 4;

        /*
         * Lesingen av inputen skal avbrytes når den leser 0.
         * j er den som holder på hvor langt vi er i split arrayet
         * når den møter på 0 
         */
        while(split[j].compareTo("0") != 0) {
            int tmp = Integer.parseInt(split[j])-1;

            //  System.out.println(tmp+1 + " Aktivitetens navn : " + act); //+ " tiden aktiviteten tar tid: " + tid + " avhengihet: " + split[j]);

            j++;

            if (ids[tmp] == null) {
            ids[tmp] = new Task(id, act, tid, staff);
            ids[tmp].visited = true;
            }
            ids[i].cntPredecessors++;
            if(ids[tmp].outEdge == null) {
            ids[tmp].outEdge = new Edge(ids[tmp], ids[i]);
            } else {
            til = ids[tmp].outEdge;

            while(til.neste != null) {
                til = til.neste;
            }
            //  til.neste = new Edge(ids[tmp], ids[i]);
            }
        }
        counter++;
        i++;
        }

        if (antTask == counter) {
        System.out.println("Lesinga gikk som planlagt av fil: " + fil);
        System.out.println("Total arbeidstid: " + tTid);// + antTask + " == " + counter );
        } else {
        System.out.println("Noe gikk galt avslutter!");
        System.out.println(antTask + " || " + counter);
        System.exit(2);
        }
        in.close();
    } catch (Exception e) {
        System.err.println("Dette gikk galt med lesinga: " + e.getMessage());
    }
    }

     static void topSort() {
    LinkedList<Task> list = new LinkedList<Task>();
    ArrayList<Task> array = new ArrayList<Task>();

    Task temp;
    int totalTime = 0;
    int counter = 0;

    for(Task t : ids) {
        if (t.cntPredecessors == 0) {
        list.add(t);

        }
    }
    while (!list.isEmpty()) {
        temp = list.pop();
        counter++;
        array.add(temp);
        System.out.println("Time " + totalTime + "\t Started task " + temp.id + "\t Staff: " + temp.staff + ", Task done " + temp.id);
        totalTime += temp.time;

        for (Task t : ids)  {
        if (--t.cntPredecessors == 0) 
        list.add(t);
        }
    }


    if(counter < antTask) { // checking for loop
        System.out.println(counter + " != " + antTask);
        System.out.println("En løkke er funnet i grafen. Avslutter...");
        System.exit(0);
    }
    System.out.println("Topological sort: " + Arrays.toString(array.toArray()));// den sorterte "arraylisten" 
    System.out.println("Total tid brukt er: " + totalTime);
    }

}

class Task {

    int id, time, staff;
    int depA, depB;
    String name;
    int eStart, lStart;
    Edge outEdge;
    int cntPredecessors;
    boolean visited;

    Task(int id, String name, int time, int staff)  {
    this.id = id;
    this.name = name;
    this.time = time;
    this.staff = staff;
    visited = false;
    }

    public String getName() {
    return name;
    }
    public String toString() {
    return name;
    }
}

class Edge {

    Task fra, til;
    Task id, name, time, staff;
    Edge neste;
    //  Task fra, til;

    Edge(Task fra, Task til) { //, Task fra, Task til) {//, Task name, Task time, Task staff) {
    this.fra = fra;
    this.til = til;

//  this.id = id;
    //  this.fra = fra;
    //  this.til = til;
    /*  this.name = name;
    this.time = time;
    this.staff = staff;*/
    }

    public Task getTil() {
    return til;
    }
}

Answer 1

I'll write here some kind of simple algorithm, what you are doing is a topological sort

Important thing is that topological sort is using DFS algorithm O(V+E)

What you should do is to create some kind of additional attribute for each Node (let's call it String color and set it's initial value to white.

As you'll iterate through your nodes, set it's color to gray, and continue doing a DFS, after it's done, set it's color to black.

The point is - if you visit a node with color == gray or color == black you found a cycle

I recommend reading a Topological sort chapter from Introduction to Algorithms

And let's see your code!

You read something from input file and important part is here:

        while (!list.isEmpty()) {
            temp = list.pop();
            counter++;
            array.add(temp);
            System.out.println("Time " + totalTime + "\t Started task " + temp.id + "\t Staff: " + temp.staff + ", Task done " + temp.id);
            totalTime += temp.time;

            for (Task t : ids) {
                if (--t.cntPredecessors == 0) {
                    list.add(t);
                }
            }
        }

well sorry for saying it like this, but your code is little messy, without english documentation, etc. but I think you are missing the part of coloring your nodes, that can be the reason why you can't find a cycle ( and I suppose you never end ) , because you miss to "color" your nodes, so nobody knows that you have already visited them

btw my "color" attribute is called visited in your code (you can use boolean but then you can't color it to gray/black/white as in the book I posted here)

I guess you set it to true during initialization (you should set it to false and set it to true if you have already processed/visited the node)

// Sorry if I'm wrong but it's 1A.M. here, I just think this might be the issue

// + if you do this on directed graph, and exit if you detect cycle, you get and cycle detection algorithm in O(V) time :)