Topological Sort Example

TopologicalSort.groovy

import java.util.ArrayDeque;
import java.util.Deque;

class TopologicalSort {
  static final int NUM_VERTEXES = 7

  void applyTopologicalSortLocally(Graph g, Integer vertex, Set<Integer> visited, Deque<Integer> stack) {
    visited.add(vertex)
    g.getAdjacentVertexes(vertex).each { adjVertex ->
      if (!visited.contains(adjVertex)) {
        applyTopologicalSortLocally g, adjVertex, visited, stack
      }
    }
    stack.offerFirst vertex
  }

  Deque<Integer> sort(Graph g) {
    Deque<Integer> stack = new ArrayDeque<>()
    Set<Integer> visited = new HashSet<>()

    (0..g.getNumOfVertexes() - 1).each { vertex ->
      if (!visited.contains(vertex)) {
        applyTopologicalSortLocally g, vertex, visited, stack
      }
    }

    stack
  }

  static void main(String[] args) {
    Graph g = new Graph(NUM_VERTEXES)
    g.addEdge 0, 2
    g.addEdge 1, 2
    g.addEdge 1, 4
    g.addEdge 2, 3
    g.addEdge 3, 5
    g.addEdge 4, 5
    g.addEdge 5, 6

    g.print()

    println()

    TopologicalSort ts = new TopologicalSort()
    Deque<Integer> sortedVertexes = ts.sort(g)

    sortedVertexes.each { vertex ->
      println vertex
    }
  }
}

class Graph {
  int[][] adjacencyMatrix

  Graph(int vertexes) {
    adjacencyMatrix = new int[vertexes][vertexes]
  }

  void addEdge(Integer source, Integer target) {
    adjacencyMatrix[source][target] = 1
  }

  int getNumOfVertexes() {
    adjacencyMatrix.length;
  }

  int[] getAdjacentVertexes(Integer vertex) {
    Set<Integer> adjacentVertexes = new HashSet<Integer>();

    adjacencyMatrix[vertex].eachWithIndex { adjVertex, idx ->
      if (adjVertex == 1) {
        adjacentVertexes.add idx
      }
    }

    adjacentVertexes
  }

  void print() {
    adjacencyMatrix.each { row ->
      row.each { col ->
        print col + '\t'
      }
      println()
    }
  }
}