<commit_before>/**
 * 
 */
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 <NAME>
 */
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;
    }
  }
}<commit_msg>Mark vertices with no outgoing edges as visited by default<commit_after>/**
 * 
 */
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 <NAME>
 */
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(project.outgoingEdges.size() == 0) {
        visitedSet.add(project);
        builder.append(project.label).append(" ");
      } else {
        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;
    }
  }
}
{'fraction_non_alphanumeric': 0.12502019059925698, 'fraction_numerical': 0.00533031820384429, 'mean_word_length': 3.3, 'pattern_counts': {'":': 6, '<': 51, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3433485', 'n_tokens_mistral': 1813, 'n_tokens_neox': 1762, 'n_words': 368}