// Tidligere eksamensoppgave, med graf og søketre
// Koden er kompilert, men ikke testet

public class uke_15_6
{
    // Klassen for noder i grafen
    class grafNode
    {
	int antNaboer;  // Antall naboer
	int nabo[];     // Nodenummere for alle direkte naboer
	int lengde[];   // Kantlengder
    };
    
    // Array med noder som lagrer hele grafen
    grafNode graf[];

    // Oppgave b: Utskrift av hele grafen
    void skrivNaboer(grafNode graf[], int n)
    {
	for (int i = 0; i < n; i++)
	{
	    System.out.print(i + ": ");
	    for (int j = 0; j < graf[i].antNaboer; j++)
	    {
		System.out.print(graf[i].nabo[j] + "-" +
				 graf[i].lengde[j] + " ");
	    }
	    System.out.println();
	}
    }

    // Oppgave c: Sjekker om en gitt vei finnes/er lovlig
    // Iterativ versjon
    boolean lovligVei(grafNode graf[], int n, int vei[], int antNoder)
    {
	if (antNoder < 2)
	    return true;

	int fra = vei[0], til = vei[1];
	
	for (int i = 1; i < antNoder-1; i++)
	{
	    // Sjekker om kanten fra->til finnes i grafen
	    boolean veiOK = false;
	    for (int j = 0; j < graf[fra].antNaboer; j++)
	    {
		if (graf[fra].nabo[j] == til)
		    veiOK = true;          
	    }
	    if (veiOK == false)
		return false;
	    fra = til;
	    til = vei[i+1];
	}
	return true;
    }

    // Klassen for noder i søketreet
    class treNode
    {
	int lengde;    // Kantlengde
	int til, fra;  // Nodenummere i grafen for de to nodene som
	               // er knyttet til hverandre med denne kanten
	treNode v,h;   // Pekere til venstre og høyre barn i treet
    };

    // Oppgave d; Kopierer grafen over i et søketre med kantlengder
    treNode kantTre(grafNode graf[], int n)
    {
	treNode rot = null;

	for (int i = 0; i < n; i++)
	    for (int j = 0; j < graf[i].antNaboer; j++)
		rot = settInnKant(rot, graf[i].lengde[j],
				  i, graf[i].nabo[j]);
	return rot;
    }    

    // Hjelpemetode: Rekursiv innsetting av en kant i søketreet
    treNode settInnKant(treNode rot, int lengde, int fra, int til)
    {
	if (rot == null)
	{
	    rot = new treNode();
	    rot.lengde = lengde;
	    rot.fra = fra;
	    rot.til = til;
	    rot.v = rot.h = null;

	}
	else if (lengde < rot.lengde)
	    rot.v = settInnKant(rot.v, lengde, fra, til);
	else
	    rot.h = settInnKant(rot.h, lengde, fra, til);
	return rot;
    }
}