Topological graph sorting java

Question

私はトポロジカルソートにいくつか問題があります。それはlopsを見つけることができますが、いくつかのタスク（またはそれを呼び出す場合は「ノード」）を数回カウントします。私は、問題は私がどのように読んだり、Edgeクラスを使っているかと思っていますが、どこが間違っているのか分かりません。すべてのヘルプは本当にいただければ幸いです:)ここ

enter code here 
import java.util.*; 
import java.io.*; 
import java.lang.*; 

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 id, name, time, staff; 
    Edge neste; 
    Task fra, til; 

    Edge(Task id) { 
    this.id = id; 
     } 
} 



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[i]); 
      } else { 
      til = ids[tmp].outEdge; 

      while(til.neste != null) { 
       til = til.neste; 
      } 
      til.neste = new Edge(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("ERROR!" + e.getMessage()); 
    } 
    } 


    static void skrivUt() { 
    for (Task sort : ids) { 
     System.out.print(sort.id + " " + sort.name); 
     Edge til = sort.outEdge; 
     while (til != null) { 
     System.out.print(" " + til.id.id); 
     til = til.neste; 
     } 
     System.out.println(); 
    } 
    } 

    static void topSort() { 
    LinkedList<Task> list = new LinkedList<Task>(); 
    ArrayList<Task> array = new ArrayList<Task>(); 
    Task temp; 
    int count = 0; 
    int totalTime = 0; 

    // Legger taskene i lista 
     for (Task t : ids) { 
     if(t.cntPredecessors == 0) { 
     list.add(t); 
     totalTime += t.time; 
     // System.out.println(t); 
     t.visited = true; 
     } 
    } 
    for (Task t : ids) { 
     if(t.cntPredecessors == 1) { 

     list.add(t); 
     totalTime += t.time; 
     // System.out.println(t); 
     t.visited = true; 
     } 
    } 

    // går i evig løkke til lista er tom. 
    while (!list.isEmpty()) { 
     temp = list.pop(); // fjerner elementet fra lista 
     array.add(temp); // legger inn i arraylisten 
     count++; 
     // System.out.println(temp); 
     for(Edge til = temp.outEdge; til!=null;til=til.neste) { 
     til.id.cntPredecessors--; 
     if(til.id.cntPredecessors==0) { 
      list.add(til.id); 
     } 
     } 
    } 
    if(count < antTask) { 
     System.out.println("A loop has been found. Terminating..."); 
     System.exit(0); 
    } 
    System.out.println("Topological sort: " + Arrays.toString(array.toArray()));// den sorterte "arraylisten" 
    System.out.println("Total time spend: " + totalTime); 
    } 

} // End class Input 

は、問題は（topSort()内）このループである入力ファイル

8 

1 Build-walls  4 2  5  0 
2 Build-roofs  6 4  1  0 
3 Put-on-wallpapers 1 2  1  2  0 
4 Put-on-tiles  1 3  2  0 
5 Build-foundation 4 2  0 
6 Make-floor   2 2  5  0 
7 Put-carpet-floor 4 2  6  2  0 
8 Move-in   4 4  3  7  0 

Answer 1

の例である：

for (Task t : ids) { 
    if(t.cntPredecessors == 1) { 

    list.add(t); 
    totalTime += t.time; 
    // System.out.println(t); 
    t.visited = true; 
    } 
} 

あなただけそれを削除する必要があります。

理由：このループは、受信エッジが1つあるノードlistに追加されます。後で（whileループ内）、これらのノードではcntPredecessorsフィールドが0に減少し、listにプッシュバックされ、2回カウントされる可能性があります。

今後、「ノイズ」が少ないもの、つまり問題を説明する小さなコード（またはほぼ最小）のコードにコードを絞り込んでください。これにより、潜在的な回答者への理解が容易になります（自分で問題を見るのに役立つかもしれません）。