import java.util.ArrayList;
import java.util.Iterator;// topo.java
// demonstrates topological sorting
// to run this program: C>java TopoApp
////////////////////////////////////////////////////////////////
class Vertex
{
  public String label;  
  public Vertex(String lab) { label = lab; }
}  

public class GraphSort
{
  private final int MAX_VERTS = 40;
  private Vertex vertexList[]; // list of vertices
  private int adjMat[][];      // adjacency matrix
  private int nVerts;          // current number of vertices
  private String sortedArray[];
  
  public GraphSort()               
  {
    vertexList = new Vertex[MAX_VERTS];
                                        // adjacency matrix
    adjMat = new int[MAX_VERTS][MAX_VERTS];
    nVerts = 0;
    for (int j=0; j<MAX_VERTS; j++)      // set adjacency
       for (int k=0; k<MAX_VERTS; k++)   //    matrix to 0
          adjMat[j][k] = 0;
    sortedArray = new String[MAX_VERTS];  // sorted vert labels
  }  

  public void addVertex(String lab)
  {
    vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end)
  {
    adjMat[start][end] = 1;
  }

  public String[] topologicalSort() 
  {
    int orig_nVerts = nVerts;  // remember how many verts
  
    while (nVerts > 0)  // while vertices remain,
    {
      // get a vertex with no successors, or -1
      int currentVertex = noSuccessors();
      if (currentVertex == -1)       // must be a cycle
      {
        System.out.println("ERROR: Graph has cycles");
        return null;
      }
      // insert vertex label in sorted array (start at end)
      sortedArray[nVerts-1] = vertexList[currentVertex].label;
  
      deleteVertex(currentVertex);  // delete vertex
    }  // end while
   
    // vertices all gone;  
    String[] s2 = new String[orig_nVerts];
    for (int j=0; j<orig_nVerts; j++)
        s2[j] = sortedArray[j];
      
    return s2;    
  } 

  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<nVerts; row++)  // for each vertex,
    {
      isEdge = false;                 // check edges
      for (int col=0; col<nVerts; col++)
      {
        if (adjMat[row][col] > 0 )   // if edge to
        {                         // another,
          isEdge = true;
          break;                    // this vertex
        }                         //    has a successor
      }                            //    try another
      if( !isEdge )                   // if no edges,
        return row;                  //    has no successors
    }
    return -1;                         // no such vertex
  }  // end noSuccessors()

  public void deleteVertex(int delVert)
  {
    if (delVert != nVerts-1)      // if not last vertex,
    {                         // delete from vertexList
      for (int j=delVert; j<nVerts-1; j++)
        vertexList[j] = vertexList[j+1];
                               // delete row from adjMat
      for (int row=delVert; row<nVerts-1; row++)
        moveRowUp(row, nVerts);
                               // delete col from adjMat
      for (int col=delVert; col<nVerts-1; col++)
        moveColLeft(col, nVerts-1);
    }
    nVerts--;                    // one less vertex
  }  // end deleteVertex

  private void moveRowUp(int row, int length)
  {
   for (int col=0; col<length; col++)
     adjMat[row][col] = adjMat[row+1][col];
  }

  private void moveColLeft(int col, int length)
  {
   for (int row=0; row<length; row++)
     adjMat[row][col] = adjMat[row][col+1];
  }

  // Test
  public static void print(String[] sortedArray)
  {
    System.out.print("Topologically sorted order: ");
    for (int j=0; j<sortedArray.length; j++)
      System.out.print( sortedArray[j] + "->" );
    System.out.println("");
  }
   
  public static void mainOld(String[] args)
  {
    GraphSort theGraph = new GraphSort();
    theGraph.addVertex("A");    // 0
    theGraph.addVertex("B");    // 1
    theGraph.addVertex("C");    // 2
    theGraph.addVertex("D");    // 3
    theGraph.addVertex("E");    // 4
    theGraph.addVertex("F");    // 5
    theGraph.addVertex("G");    // 6
    theGraph.addVertex("H");    // 7

    theGraph.addEdge(0, 3);     // AD
    theGraph.addEdge(0, 4);     // AE
    theGraph.addEdge(1, 4);     // BE
    theGraph.addEdge(2, 5);     // CF
    theGraph.addEdge(3, 6);     // DG
    theGraph.addEdge(4, 6);     // EG
    theGraph.addEdge(5, 7);     // FH
    theGraph.addEdge(6, 7);     // GH

    String[] ret = theGraph.topologicalSort();            // do the sort
    print(ret);
  }  // end main()
      
  public static void main(String[] args)
  {  
    ArrayList levels = new ArrayList();
    levels.add("L1");
    levels.add("L2");
    levels.add("L3");
    levels.add("L5");
    levels.add("L7");
    
    ArrayList hier1 = new ArrayList();
    hier1.add("L1");
    hier1.add("L2");
    hier1.add("L3");
    
    ArrayList hier2 = new ArrayList();
    hier2.add("L7");
    hier2.add("L3");
  
    hier2.add("L5");
    
    ArrayList hiers = new ArrayList();
    hiers.add(hier1);
    hiers.add(hier2);
  
    GraphSort theGraph = new GraphSort();
    for (Iterator it = levels.iterator(); it.hasNext();)
    {
      String level = (String) it.next();
      theGraph.addVertex(level);
    }
              
    for (Iterator it = hiers.iterator(); it.hasNext();)
    {
      ArrayList hier = (ArrayList) it.next();
      String prevLevel = null;    
      for (Iterator hit = hier.iterator(); hit.hasNext();)
      {
        String level = (String) hit.next();
        if (prevLevel != null)
        {
          int end = levels.indexOf(level);
          int start = levels.indexOf(prevLevel);            
          theGraph.addEdge(start, end);
          System.out.println("adding edge start=" + start + " end=" + end);
        }
        prevLevel = level;
      }     
    }
      
    String[] sortedArray = theGraph.topologicalSort();            // do the sort
    print(sortedArray);
  }  // end main()
   
}