Hilfestellung zur Programmierung mit dem Graphentester

Soll der Algorithmus mit allen Knoten des Graphen etwas Bestimmtes machen, dann verwendet man die Methode getAlleKnoten() bzw. getAlleKanten() des Objekts g (Klasse Graph):

import java.util.List;

// Eine Liste aller Knoten anfordern
List<Knoten> alleKnoten = g.getAlleKnoten();
 
// Schleife über alle Knoten der Liste
for (Knoten aktuellerKnoten: alleKnoten) {
   // mache etwas mit dem aktuellen Knoten, z.B. markieren
   aktuellerKnoten.setMarkiert(true);
   // Ausführung unterbrechen
   step();Hilfestellung zur Programmierung mit dem Graphentester
}

Soll der Algorithmus mit bestimmten Knoten/Kanten des Graphen etwas bestimmtes machen, dann holt man sich eine Liste aller Knoten/Kanten, die einer Bedingung genügen. Diese Bedingung kann als Prädikat, d.h. einem Lambda-Ausdruck, der true oder false zurück liefert, angegeben werden.

import java.util.List;

// Eine Liste aller markierten Knoten anfordern
List<Knoten> markierteKnoten = g.getAlleKnoten(k->k.isMarkiert());
 
// Schleife über alle Knoten der Liste
for (Knoten aktuellerKnoten: markierteKnoten ) {
   // mache etwas mit dem aktuellen Knoten, z.B. Markierung löschen
   aktuellerKnoten.setMarkiert(false);
   // Ausführung unterbrechen
   step();
}

Diese Beschränkung auf eine Teilmenge mittels eines Lambda-Ausdrucks funktioniert auch bei den Methoden:

• getAlleKanten(…)
• getAusgehendeKanten(…)
• getEingehendeKanten(…)
• getNachbarknoten(…)

Möchte man eine Knoten- oder Kantenliste sortieren oder den größten/kleinsten wert ermitteln, kann man folgendermaßen vorgehen:
Zunächst holt man sich eine Liste der Knoten/Kanten. Mit Collections.sort(…) kann man die Kanten nach ihrem Gewicht und die Knoten nach ihrem Wert aufsteigend sortieren lassen. Das erste Element der Liste (Index=0) ist dann das mit dem kleinsten Wert, das letzte das mit dem größten Wert (Index=(Länge der Liste -1)).

import java.util.List;
import java.util.Collections;

// Liste aller Kanten holen
List<Kante> kanten = g.getAlleKanten();
// Kanten nach Gewicht aufsteigend sortieren
Collections.sort(kanten);
// Kante mit minimalem bzw. maximalem Gewicht ermitteln
Kante min = kanten.get(0);
Kante max = kanten.get(kanten.size()-1);

Benötigt man eine andere Sortierung, kann man die Klasse Comparator benutzen und angeben nach welchem Wert sortiert werden soll:

import java.util.Comparator;

//aufsteigend sortieren
knoten.sort(Comparator.comparing(Knoten::getIntWert)); 
//absteigend sortieren
knoten.sort(Comparator.comparing(Knoten::getIntWert).reversed()); 

In vielen Fällen arbeitet man die Knoten in einer vorher nicht feststehenden Reihenfolge ab. Die Knoten werden während des Algorithmus einer ToDo-Liste hinzugefügt und dann der Reihe nach abgearbeitet, bis die ToDo-Liste leer ist.

import java.util.ArrayList;

// ToDo-Liste erzeugen und mit Startknoten füllen
ArrayList<Knoten> toDo = new ArrayList<Knoten>();
toDo.add(getStartKnoten());
 
// Solange die ToDo-Liste nicht leer ist...
while(toDo.size()>0) {
  // ersten Knoten aus der Liste herausnehmen
  Knoten k = toDo.remove(0);
 
  // markiere ihn als besucht
  k.setBesucht(true);
 
  // füge alle nicht besuchten Nachbarknoten der Liste hinzu
  for(Knoten nachbar : g.getNachbarKnoten(k)) {
    if(!nachbar.isMarkiert() && !toDo.contains(nachbar)) {
      toDo.add(0, n); //füge am Anfang der Liste hinzu
      // oder 
      // toDo.add(n)  //füge am Ende der Liste hinzu 
    }
  }
  step();    // Ausführung unterbrechen
}

Alternativ kann man statt einer ArrayList auch die ADTs Stapel (Stack) oder Schlange (Queue) benutzen, die automatisch das Einfügen an der richtigen Stelle übernehmen.