Uebungsaufgaben/GraphenTeorie/Graph.java
2024-06-11 16:23:46 +02:00

320 lines
8.9 KiB
Java

package GraphenTeorie;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Queue;
public class Graph {
private ArrayList<Knoten> knotenArrayList;
private ArrayList<Kante> kantenArrayList;
ArrayList<ArrayList<Object>> adjazenzmatrix;
ArrayList<ArrayList<Knoten>> adjazenzliste;
public Graph () {
this.knotenArrayList = new ArrayList<>();
this.kantenArrayList = new ArrayList<>();
this.adjazenzmatrix = this.createAdjazenzmatrix();
this.adjazenzliste = this.createAdjazenzliste();
}
public static void main(String[] args) {
Graph meinGraph = new Graph();
Knoten k1 = meinGraph.addKnoten();
Knoten k2 = meinGraph.addKnoten();
Knoten k3 = meinGraph.addKnoten();
meinGraph.addKante(k1, k2);
//meinGraph.addKante(k2, k1);
//meinGraph.addKante(k2, k3);
meinGraph.addKante(k3, k1);
//meinGraph.addKante(k1, k3);
System.out.println(meinGraph.createAdjazenzmatrix());
System.out.println(meinGraph.createAdjazenzliste());
System.out.println(meinGraph.isSchwachZusammenhaengend());
System.out.println(meinGraph.isVollstaendig());
System.out.println(meinGraph.isZyklus());
}
public Knoten addKnoten() {
Knoten neu = new Knoten();
this.knotenArrayList.add(neu);
return neu;
}
public Kante addKante(Knoten von, Knoten nach) {
Kante neu = new Kante(von, nach);
this.kantenArrayList.add(neu);
return neu;
}
public void removeKnoten(Knoten loeschObjekt) {
for (Kante i: loeschObjekt.getAnliegendeKanten()) {
this.removeKante(i);
}
this.knotenArrayList.remove(loeschObjekt);
}
public void removeKante(Kante loeschObjekt) {
this.kantenArrayList.remove(loeschObjekt);
}
public void fusioniereKnoten(Knoten k1, Knoten k2) {
Knoten fusion = this.addKnoten();
for (Kante i: k1.getEingehendeKanten()) {
fusion.addEingehendeKante(this.addKante(i.getOtherSide(k1), fusion));
}
for (Kante i: k2.getEingehendeKanten()) {
fusion.addEingehendeKante(this.addKante(i.getOtherSide(k2), fusion));
}
for (Kante i: k1.getAusgehendeKanten()) {
fusion.addEingehendeKante(this.addKante(fusion, i.getOtherSide(k1)));
}
for (Kante i: k2.getAusgehendeKanten()) {
fusion.addEingehendeKante(this.addKante(fusion, i.getOtherSide(k2)));
}
this.removeKnoten(k1);
this.removeKnoten(k2);
}
public void kontrahiereKante(Kante k1) {
this.fusioniereKnoten(k1.getStartKnoten(), k1.getEndKnoten());
}
public void entmarkiereAlle() {
for (Knoten i: this.knotenArrayList) {
i.setMarkierung(false);
}
}
public ArrayList<ArrayList<Object>> createAdjazenzmatrix() {
ArrayList<ArrayList<Object>> matrix = new ArrayList<>();
// Erstellt leere Matrix nur mit "Beschriftung"
matrix.add(new ArrayList<Object>()); // Erstellt oberste Zeile
for (int i = 0; i < this.knotenArrayList.size(); i++) {
matrix.getFirst().add(knotenArrayList.get(i)); // Füge Zeile Objekt hinzu
matrix.add(new ArrayList<Object>()); // Erstellt neue Spalte
matrix.get(i+1).add(knotenArrayList.get(i)); // Füge Spalte Objekt hinzu
}
// Füllt alles mit 0 auf.
for (ArrayList<Object> i: matrix) {
if (i.size() != matrix.getFirst().size()) {
for (int j = 0; j < matrix.getFirst().size(); j++) {
i.add(0);
}
}
}
// Setzt die Werte ein
for (Kante i: kantenArrayList) {
int von = matrix.getFirst().indexOf(i.getStartKnoten());
int nach = matrix.getFirst().indexOf(i.getEndKnoten());
ArrayList<Object> neu = matrix.get(von+1);
neu.set(nach+1, i.getGewichtung());
matrix.set(von+1, neu);
}
this.adjazenzmatrix = matrix;
return matrix;
}
public ArrayList<ArrayList<Knoten>> createAdjazenzliste() {
ArrayList<ArrayList<Knoten>> liste = new ArrayList<>();
for (int i = 0; i < this.knotenArrayList.size(); i++) {
liste.add(new ArrayList<Knoten>());
liste.get(i).add(knotenArrayList.get(i));
for (Kante j: knotenArrayList.get(i).getAusgehendeKanten()) {
liste.get(i).add(j.getEndKnoten());
}
}
this.adjazenzliste = liste;
return liste;
}
public boolean isUntergraphOf(Graph g1) {
return true;
}
public boolean isTeilgraphOf(Graph g1) {
return true;
}
// Man könnte über ungerichtete Kanten von jedem Knoten zum jedem kommen.
// Realisiert mit Stack DFS
public boolean isSchwachZusammenhaengend() {
this.entmarkiereAlle();
Stack<Knoten> stack = new Stack<>();
this.knotenArrayList.getFirst().setMarkierung(true);
stack.add(this.knotenArrayList.getFirst());
while (!stack.empty()) {
for (Knoten i : stack.pop().getAllNachbarKnoten()) {
if (!i.getMarkierung()) {
i.setMarkierung(true);
stack.add(i);
}
}
}
for (Knoten i: this.knotenArrayList) {
if (!i.getMarkierung()) {
return false;
}
}
return true;
}
// Man kann über die Pfeile zu jedem Punkt kommen
public boolean isStarkZusammenhaengend() {
return true;
}
// Jeder Konten ist direkt mit jedem anderen verknüpft
public boolean isVollstaendig() {
this.createAdjazenzliste();
for (ArrayList<Knoten> i : this.adjazenzliste) {
for (Knoten j : this.knotenArrayList) {
if (!i.contains(j)) {
return false;
}
}
}
return true;
}
// Graph is 2 colorble or no odd length cycles
// Der Graph lässt sich in 2 Mengen zerlegen die untereinander keine Verbindungen haben
public boolean isBipartit() {
return true;
}
// Bipartit + jeder Knoten von M1 ist mit jedem aus M2 zusammen
public boolean isVollstaendigBipartit() {
return true;
}
// Man kann im Graphen in die Runde laufen
// Realisiert mit BFS abgewandelt
public boolean isZyklus() {
this.entmarkiereAlle();
Queue<Knoten> queue = new LinkedList<>();
Knoten neuerStartKonten = this.knotenArrayList.getFirst();
boolean notDone = true;
while (notDone) {
neuerStartKonten.setMarkierung(true);
queue.add(neuerStartKonten);
while (!queue.isEmpty()) {
for (Kante i : queue.remove().getAusgehendeKanten()) {
if (!i.getEndKnoten().getMarkierung()) {
queue.add(i.getEndKnoten());
i.getEndKnoten().setMarkierung(true);
} else {
for (Kante j: i.getEndKnoten().getAusgehendeKanten()) {
if (j.getEndKnoten().getMarkierung()) { // FIXME Problem, wenn es aus der whileschleife ausbricht und sich einen neuen Konoten anschaut
return true;
}
}
}
}
}
notDone = false;
for (Knoten i : knotenArrayList) {
if (!i.getMarkierung()) {
notDone = true;
neuerStartKonten = i;
break;
}
}
}
return false;
}
// Jeder Knoten hat den gleichen Grad
public boolean isRegulaer() {
return true;
}
// Man kann den Graphen ohne Kreuzung mahlen
public boolean isPlanar() {
return true;
}
// Maximum aller maximalen Distanzen zwischen Knoten
public int durchmesser() {
return 1;
}
// Minimum aller maximalen Distanzen zwischen Knoten
public int radius() {
return 1;
}
// Alle Knoten mit maximaler Exzentrizität
public ArrayList<Knoten> rand() {
ArrayList<Knoten> liste = new ArrayList<>();
int d1 = this.durchmesser();
for (Knoten i: this.knotenArrayList) {
if (i.exzentrizitaet() == d1) {
liste.add(i);
}
}
return liste;
}
// Alle Knoten mit minimaler Exzentrizität
public ArrayList<Knoten> zentrum() {
ArrayList<Knoten> liste = new ArrayList<>();
int r1 = this.radius();
for (Knoten i: this.knotenArrayList) {
if (i.exzentrizitaet() == r1) {
liste.add(i);
}
}
return liste;
}
public boolean isIsomorphTo(Graph g1) {
return true;
}
}