Klasse KursblockungMatrix

java.lang.Object
de.svws_nrw.core.kursblockung.KursblockungMatrix

public class KursblockungMatrix extends Object
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

    Konstruktoren
    Konstruktor
    Beschreibung
    KursblockungMatrix(@NotNull Random pRandom, int rows, int cols)
    Erzeugt eine neue Matrix mit rows Zeilen und cols Spalten.
  • Methodenübersicht

    Modifizierer und Typ
    Methode
    Beschreibung
    @NotNull String
    convertToString(@NotNull String kommentar, int zellenbreite, boolean mitKnotenPotential)
    Erzeugt String-Ausgabe des Arrays sowie der Zeilen-zu-Spalten-Zuordnung r2c.
    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.

    Von Klasse geerbte Methoden java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Konstruktordetails

    • KursblockungMatrix

      public KursblockungMatrix(@NotNull @NotNull Random pRandom, int rows, int cols)
      Erzeugt eine neue Matrix mit rows Zeilen und cols Spalten.
      Parameter:
      pRandom - Ein Random-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-Zuordnung r2c. 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 - Falls true, 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.