/*
 * DiGraph.java
 *
 * Created on December 8, 2008, 6:25 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package graph2;

/**
 *
 * @author suchenek
 */
//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008

class DiGraph {

private int         size;    //number of vertices
private LIST[] AdjLists; //array of adjacency lists
private boolean[]   mark;    //to mark "visited"
private boolean[]   tempmark;    //to mark "temporarily visited" 
                                // (for detection of back edges)
boolean cycle; //for acyclicity test
private LIST path;

//creates a graph with i unvisited vertices and no edges
public DiGraph(int i) {
size = i;
AdjLists = new LIST[i];
for (int j = 0; j < i; j++)
    AdjLists[j] = new LIST();
mark = new boolean[i];
tempmark = new boolean[i];
cycle = false;
path = new LIST();
}

// For testing only

public void Dump() {
     System.out.println("Dump start");

for (int v = 0; v < size; v++)
{
    LIST L = AdjLists[v];
    System.out.print("AdjList[" + v + "]: ");
for (POSITION p = L.First(); !p.isEqual(L.End()); p = L.Next(p))
    System.out.print(L.Select(p) + " ");
    System.out.println();
}
    System.out.println("Dump end");

    }

//Returns the size of the graph (number of vertices)

public int Size()
{
    return size;
}

//connects vertex v to vertex w with an edge (this direction only)
public void InsertEdge(int v, int w) {
    LIST L = AdjLists[v];
    L.Insert(L.End(), new Integer(w));
    }

//verifies if w is adjacent to v (that is,
//if there is an edge connecting v to w
public boolean IsAdjacent(int v, int w) 
{
    boolean found = false;
    LIST L = AdjLists[v];
    for (POSITION p = L.First(); !p.isEqual(L.End()); p = L.Next(p))
        if ((Integer)L.Select(p) == w) found = true;
return found;
}

//gets first unvisited vertex of G
//returns -1 if all vertices of G have been
//already visited
public int FirstUnvisited() {
int i;
for (i = 0; i < size; i++) if (!mark[i]) return i;
return -1;
}

//gets first unvisited vertex of G after v
//returns -1 if all vertices of G after v have been
//already visited
public int NextUnvisited(int v) {
int i;
for (i = v+1; i < size; i++) if (!mark[i]) return i;
return -1;
}
//gets the first vertex of G which is adjacent
//to v and is past i
//returns -1 if there are no vertices adjacent
//to v past i in G
public int NextAdj(int v, POSITION i) {
    LIST L = AdjLists[v];
if (i.isEqual(L.End())) return -1;
i = L.Next(i);
if (i.isEqual(L.End())) return -1;
return (Integer)(L.Select(i)); 
}

//gets the first vertex of G which is adjacent
//to v
//returns null if there are no vertices adjacent
//to v in G
public int FirstAdj(int v) {
return (Integer)AdjLists[v].Select(AdjLists[v].First());
}

//outputs v and marks it "visited"
public void Visit(int v) {
mark[v] = true;
System.out.println(v);
}

//Marks v "temporarily visited"
public void tempVisit(int v) {
tempmark[v] = true;
}

//Marks v "temporarilyunvisited"
public void unVisit(int v) {
tempmark[v] = false;
}

//verifies if v has been already visited
public boolean IsVisited(int v) {
return mark[v];
}

//verifies if v has been temporarily visited
public boolean IstempVisited(int v) {
return tempmark[v];
}

//traverses (a connected component) of graph G
//beginning with vertex v
//using the depth-first search strategy
public static void DFS(DiGraph G, int v) 
{
if (!G.IsVisited(v)) {
G.Visit(v);
LIST L = G.AdjLists[v];
for (POSITION w = L.First(); !w.isEqual(L.End()); w = L.Next(w)) 
    DFS(G, (Integer)L.Select(w));
System.out.println("Back out of " + v);

}
}

//Acyclicity test - seeks back arcs during DFS
public static void CycleDFS(DiGraph G, int v) {
//if (G.cycle) return;
if (!G.IsVisited(v)) {
G.path.Insert(G.path.End(), new Integer(v));
G.Visit(v);
G.tempVisit(v);
LIST L = G.AdjLists[v];
for (POSITION w = L.First(); !w.isEqual(L.End()); w = L.Next(w)) 
    CycleDFS(G, (Integer)L.Select(w));
G.unVisit(v);
G.path.Delete(G.path.Last()); 
System.out.println("Back out of " + v);
}
else if (G.IstempVisited(v)) 
{
    G.cycle = true;
    POSITION q;
    for (q = G.path.First(); (Integer)(G.path.Select(q)) != v; q = G.path.Next(q))
    {
        //Skipping beginning of the path that is not a part of the loop 
    }
    
    
    System.out.print("A cycle: ");
    for (POSITION p = q; !p.isEqual(G.path.End()); p = G.path.Next(p))
        System.out.print(G.path.Select(p) + " ");
    System.out.println(v); //To visualize how the loop loops
//    G.path.Delete(G.path.Last());
}
}
}