Package directedGraph

Class AdjacencyListDirectedGraph<V>

java.lang.Object
directedGraph.AdjacencyListDirectedGraph<V>
Type Parameters:
V - Knotentyp.
All Implemented Interfaces:
DirectedGraph<V>
public class AdjacencyListDirectedGraph<V> extends Object implements DirectedGraph<V>
Implementierung von DirectedGraph mit einer doppelten TreeMap für die Nachfolgerknoten und einer einer doppelten TreeMap für die Vorgängerknoten.

Beachte: V muss vom Typ Comparable<V> sein.

Entspicht einer Adjazenzlisten-Implementierung mit schnellem Zugriff auf die Knoten.

Since:
1.8.2023

  • Constructor Summary

    Constructors
    Constructor
    Description
    AdjacencyListDirectedGraph()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    addEdge​(V v, V w)
    Fügt neue Kante (mit Gewicht 1) zum Graph dazu.
    boolean
    addEdge​(V v, V w, double weight)
    Fügt neue Kante mit Gewicht weight zum Graph dazu.
    boolean
    addVertex​(V v)
    Fügt neuen Knoten zum Graph dazu.
    boolean
    containsEdge​(V v, V w)
    Prüft ob Kante im Graph vorhanden ist.
    boolean
    containsVertex​(V v)
    Prüft ob Knoten v im Graph vorhanden ist.
    int
    getInDegree​(V v)
    Liefert Eingangsgrad des Knotens v zurück.
    int
    getNumberOfEdges()
    Liefert Anzahl der Kanten im Graph zurück.
    int
    getNumberOfVertexes()
    Liefert Anzahl der Knoten im Graph zurück.
    int
    getOutDegree​(V v)
    Liefert Ausgangsgrad des Knotens v zurück.
    Set<V>
    getPredecessorVertexSet​(V v)
    Liefert eine nicht modifizierbare Sicht (unmodifiable view) auf die Menge aller Vorgängerknoten von v zurück.
    Set<V>
    getSuccessorVertexSet​(V v)
    Liefert eine nicht modifizierbare Sicht (unmodifiable view) auf die Menge aller Nachfolgerknoten von v zurück.
    Set<V>
    getVertexSet()
    Liefert eine nicht modifizierbare Sicht (unmodifiable view) auf die Menge aller Knoten im Graph zurück.
    double
    getWeight​(V v, V w)
    Liefert Gewicht der Kante zurück.
    DirectedGraph<V>
    invert()
    Erzeugt einen invertierten Graphen, indem jede Kante dieses Graphens in umgekehrter Richtung abgespeichert wird.
    static void
    main​(String[] args)
     
    String
    toString()
     

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • AdjacencyListDirectedGraph

      public AdjacencyListDirectedGraph()

  • Method Details

    • addVertex

      public boolean addVertex​(V v)
      Description copied from interface: DirectedGraph
      Fügt neuen Knoten zum Graph dazu.
      Specified by:
      addVertex in interface DirectedGraph<V>
      Parameters:
      v - Knoten
      Returns:
      true, falls Knoten noch nicht vorhanden war.

    • addEdge

      public boolean addEdge​(V v, V w, double weight)
      Description copied from interface: DirectedGraph
      Fügt neue Kante mit Gewicht weight zum Graph dazu. Falls einer der beiden Knoten noch nicht im Graphen vorhanden ist, dann wird er dazugefügt. Falls die Kante schon vorhanden ist, dann wird das Gewicht mit weight überschrieben.
      Specified by:
      addEdge in interface DirectedGraph<V>
      Parameters:
      v - Startknoten
      w - Zielknoten
      weight - Gewicht
      Returns:
      true, falls Kante noch nicht vorhanden war.

    • addEdge

      public boolean addEdge​(V v, V w)
      Description copied from interface: DirectedGraph
      Fügt neue Kante (mit Gewicht 1) zum Graph dazu. Falls einer der beiden Knoten noch nicht im Graphen vorhanden ist, dann wird er dazugefügt. Falls die Kante schon vorhanden ist, dann wird das Gewicht mit 1 überschrieben.
      Specified by:
      addEdge in interface DirectedGraph<V>
      Parameters:
      v - Startknoten
      w - Zielknoten
      Returns:
      true, falls Kante noch nicht vorhanden war.

    • containsVertex

      public boolean containsVertex​(V v)
      Description copied from interface: DirectedGraph
      Prüft ob Knoten v im Graph vorhanden ist.
      Specified by:
      containsVertex in interface DirectedGraph<V>
      Parameters:
      v - Knoten
      Returns:
      true, falls Knoten vorhanden ist.

    • containsEdge

      public boolean containsEdge​(V v, V w)
      Description copied from interface: DirectedGraph
      Prüft ob Kante im Graph vorhanden ist.
      Specified by:
      containsEdge in interface DirectedGraph<V>
      Parameters:
      v - Startknoten
      w - Endknoten
      Returns:
      true, falls Kante vorhanden ist.

    • getWeight

      public double getWeight​(V v, V w)
      Description copied from interface: DirectedGraph
      Liefert Gewicht der Kante zurück.
      Specified by:
      getWeight in interface DirectedGraph<V>
      Parameters:
      v - Startknoten
      w - Endknoten
      Returns:
      Gewicht der Kante.

    • getInDegree

      public int getInDegree​(V v)
      Description copied from interface: DirectedGraph
      Liefert Eingangsgrad des Knotens v zurück. Das ist die Anzahl der Kanten mit Zielknoten v.
      Specified by:
      getInDegree in interface DirectedGraph<V>
      Parameters:
      v - Knoten
      Returns:
      Knoteneingangsgrad

    • getOutDegree

      public int getOutDegree​(V v)
      Description copied from interface: DirectedGraph
      Liefert Ausgangsgrad des Knotens v zurück. Das ist die Anzahl der Kanten mit Quellknoten v.
      Specified by:
      getOutDegree in interface DirectedGraph<V>
      Parameters:
      v - Knoten
      Returns:
      Knotenausgangsgrad

    • getPredecessorVertexSet

      public Set<V> getPredecessorVertexSet​(V v)
      Description copied from interface: DirectedGraph
      Liefert eine nicht modifizierbare Sicht (unmodifiable view) auf die Menge aller Vorgängerknoten von v zurück. Das sind alle die Knoten, von denen eine Kante zu v führt.
      Specified by:
      getPredecessorVertexSet in interface DirectedGraph<V>
      Parameters:
      v - Knoten
      Returns:
      Knotenmenge

    • getSuccessorVertexSet

      public Set<V> getSuccessorVertexSet​(V v)
      Description copied from interface: DirectedGraph
      Liefert eine nicht modifizierbare Sicht (unmodifiable view) auf die Menge aller Nachfolgerknoten von v zurück. Das sind alle die Knoten, zu denen eine Kante von v führt.
      Specified by:
      getSuccessorVertexSet in interface DirectedGraph<V>
      Parameters:
      v - Knoten
      Returns:
      Knotenmenge

    • getNumberOfVertexes

      public int getNumberOfVertexes()
      Description copied from interface: DirectedGraph
      Liefert Anzahl der Knoten im Graph zurück.
      Specified by:
      getNumberOfVertexes in interface DirectedGraph<V>
      Returns:
      Knotenzahl.

    • getNumberOfEdges

      public int getNumberOfEdges()
      Description copied from interface: DirectedGraph
      Liefert Anzahl der Kanten im Graph zurück.
      Specified by:
      getNumberOfEdges in interface DirectedGraph<V>
      Returns:
      Kantenzahl.

    • getVertexSet

      public Set<V> getVertexSet()
      Description copied from interface: DirectedGraph
      Liefert eine nicht modifizierbare Sicht (unmodifiable view) auf die Menge aller Knoten im Graph zurück.
      Specified by:
      getVertexSet in interface DirectedGraph<V>
      Returns:
      Knotenmenge

    • invert

      public DirectedGraph<V> invert()
      Description copied from interface: DirectedGraph
      Erzeugt einen invertierten Graphen, indem jede Kante dieses Graphens in umgekehrter Richtung abgespeichert wird.
      Specified by:
      invert in interface DirectedGraph<V>
      Returns:
      invertierter Graph

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • main

      public static void main​(String[] args)