import Liste. *;
/**
 * Verwaltet einen Graphen mit Hilfe einer Adjazenzmatrix.
 * 
 * @author Albert
 * @version 1.0
 */
class GRAPH_MATRIX
{
    /** Feld mit den Knoten. */
    private KNOTEN [] knoten;
    /** Adjazenzmatrix */
    private int [] [] matrix;
    /** Zaehler fuer das Einfuegen der Knoten. */
    private int anzahlKnoten;
    /** Markierung fuer besuchte Knoten */
    private boolean [] besucht;
    
    /** Liste der gerade in Arbeit befindlichen Knoten der Breitensuche */
    private LISTE offeneKnoten;

    /**
     * Legt die Felder mit gegebener Groesse an.
     * @param anzahl Anzahl der zu speichernden Knoten
     */
    GRAPH_MATRIX (int anzahl)
    {
        knoten = new KNOTEN [anzahl];
        matrix = new int [anzahl] [anzahl];
        besucht = new boolean [anzahl];
        anzahlKnoten = 0;

    }
    
    /**
     * Gibt den Index des Knotens oder -1, wenn es keinen Knoten mit diesem Bezeichner gibt.
     * @return Knotenindex oder -1
     */
    private int KnotenNummerGeben (String bezeichner)
    {
        for (int i = 0; i < anzahlKnoten; i++)
        {
            if (knoten [i]. BezeichnungGeben (). equals (bezeichner))
            {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * Fuegt einen neuen Knoten mit dem angegebenen Bezeichner ein.
     * Falls das Feld voll ist oder der Bezeichner schon existiert, wird nichts eingefuegt.
     * @param bezeichner Bezeichner des neuen Knoten
     */
    void KnotenEinfuegen (String bezeichner)
    {
        if ((anzahlKnoten < knoten. length) && (KnotenNummerGeben (bezeichner) == -1))
        {
            knoten [anzahlKnoten] = new KNOTEN (bezeichner);
            matrix [anzahlKnoten] [anzahlKnoten] = 0;
            for (int i = 0; i < anzahlKnoten; i++)
            {
                matrix [i] [anzahlKnoten] = -1;
                matrix [anzahlKnoten] [i] = -1;
            }
            anzahlKnoten += 1;
        }
    }
    
    /**
     * Fuegt eine neue Kante in den Graphen ein.
     * @param von Bezeichner des Startknotens
     * @param nach Bezeichner des Zielknotens
     * @param gewichtung Gewicht der Kante
     */
    void KanteEinfuegen (String von, String nach, int gewichtung)
    {
        int vonNummer;
        int nachNummer;
        vonNummer = KnotenNummerGeben (von);
        nachNummer = KnotenNummerGeben (nach);
        if ((vonNummer != -1) && (nachNummer != -1) && (vonNummer != nachNummer))
        {
            matrix [vonNummer] [nachNummer] = gewichtung;
            matrix [nachNummer] [vonNummer] = gewichtung;
        }
    }
    
    /**
     * Gibt die Adjazenzmatrix aus.
     */
    void Ausgeben ()
    {
        int breite = 4;
        String fueller = "    ";
        System. out. print (fueller);
        for (int i = 0; i < anzahlKnoten; i++)
        {
            System. out. print (knoten [i]. BezFormatGeben (breite));
        }
        System. out. println ();
        for (int zeile = 0; zeile < anzahlKnoten; zeile++)
        {
            System. out. print (knoten [zeile]. BezFormatGeben (breite));
            for (int spalte = 0; spalte < anzahlKnoten; spalte++)
            {
                System. out. print ((matrix [zeile] [spalte] + fueller). substring (0, breite));
            }
            System. out. println ();
        }
    }
    
    /**
     * Erledigt die Aufgabe, einen Knoten zu besuchen.
     * @param knotenNummer der zu besuchende Knoten
     */
    private void Besuchen (int knotenNummer)
    {
        besucht [knotenNummer] = true;
        System. out. print (knoten [knotenNummer]. BezeichnungGeben () + "; ");
        
        for (int abzweigNummer = 0; abzweigNummer < anzahlKnoten; abzweigNummer ++)
        {
            if ((matrix [knotenNummer] [abzweigNummer] > 0) && (! besucht [abzweigNummer]))
            {
                Besuchen (abzweigNummer);
            }
        }
        
        System. out. println (knoten [knotenNummer]. BezeichnungGeben () + "(fertig);");
    }
    
    /**
     * Rahmen fuer die Tiefensuche.
     * @param startKnoten Bezeichner des Startknotens
     */
    void TiefenSuche (String startKnoten)
    {
        int startNummer;
        startNummer = KnotenNummerGeben (startKnoten);
        if (startNummer != -1)
        {
            for (int i = 0; i < anzahlKnoten; i++)
            {
                besucht [i] = false;
            }
            Besuchen (startNummer);
        }
    }
     
    
    /**
     * Breitensuche.
     * @param startKnoten Bezeichner des Startknotens
     */
    void BreitenSuche (String startKnoten)
    {
        int startNummer;
        int aktKnoten;
        KNOTENINFO info;
        startNummer = KnotenNummerGeben (startKnoten);
        if (startNummer != -1)
        {
            for (int i = 0; i < anzahlKnoten; i++)
            {
                besucht [i] = false;
            }
            offeneKnoten = new LISTE ();
            aktKnoten = startNummer;
            do
            {
                System. out. println (knoten [aktKnoten]. BezeichnungGeben ());
                besucht [aktKnoten] = true;
                for (int k = 0; k < anzahlKnoten; k++)
                {
                    info = new KNOTENINFO (k);
                    if ((matrix [aktKnoten] [k] > 0) && (! besucht [k]) && (! offeneKnoten. Enthaelt (info)))
                    {
                        offeneKnoten. HintenEinfuegen (info);
                        
                    }
                }
                info = (KNOTENINFO) offeneKnoten. AnfangEntfernen ();
                if (info != null)
                {
                    aktKnoten = info. KnotennummerGeben ();
                }
                else
                {
                    aktKnoten = -1;
                }
            } while (aktKnoten >= 0);
        }
    }
    

}