Package graph

Class Graph

java.lang.Object
graph.Graph
public class Graph extends Object
Dies ist das Herz vom "GraphTester" - der Graph selber, gepeichert als Adjazenzliste. Die Klasse erlaubt durch geeignete Methoden: - die Speicherung als Adjazenzmatrix, - das Hinzufuegen und Loeschen von knoten und Kanten, - das Markieren von Knoten und Kanten, - eine Aussage darueber, ob Knoten oder Kanten enthalten sind und - eine Ausgabe des Graphen in textueller Form sowie als csv-Datei.
Version:
31.01.2021 (v6.5)
Author:
Dirk Zechnall, Thomas Schaller

  • Constructor Summary

    Constructors
    Constructor
    Description
    Graph()
    Der Konstruktor erstellt einen neuen ungerichteten, ungewichteten Graphen (genauer eine neue Adjazenzliste)
    Graph(boolean isGerichtet, boolean isGewichtet)
    Der Konstruktor erstellt einen neuen Graphen (genauer eine neue Adjazenzliste)

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    ausgabe()
    Konsolenausgabe der textuellen Repraesentation des Graphen.
    void
    entferneKante(int startnr, int zielnr)
    Entfernt eine Kante aus dem Graphen.
    void
    entferneKante(graph.Kante e)
    Entfernt eine Kante aus dem Graphen.
    void
    entferneKante(graph.Knoten start, graph.Knoten ziel)
    Entfernt eine Kante aus dem Graphen.
    void
    entferneKnoten(int knotennr)
    Entfernt einen Knoten aus dem Graphen
    boolean
    entferneKnoten(graph.Knoten k)
    Entfernt einen Knoten aus dem Graphen
    void
    entferneMarkierungBeiAllenKnoten()
    Entfernt die Markierung bei allen Knoten des Graphen.
    double[][]
    getAdjazenzMatrix()
    Die Methode getAdjazenzMatrix() gibt die Adjazenzmatrix zurueck.
    List<graph.Kante>
    getAlleKanten(Predicate<graph.Kante>... filter)
    Gibt eine Liste aller Kanten des Graphen zurück.
    List<graph.Knoten>
    getAlleKnoten(Predicate<graph.Knoten>... filter)
    Gibt eine Liste aller Knoten des Graphen zurueck.
    int
    getAnzahlKnoten()
    Gibt die Anzahl der Knoten im Graph zurueck
    List<graph.Kante>
    getAusgehendeKanten(int knotennr, Predicate<graph.Kante>... filter)
    Gibt eine Liste der ausgehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
    List<graph.Kante>
    getAusgehendeKanten(graph.Knoten k, Predicate<graph.Kante>... filter)
    Gibt eine Liste der ausgehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
    List<graph.Kante>
    getEingehendeKanten(int knotennr, Predicate<graph.Kante>... filter)
    Gibt eine Liste der eingehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
    List<graph.Kante>
    getEingehendeKanten(graph.Knoten k, Predicate<graph.Kante>... filter)
    Gibt eine Liste der eingehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
    graph.Kante
    getKante(int startnr, int zielnr)
    Gibt eine gesuchte Kante aus dem Graphen zurueck.
    graph.Kante
    getKante(graph.Knoten start, graph.Knoten ziel)
    Gibt eine gesuchte Kante aus dem Graphen zurueck.
    graph.Knoten
    getKnoten(int knotennr)
    Liefert einen Knoten des Graphen
    String
    getKnoteninfo(graph.Knoten k, boolean zeigeWert)
    Info über einen Knoten zurückgeben
    List<graph.Knoten>
    getNachbarknoten(graph.Knoten k, Predicate<graph.Knoten>... filter)
    Gibt die Liste aller Nachbarknoten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
    int
    getNummer(graph.Kante k)
    Gibt die Nummer einer Kante zurück
    int
    getNummer(graph.Knoten k)
    Gibt die Nummer eines Knotens im Graphen zurück
    List<String>
    getStatus()
    Speichert den Zustand des Graphen als String-List
    void
    initialisiereAlleKanten()
    Initialisiert alle Kanten des Graphen.
    void
    initialisiereAlleKnoten()
    Initialisiert alle Knoten des Graphen.
    boolean
    isGerichtet()
    Gibt zurueck, ob der Graph gerichtet oder ungerichtet ist.
    boolean
    isGewichtet()
    Gibt zurueck, ob der Graph gewichtet oder ungewichtet ist
    boolean
    isKanteEnthalten(int startNr, int zielNr)
    Ueberprueft, ob eine Kante im Graphen enthalten ist.
    boolean
    isKanteEnthalten(graph.Kante e)
    Ueberprueft, ob eine Kante im Graphen enthalten ist.
    boolean
    isKanteEnthalten(graph.Knoten start, graph.Knoten ziel)
    Ueberprueft, ob eine Kante im Graphen enthalten ist.
    boolean
    isKnotenEnthalten(graph.Knoten k)
    Ueberprueft, ob ein Knoten in der Knotenliste enthalten ist.
    boolean
    isLeer()
    Ueberprueft, ob die Adjazenzliste leer ist, d.h. keine Knoten im Graphen enthalten sind.
    boolean
    ladeGraph(imp.Table csvParser)
    Ein Graph wird aus einer csv-Datei erstellt, die entweder eine Matrix oder eine Adjazenzliste enthält, die den Graph beschreibt.
    void
    loescheAlles()
    Loescht den gesamten Graphen
    void
    loescheGraph()
    Löscht alle Knoten und Kanten eines Graphen und stellt auf ungerichtet und ungewichtet zurück.
    void
    neueKante(graph.Kante e)
    Fuegt eine Kante dem Graphen hinzu.
    void
    neueKante(graph.Knoten start, graph.Knoten ziel, double gewicht)
    Fuegt eine Kante dem Graphen hinzu.
    void
    neuerKnoten(graph.Knoten k)
    Fügt einen Knoten dem Graph hinzu.
    void
    setGerichtet(boolean isGerichtet)
    Legt fest, ob der Graph gerichtet oder ungerichtet ist.
    void
    setGewichtet(boolean isGewichtet)
    Legt fest, ob der Graph gewichtet oder ungewichtet ist.
    void
    setStatus(List<String> status)
    Stellt den Zustand des Graphen aus String-List wieder her
    String
    toCSVString(boolean asMatrix)
    Die Methode erstellt eine CSV-Ausgabe des Graphen entweder als Adjazenzliste oder als Adjazenzmatrix.
    String
    toString()
    Textuelle Repraesentation des Graphen.

    Methods inherited from class java.lang.Object

    clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • Graph

      public Graph(boolean isGerichtet, boolean isGewichtet)
      Der Konstruktor erstellt einen neuen Graphen (genauer eine neue Adjazenzliste)
      Parameters:
      isGerichtet - gibt an, ob es sich um einen gerichteten Graphen handelt
      isGewichtet - gibt an, ob die Kanten gewichtet sind.

    • Graph

      public Graph()
      Der Konstruktor erstellt einen neuen ungerichteten, ungewichteten Graphen (genauer eine neue Adjazenzliste)

  • Method Details

    • loescheGraph

      public void loescheGraph()
      Löscht alle Knoten und Kanten eines Graphen und stellt auf ungerichtet und ungewichtet zurück.

    • ladeGraph

      public boolean ladeGraph(imp.Table csvParser)
      Ein Graph wird aus einer csv-Datei erstellt, die entweder eine Matrix oder eine Adjazenzliste enthält, die den Graph beschreibt.
      Parameters:
      csvParser - Eine CSV-Datei als Table-Objekt
      Returns:
      gibt zurück, ob das Laden erfolgreich war

    • setGewichtet

      public void setGewichtet(boolean isGewichtet)
      Legt fest, ob der Graph gewichtet oder ungewichtet ist.
      Parameters:
      isGewichtet - neuer Wert

    • isGewichtet

      public boolean isGewichtet()
      Gibt zurueck, ob der Graph gewichtet oder ungewichtet ist
      Returns:
      gewichtet? (true/false)

    • setGerichtet

      public void setGerichtet(boolean isGerichtet)
      Legt fest, ob der Graph gerichtet oder ungerichtet ist.
      Parameters:
      isGerichtet - neuer Wert

    • isGerichtet

      public boolean isGerichtet()
      Gibt zurueck, ob der Graph gerichtet oder ungerichtet ist.
      Returns:
      gerichtet? (true/false)

    • getNummer

      public int getNummer(graph.Knoten k)
      Gibt die Nummer eines Knotens im Graphen zurück
      Parameters:
      k - gesuchter Knoten
      Returns:
      Nummer des Knotens (mit 0 beginnend)

    • getNummer

      public int getNummer(graph.Kante k)
      Gibt die Nummer einer Kante zurück
      Parameters:
      k - gesuchte Kante
      Returns:
      Nummer der Kante (mit 0 beginnend)

    • getAdjazenzMatrix

      public double[][] getAdjazenzMatrix()
      Die Methode getAdjazenzMatrix() gibt die Adjazenzmatrix zurueck.
      Returns:
      double[][] Die AdjazenzMatrix als zweidimensionales Array

    • getAlleKanten

      public List<graph.Kante> getAlleKanten(Predicate<graph.Kante>... filter)
      Gibt eine Liste aller Kanten des Graphen zurück.
      Parameters:
      filter - optionaler Filter, der auf die Liste angewendet wird. Er muss einen boolean-Wert zurückgeben: z.B. @literal{k->k.isMarkiert() && k.isBesucht()}
      Returns:
      Liste aller Kanten

    • entferneMarkierungBeiAllenKnoten

      public void entferneMarkierungBeiAllenKnoten()
      Entfernt die Markierung bei allen Knoten des Graphen.

    • initialisiereAlleKnoten

      public void initialisiereAlleKnoten()
      Initialisiert alle Knoten des Graphen.

    • initialisiereAlleKanten

      public void initialisiereAlleKanten()
      Initialisiert alle Kanten des Graphen.

    • isKnotenEnthalten

      public boolean isKnotenEnthalten(graph.Knoten k)
      Ueberprueft, ob ein Knoten in der Knotenliste enthalten ist. Sobald in der Knotenliste der Knoten k gefunden wird, wird true ausgegeben.
      Parameters:
      k - Der gesuchte Knoten
      Returns:
      true= ist enthalten, false = ist nicht enthalten

    • getAnzahlKnoten

      public int getAnzahlKnoten()
      Gibt die Anzahl der Knoten im Graph zurueck
      Returns:
      Anzahl der Knoten

    • getAlleKnoten

      public List<graph.Knoten> getAlleKnoten(Predicate<graph.Knoten>... filter)
      Gibt eine Liste aller Knoten des Graphen zurueck.
      Parameters:
      filter - optionaler Filter, der auf die Liste angewendet wird. Er muss einen boolean-Wert zurückgeben: z.B. @literal{k->k.isMarkiert() && k.isBesucht()}
      Returns:
      Die Knotenliste. Falls leer wird eine leere Liste zurueckgegeben

    • getNachbarknoten

      public List<graph.Knoten> getNachbarknoten(graph.Knoten k, Predicate<graph.Knoten>... filter)
      Gibt die Liste aller Nachbarknoten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
      Parameters:
      k - Der Knoten, zu dem die Adjazenzliste gesucht wird
      filter - optionaler Filter, der auf die Liste angewendet wird. Er muss einen boolean-Wert zurückgeben: z.B. @literal{k->k.isMarkiert() && k.isBesucht()}
      Returns:
      Liste der Nachbarknoten

    • getAusgehendeKanten

      public List<graph.Kante> getAusgehendeKanten(graph.Knoten k, Predicate<graph.Kante>... filter)
      Gibt eine Liste der ausgehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist. Bei ungerichteten Graphen wird nicht zwischen eingehenden und ausgehenden Kanten unterschieden.
      Parameters:
      k - Der Knoten, zu dem die Kanten gesucht werden
      filter - optionaler Filter, der auf die Liste angewendet wird. Er muss einen boolean-Wert zurückgeben: z.B. @literal{k->k.isMarkiert() && k.isBesucht()}
      Returns:
      Liste der ausgehenden Kanten.

    • getAusgehendeKanten

      public List<graph.Kante> getAusgehendeKanten(int knotennr, Predicate<graph.Kante>... filter)
      Gibt eine Liste der ausgehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist. Bei ungerichteten Graphen wird nicht zwischen eingehenden und ausgehenden Kanten unterschieden.
      Parameters:
      knotennr - Nummer des Knoten, zu dem die Kanten gesucht werden
      filter - optionaler Filter, der auf die Liste angewendet wird. Er muss einen boolean-Wert zurückgeben: z.B. @literal{k->k.isMarkiert() && k.isBesucht()}
      Returns:
      Liste der ausgehenden Kanten.

    • getEingehendeKanten

      public List<graph.Kante> getEingehendeKanten(int knotennr, Predicate<graph.Kante>... filter)
      Gibt eine Liste der eingehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist. Bei ungerichteten Graphen wird nicht zwischen eingehenden und ausgehenden Kanten unterschieden.
      Parameters:
      knotennr - Die Nummer des Knotens, zu dem die Kanten gesucht werden
      filter - optionaler Filter, der auf die Liste angewendet wird. Er muss einen boolean-Wert zurückgeben: z.B. @literal{k->k.isMarkiert() && k.isBesucht()}
      Returns:
      Liste der eingehenden Kanten.

    • getEingehendeKanten

      public List<graph.Kante> getEingehendeKanten(graph.Knoten k, Predicate<graph.Kante>... filter)
      Gibt eine Liste der eingehenden Kanten eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist. Bei ungerichteten Graphen wird nicht zwischen eingehenden und ausgehenden Kanten unterschieden.
      Parameters:
      k - Knoten, zu dem die Kanten gesucht werden
      filter - optionaler Filter, der auf die Liste angewendet wird. Er muss einen boolean-Wert zurückgeben: z.B. @literal{k->k.isMarkiert() && k.isBesucht()}
      Returns:
      Liste der eingehenden Kanten.

    • getKnoten

      public graph.Knoten getKnoten(int knotennr)
      Liefert einen Knoten des Graphen
      Parameters:
      knotennr - Nummer der Knoten (beginnend mit 0)
      Returns:
      liefert den Knoten mit dieser Nummer

    • neuerKnoten

      public void neuerKnoten(graph.Knoten k)
      Fügt einen Knoten dem Graph hinzu.
      Parameters:
      k - Der Knoten, der hinzugefuegt werden soll

    • entferneKnoten

      public void entferneKnoten(int knotennr)
      Entfernt einen Knoten aus dem Graphen
      Parameters:
      knotennr - Nummer des Knotens, der geloescht werden soll

    • entferneKnoten

      public boolean entferneKnoten(graph.Knoten k)
      Entfernt einen Knoten aus dem Graphen
      Parameters:
      k - Knoten, der geloescht werden soll
      Returns:
      gibt zurück, ob der Knoten erfolgreich entfernt wurde.

    • isKanteEnthalten

      public boolean isKanteEnthalten(graph.Kante e)
      Ueberprueft, ob eine Kante im Graphen enthalten ist.
      Parameters:
      e - Die zu suchende Kante
      Returns:
      Kante enthalten (true) oder nicht (false)

    • isKanteEnthalten

      public boolean isKanteEnthalten(int startNr, int zielNr)
      Ueberprueft, ob eine Kante im Graphen enthalten ist. In ungerichteten Graphen wird nicht zwischen Start- und Zielknoten unterschieden
      Parameters:
      startNr - Nummer des Startknotens
      zielNr - Nummer des Zielknotens
      Returns:
      boolean Kante enthalten (true) oder nicht (false)

    • isKanteEnthalten

      public boolean isKanteEnthalten(graph.Knoten start, graph.Knoten ziel)
      Ueberprueft, ob eine Kante im Graphen enthalten ist. In ungerichteten Graphen wird nicht zwischen Start- und Zielknoten unterschieden
      Parameters:
      start - Startknoten
      ziel - Zielknoten
      Returns:
      boolean Kante enthalten (true) oder nicht (false)

    • getKante

      public graph.Kante getKante(graph.Knoten start, graph.Knoten ziel)
      Gibt eine gesuchte Kante aus dem Graphen zurueck. In ungerichteten Graphen wird nicht zwischen Start- und Zielknoten unterschieden
      Parameters:
      start - Der StartKnoten
      ziel - Der StartKnoten
      Returns:
      Die gesuchte Kante

    • getKante

      public graph.Kante getKante(int startnr, int zielnr)
      Gibt eine gesuchte Kante aus dem Graphen zurueck. In ungerichteten Graphen wird nicht zwischen Start- und Zielknoten unterschieden
      Parameters:
      startnr - Der Nummer des StartKnoten
      zielnr - Die Nummer des Zielknoten
      Returns:
      Die gesuchte Kante

    • neueKante

      public void neueKante(graph.Kante e)
      Fuegt eine Kante dem Graphen hinzu. Dabei wird ueberprueft, ob die Kante schon im Graphen enthalten ist. Ist der Graph ungerichtet, werden sowohl "Hin-" und "RueckKante" erstellt.
      Parameters:
      e - Die Kante, die hinzugefuegt werden soll

    • neueKante

      public void neueKante(graph.Knoten start, graph.Knoten ziel, double gewicht)
      Fuegt eine Kante dem Graphen hinzu. Dabei wird ueberprueft, ob die Kante schon im Graphen enthalten ist. Ist der Graph ungerichtet, werden sowohl "Hin-" und "RueckKante" erstellt.
      Parameters:
      start - Der StartKnoten der Kante, die hinzugefuegt werden soll
      ziel - Der ZielKnoten der Kante, die hinzugefuegt werden soll
      gewicht - Das Gewicht der Kante, die hinzugefuegt werden soll

    • entferneKante

      public void entferneKante(graph.Kante e)
      Entfernt eine Kante aus dem Graphen. Ist der Graph ungerichtet, werden sowohl "Hin-" und "RueckKante" entfernt.
      Parameters:
      e - Die zu entfernende Kante

    • entferneKante

      public void entferneKante(graph.Knoten start, graph.Knoten ziel)
      Entfernt eine Kante aus dem Graphen. Dabei wird ueberprueft, ob die Kante ueberhaupt im Graphen enthalten ist. Ist der Graph ungerichtet, werden sowohl "Hin-" und "RueckKante" entfernt.
      Parameters:
      start - StartKnotens
      ziel - ZielKnotens

    • entferneKante

      public void entferneKante(int startnr, int zielnr)
      Entfernt eine Kante aus dem Graphen. Ist der Graph ungerichtet, werden sowohl "Hin-" und "RueckKante" entfernt.
      Parameters:
      startnr - Nummer des StartKnotens
      zielnr - Nummer des ZielKnotens

    • isLeer

      public boolean isLeer()
      Ueberprueft, ob die Adjazenzliste leer ist, d.h. keine Knoten im Graphen enthalten sind.
      Returns:
      true, wenn die Liste leer ist, sonst false

    • loescheAlles

      public void loescheAlles()
      Loescht den gesamten Graphen

    • toCSVString

      public String toCSVString(boolean asMatrix)
      Die Methode erstellt eine CSV-Ausgabe des Graphen entweder als Adjazenzliste oder als Adjazenzmatrix.
      Parameters:
      asMatrix - true, falls die CSV-Ausgabe eine AdjazenzMatrix sein soll, sonst false
      Returns:
      CSV-Ausgabe

    • toString

      public String toString()
      Textuelle Repraesentation des Graphen.
      Overrides:
      toString in class Object
      Returns:
      Der Graph als Stringrepraesentation

    • ausgabe

      public void ausgabe()
      Konsolenausgabe der textuellen Repraesentation des Graphen.

    • getKnoteninfo

      public String getKnoteninfo(graph.Knoten k, boolean zeigeWert)
      Info über einen Knoten zurückgeben
      Parameters:
      k - Knoten, des Info ermittelt werden soll
      zeigeWert - Soll der Wert des Knoten in der Info enthalten sein
      Returns:
      Infotext oder Nummer des Knoten und ggf. sein Wert

    • getStatus

      public List<String> getStatus()
      Speichert den Zustand des Graphen als String-List
      Returns:
      List mit Zustand

    • setStatus

      public void setStatus(List<String> status)
      Stellt den Zustand des Graphen aus String-List wieder her
      Parameters:
      status - List mit Zustand