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

package graph;

/**
 *
 * @author suchenek
 */

//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008

class DiGraph {

private int         size;    //number of vertices
private boolean[][] AdjMtrx; //adjacency matrix
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; //for cycles

//creates a graph with i unvisited vertices and no edges
public DiGraph(int i) {
size = i;
AdjMtrx = new boolean[i][i];
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++)
{
    System.out.print("AdjList[" + v + "]: ");
//    System.out.println(" Test: " + FirstAdj(v));
    for (int p = FirstAdj(v); p >= 0; p = NextAdj(v, p))
        System.out.print(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) {
AdjMtrx[v][w] = true;
}

//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) {
return AdjMtrx[v][w];
}

//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, int i) {
int w;
for (w=i+1; w < size; w++) if (AdjMtrx[v][w]) return w;
return -1;
}

//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 NextAdj(v, -1);
}

//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) {
int w;
if (!G.IsVisited(v)) {
G.Visit(v);
for (w = G.FirstAdj(v); w != -1; w = G.NextAdj(v, w)) DFS(G, 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.IsVisited(v)) {
//System.out.println("Inserting " + v);
G.path.Insert(G.path.End(), new Integer(v));
G.Visit(v);
G.tempVisit(v);
for (int w = G.FirstAdj(v); w != -1; w = G.NextAdj(v, w)) CycleDFS(G, 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());
}
}
}