Package graph

Class Graph


  • public class Graph
    extends java.lang.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. Zu Vor- und Nachteilen der Speicherung als Adjazenzliste oder -matrix siehe "LI1_Hintergrund.odt"
    Version:
    11.07.2019 (v5.0)
    Author:
    Dirk Zechnall, Tom Schaller
    • Constructor Summary

      Constructors 
      Constructor Description
      Graph()
      Der Konstruktor erstellt einen neuen Graphen (genauer eine neue Adjazenzliste)
      Graph​(boolean isGerichtet, boolean isGewichtet)
      Der Konstruktor erstellt einen neuen Graphen (genauer eine neue Adjazenzliste)
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addKante​(graph.Kante e)
      Fuegt eine Kante dem Graphen hinzu.
      void addKante​(graph.Knoten start, graph.Knoten ziel, double gewicht)
      Fuegt eine Kante dem Graphen hinzu.
      void addKnoten​(graph.Knoten k)
      Diese Methode erstellt ein Knoten, der dem graphen hinzugefuegt wird.
      void ausgabe()
      Konsolenausgabe der textuellen Repraesentation des Graphen.
      void ausgabe​(java.lang.String text)
      Konsolenausgabe der textuellen Repraesentation des Graphen mit vorangestelltem Text.
      void clear()
      Loescht den gesamten Graphen
      void entferneMarkierungBeiAllenKnoten()
      Entfernt die Markierung bei allen Knoten des Graphen.
      boolean erzeugeGraphAusAdjazenzliste​(java.lang.String[][] liste)
      Ein Graph wird aus einem Adjazenzlisten-Array erstellt.
      boolean erzeugeGraphAusMatrix​(java.lang.String[][] matrix)
      Ein Graph wird aus einem Matrix-Array erstellt.
      double[][] getAdjazenzMatrix()
      Die Methode getAdjazenzMatrix() gibt die Adjazenzmatrix zurueck.
      java.util.ArrayList<graph.Kante> getAlleKanten()
      Gibt eine Liste aller Kanten des Graphen zurück.
      java.util.ArrayList<graph.Knoten> getAlleKnoten()
      Gibt die Knotenliste zurueck.
      int getAnzahlKnoten()
      Gibt die Anzahl der Knoten in der knotenliste zurueck
      java.util.ArrayList<graph.Kante> getAusgehendeKanten​(int knotennr)
      Gibt die Kantenliste alle Kanten, die von diesem Knoten k ausgehen, zurueck, falls k in der Knotenliste vorhanden ist.
      java.util.ArrayList<graph.Kante> getAusgehendeKanten​(graph.Knoten k)
      Gibt die Adjazenzliste (Kantenliste) eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
      java.util.ArrayList<graph.Kante> getEingehendeKanten​(int knotennr)
      Gibt die Kantenliste alle Kanten, die zu diesem Knoten k führen, zurück, falls k in der Knotenliste vorhanden ist.
      java.util.ArrayList<graph.Kante> getEingehendeKanten​(graph.Knoten k)
      Gibt die Kantenliste alle Kanten, die zu diesem Knoten k führen, zurück, 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 den n.
      java.util.ArrayList<graph.Knoten> getNachbarKnoten​(graph.Knoten k)
      Gibt die Adjazenzliste (Kantenliste) eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
      int getNummer​(graph.Knoten k)
      Gibt die Nummer eines Knotens zurück
      void initialisiereAlleKanten()
      Initialisiert (via init-Methode der Klasse Kante) alle Kanten des Graphen.
      void initialisiereAlleKnoten()
      Initialisiert (via init-Methode der Klasse Knoten) alle Knoten des Graphen.
      boolean isEmpty()
      Ueberprueft, ob die Adjazenzliste leer ist, d.h. keine Knoten im Graphen enthalten sind.
      boolean isGerichtet()
      Gibt das Attribut directed zurueck.
      boolean isGewichtet()
      Gibt das Attribut weighted zurueck.
      boolean isKanteEnthalten​(int startNr, int zielNr)
      Ueberprueft, ob eine Kante mit Start-, Zielnamen und Kantengewicht 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 mit Start- und Zielknoten im Graphen enthalten ist.
      boolean isKnotenEnthalten​(graph.Knoten k)
      Ueberprueft, ob ein Knoten in der Knotenliste enthalten ist.
      void loescheGraph()
      Löscht alle Knoten und Kanten eines Graphen und stellt auf ungerichtet und ungewichtet zurück.
      void removeKante​(int start, int ziel)
      Entfernt eine Kante aus dem Graphen.
      void removeKante​(graph.Kante e)
      Entfernt eine Kante aus dem Graphen.
      void removeKante​(graph.Knoten start, graph.Knoten ziel)
      Entfernt eine Kante aus dem Graphen.
      void removeKnoten​(int knotennr)
      Diese Methode entfernt einen Knoten mit dem angegebenen KnotenNamen.
      boolean removeKnoten​(graph.Knoten k)
      Diese Methode entfernt einen Knoten.
      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.
      java.lang.String toCSVString​(boolean asMatrix)
      Die Methode erstellt eine CSV-Ausgabe des Graphen entweder als Adjazenzliste oder als Adjazenzmatrix.
      java.lang.String toString()
      Textuelle Repraesentation des Graphen.
      java.lang.String toString​(java.lang.String text)
      Textuelle Repraesentation des Graphen mit vorangestelltem Text.
      • Methods inherited from class java.lang.Object

        clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Constructor Detail

      • 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 Graphen (genauer eine neue Adjazenzliste)
    • Method Detail

      • loescheGraph

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

        public boolean erzeugeGraphAusMatrix​(java.lang.String[][] matrix)
        Ein Graph wird aus einem Matrix-Array erstellt.
        Parameters:
        String - [][] matrix Die Matrix
      • erzeugeGraphAusAdjazenzliste

        public boolean erzeugeGraphAusAdjazenzliste​(java.lang.String[][] liste)
        Ein Graph wird aus einem Adjazenzlisten-Array erstellt.
        Parameters:
        String - [][] liste Die Liste
      • setGewichtet

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

        public boolean isGewichtet()
        Gibt das Attribut weighted zurueck.
        Returns:
        boolean gewichtet (true/false)
      • setGerichtet

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

        public boolean isGerichtet()
        Gibt das Attribut directed zurueck.
        Returns:
        boolean gerichtet (true/false)
      • getNummer

        public int getNummer​(graph.Knoten k)
        Gibt die Nummer eines Knotens zurück
        Returns:
        int Nummer des Knotens (mit 0 beginnend)
      • getAdjazenzMatrix

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

        public java.util.ArrayList<graph.Kante> getAlleKanten()
        Gibt eine Liste aller Kanten des Graphen zurück.
        Returns:
        Liste aller Kanten
      • entferneMarkierungBeiAllenKnoten

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

        public void initialisiereAlleKnoten()
        Initialisiert (via init-Methode der Klasse Knoten) alle Knoten des Graphen.
      • initialisiereAlleKanten

        public void initialisiereAlleKanten()
        Initialisiert (via init-Methode der Klasse Kante) 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:
        Knoten - k Der gesuchte Knoten
        Returns:
        boolean
      • getAnzahlKnoten

        public int getAnzahlKnoten()
        Gibt die Anzahl der Knoten in der knotenliste zurueck
        Returns:
        int
      • getAlleKnoten

        public java.util.ArrayList<graph.Knoten> getAlleKnoten()
        Gibt die Knotenliste zurueck.
        Returns:
        ArrayList Die Knotenliste. Falls leer wird null zurueckgegeben
      • getNachbarKnoten

        public java.util.ArrayList<graph.Knoten> getNachbarKnoten​(graph.Knoten k)
        Gibt die Adjazenzliste (Kantenliste) eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
        Parameters:
        Knoten - k Der Knoten, zu dem die Adjazenzliste gesucht wird
        Returns:
        ArrayList
      • getAusgehendeKanten

        public java.util.ArrayList<graph.Kante> getAusgehendeKanten​(graph.Knoten k)
        Gibt die Adjazenzliste (Kantenliste) eines Knotens k zurueck, falls k in der Knotenliste vorhanden ist.
        Parameters:
        Knoten - k Der Knoten, zu dem die Adjazenzliste gesucht wird
        Returns:
        ArrayList
      • getAusgehendeKanten

        public java.util.ArrayList<graph.Kante> getAusgehendeKanten​(int knotennr)
        Gibt die Kantenliste alle Kanten, die von diesem Knoten k ausgehen, zurueck, falls k in der Knotenliste vorhanden ist.
        Parameters:
        Knoten - k Der Knoten, zu dem die Adjazenzliste gesucht wird
        Returns:
        ArrayList
      • getEingehendeKanten

        public java.util.ArrayList<graph.Kante> getEingehendeKanten​(int knotennr)
        Gibt die Kantenliste alle Kanten, die zu diesem Knoten k führen, zurück, falls k in der Knotenliste vorhanden ist.
        Parameters:
        int - knotennr Nummer des Knoten, zu dem die Adjazenzliste gesucht wird
        Returns:
        ArrayList
      • getEingehendeKanten

        public java.util.ArrayList<graph.Kante> getEingehendeKanten​(graph.Knoten k)
        Gibt die Kantenliste alle Kanten, die zu diesem Knoten k führen, zurück, falls k in der Knotenliste vorhanden ist.
        Parameters:
        Knoten - k Der Knoten, zu dem die Adjazenzliste gesucht wird
        Returns:
        ArrayList
      • getKnoten

        public graph.Knoten getKnoten​(int knotennr)
        Liefert den n. Knoten des Graphen
        Parameters:
        int - knotennr Nummer der Knoten (beginnend mit 0)
      • addKnoten

        public void addKnoten​(graph.Knoten k)
        Diese Methode erstellt ein Knoten, der dem graphen hinzugefuegt wird. Dabei wird sowohl die Adjazenzliste, als auch die graphische Repraesentation (jgraphx) aktualisiert. Falls der Knoten schon enthalten ist oder ein Fehler beim hinzufuegen auftritt, wird false zurueckgegeben.
        Parameters:
        Knoten - k Der Knoten, der hinzugefuegt werden soll
      • removeKnoten

        public void removeKnoten​(int knotennr)
        Diese Methode entfernt einen Knoten mit dem angegebenen KnotenNamen. Dabei wird nur die Adjazenzliste aktualisiert, die graphische Repraesentation (jgraphx) erst, wenn der Graph neu gezeichnet wird (in der Klasse GraphPlotter). Falls der Knoten nicht enthalten ist oder ein Fehler beim hinzufuegen auftritt, wird false zurueckgegeben.
        Parameters:
        String - k Der Knotenname des Knotens, der geloescht werden soll
      • removeKnoten

        public boolean removeKnoten​(graph.Knoten k)
        Diese Methode entfernt einen Knoten. Dabei wird nur die Adjazenzliste aktualisiert, die graphische Repraesentation (jgraphx) erst, wenn der Graph neu gezeichnet wird (in der Klasse GraphPlotter). Falls der Knoten nicht enthalten ist oder ein Fehler beim hinzufuegen auftritt, wird false zurueckgegeben.
        Parameters:
        Knoten - k Der zu entfernende Knoten
        Returns:
        boolean Entfernen hat geklappt (true) oder nicht (false)
      • isKanteEnthalten

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

        public boolean isKanteEnthalten​(int startNr,
                                        int zielNr)
        Ueberprueft, ob eine Kante mit Start-, Zielnamen und Kantengewicht im Graphen enthalten ist.
        Parameters:
        String - startName Der StartName
        String - zielName Der StartName
        Returns:
        boolean Kante enthalten (true) oder nicht (false)
      • isKanteEnthalten

        public boolean isKanteEnthalten​(graph.Knoten start,
                                        graph.Knoten ziel)
        Ueberprueft, ob eine Kante mit Start- und Zielknoten im Graphen enthalten ist.
        Parameters:
        Knoten - start Der StartKnoten
        Knoten - ziel Der StartKnoten
        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.
        Parameters:
        Knoten - start Der StartKnoten
        Knoten - ziel Der StartKnoten
        Returns:
        Kante Die gesuchte Kante
      • getKante

        public graph.Kante getKante​(int startnr,
                                    int zielnr)
        Gibt eine gesuchte Kante aus dem Graphen zurueck.
        Parameters:
        int - startnr Der Nummer des StartKnoten
        int - zielnr Die Nummer des Zielknoten
        Returns:
        Kante Die gesuchte Kante
      • addKante

        public void addKante​(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:
        Kante - e Die Kante, die hinzugefuegt werden soll
      • addKante

        public void addKante​(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:
        Knoten - start Der StartKnoten der Kante, die hinzugefuegt werden soll
        Knoten - ziel Der ZielKnoten der Kante, die hinzugefuegt werden soll
        double - gewicht Das Gewicht der Kante, die hinzugefuegt werden soll
      • removeKante

        public void removeKante​(graph.Kante e)
        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:
        Kante - e Die zu entfernende Kante
      • removeKante

        public void removeKante​(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:
        Knoten - start StartKnotens
        Knoten - ziel ZielKnotens
      • removeKante

        public void removeKante​(int start,
                                int 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:
        int - start StartKnotens
        int - ziel ZielKnotens
      • isEmpty

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

        public void clear()
        Loescht den gesamten Graphen
      • toCSVString

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

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

        public java.lang.String toString​(java.lang.String text)
        Textuelle Repraesentation des Graphen mit vorangestelltem Text.
        Parameters:
        String - text Der Text, der vorangestellt werden soll
        Returns:
        String Der Graph als Stringrepraesentation
      • ausgabe

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

        public void ausgabe​(java.lang.String text)
        Konsolenausgabe der textuellen Repraesentation des Graphen mit vorangestelltem Text.
        Parameters:
        String - text Der Text, der vorangestellt werden soll