123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349 |
- "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
|