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; }}