419 lines
12 KiB
Java
419 lines
12 KiB
Java
package graph;
|
|
|
|
import OurApplication.OurLogElement;
|
|
import logging.LogElementList;
|
|
|
|
import java.awt.Color;
|
|
import java.util.Vector;
|
|
import java.util.Objects;
|
|
|
|
/**
|
|
* Abstract class representing a generic graph.
|
|
* @param <T> Type parameter for vertex markings, extends VertexMarking.
|
|
* @param <U> Type parameter for edge markings, extends EdgeMarking.
|
|
*/
|
|
public abstract class Graph<T extends VertexMarking, U extends EdgeMarking> {
|
|
|
|
// ATTRIBUTE
|
|
|
|
/** The name of the graph. */
|
|
private String name;
|
|
|
|
/** Vector containing all marked vertices in the graph. */
|
|
private Vector<MarkedVertex<T>> vertexes;
|
|
|
|
/** Vector containing all marked edges in the graph. */
|
|
private Vector<MarkedEdge<U>> edges;
|
|
|
|
|
|
// KONSTRUKTOREN
|
|
|
|
/**
|
|
* Default constructor initializes an empty graph.
|
|
*/
|
|
public Graph() {
|
|
this.edges = new Vector<>();
|
|
this.vertexes = new Vector<>();
|
|
}
|
|
|
|
|
|
/**
|
|
* Constructor that initializes the graph with a given name.
|
|
* @param s The name of the graph.
|
|
*/
|
|
public Graph(String s) {
|
|
this();
|
|
this.name = s;
|
|
}
|
|
|
|
|
|
// GET-ER
|
|
|
|
/**
|
|
* Returns the name of the graph.
|
|
* @return The name of the graph.
|
|
*/
|
|
public String getName() {
|
|
return this.name;
|
|
}
|
|
|
|
|
|
/**
|
|
* Returns all edges in the graph.
|
|
* @return Vector containing all edges in the graph.
|
|
*/
|
|
public Vector<MarkedEdge<U>> getAllEdges() {
|
|
return this.edges;
|
|
}
|
|
|
|
|
|
/**
|
|
* Returns all vertices in the graph.
|
|
* @return Vector containing all vertices in the graph.
|
|
*/
|
|
public Vector<MarkedVertex<T>> getAllVertexes() {
|
|
return this.vertexes;
|
|
}
|
|
|
|
|
|
/**
|
|
* Abstract method to get the visualization representation of the graph.
|
|
* @return Visualization representation of the graph.
|
|
*/
|
|
public abstract visualizationElements.Graph getScreenGraph();
|
|
|
|
|
|
/**
|
|
* Abstract method to get the log list associated with the graph.
|
|
* @return LogElementList containing log elements associated with the graph.
|
|
*/
|
|
public abstract LogElementList<OurLogElement> getLogList();
|
|
|
|
|
|
// SET-ER
|
|
|
|
/**
|
|
* Sets the name of the graph.
|
|
* @param s The name to set for the graph.
|
|
*/
|
|
public void setName(String s) {
|
|
this.name = s;
|
|
}
|
|
|
|
|
|
/**
|
|
* Returns a string representation of the graph.
|
|
* @return String representation of the graph.
|
|
*/
|
|
public String toString() {
|
|
String output = "";
|
|
for (Vertex i: this.vertexes) {
|
|
output += i.toString();
|
|
output += "\n";
|
|
}
|
|
for (Edge i: this.edges) {
|
|
output += i.toString();
|
|
output += "\n";
|
|
}
|
|
return output;
|
|
}
|
|
|
|
|
|
// HINZUFÜGEN
|
|
|
|
/**
|
|
* Adds an edge to the graph.
|
|
* @param e The edge to add.
|
|
*/
|
|
public void addEdge(MarkedEdge<U> e) {
|
|
this.edges.add(e);
|
|
}
|
|
|
|
|
|
/**
|
|
* Adds a vertex to the graph.
|
|
* @param n The vertex to add.
|
|
*/
|
|
public void addVertex(MarkedVertex<T> n) {
|
|
this.vertexes.add(n);
|
|
}
|
|
|
|
|
|
// LÖSCHEN
|
|
|
|
/**
|
|
* Removes an edge from the graph.
|
|
* @param e The edge to remove.
|
|
*/
|
|
public void removeEdge(MarkedEdge<U> e) {
|
|
this.edges.remove(e);
|
|
}
|
|
|
|
|
|
/**
|
|
* Removes an edge from the graph based on its name.
|
|
* @param s The name of the edge to remove.
|
|
* @throws NameDoesNotExistException If the edge with the specified name does not exist.
|
|
*/
|
|
public void removeEdge(String s) throws NameDoesNotExistException {
|
|
for (MarkedEdge<U> i: this.edges) {
|
|
if (Objects.equals(i.getName(), s)) {
|
|
this.removeEdge(i);
|
|
return;
|
|
}
|
|
}
|
|
throw new NameDoesNotExistException("One of the Edges might not exist");
|
|
}
|
|
|
|
|
|
/**
|
|
* Removes a vertex from the graph.
|
|
* @param n The vertex to remove.
|
|
*/
|
|
public void removeVertex(MarkedVertex<T> n) {
|
|
for (MarkedEdge<U> i: this.edges) {
|
|
if (i.getSource() == n || i.getDestination() == n) {
|
|
this.removeEdge(i);
|
|
}
|
|
}
|
|
this.vertexes.remove(n);
|
|
}
|
|
|
|
|
|
/**
|
|
* Removes a vertex from the graph based on its name.
|
|
* @param s The name of the vertex to remove.
|
|
* @throws NameDoesNotExistException If the vertex with the specified name does not exist.
|
|
*/
|
|
public void removeVertex(String s) throws NameDoesNotExistException {
|
|
for (MarkedVertex<T> i: this.vertexes) {
|
|
if (Objects.equals(i.getName(), s)) {
|
|
this.removeVertex(i);
|
|
return;
|
|
}
|
|
}
|
|
throw new NameDoesNotExistException("One of the Vertexes might not exist");
|
|
}
|
|
|
|
|
|
// GRAPH EIGENSCHAFTEN
|
|
|
|
/**
|
|
* Returns the number of edges in the graph.
|
|
* @return The number of edges in the graph.
|
|
*/
|
|
public int numberOfEdges() {
|
|
return this.edges.size();
|
|
}
|
|
|
|
|
|
/**
|
|
* Returns the number of vertices in the graph.
|
|
* @return The number of vertices in the graph.
|
|
*/
|
|
public int numberOfVertexes() {
|
|
return this.vertexes.size();
|
|
}
|
|
|
|
|
|
/**
|
|
* Computes and returns the degree of the graph.
|
|
* @return The degree of the graph.
|
|
*/
|
|
public int degree() {
|
|
return 2 * this.edges.size();
|
|
}
|
|
|
|
|
|
/**
|
|
* Checks if a vertex is present in the graph.
|
|
* @param n The vertex to check.
|
|
* @return True if the vertex is present, false otherwise.
|
|
*/
|
|
public boolean hasVertex(MarkedVertex<T> n) {
|
|
return this.vertexes.contains(n);
|
|
}
|
|
|
|
/**
|
|
* Checks if a vertex with a specific name is present in the graph.
|
|
* @param s The name of the vertex to check.
|
|
* @return True if the vertex with the given name is present, false otherwise.
|
|
*/
|
|
public boolean hasVertex(String s) {
|
|
for (MarkedVertex<T> i: this.vertexes) {
|
|
if (Objects.equals(i.getName(), s)) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
/**
|
|
* Checks if an edge is present in the graph.
|
|
* @param e The edge to check.
|
|
* @return True if the edge is present, false otherwise.
|
|
*/
|
|
public boolean hasEdge(MarkedEdge<U> e) {
|
|
return this.edges.contains(e);
|
|
}
|
|
|
|
/**
|
|
* Checks if an edge with a specific name is present in the graph.
|
|
* @param s The name of the edge to check.
|
|
* @return True if the edge with the given name is present, false otherwise.
|
|
*/
|
|
public boolean hasEdge(String s) {
|
|
for (MarkedEdge<U> i: this.edges) {
|
|
if (Objects.equals(i.getName(), s)) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
// KNOTEN EIGENSCHAFTEN
|
|
|
|
/**
|
|
* Checks if there is an edge between two vertices in the graph.
|
|
* @param v1 First vertex.
|
|
* @param v2 Second vertex.
|
|
* @return True if there is an edge between the vertices, false otherwise.
|
|
*/
|
|
public boolean hasEdge(MarkedVertex<T> v1, MarkedVertex<T> v2) {
|
|
for (MarkedEdge<U> i: this.edges) {
|
|
if ((i.getSource() == v1 && i.getDestination() == v2) || (i.getSource() == v2 && i.getDestination() == v1)) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
/**
|
|
* Checks if there is an edge between two vertices identified by their names.
|
|
* @param s1 Name of the first vertex.
|
|
* @param s2 Name of the second vertex.
|
|
* @return True if there is an edge between the vertices, false otherwise.
|
|
* @throws NameDoesNotExistException If one of the vertex names does not exist in the graph.
|
|
*/
|
|
public boolean hasEdge(String s1, String s2) throws NameDoesNotExistException {
|
|
MarkedVertex<T> n1 = null;
|
|
MarkedVertex<T> n2 = null;
|
|
for (MarkedVertex<T> i: this.getAllVertexes()) {
|
|
if (Objects.equals(i.getName(), s1)) {
|
|
n1 = i;
|
|
} else if (Objects.equals(i.getName(), s2)) {
|
|
n2 = i;
|
|
}
|
|
}
|
|
if (n1 == null || n2 == null) {
|
|
throw new NameDoesNotExistException("One of the Vertexes might not exist");
|
|
} else {
|
|
return hasEdge(n1, n2);
|
|
}
|
|
}
|
|
|
|
|
|
/**
|
|
* Checks if two vertices are adjacent (connected by an edge) in the graph.
|
|
* @param n1 First vertex.
|
|
* @param n2 Second vertex.
|
|
* @return True if the vertices are adjacent, false otherwise.
|
|
*/
|
|
public boolean areAdjacent(MarkedVertex<T> n1, MarkedVertex<T> n2) {
|
|
for (MarkedEdge<U> i: this.edges) {
|
|
if ((i.getSource() == n1 && i.getDestination() == n2) || (i.getSource() == n2 && i.getDestination() == n1)) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
/**
|
|
* Checks if two vertices identified by their names are adjacent (connected by an edge) in the graph.
|
|
* @param s1 Name of the first vertex.
|
|
* @param s2 Name of the second vertex.
|
|
* @return True if the vertices are adjacent, false otherwise.
|
|
* @throws NameDoesNotExistException If one of the vertex names does not exist in the graph.
|
|
*/
|
|
public boolean areAdjacent(String s1, String s2) throws NameDoesNotExistException {
|
|
MarkedVertex<T> n1 = null;
|
|
MarkedVertex<T> n2 = null;
|
|
for (MarkedVertex<T> i: this.getAllVertexes()) {
|
|
if (Objects.equals(i.getName(), s1)) {
|
|
n1 = i;
|
|
} else if (Objects.equals(i.getName(), s2)) {
|
|
n2 = i;
|
|
}
|
|
}
|
|
if (n1 == null || n2 == null) {
|
|
throw new NameDoesNotExistException("One of the Vertexes might not exist");
|
|
} else {
|
|
return areAdjacent(n1, n2);
|
|
}
|
|
}
|
|
|
|
|
|
/**
|
|
* Checks if a vertex has a loop (an edge connecting it to itself) in the graph.
|
|
* @param n The vertex to check.
|
|
* @return True if the vertex has a loop, false otherwise.
|
|
*/
|
|
public boolean hasLoop(MarkedVertex<T> n) {
|
|
for (MarkedEdge<U> i: this.edges) {
|
|
if (i.getSource() == i.getDestination() && i.getSource() == n) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
/**
|
|
* Checks if a vertex identified by its name has a loop (an edge connecting it to itself) in the graph.
|
|
* @param s The name of the vertex to check.
|
|
* @return True if the vertex has a loop, false otherwise.
|
|
* @throws NameDoesNotExistException If the vertex name does not exist in the graph.
|
|
*/
|
|
public boolean hasLoop(String s) throws NameDoesNotExistException {
|
|
for (MarkedVertex<T> i: this.vertexes) {
|
|
if (Objects.equals(i.getName(), s)) {
|
|
return hasLoop(i);
|
|
}
|
|
}
|
|
throw new NameDoesNotExistException("One of the Vertexes might not exist");
|
|
}
|
|
|
|
|
|
/**
|
|
* Resets the screen graph colors of all vertices to black.
|
|
*/
|
|
public void clearScreenGraphColor() {
|
|
for (visualizationElements.Vertex screenVertexes : this.getScreenGraph().getVertexes()) {
|
|
screenVertexes.setColor(Color.BLACK);
|
|
}
|
|
}
|
|
|
|
|
|
/**
|
|
* Abstract method to find the shortest path between two vertices using Dijkstra's algorithm.
|
|
* @param n1 Starting vertex.
|
|
* @param n2 Destination vertex.
|
|
* @return Length of the shortest path between the vertices.
|
|
*/
|
|
public abstract int getShortestPathDijkstra(MarkedVertex<T> n1, MarkedVertex<T> n2);
|
|
|
|
|
|
/**
|
|
* Abstract method to find the shortest path between two vertices using A* algorithm.
|
|
* @param n1 Starting vertex.
|
|
* @param n2 Destination vertex.
|
|
* @return Length of the shortest path between the vertices.
|
|
*/
|
|
public abstract double getShortestPathAStar(MarkedVertex<T> n1, MarkedVertex<T> n2);
|
|
}
|
|
|