import java.io.*;
import jsjf.CircularArrayQueue;
import jsjf.ArrayStack;

// Dybde-først og bredde-først traversering av graf.
//
// Bruker en enkel urettet graf med nabomatrise, der data i nodene
// bare er en tekststreng (superklassen enkelGraf)
//
public class traverserGraf_2 extends enkelGraf
{
    // Bruker en boolsk array til å merke av oppsøkte noder under
    // traversering
    boolean oppsokt[];

    // Konstruktør, leser inn en graf fra fil
    //
    public traverserGraf_2(String filNavn)
    {
	super(filNavn);
	oppsokt = new boolean[n];
    }

    // Dybde-først traversering med start i gitt node
    // Oppsøker hver node og skriver ut data i noden
    //
    public void DFS(int start)
    {
	// Markerer alle noder som ikke oppsøkte
	for (int i = 0; i < n; i++)
	    oppsokt[i] = false;

	// Kaller en intern rekursiv metode som gjør selve
	// traverseringen
	rDFS(start);

	System.out.println();
    }

    // Intern rekursiv dybde-først traversering med start i gitt node
    //
    private void rDFS(int x)
    {
	// Skriver ut innholdet i noden
	System.out.print(data[x] + " ");

	// Markerer at denne noden er oppsøkt
	oppsokt[x] = true;

	// Oppsøker rekursivt alle nodens naboer som ikke er oppsøkt
	// tidligere
	for (int y = 0; y < n; y++)
	    if (nabo[x][y] && !oppsokt[y])
		rDFS(y);
    }


    // Iterativ dybde-først traversering med start i gitt node
    // Bruker stack-modulen fra læreboka
    //
    public void iDFS(int start)
    {
	// Markerer alle noder som ikke oppsøkte
	for (int i = 0; i < n; i++)
	    oppsokt[i] = false;

	// Lager ny tom stack med heltall/nodenumre
        ArrayStack<Integer> S = new ArrayStack<Integer>(); 

	// Legger start-noden på stack
	S.push(new Integer(start));

	// Markerer at startnoden er lagret/oppsøkt, slik at den ikke
	// legges i kø en gang til senere
	oppsokt[start] = true;

	// Går i løkke inntil stacken er tom og alle noder er oppsøkt
	while (!S.isEmpty())
	{
	    // Tar ut første node fra stack og oppsøker/skriver ut
	    // denne
	    int x = S.pop().intValue();
	    System.out.print(data[x] + " ");

	    // Legger alle uoppsøkte/ikke-lagrede naboer til nåværende
	    // node på stacken, slik at de oppsøkes i stigende
	    // rekkefølge
	    for (int y = n-1; y >= 0; y--)
		if (nabo[x][y] && !oppsokt[y])
		{
		    S.push(new Integer(y));
		    oppsokt[y] = true;
		}
	}
	System.out.println();
    }
 
    
    // Bredde-først traversering med start i gitt node
    // Bruker kø-modulen fra læreboka
    //
    public void BFS(int start)
    {
	// Markerer alle noder som ikke oppsøkte
	for (int i = 0; i < n; i++)
	    oppsokt[i] = false;

	// Lager ny tom kø med heltall/nodenumre
        CircularArrayQueue<Integer> Q = new CircularArrayQueue<Integer>(); 

	// Legger start-noden først i køen
	Q.enqueue(new Integer(start));

	// Markerer at startnoden er lagret/oppsøkt, slik at den ikke
	// legges i kø en gang til senere
	oppsokt[start] = true;

	// Går i løkke inntil køen er tom og alle noder er oppsøkt
	while (!Q.isEmpty())
	{
	    // Tar ut første node fra køen og oppsøker/skriver ut
	    // denne
	    int x = Q.dequeue().intValue();
	    System.out.print(data[x] + " ");

	    // Legger alle uoppsøkte/ikke-lagrede naboer til nåværende
	    // node bakerst i køen
	    for (int y = 0; y < n; y++)
		if (nabo[x][y] && !oppsokt[y])
		{
		    Q.enqueue(new Integer(y));
		    oppsokt[y] = true;
		}
	}
	System.out.println();
    }
 
    // Testprogram
    //
    public static void main(String args[])
    {
	// Leser navnet på en fil med grafdata som input fra
	// kommandolinjen
	String filNavn = " ";
	try
	{
	     if (args.length != 1)
		 throw new IOException("Mangler filnavn");
	     filNavn = args[0];
       	}
        catch (Exception e)
	{
	     System.err.println(e);
	     System.exit(1);
	}

	// Oppretter ny graf
	traverserGraf_2 G = new traverserGraf_2(filNavn);

	// Rekursiv dybde-først traversering en gang med start i hver
	// node
	System.out.println("Rekursiv DFS:");
	for (int i = 0; i < G.antallNoder(); i++)
	    G.DFS(i);

	// Iterativ dybde-først traversering en gang med start i hver
	// node
	System.out.println("\nIterativ DFS:");
	for (int i = 0; i < G.antallNoder(); i++)
	    G.iDFS(i);

	// Bredde-først traversering en gang med start i hver node
	System.out.println("\nBFS:");
	for (int i = 0; i < G.antallNoder(); i++)
	    G.BFS(i);
    }
}