270 lines
13 KiB
Java
270 lines
13 KiB
Java
package graph;
|
|
|
|
/**
|
|
* Class containing example graphs for demonstration purposes.
|
|
*/
|
|
public class ExampleGraphs {
|
|
|
|
/**
|
|
* Creates an example graph suitable for demonstrating Dijkstra's and A* algorithms.
|
|
* This graph contains multiple nodes connected by weighted edges, allowing efficient
|
|
* calculation of shortest paths from a start node to an end node.
|
|
*
|
|
* @return Directed graph instance for example 1.
|
|
*/
|
|
public DirectedGraph<VertexMarking, EdgeMarking> example1() {
|
|
|
|
/**
|
|
* Beispiel 1 zeigt ein Gitter aus Knoten und Kanten, bei dem jeder Knoten mit
|
|
/*
|
|
* Erstellt einen Beispielgraphen, der sich ideal für die Demonstration der Funktionsweise
|
|
* des Dijkstra- und A*-Algorithmus eignet. Der Graph enthält eine Vielzahl von Knoten, die durch
|
|
* gewichtete Kanten verbunden sind. Dies ermöglicht es, den kürzesten Weg von einem Startknoten zu einem
|
|
* Zielknoten effizient zu berechnen und die Pfadfindung der beiden Algorithmen zu veranschaulichen.
|
|
*
|
|
*/
|
|
|
|
DirectedGraph<VertexMarking, EdgeMarking> example1 = new DirectedGraph<>();
|
|
|
|
// Erstellung der Knoten mit Koordinaten
|
|
MarkedVertex<VertexMarking> A = new MarkedVertex<>(50, 250, "Start", null, null);
|
|
MarkedVertex<VertexMarking> B = new MarkedVertex<>(150, 150, "B", null, null);
|
|
MarkedVertex<VertexMarking> C = new MarkedVertex<>(150, 350, "C", null, null);
|
|
MarkedVertex<VertexMarking> D = new MarkedVertex<>(250, 100, "D", null, null);
|
|
MarkedVertex<VertexMarking> E = new MarkedVertex<>(250, 250, "E", null, null);
|
|
MarkedVertex<VertexMarking> F = new MarkedVertex<>(350, 200, "F", null, null);
|
|
MarkedVertex<VertexMarking> G = new MarkedVertex<>(450, 300, "G", null, null);
|
|
MarkedVertex<VertexMarking> H = new MarkedVertex<>(450, 100, "Ende", null, null);
|
|
|
|
|
|
// Hinzufügen der Knoten zum Graphen
|
|
example1.addVertex(A);
|
|
example1.addVertex(B);
|
|
example1.addVertex(C);
|
|
example1.addVertex(D);
|
|
example1.addVertex(E);
|
|
example1.addVertex(F);
|
|
example1.addVertex(G);
|
|
example1.addVertex(H);
|
|
|
|
// Erstellung der Kanten mit Gewichtungen
|
|
example1.addEdge(new MarkedEdge<>("AB", A, B, new EdgeWeightMarking(4)));
|
|
example1.addEdge(new MarkedEdge<>("AC", A, C, new EdgeWeightMarking(2)));
|
|
example1.addEdge(new MarkedEdge<>("BC", B, C, new EdgeWeightMarking(5)));
|
|
example1.addEdge(new MarkedEdge<>("BD", B, D, new EdgeWeightMarking(10)));
|
|
example1.addEdge(new MarkedEdge<>("CD", C, D, new EdgeWeightMarking(3)));
|
|
example1.addEdge(new MarkedEdge<>("CE", C, E, new EdgeWeightMarking(7)));
|
|
example1.addEdge(new MarkedEdge<>("DE", D, E, new EdgeWeightMarking(2)));
|
|
example1.addEdge(new MarkedEdge<>("DF", D, F, new EdgeWeightMarking(2)));
|
|
example1.addEdge(new MarkedEdge<>("EF", E, F, new EdgeWeightMarking(5)));
|
|
example1.addEdge(new MarkedEdge<>("EG", E, G, new EdgeWeightMarking(10)));
|
|
example1.addEdge(new MarkedEdge<>("FG", F, G, new EdgeWeightMarking(3)));
|
|
example1.addEdge(new MarkedEdge<>("FH", F, H, new EdgeWeightMarking(6)));
|
|
example1.addEdge(new MarkedEdge<>("GH", G, H, new EdgeWeightMarking(1)));
|
|
|
|
return example1;
|
|
}
|
|
|
|
/**
|
|
* Creates an example grid graph where each node is connected to its horizontal and vertical neighbors.
|
|
* All edges have the same weight. The start node is in one corner of the grid, and the end node is
|
|
* in the opposite corner, demonstrating the efficiency of the A* algorithm in structured grid graphs.
|
|
*
|
|
* @return Directed graph instance for example 2.
|
|
*/
|
|
public DirectedGraph<VertexMarking, EdgeMarking> example2() {
|
|
|
|
/*
|
|
* Beispiel 2 zeigt ein Gitter aus Knoten und Kanten, bei dem jeder Knoten mit
|
|
* seinen horizontal und vertikal benachbarten Knoten verbunden ist. Alle Kanten
|
|
* haben die gleiche Gewichtung. Der Startknoten befindet sich in einer Ecke
|
|
* des Gitters und der Zielknoten in der gegenüberliegenden Ecke. Dadurch wird gezeigt,
|
|
* wie der A*-Algorithmus durch gezieltere Suche effizienter ist
|
|
* als der Dijkstra-Algorithmus in einem strukturierten Gittergraphen.
|
|
*
|
|
*/
|
|
|
|
DirectedGraph<VertexMarking, EdgeMarking> example2 = new DirectedGraph<>();
|
|
|
|
int size = 5;
|
|
MarkedVertex<VertexMarking>[][] vertices = new MarkedVertex[size][size];
|
|
|
|
// Knoten erstellen und zum Graph hinzufügen
|
|
for (int row = 0; row < size; row++) {
|
|
for (int col = 0; col < size; col++) {
|
|
String name = String.valueOf((char) ('A' + row * size + col));
|
|
if (name.equals("A")) {
|
|
name = "Start";
|
|
} else if (name.equals("Y")) {
|
|
name = "Ende";
|
|
}
|
|
vertices[row][col] = new MarkedVertex<>(50 + col * 100, 50 + row * 100, name, null, null);
|
|
example2.addVertex(vertices[row][col]);
|
|
}
|
|
}
|
|
|
|
// Kanten horizontal und vertikal verbinden
|
|
for (int row = 0; row < size; row++) {
|
|
for (int col = 0; col < size; col++) {
|
|
if (col < size - 1) {
|
|
addBidirectionalEdge(example2, vertices[row][col], vertices[row][col + 1], new EdgeWeightMarking(1));
|
|
}
|
|
if (row < size - 1) {
|
|
addBidirectionalEdge(example2, vertices[row][col], vertices[row + 1][col], new EdgeWeightMarking(1));
|
|
}
|
|
}
|
|
}
|
|
|
|
return example2;
|
|
}
|
|
|
|
/**
|
|
* Creates an example graph illustrating two paths from a start node to an end node with different characteristics:
|
|
* one path with few nodes and mostly low-weight edges, and another path with more nodes and higher-weight edges.
|
|
* The algorithms will alternate exploration between these paths.
|
|
*
|
|
* @return Directed graph instance for example 3.
|
|
*/
|
|
public DirectedGraph<VertexMarking, EdgeMarking> example3() {
|
|
|
|
/*
|
|
* Beispiel 3 zeigt zwei Wege von einem Startknoten zu einem Zielknoten mit unterschiedlichen Eigenschaften:
|
|
* Ein Weg (oben) hat wenige Knoten mit Kanten geringer Gewichtung, außer der vorletzten Kante, die hohe Gewichtung hat.
|
|
* Der andere Weg (unten) hat mehr Knoten mit höherer Gewichtung der Kanten. Die Algorithmen wechseln also mit dem Erkunden
|
|
* zwischen den beiden Pfaden.
|
|
*
|
|
*/
|
|
|
|
DirectedGraph<VertexMarking, EdgeMarking> example3 = new DirectedGraph<>();
|
|
|
|
MarkedVertex A = new MarkedVertex<>(100, 100, "Start", null, null);
|
|
MarkedVertex B = new MarkedVertex<>(250, 50, "B", null, null);
|
|
MarkedVertex C = new MarkedVertex<>(400, 100, "C", null, null);
|
|
MarkedVertex D = new MarkedVertex<>(550, 50, "D", null, null);
|
|
MarkedVertex E = new MarkedVertex<>(700, 100, "Ende", null, null);
|
|
MarkedVertex F = new MarkedVertex<>(250, 200, "F", null, null);
|
|
MarkedVertex G = new MarkedVertex<>(550, 200, "G", null, null);
|
|
|
|
example3.addVertex(A);
|
|
example3.addVertex(B);
|
|
example3.addVertex(C);
|
|
example3.addVertex(D);
|
|
example3.addVertex(E);
|
|
example3.addVertex(F);
|
|
example3.addVertex(G);
|
|
|
|
example3.addEdge(new MarkedEdge<>("AB", A, B, new EdgeWeightMarking(1)));
|
|
example3.addEdge(new MarkedEdge<>("BC", B, C, new EdgeWeightMarking(1)));
|
|
example3.addEdge(new MarkedEdge<>("CD", C, D, new EdgeWeightMarking(10)));
|
|
example3.addEdge(new MarkedEdge<>("DE", D, E, new EdgeWeightMarking(1)));
|
|
|
|
example3.addEdge(new MarkedEdge<>("AF", A, F, new EdgeWeightMarking(5)));
|
|
example3.addEdge(new MarkedEdge<>("FG", F, G, new EdgeWeightMarking(5)));
|
|
example3.addEdge(new MarkedEdge<>("GE", G, E, new EdgeWeightMarking(5)));
|
|
|
|
return example3;
|
|
}
|
|
|
|
/**
|
|
* Creates an example labyrinth graph with four horizontal paths, each consisting of four nodes.
|
|
* Each path leads to a respective endpoint, demonstrating how algorithms may explore potentially incorrect paths
|
|
* before finding the correct one, and showing the efficiency of A* in finding the correct path quickly.
|
|
*
|
|
* @return Directed graph instance for example 4.
|
|
*/
|
|
public DirectedGraph<VertexMarking, EdgeMarking> example4() {
|
|
|
|
/*
|
|
* Beispiel 4 zeigt ein Labyrinth mit vier horizontalen Wegen, die jeweils aus vier Knoten bestehen.
|
|
* Jeder Weg führt zum Endpunkt E1, E2, E3 bzw. Ende. Ziel ist es zu zeigen, dass die Algorithmen auch
|
|
* potenziell falsche Wege erkunden können, bevor sie den Endknoten erreichen. Zudem wird gezeigt,
|
|
* wie A* schnell den richtigen Weg findet, während Djkstra alle Wege durchsucht.
|
|
*
|
|
*/
|
|
|
|
DirectedGraph<VertexMarking, EdgeMarking> example4 = new DirectedGraph<>();
|
|
|
|
// Startpunkt A in der Mitte der Y-Koordinate
|
|
MarkedVertex A = new MarkedVertex<>(100, 250, "Start", null, null);
|
|
|
|
// Erster Weg
|
|
MarkedVertex B1 = new MarkedVertex<>(200, 100, "B1", null, null);
|
|
MarkedVertex C1 = new MarkedVertex<>(300, 100, "C1", null, null);
|
|
MarkedVertex D1 = new MarkedVertex<>(400, 100, "D1", null, null);
|
|
MarkedVertex E1 = new MarkedVertex<>(500, 100, "E1", null, null); // Endpunkt des ersten Weges
|
|
|
|
// Zweiter Weg
|
|
MarkedVertex B2 = new MarkedVertex<>(200, 200, "B2", null, null);
|
|
MarkedVertex C2 = new MarkedVertex<>(300, 200, "C2", null, null);
|
|
MarkedVertex D2 = new MarkedVertex<>(400, 200, "D2", null, null);
|
|
MarkedVertex E2 = new MarkedVertex<>(500, 200, "E2", null, null); // Endpunkt des zweiten Weges
|
|
|
|
// Dritter Weg
|
|
MarkedVertex B3 = new MarkedVertex<>(200, 300, "B3", null, null);
|
|
MarkedVertex C3 = new MarkedVertex<>(300, 300, "C3", null, null);
|
|
MarkedVertex D3 = new MarkedVertex<>(400, 300, "D3", null, null);
|
|
MarkedVertex E3 = new MarkedVertex<>(500, 300, "E3", null, null); // Endpunkt des dritten Weges
|
|
|
|
// Vierter Weg
|
|
MarkedVertex B4 = new MarkedVertex<>(200, 400, "B4", null, null);
|
|
MarkedVertex C4 = new MarkedVertex<>(300, 400, "C4", null, null);
|
|
MarkedVertex D4 = new MarkedVertex<>(400, 400, "D4", null, null);
|
|
MarkedVertex E4 = new MarkedVertex<>(500, 400, "Ende", null, null); // Endpunkt des vierten Weges
|
|
|
|
example4.addVertex(A);
|
|
example4.addVertex(B1);
|
|
example4.addVertex(C1);
|
|
example4.addVertex(D1);
|
|
example4.addVertex(B2);
|
|
example4.addVertex(C2);
|
|
example4.addVertex(D2);
|
|
example4.addVertex(B3);
|
|
example4.addVertex(C3);
|
|
example4.addVertex(D3);
|
|
example4.addVertex(B4);
|
|
example4.addVertex(C4);
|
|
example4.addVertex(D4);
|
|
example4.addVertex(E1);
|
|
example4.addVertex(E2);
|
|
example4.addVertex(E3);
|
|
example4.addVertex(E4);
|
|
|
|
example4.addEdge(new MarkedEdge<>("AB1", A, B1, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("AB2", A, B2, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("AB3", A, B3, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("AB4", A, B4, new EdgeWeightMarking(1)));
|
|
|
|
example4.addEdge(new MarkedEdge<>("B1C1", B1, C1, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("B2C2", B2, C2, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("B3C3", B3, C3, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("B4C4", B4, C4, new EdgeWeightMarking(1)));
|
|
|
|
example4.addEdge(new MarkedEdge<>("C1D1", C1, D1, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("C2D2", C2, D2, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("C3D3", C3, D3, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("C4D4", C4, D4, new EdgeWeightMarking(1)));
|
|
|
|
example4.addEdge(new MarkedEdge<>("D1E1", D1, E1, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("D2E2", D2, E2, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("D3E3", D3, E3, new EdgeWeightMarking(1)));
|
|
example4.addEdge(new MarkedEdge<>("D4E4", D4, E4, new EdgeWeightMarking(1)));
|
|
|
|
return example4;
|
|
}
|
|
|
|
/**
|
|
* Helper method to add a bidirectional edge between two vertices in a graph.
|
|
*
|
|
* @param graph The graph instance where the edge should be added.
|
|
* @param from The starting vertex of the edge.
|
|
* @param to The ending vertex of the edge.
|
|
* @param weight The weight marking of the edge.
|
|
*/
|
|
private void addBidirectionalEdge(DirectedGraph<VertexMarking, EdgeMarking> graph, MarkedVertex<VertexMarking> from, MarkedVertex<VertexMarking> to, EdgeWeightMarking weight) {
|
|
MarkedEdge<EdgeMarking> forwardEdge = new MarkedEdge<>("edge" + from.getName() + "_" + to.getName(), from, to, weight);
|
|
MarkedEdge<EdgeMarking> backwardEdge = new MarkedEdge<>("edge" + to.getName() + "_" + from.getName(), to, from, weight);
|
|
graph.addEdge(forwardEdge);
|
|
graph.addEdge(backwardEdge);
|
|
}
|
|
}
|