Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start [14.11.2022 16:39] – [Bearbeiten - Panel] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start [09.04.2025 10:54] (aktuell) – [Bearbeiten - Panel] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
+~~NOTOC~~
 ====== Hilfestellung zur Programmierung mit dem Graphentester ======
+<WRAP center round info 96%>
+**[[https://info-bw.de/static/gtdoc/|Hier findest du die vollständige Dokumentation]]** für die Methoden, die der Graphentester mitbringt.
+</WRAP>
+===== Grundsätzliche Strukur =====
+Damit deine Algorithmen überhaupt kompilieren können und vom Graphentester erkannt werden, muss jede Klasse ein paar bestimmte Befehle enthalten. Grundsätzlich gilt folgende Struktur.
+<code java>
+package eigeneAlgorithmen;
+import graph.*;
+import algorithmen.*;
+public class GraphAlgo_MeineKlasse extends GraphAlgo
+{
+    Graph g;
+    public String getBezeichnung() {
+        return "MeineKlasse";
+    }
+    public void fuehreAlgorithmusAus() {
+        g = getGraph();
+        // ...
+    }
+}
+</code>
+Folgende Punkte sind dabei wichtig:
+  * Das ''package'' ergibt sich automatisch aus dem Verzeichnis
+  * Die beiden import-Statements benötigt man, um die bereits vorgefertigten Graphen-Algorithmen nutzen zu können.
+  * **Der Klassenname muss mit GraphAlgo_ beginnen**
+  * Die Klasse muss die Elternklasse GraphAlgo erweitern
+  * Wegen der Vererbung müssen die folgenden zwei Methoden geerbt werden:
+    * ''public String getBezeichnung()'': Darin wird der leserliche Name definiert/zurückgegeben, der in der GUI auf deinen Algorithmus verweist.
+    * ''public void fuehreAlgorithmusAus()'': Hierin schreibst du deinen Algorithmus (das ersetzt sozusagen die main-Methode).
+===== Wichtige Tasks =====
 <accordion id="hilfekarte">
 <panel title="Aktion auf allen Knoten/Kanten">
 Soll der Algorithmus mit allen Knoten des Graphen etwas Bestimmtes machen, dann verwendet man die Methode ''getAlleKnoten()'' bzw. ''getAlleKanten()'' des Objekts ''g'' (Klasse Graph):
+<code java>
+import java.util.List;
+</code>
 <code java>
@@ Zeile 14: / Zeile 60: @@
    aktuellerKnoten.setMarkiert(true);
    // Ausführung unterbrechen
-   step();Hilfestellung zur Programmierung mit dem Graphentester
+   step();
 }
 </code>
+</panel>
+<panel title="Aktion auf bestimmten Knoten/Kanten">
+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.
+<code java>
+import java.util.List;
+</code>
+<code java>
+// 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();
+}
+</code>
+Diese Beschränkung auf eine Teilmenge mittels eines Lambda-Ausdrucks funktioniert auch bei den Methoden:
+  * ''getAlleKanten(...)''
+  * ''getAusgehendeKanten(...)''
+  * ''getEingehendeKanten(...)''
+  * ''getNachbarknoten(...)''
+</panel>
+<panel title="Knoten/Kanten sortieren oder Aktion mit Knoten/Kante mit kleinstem/größtem Wert">
+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)).
+<code java>
+import java.util.List;
+import java.util.Collections;
+</code>
+<code java>
+// 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);
+</code>
+Benötigt man eine andere Sortierung, kann man die Klasse Comparator benutzen und angeben nach welchem Wert sortiert werden soll:
+<code java>
+import java.util.Comparator;
+</code>
+<code java>
+//aufsteigend sortieren
+knoten.sort(Comparator.comparing(Knoten::getIntWert));
+//absteigend sortieren
+knoten.sort(Comparator.comparing(Knoten::getIntWert).reversed());
+</code>
+</panel>
+<panel title="Arbeiten mit einer ToDo-Liste">
+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.
+<code java>
+import java.util.ArrayList;
+</code>
+<code java>
+// 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
+}
+</code>
+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.
+</panel>
+<panel title="Rekursiv arbeiten">
+Standartmäßig wird beim Start des Algorithmus einmal die Methode ''fuehreAlgorithmusAus()'' aufgerufen. Um rekursiv zu arbeiten, benötigt man neben ''fuehreAlgorithmusAus()'' noch eine weitere Methode - ''fuehreAlgorithmusAus()'' ruft diese mit dem Startknoten als Parameter auf, im folgenden kann diese Methode sich dann wiederum rekursiv selbst aufrufen:
+<code java>
+import java.util.ArrayList;
+import java.util.Collections;
+</code>
+<code java>
+public void fuehreAlgorithmusAus() {
+  rekursiveMethode(getStartKnoten());
+}
+public void rekursiveMethode(Knoten k){
+  // Abbruchbedingung
+  if (k.isMarkiert()) {
+    // Ausführung unterbrechen
+    step();
+    return true;
+  } else {
+    // Aktion mit Knoten durchführen, z.B. markieren
+    k.setMarkiert(true);
+    // Ausführung unterbrechen
+    step();
+    // Rekursiver Aufruf mit allen Nachbarknoten
+    for(Knoten nachbar : g.getNachbarknoten(k)) {
+      rekursiveMethode(nachbar);
+    }
+  }
+}
+</code>
+</panel>
+<panel title="Backtracking">
+Backtracking lässt sich am leichtesten rekursiv implementieren.
+<code java>
+import java.util.ArrayList;
+</code>
+<code java>
+public void fuehreAlgorithmusAus() {
+  // Starte Backtracking mit Startknoten
+  ArrayList<String> loesung = backtracking(getStartKnoten());
+  // Wenn Lösung gefunden, dann anzeigen
+  if(loesung != null) g.restoreStatus(loesung);
+  step();
+}
+public ArrayList<String> backtracking(Knoten k){
+  // Bisher keine Lösung gefunden
+  ArrayList<String> loesung = null;
+  // Abbruchbedingung: Lösung gefunden
+  if (k.isMarkiert()) {
+    step();                       // Ausführung unterbrechen
+    loesung = g.saveStatus();     // Lösung merken
+  }
+  // Rekursionsschritt
+  else {
+    // aktuellen Zustand sichern
+    ArrayList<String> aktuellerZustand = g.saveStatus();
+    // Probiere alle Möglichkeiten
+    // hier alle nicht markierten, ausgehenden Kanten
+    ArrayList<Kante> ausgehend = g.getAusgehendeKanten(k);
+    ArrayList<Kante> nichtMarkiert =  g.beschraenkeKantenAuf(ausgehend, Graph.NICHTMARKIERT, Graph.BELIEBIG);
+    for(Kante ausgehendeKante : nichtMarkiert) {
+      // Führe Aktionen aus und anzeigen
+      k.setMarkiert(true);
+      ausgehendeKante.setMarkiert(true);
+      step();
+      // Rekursion
+      Knoten nachbar = ausgehendeKante.getAnderesEnde(k);
+      loesung =  backtracking(nachbar);
+      // Rückschritt
+      g.restoreStatus(aktuellerZustand);
+      step();
+      if(loesung != null) break;
+    }
+  }
+  return loesung;
+}
+</code>
+</panel>
+<panel title="Ausgabe von Informationen/Ergebnissen">
+Um Informationen oder Ergebnisse eigener Algorithmen auszugeben, bietet der Graphentester drei Möglichkeiten an:
+==== Java Konsole ====
+Man kann mit ''System.out.println()'' Dinge auf die Konsole schreiben. Zu beachten ist dabei, dass die JavaFX-Applikation die Konsole nicht automatisch öffnet, wenn man etwas ausgibt - man muss diese im BlueJ-Menü ''Ansicht'' oder mit der Tastenkombination ''CTRL-T'' öffnen, um die Ausgabe sehen zu können.
+==== melde() ====
+Mit der Methode ''melde(String Ausgabe)'' erzeugt man ein Fenster mit O.K. Button, in dem der Ausgabestring angezeigt wird. Dabei kann man innerhalb des Ausgabestrings auch ''\n'' verwenden, um eine neue Zeile zu beginnen.
+   melde("Apfel\nBirne\nMango");
+{{:faecher:informatik:oberstufe:graphen:zpg:hilfekarten:okwindow.png|}}
+==== info() ====
+{{ :faecher:informatik:oberstufe:graphen:zpg:hilfekarten:help.png?320|}}
+Mit Hilfe der Methoden ''info(String s)'', ''resetInfo()'', ''infoIndentMore()'' und ''infoIndentLess()'' kann man Informationen -- auch während des Programmablaufs -- innerhalb des Hilfefensters ausgeben. Das Hilfe-Fenster kann man im Graphentester im Menü ''Hilfe->Hilfefenster anzeigen'' aktivieren
+Beispiel:
+<code java>
+info("Setze Eingangsgrad aller Knoten.");
+infoIndentMore();
+for(Knoten k: alleKnoten) {
+    int Eingangsgrad = g.getEingehendeKanten(k).size();
+    info("Setze Eingangsgrad von " + k.getInfotext());
+    k.setWert(Eingangsgrad);
+}
+infoIndentLess();
+info("Eingangsgrade gesetzt");
+</code>
+{{:faecher:informatik:oberstufe:graphen:zpg:hilfekarten:hilfefenster.png |}}
 </panel>
 </accordion>
+==== Code-Beispiele ====
+=== Setze alle Knotenwerte ===
+Alle Knoten kann man direkt in einer Schleife verarbeiten:
+<code java>
+// Setze alle Knotenwerte auf 0
+for(Knoten k : g.getAlleKnoten()) {
+    k.setWert(0);
+}
+</code>
+<code java>
+// Setze alle Knotenwerte auf "unendlich"
+for(Knoten k : g.getAlleKnoten()) {
+    k.setWert(Double.POSITIVE_INFINITY);
+}
+</code>