"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.cast_de_nrw_schule_svws_core_kursblockung_KursblockungMatrix = exports.KursblockungMatrix = void 0;
const JavaObject_1 = require("../../java/lang/JavaObject");
const Random_1 = require("../../java/util/Random");
const StringBuilder_1 = require("../../java/lang/StringBuilder");
const Arrays_1 = require("../../java/util/Arrays");
const System_1 = require("../../java/lang/System");
class KursblockungMatrix extends JavaObject_1.JavaObject {
RND = new Random_1.Random();
matrix;
rows;
cols;
permR;
permC;
r2c;
c2r;
besuchtR;
abgearbeitetC;
vorgaengerCzuR;
queueR;
potentialR;
potentialC;
distanzC;
/**
* Erzeugt eine neue Matrix mit {@code rows} Zeilen und {@code cols} Spalten.
*
* @param rows Die Anzahl der Zeilen der Matrix.
* @param cols Die Anzahl der Spalten der Matrix.
*/
constructor(rows, cols) {
super();
this.rows = rows;
this.cols = cols;
this.matrix = [...Array(rows)].map(e => Array(cols).fill(0));
this.permR = Array(rows).fill(0);
this.permC = Array(cols).fill(0);
this.r2c = Array(rows).fill(0);
this.c2r = Array(cols).fill(0);
this.besuchtR = Array(rows).fill(false);
this.abgearbeitetC = Array(cols).fill(false);
this.vorgaengerCzuR = Array(cols).fill(0);
this.queueR = Array(rows).fill(0);
this.potentialR = Array(rows).fill(0);
this.potentialC = Array(cols).fill(0);
this.distanzC = Array(cols).fill(0);
KursblockungMatrix.initialisiere(this.permR);
KursblockungMatrix.initialisiere(this.permC);
}
/**
* 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³).
*
* @param nichtdeterministisch definiert, ob das Ergebnis zufällig sein soll,
* falls es mehrere optimale Lösungen gibt.
*
* @return die Zeilen- zu Spaltenzuordnung, negative Werte entsprechen einer
* Nichtzuordnung.
*/
gibMaximalesBipartitesMatching(nichtdeterministisch) {
Arrays_1.Arrays.fill(this.r2c, -1);
Arrays_1.Arrays.fill(this.c2r, -1);
this.initialisierPermRundPermC(nichtdeterministisch);
for (let pseudoR = 0; pseudoR < this.rows; pseudoR++) {
let r = this.permR[pseudoR];
Arrays_1.Arrays.fill(this.besuchtR, false);
Arrays_1.Arrays.fill(this.vorgaengerCzuR, -1);
let queue_first = 0;
let queue_last = 0;
this.queueR[queue_last] = r;
queue_last++;
this.besuchtR[r] = true;
while (queue_first < queue_last) {
let vonR = this.queueR[queue_first];
queue_first++;
for (let pseudoC = 0; pseudoC < this.cols; pseudoC++) {
let ueberC = this.permC[pseudoC];
if ((this.matrix[vonR][ueberC] !== 0) && (this.r2c[vonR] !== ueberC)) {
let zuR = this.c2r[ueberC];
if (zuR === -1) {
this.vorgaengerCzuR[ueberC] = vonR;
for (let c2 = ueberC; c2 >= 0;) {
let r2 = this.vorgaengerCzuR[c2];
let saveC = this.r2c[r2];
this.c2r[c2] = r2;
this.r2c[r2] = c2;
c2 = saveC;
}
queue_last = queue_first;
break;
}
if (this.besuchtR[zuR] === false) {
this.besuchtR[zuR] = true;
this.queueR[queue_last] = zuR;
queue_last++;
this.vorgaengerCzuR[ueberC] = vonR;
}
}
}
}
}
return this.r2c;
}
/**
* 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³).
*
* @see Wikipedia
* - Shortest_path_problem
*
* @see Wikipedia
* - Johnsons Algorithm
*
* @param nichtdeterministisch definiert, ob das Ergebnis zufällig sein soll,
* falls es mehrere optimale Lösungen gibt.
*
* @return die Zeilen- zu Spaltenzuordnung, negative Werte entsprechen einer
* Nichtzuordnung.
*/
gibMinimalesBipartitesMatchingGewichtet(nichtdeterministisch) {
Arrays_1.Arrays.fill(this.r2c, -1);
Arrays_1.Arrays.fill(this.c2r, -1);
Arrays_1.Arrays.fill(this.potentialR, 0);
Arrays_1.Arrays.fill(this.potentialC, 0);
this.initialisierPermRundPermC(nichtdeterministisch);
if (this.rows <= this.cols) {
for (let r = 0; r < this.rows; r++) {
let min = this.matrix[r][0] + this.potentialR[r] - this.potentialC[0];
for (let c = 0; c < this.cols; c++) {
let kante = this.matrix[r][c] + this.potentialR[r] - this.potentialC[c];
min = Math.min(min, kante);
}
this.potentialR[r] -= min;
}
}
if (this.cols <= this.rows) {
for (let c = 0; c < this.cols; c++) {
let min = this.matrix[0][c] + this.potentialR[0] - this.potentialC[c];
for (let r = 0; r < this.rows; r++) {
let kante = this.matrix[r][c] + this.potentialR[r] - this.potentialC[c];
min = Math.min(min, kante);
}
this.potentialC[c] += min;
}
}
let dijkstraRunden = Math.min(this.rows, this.cols);
Arrays_1.Arrays.fill(this.abgearbeitetC, false);
for (let ir = 0; ir < this.rows; ir++) {
let r = this.permR[ir];
for (let ic = 0; ic < this.cols; ic++) {
let c = this.permC[ic];
if (!this.abgearbeitetC[c]) {
let kante = this.matrix[r][c] + this.potentialR[r] - this.potentialC[c];
if (kante === 0) {
this.r2c[r] = c;
this.c2r[c] = r;
this.abgearbeitetC[c] = true;
dijkstraRunden--;
break;
}
}
}
}
for (let dijkstraRunde = 0; dijkstraRunde < dijkstraRunden; dijkstraRunde++) {
for (let ic = 0; ic < this.cols; ic++) {
let c = this.permC[ic];
this.vorgaengerCzuR[c] = -1;
this.abgearbeitetC[c] = false;
this.distanzC[c] = Number.MAX_VALUE;
for (let ir = 0; ir < this.rows; ir++) {
let r = this.permR[ir];
if (this.r2c[r] < 0) {
let kante = this.matrix[r][c] + this.potentialR[r] - this.potentialC[c];
if (kante < this.distanzC[c]) {
this.distanzC[c] = kante;
this.vorgaengerCzuR[c] = r;
}
}
}
}
let endknotenC = -1;
for (let dijkstraZyklus = 0; dijkstraZyklus < this.cols; dijkstraZyklus++) {
let fromC = 0;
for (let ic = 0; ic < this.cols; ic++) {
let c = this.permC[ic];
if (!this.abgearbeitetC[c]) {
if ((this.abgearbeitetC[fromC]) || (this.distanzC[c] < this.distanzC[fromC])) {
fromC = c;
}
}
}
this.abgearbeitetC[fromC] = true;
let overR = this.c2r[fromC];
if (overR >= 0) {
for (let ic = 0; ic < this.cols; ic++) {
let toC = this.permC[ic];
let kante = this.matrix[overR][toC] + this.potentialR[overR] - this.potentialC[toC];
let distance = this.distanzC[fromC] + kante;
if (distance < this.distanzC[toC]) {
this.distanzC[toC] = distance;
this.vorgaengerCzuR[toC] = overR;
}
}
}
else {
if (endknotenC < 0) {
endknotenC = fromC;
}
}
}
let currentC = endknotenC;
while (currentC >= 0) {
let prevR = this.vorgaengerCzuR[currentC];
let prevC = this.r2c[prevR];
this.r2c[prevR] = currentC;
this.c2r[currentC] = prevR;
currentC = prevC;
}
for (let r = 0; r < this.rows; r++) {
let c = this.r2c[r];
if (c >= 0) {
let kante = this.matrix[r][c] + this.potentialR[r] - this.potentialC[c];
this.potentialR[r] += this.distanzC[c] - kante;
this.potentialC[c] += this.distanzC[c];
}
}
}
return this.r2c;
}
/**
* Interne Methode zum Permutieren oder Initialisieren der Arrays
* {@link KursblockungMatrix#permR} und {@link KursblockungMatrix#permC}.
*
* @param nichtdeterministisch falls {@code true} werden
* {@link KursblockungMatrix#permR} und
* {@link KursblockungMatrix#permC} permutiert,
* sonst initialisiert.
*/
initialisierPermRundPermC(nichtdeterministisch) {
if (nichtdeterministisch) {
this.permutiere(this.permR);
this.permutiere(this.permC);
}
else {
KursblockungMatrix.initialisiere(this.permR);
KursblockungMatrix.initialisiere(this.permC);
}
}
/**
* Interne Methode zum Initialisieren eines Arrays so, dass das Array mit den
* Zahlen {@code 0,1,2...} gefüllt wird.
*
* @param perm Das Array, welches mit den Zahlen {@code 0,1,2...} gefüllt wird.
*/
static initialisiere(perm) {
let laenge = perm.length;
for (let i = 0; i < laenge; i++) {
perm[i] = i;
}
}
/**
* Interne Methode zum zufälligen Permutieren eines Arrays.
*
* @param perm Das Array, dessen Inhalt zufällig permutiert wird.
*/
permutiere(perm) {
let laenge = perm.length;
for (let i = 0; i < laenge; i++) {
let j = this.RND.nextInt(laenge);
let saveI = perm[i];
let saveJ = perm[j];
perm[i] = saveJ;
perm[j] = saveI;
}
}
/**
* Erlaubt Zugriff auf den Inhalt des Arrays.
*
* @return Die Array-Referenz.
*/
getMatrix() {
return this.matrix;
}
/**
* Erzeugt String-Ausgabe des Arrays sowie der Zeilen-zu-Spalten-Zuordnung
* {@link KursblockungMatrix#r2c}. Diese Methode ist für Debug-Zwecke gedacht.
*
* @param kommentar Ein Kommentar der über der Matrix angezeigt wird.
* @param zellenbreite Die Breite bei der Ausgabe der Zelle.
* @param mitKnotenPotential Falls {@code true}, werden die Kantenwerte
* umgewichtet entsprechenden der Knotenpotentiale,
* andernfalls bleiben die Kantenwerte unverändert.
*
* @return Eine String-Representation der Matrix.
*/
convertToString(kommentar, zellenbreite, mitKnotenPotential) {
let sb = new StringBuilder_1.StringBuilder();
sb.append(kommentar.valueOf() + System_1.System.lineSeparator().valueOf());
for (let r = 0; r < this.rows; r++) {
for (let c = 0; c < this.cols; c++) {
let wert = mitKnotenPotential ? this.matrix[r][c] + this.potentialR[r] - this.potentialC[c] : this.matrix[r][c];
let sWert = "" + wert;
while (sWert.length < zellenbreite)
sWert = " " + sWert.valueOf();
let sZusatz = this.r2c[r] === c ? "*" : " ";
sb.append(sWert.valueOf() + sZusatz.valueOf());
}
sb.append("\n");
}
sb.append("r2c = " + Arrays_1.Arrays.toString(this.r2c).valueOf());
sb.append("\n");
return sb.toString();
}
/**
* Füllt die Matrix mit ganzzahligen zufälligen Zahlenwerten aus dem Intervall
* {@code [von;bis]}.
*
* @param von Der kleinstmögliche zufällige Wert (inklusive).
* @param bis Der größtmögliche zufällige Wert (inklusive).
*/
fuelleMitZufallszahlenVonBis(von, bis) {
for (let r = 0; r < this.rows; r++) {
for (let c = 0; c < this.cols; c++) {
this.matrix[r][c] = this.RND.nextInt(bis - von + 1) + von;
}
}
}
isTranspiledInstanceOf(name) {
return ['de.nrw.schule.svws.core.kursblockung.KursblockungMatrix'].includes(name);
}
}
exports.KursblockungMatrix = KursblockungMatrix;
function cast_de_nrw_schule_svws_core_kursblockung_KursblockungMatrix(obj) {
return obj;
}
exports.cast_de_nrw_schule_svws_core_kursblockung_KursblockungMatrix = cast_de_nrw_schule_svws_core_kursblockung_KursblockungMatrix;
//# sourceMappingURL=KursblockungMatrix.js.map