ts-api/dist/core/kursblockung/KursblockungMatrix.js

"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 <a href= "https://en.wikipedia.org/wiki/Shortest_path_problem">Wikipedia
     *      - Shortest_path_problem</a>
     *
     * @see <a href= "https://en.wikipedia.org/wiki/Johnson%27s_algorithm">Wikipedia
     *      - Johnsons Algorithm</a>
     *
     * @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