/**
 * 
 */
package chapter_4;

import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import datastructures.graph.AbstractGraph;
import datastructures.graph.DirectedGraph;
import datastructures.graph.Vertex;
import util.InputUtil;

/**
 * Question 4.7
 * 
 * @author Sudharsanan Muralidharan
 */
public class BuildOrder {
  AbstractGraph<Character> graph = null;
  List<Vertex<Character>> projects = new ArrayList<Vertex<Character>>();

  public BuildOrder() {
    graph = new DirectedGraph<Character>();
  }

  private void constructGraph(String[] input) {
    for (String line : input) {
      String[] values = line.split(" ");
      String action = values[0];
      switch (action) {
      case "vertex":
        char c = values[1].charAt(0);
        projects.add(graph.createVertex(c));
        break;
      case "edge":
        Vertex<Character> sourceVertex = graph.getVertex(values[1].charAt(0));
        Vertex<Character> destVertex = graph.getVertex(values[2].charAt(0));
        if (sourceVertex != null && destVertex != null) {
          graph.addEdge(sourceVertex, destVertex);
        }
        break;
      case "print":
        graph.print();
        break;
      }
    }
  }

  private String fetchBuildOrder() {
    Collections.sort(projects, new Comparator<Vertex<Character>>() {
      @Override
      public int compare(Vertex<Character> o1, Vertex<Character> o2) {
        return Integer.valueOf(o1.outgoingEdges.size()).compareTo(Integer.valueOf(o2.outgoingEdges.size()));
      }
    });

    Set<Vertex<Character>> visitedSet = new HashSet<Vertex<Character>>();
    StringBuilder builder = new StringBuilder();
    for (Vertex<Character> project : projects) {
      if (!visitedSet.contains(project)) {
        depthFirstTraversal(project, builder, visitedSet);
      }
    }

    return builder.toString();
  }

  private void depthFirstTraversal(Vertex<Character> sourceVertex, StringBuilder builder,
      Set<Vertex<Character>> visitedSet) {
    if (sourceVertex == null) {
      return;
    }

    visitedSet.add(sourceVertex);

    List<Vertex<Character>> neighbours = graph.neighboursOf(sourceVertex);
    for (Vertex<Character> vertex : neighbours) {
      if (!visitedSet.contains(vertex)) {
        depthFirstTraversal(vertex, builder, visitedSet);
      }
    }

    builder.append(sourceVertex.label).append(" ");
  }

  public static void main(String[] args) throws FileNotFoundException {
    String[] input = InputUtil.readContents(4, "build_order");
    BuildOrder buildOrder = new BuildOrder();
    buildOrder.constructGraph(input);
    System.out.println(buildOrder.fetchBuildOrder());
  }

  class Project {
    char label;
    int numDependencies = 0;

    public Project(char label, int numDependencies) {
      this.label = label;
      this.numDependencies = numDependencies;
    }
  }
}

@@ -1647,17 +1647,21 @@
     %7D);%0A
+    
 %0A
-
     Set%3C
@@ -1774,33 +1774,32 @@
 ilder();%0A    for
- 
 (Vertex%3CCharacte
@@ -1812,32 +1812,176 @@
 ject
- : projects) %7B%0A      if 
+:projects) %7B%0A      if(project.outgoingEdges.size() == 0) %7B%0A        visitedSet.add(project);%0A        builder.append(project.label).append(%22 %22);%0A      %7D else %7B%0A        if
 (!vi
@@ -2006,24 +2006,26 @@
 project)) %7B%0A
+  
         dept
@@ -2063,32 +2063,42 @@
 r, visitedSet);%0A
+        %7D%0A
       %7D%0A    %7D%0A%0A 
@@ -2091,25 +2091,29 @@
     %7D%0A    %7D%0A
+    
 %0A
-
     return b
@@ -2127,32 +2127,34 @@
 toString();%0A  %7D%0A
+  
 %0A  private void 
@@ -2227,22 +2227,16 @@
 builder,
-%0A     
  Set%3CVer
@@ -2267,25 +2267,24 @@
 et) %7B%0A    if
- 
 (sourceVerte
@@ -2312,25 +2312,29 @@
 turn;%0A    %7D%0A
+    
 %0A
-
     visitedS
@@ -2355,17 +2355,21 @@
 ertex);%0A
+    
 %0A
-
     List
@@ -2442,17 +2442,16 @@
 %0A    for
- 
 (Vertex%3C
@@ -2492,17 +2492,16 @@
       if
- 
 (!visite
@@ -2597,17 +2597,21 @@
 %7D%0A    %7D%0A
+    
 %0A
-
     buil
@@ -2936,17 +2936,19 @@
 ));%0A  %7D%0A
+  
 %0A
-
   class 
@@ -3002,16 +3002,20 @@
 es = 0;%0A
+    
 %0A    pub

Mark vertices with no outgoing edges as visited by default