Package de.svws_nrw.core.kursblockung
Klasse KursblockungMatrix
java.lang.Object
de.svws_nrw.core.kursblockung.KursblockungMatrix
Diese Klasse realisiert eine Adjazenzmatrix und implementiert einige Graph-Algorithmen (Maximum-cardinality
bipartite matching, maximum/minimum weighted bipartite matching, ...). Die Adjazenzmatrix wird im Folgenden Matrix
genannt.
- Siehe auch:
-
Konstruktorübersicht
KonstruktorBeschreibungKursblockungMatrix
(@NotNull Random pRandom, int rows, int cols) Erzeugt eine neue Matrix mitrows
Zeilen undcols
Spalten. -
Methodenübersicht
Modifizierer und TypMethodeBeschreibung@NotNull String
convertToString
(@NotNull String kommentar, int zellenbreite, boolean mitKnotenPotential) Erzeugt String-Ausgabe des Arrays sowie der Zeilen-zu-Spalten-Zuordnungr2c
.void
fuelleMitWert
(long wert) Füllt die Matrix mit dem übergebenen Wert.void
fuelleMitZufallszahlenVonBis
(int von, int bis) Füllt die Matrix mit ganzzahligen zufälligen Zahlenwerten aus dem Intervall[von;bis]
.@jakarta.validation.constraints.NotNull long[] @NotNull []
Erlaubt Zugriff auf den Inhalt des Arrays.@jakarta.validation.constraints.NotNull int[]
gibMaximalesBipartitesMatching
(boolean nichtdeterministisch) Berechnet zur aktuellen Matrix ein maximales bipartites Matching.@jakarta.validation.constraints.NotNull int[]
gibMinimalesBipartitesMatchingGewichtet
(boolean nichtdeterministisch) Berechnet zur aktuellen Matrix ein minimales gewichtetes Matching.int
Liefert die Anzahl an Spalten der Matrix.int
Liefert die Anzahl an Zeilen der Matrix.
-
Konstruktordetails
-
KursblockungMatrix
Erzeugt eine neue Matrix mitrows
Zeilen undcols
Spalten.- Parameter:
pRandom
- EinRandom
-Objekt zur Steuerung des Zufalls über einen Anfangs-Seed.rows
- Die Anzahl der Zeilen der Matrix.cols
- Die Anzahl der Spalten der Matrix.
-
-
Methodendetails
-
gibMaximalesBipartitesMatching
@NotNull public @jakarta.validation.constraints.NotNull int[] gibMaximalesBipartitesMatching(boolean nichtdeterministisch) Berechnet zur aktuellen Matrix ein maximales bipartites Matching. Die Methode geht davon aus, dass in der Matrix ausschließlich die Werte 0 und 1 vorkommen. Werte ungleich 0 werden andernfalls als 1 (eine Kante im Graphen) interpretiert. Nichtquadratische Matrizen sind erlaubt. Das Ergebnis der Methode ist eine größtmögliche Zeilen- zu Spaltenzuordnung. Der Algorithmus hat eine Laufzeit von O(n³).- Parameter:
nichtdeterministisch
- definiert, ob das Ergebnis zufällig sein soll, falls es mehrere optimale Lösungen gibt.- Gibt zurück:
- die Zeilen- zu Spaltenzuordnung, negative Werte entsprechen einer Nichtzuordnung.
-
gibMinimalesBipartitesMatchingGewichtet
@NotNull public @jakarta.validation.constraints.NotNull int[] gibMinimalesBipartitesMatchingGewichtet(boolean nichtdeterministisch) Berechnet zur aktuellen Matrix ein minimales gewichtetes Matching. Die Methode geht davon aus, dass in der Matrix ganzzahlige Werte vorkommen, d.h. es existiert eine Kante von jedem linken Knoten zu jedem rechten Knoten. Negative Werte und nichtquadratische Matrizen sind erlaubt. Zur Berechnung eines maximalen Matching kann man vorher alle Zellenwerte negieren. Das Ergebnis der Methode ist eine Zeilen- zu Spaltenzuordnung, deren Summe minimal ist. Der Algorithmus verwendet mehrere Runden eines SSSP-Algorithmus (Dijkstra). Damit dies bei negativen Werten funktioniert, werden die Kanten mit Hilfe von Knoten-Potentialen umgewichtet. Der Algorithmus hat eine Laufzeit von O(n³).- Parameter:
nichtdeterministisch
- definiert, ob das Ergebnis zufällig sein soll, falls es mehrere optimale Lösungen gibt.- Gibt zurück:
- die Zeilen- zu Spaltenzuordnung, negative Werte entsprechen einer Nichtzuordnung.
- Siehe auch:
-
getMatrix
@NotNull public @jakarta.validation.constraints.NotNull long[] @NotNull [] getMatrix()Erlaubt Zugriff auf den Inhalt des Arrays.- Gibt zurück:
- Die Array-Referenz.
-
convertToString
@NotNull public @NotNull String convertToString(@NotNull @NotNull String kommentar, int zellenbreite, boolean mitKnotenPotential) Erzeugt String-Ausgabe des Arrays sowie der Zeilen-zu-Spalten-Zuordnungr2c
. Diese Methode ist für Debug-Zwecke gedacht.- Parameter:
kommentar
- Ein Kommentar der über der Matrix angezeigt wird.zellenbreite
- Die Breite bei der Ausgabe der Zelle.mitKnotenPotential
- Fallstrue
, werden die Kantenwerte umgewichtet entsprechenden der Knotenpotentiale, andernfalls bleiben die Kantenwerte unverändert.- Gibt zurück:
- Eine String-Representation der Matrix.
-
fuelleMitZufallszahlenVonBis
public void fuelleMitZufallszahlenVonBis(int von, int bis) Füllt die Matrix mit ganzzahligen zufälligen Zahlenwerten aus dem Intervall[von;bis]
.- Parameter:
von
- Der kleinstmögliche zufällige Wert (inklusive).bis
- Der größtmögliche zufällige Wert (inklusive).
-
fuelleMitWert
public void fuelleMitWert(long wert) Füllt die Matrix mit dem übergebenen Wert.- Parameter:
wert
- Der Wert, der alle Zellen überschreibt.
-
gibZeilen
public int gibZeilen()Liefert die Anzahl an Zeilen der Matrix.- Gibt zurück:
- die Anzahl an Zeilen der Matrix.
-
gibSpalten
public int gibSpalten()Liefert die Anzahl an Spalten der Matrix.- Gibt zurück:
- die Anzahl an Spalten der Matrix.
-