import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;

/**
 * Diese Klasse modelliert gewichtete, ungerichtete Graphen.
 * Über die Schnittstelle können Knoten und gewichtete Kanten
 * in einen Graphen eingefügt werden.
 * 
 * @author Axel Schmolitzky
 * @version 2007-02
 */
public class Graph implements Iterable<Knoten>
{
    private Set<Knoten> _knotenmenge;
    private Set<Knoten> _verlauf;
    private boolean verbundenx;
    private Set<Knoten> _delete;
    private Set<Knoten> _delete2;

    /**
     * Erstelle einen neuen Graphen ohne Knoten.
     */
    public Graph()
    {
        _knotenmenge = new HashSet<Knoten>();
        _verlauf = new HashSet<Knoten>();
    }

    /**
     * Füge einen Knoten zu diesem Graph hinzu. Der Graph wird nicht
     * verändert, wenn der Knoten bereits Teil des Graphen ist.
     * @param k der hinzuzufügende Knoten
     */
    public void neuerKnoten(Knoten k)
    {
        _knotenmenge.add(k);
    }

    /**
     * Entferne einen Knoten aus diesem Graph, sofern er Teil
     * dieses Graphen ist.
     * @param k der zu entfernende Knoten
     */
    public void entferneKnoten(Knoten k)
    {
        _knotenmenge.remove(k);
    }
    
    public Set<Knoten> unverbunden()
    {
        Set<Knoten> _unv = new HashSet<Knoten>();
        int max, current;
        Knoten knot, knot2;
        for (Iterator iter = iterator(); iter.hasNext();)
        {
            knot = (Knoten)iter.next();
            current = 0;
            for (Iterator iter2 = knot.iterator(); iter2.hasNext();)
            {
                knot2 = (Knoten)iter2.next();
                current++;
            }
            if (current == 0)
            {
               _unv.add(knot);
            }
        }
        return _unv;
       
    }

    /**
     * Definiere in diesem Graph eine neue, gewichtete Kante
     * zwischen zwei Knoten dieses Graphen. Wenn die Knoten nicht
     * Teil dieses Graphen sind, tue nichts.
     * @param k1 der erste Knoten
     * @param k2 der zweite Knoten
     * @param gewicht das Gewicht der Kante
     */
    public void verbindeDirekt(Knoten k1, Knoten k2, int gewicht)
    {
        if ((k1 != k2) && enthaelt(k1) && enthaelt(k2))
        {
            k1.verbindeMit(k2, gewicht);
            k2.verbindeMit(k1, gewicht);
        }
    }

    /**
     * Prüfe, ob dieser Graph einen bestimmten Knoten enthält.
     * @param k der fragliche Knoten
     * @return true, wenn der Knoten enthalten ist, false sonst
     */
    public boolean enthaelt(Knoten k)
    {
        return _knotenmenge.contains(k);
    }

    /**
     * @return die Anzahl der Knoten in diesem Graphen.
     */
    public int anzahlKnoten()
    {
        return _knotenmenge.size();
    }

    /**
     * Liefere einen Iterator über alle Knoten dieses Graphen.
     * @return den Iterator über alle Knoten
     */
    public Iterator<Knoten> iterator()
    {
        return _knotenmenge.iterator();
    }
    
    /**
     * Ermittle, ob die beiden Knoten k1 und k2 direkt oder
     * indirekt miteinander verbunden sind. Wenn die Knoten nicht
     * Teil dieses Graphen sind, tue nichts.
     * @param k1 der erste Knoten
     * @param k2 der zweite Knoten
     * @return true, wenn die Knoten verbunden sind, false sonst.
     */
    public boolean verbunden(Knoten k1, Knoten k2)
    {
        _verlauf.clear();
        return verbunden2(k1, k2);
    }
    
    private boolean verbunden2(Knoten k1, Knoten k2)
    {
        boolean verbunden = false;
        
        if ((k1 != k2) && enthaelt(k1) && enthaelt(k2))
        {
            for (Knoten x : k1)
            {
                if (x == k2)
                {
                    verbunden = true;
                    ;
                }
                else
                {
                    if (_verlauf.contains(x) == false) 
                    {
                        System.out.println("Vergleiche Knoten " + k2.nummer() + " mit " + x.nummer());
                        _verlauf.add(x);
                        System.out.println("Verlauf groesse: " + _verlauf.size());
                        verbunden = verbunden || (verbunden2(x,k2));
                    }
                }
            }
        }
        return verbunden;
    }
        
    public int anzahlTeilgraphen()
    {
        int count = 0;
        Knoten knot, knot2, testknot;
        Set<Knoten> _unverbunden = unverbunden();
        _delete = _knotenmenge;
       for (Iterator iter2 = _unverbunden.iterator(); iter2.hasNext();)
       {
            testknot = (Knoten)iter2.next();
            if ( _delete.contains(testknot))
            {
                _delete.remove(testknot);
                 count++;
            }
        }
        System.out.println("Keine Unverbundenen");
        _delete2 = _delete;
        for (Iterator iter3 = _delete.iterator(); iter3.hasNext();)        
        {
            knot = (Knoten)iter3.next();
            for (Iterator iter4 = knot.iterator(); iter4.hasNext();)
            {
                knot2 = (Knoten)iter4.next();
                _delete2.remove(knot);
                knot = knot2;
            }
            count++;
        }    
        return count;
    }
    /**
     * Liefere die Anzahl der verbundenen Teilgraphen
     * dieses Graphen.
     * @return die Anzahl der Teilgraphen
     */
        public int maxVerbindungsgrad()
        {
        int max, current;
        Knoten knot, knot2;
        max = 0;
        for (Iterator iter = iterator(); iter.hasNext();)
        {
            knot = (Knoten)iter.next();
            current = 0;
            for (Iterator iter2 = knot.iterator(); iter2.hasNext();)
            {
                knot2 = (Knoten)iter2.next();
                current++;
            }
            if (current > max)
            {
                max = current;
            }
        }
        return max;
    }

    /**
     * Ermittele den kürzesten Weg von startKnoten nach zielKnoten. 
     * @param startKnoten der erste Knoten
     * @param zielKnoten der zweite Knoten
     * @return die Länge des kürzesten Weges oder -1,
     *         falls nicht verbunden
     */
    public int kuerzesterWeg(Knoten startKnoten, Knoten zielKnoten)
    {
        // TODO: implementieren mit Hilfe des Dijkstra-Algorithmus
        return -1;
    }
}