Package graph
Class Graph
- java.lang.Object
-
- graph.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
-
-
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 Graphenvoid
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 zurueckjava.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ückvoid
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.
-
-
-
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 handeltisGewichtet
- 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 StartNameString
- 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 StartKnotenKnoten
- 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 StartKnotenKnoten
- 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 StartKnotenint
- 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 sollKnoten
- ziel Der ZielKnoten der Kante, die hinzugefuegt werden solldouble
- 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 StartKnotensKnoten
- 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 StartKnotensint
- 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 classjava.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
-
-