#include <stdio.h>
#include <limits.h>
 
class Vertex 
{
  public char label;
  public Vertex(char lab) 
  {
    label = lab;
  }
}
 
public class Graphs 
{
  private final int MAX_VERTS = 20;
  private Vertex vertexList[]; // list of vertices
  private int matrix[][]; // adjacency matrix
  private int numVerts; // current number of vertices
  private char sortedArray[];
  public Graphs() 
  {
    vertexList = new Vertex[MAX_VERTS];
    matrix = new int[MAX_VERTS][MAX_VERTS];
    numVerts = 0;
    for (int i = 0; i < MAX_VERTS; i++)
      for (int k = 0; k < MAX_VERTS; k++)
        matrix[i][k] = 0;
    sortedArray = new char[MAX_VERTS]; // sorted vert labels
  }
 
  public void addVertex(char lab) 
  {
    vertexList[numVerts++] = new Vertex(lab);
  }
 
  public void addEdge(int start, int end) 
  {
    matrix[start][end] = 1;
  }
 
  public void displayVertex(int v) 
  {
    printf(vertexList[v].label);
  }
 
  // toplogical sort
  public void topo() 
  {
    int orig_nVerts = numVerts; 
 
	//vertices remain,
    while (numVerts > 0)
    {
      // get a vertex with no successors, or -1
      int currentVertex = noSuccessors();
      if (currentVertex == -1) // must be a cycle
      {
        printf("ERROR: Graph has cycles");
        return;
      }
      // insert vertex label in sorted array (start at end)
      sortedArray[numVerts - 1] = vertexList[currentVertex].label;
 
      deleteVertex(currentVertex); // delete vertex
    }
 
    // vertices all gone; display sortedArray
    printf("Topologically sorted order: ");
    for (int j = 0; j < orig_nVerts; j++)
      printf(sortedArray[j]);
    printf("");
  }
 
  public int noSuccessors() // returns vert with no successors (or -1 if no such verts)
  { 
    boolean isEdge; // edge from row to column in adjMat
 
    for (int row = 0; row < numVerts; row++) {
      isEdge = false; // check edges
      for (int col = 0; col < numVerts; col++) {
        if (matrix[row][col] > 0) // if edge to another,
        {
          isEdge = true;
          break; 
        }
      }
      if (!isEdge) 
        return row;
    }
    return -1; 
  }
 
  public void deleteVertex(int delVert) {
    if (delVert != numVerts - 1) // if not last vertex, delete from vertexList
    {
      for (int j = delVert; j < numVerts - 1; j++)
        vertexList[j] = vertexList[j + 1];
 
      for (int row = delVert; row < numVerts - 1; row++)
        moveRowUp(row, numVerts);
 
      for (int col = delVert; col < numVerts - 1; col++)
        moveColLeft(col, numVerts - 1);
    }
    numVerts--; // one less vertex
  }
 
  private void moveRowUp(int row, int length) {
    for (int col = 0; col < length; col++)
      matrix[row][col] = matrix[row + 1][col];
  }
 
  private void moveColLeft(int col, int length) {
    for (int row = 0; row < length; row++)
      matrix[row][col] = matrix[row][col + 1];
  }
 
  public static void main(String[] args) {
    Graphs g = new Graphs();
    g.addVertex('A'); // 0
    g.addVertex('B'); // 1
    g.addVertex('C'); // 2
    g.addVertex('D'); // 3
    g.addVertex('E'); // 4
    g.addVertex('F'); // 5
    g.addVertex('G'); // 6
    g.addVertex('H'); // 7
 
    g.addEdge(0, 3); // AD
    g.addEdge(0, 4); // AE
    g.addEdge(1, 4); // BE
    g.addEdge(2, 5); // CF
    g.addEdge(3, 6); // DG
    g.addEdge(4, 6); // EG
    g.addEdge(5, 7); // FH
    g.addEdge(6, 7); // GH
 
    g.topo(); // do the sort
  }
}