SimGo123 · Oct 3, 2023 · Oct 3, 2023 · Oct 3, 2023 · Oct 3, 2023 · Oct 3, 2023
diff --git a/index.html b/index.html
@@ -48,7 +48,7 @@
   <ul class="list-group list-group-horizontal my-3 collapse" id="algorithms">
     <li class="list-group-item list-group-item-action" onclick="algorithmClick(0)">Triangulate</li>
     <li class="list-group-item list-group-item-action" onclick="algorithmClick(1)">Planar Separator Case 1, (Case 2 WIP)</li>
-    <li class="list-group-item list-group-item-action" onclick="algorithmClick(2)">Weight Max. Matching (WIP)</li>
+    <li class="list-group-item list-group-item-action" onclick="algorithmClick(2)">Weight Max. Matching</li>
     <li class="list-group-item list-group-item-action" onclick="algorithmClick(3)">Mixed Max Cut (WIP)</li>
     <li class="list-group-item list-group-item-action" onclick="algorithmClick(4)">Max Flow</li>
     <li class="list-group-item list-group-item-action" onclick="algorithmClick(5)">Disjunct S-T-Paths</li>
@@ -61,11 +61,11 @@
     <li class="list-group-item list-group-item-action" onclick="predefinedClick(3)">Sigma Graph</li>
     <li class="list-group-item list-group-item-action" onclick="predefinedClick(4)">Star Graph</li>
     <li class="list-group-item list-group-item-action" onclick="predefinedClick(5)">Tri Star Graph (Pre-Cases)</li>
-    <li class="list-group-item list-group-item-action" onclick="predefinedClick(6)">Big mü Graph (Case 2)</li>
-    <li class="list-group-item list-group-item-action" onclick="predefinedClick(7)">Case 1 Graph</li>
+    <li class="list-group-item list-group-item-action" onclick="predefinedClick(6)">Big mü Graph (PS Case 2)</li>
+    <li class="list-group-item list-group-item-action" onclick="predefinedClick(7)">PS Case 1 Graph</li>
     <li class="list-group-item list-group-item-action" onclick="predefinedClick(8)">Create Wheel</li>
-    <li class="list-group-item list-group-item-action" onclick="predefinedClick(9)">Mixed Max Graph</li>
-    <li class="list-group-item list-group-item-action" onclick="predefinedClick(10)">Weight Max 2 Graph</li>
+    <li class="list-group-item list-group-item-action" onclick="predefinedClick(9)">Weight Max Graph</li>
+    <li class="list-group-item list-group-item-action" onclick="predefinedClick(10)">Mixed Max Graph</li>
     <li class="list-group-item list-group-item-action" onclick="predefinedClick(11)">Max Flow Graph</li>
     <li class="list-group-item list-group-item-action" onclick="predefinedClick(12)">Nice ST Graph</li>
     <li class="list-group-item list-group-item-action" onclick="predefinedClick(13)">Planarity Test Graph</li>

diff --git a/js/eventHandler.js b/js/eventHandler.js
@@ -28,18 +28,15 @@ function modeClick(param) {
             func(false);
         });
         changePredefinedVisible(true);
-        $("#algoControlPanel").addClass("invisible");
     } else if (param == Modes.JSON) {
         $.each(toolBoxFuncs, function(_i, func) {
             func(false);
         });
         changeJsonToolsVisible(true);
-        $("#algoControlPanel").addClass("invisible");
     } else {
         changeAlgorithmsVisible(false);
         changePredefinedVisible(false);
         changeJsonToolsVisible(false);
-        $("#algoControlPanel").addClass("invisible");
     }
 
     for (var i = 0; i < modeItems.length; i++) {

diff --git a/js/graphAlgorithms/mixedMaxCutAlgo.js b/js/graphAlgorithms/mixedMaxCutAlgo.js
@@ -1,6 +1,6 @@
 class MixedMaxCutAlgo extends Algorithm {
     async run() {
-        super.numSteps = "X";
+        super.numSteps = 11;
 
         if (!this.preconditionsCheck()) {
             super.onFinished();
@@ -9,7 +9,8 @@ class MixedMaxCutAlgo extends Algorithm {
 
         let originalGraph = graph.getCopy();
 
-        await super.pause("Triangulate the graph", "Triangulate the graph, new edges get weight 0");
+        await super.pause("Triangulate the graph",
+            "Triangulate the graph, new edges get weight 0");
         let triangulationAlgo = new TriangulationAlgo();
         triangulationAlgo.shouldContinue = true;
         triangulationAlgo.runComplete = true;
@@ -24,12 +25,43 @@ class MixedMaxCutAlgo extends Algorithm {
         redrawAll();
 
         await super.pause("Calculate dual graph", "Build the dual graph from the current graph, keep edges");
+
+        if (!graph.isPlanarEmbedded() && this.isSubAlgo) {
+            alert("Can't run to completion, a step requires manually changing the graph");
+            super.onFinished();
+            return;
+        }
+        // If running to completion (runComplete = true), this will loop forever otherwise
+        if (!graph.isPlanarEmbedded() && this.runComplete && !this.isSubAlgo) {
+            this.runComplete = false;
+        }
+        while (!graph.isPlanarEmbedded()) {
+            this.currentStep--;
+            await super.pause("Problem: Graph is not planar embedded",
+                "Graph is not planar embedded, try to find a planar embedding first");
+        }
+
         let [dualGraph, edgeEqualities, vertexFacets] = graph.getDualGraph();
+        // Clone edge equalities, as their edges will be modified later
+        for (let i = 0; i < edgeEqualities.length; i++) {
+            let edgeEquality = edgeEqualities[i];
+            let edge1 = edgeEquality.edge1;
+            let edge2 = edgeEquality.edge2;
+            edgeEqualities[i] = new EdgeEquality(
+                new Edge(edge1.v1nr, edge1.v2nr, edge1.id, edge1.weight),
+                new Edge(edge2.v1nr, edge2.v2nr, edge2.id, edge2.weight));
+        }
+        console.log('edgeEqualities: ', edgeEqualities);
         let dualCopy = dualGraph.getCopy();
         graph = dualGraph;
         redrawAll();
 
         await super.pause("Out of one vertex, make three", "Replace every vertex by three interconnected (w=0) vertices");
+        if (graph.getLoops().length > 0 || graph.getMultiEdges().length > 0) {
+            alert("Can't run to calculate mixed max cut, dual graph contains loops or multi edges");
+            super.onFinished();
+            return;
+        }
         let vertexEqualities = this.oneVertexToThree();
         let modifiedGraph = graph.getCopy();
 
@@ -55,34 +87,28 @@ class MixedMaxCutAlgo extends Algorithm {
 
         await super.pause("Calculate weight min. 1-factor",
             "Run max matching algorithm to get a weight max. 1-factor M for w'' in O(n^(3/2))");
+
+        if (!graph.isPlanarEmbedded() && this.isSubAlgo) {
+            alert("Can't run to completion, a step requires manually changing the graph");
+            super.onFinished();
+            return;
+        }
+        // If running to completion (runComplete = true), this will loop forever otherwise
+        if (!graph.isPlanarEmbedded() && this.runComplete && !this.isSubAlgo) {
+            this.runComplete = false;
+        }
+        while (!graph.isPlanarEmbedded()) {
+            this.currentStep--;
+            await super.pause("Problem: Graph is not planar embedded",
+                "Graph is not planar embedded, try to find a planar embedding first");
+        }
+
         let weightMaxMatchAlgo = new WeightMaxMatchingAlgo();
         weightMaxMatchAlgo.shouldContinue = true;
         weightMaxMatchAlgo.runComplete = true;
         weightMaxMatchAlgo.isSubAlgo = true;
-        // TODO await weightMaxMatchAlgo.run();
-        // console.log('Starting brute force...');
+        let weightMaxEdges = await weightMaxMatchAlgo.run();
         let wmeColorSet = new ColorSet();
-        let wmeBf = weightMaxMatchAlgo.bruteForce(graph);
-        let wmeString = "";
-        wmeBf.forEach(function (edge) {
-            wmeColorSet.addEdgeColor(edge, "red");
-            wmeString += edge.print() + " ";
-        });
-        console.log(wmeString);
-        // console.log('...finished brute force');
-
-        // Weight max edges for the mixed-max-graph
-        // TODO Delete when non-brute-force weight max matching is implemented
-        let weightMaxEdges = [];
-        weightMaxEdges.push(new Edge(19, 25));
-        weightMaxEdges.push(new Edge(13, 26));
-        weightMaxEdges.push(new Edge(22, 27));
-        weightMaxEdges.push(new Edge(16, 28));
-        weightMaxEdges.push(new Edge(11, 12));
-        weightMaxEdges.push(new Edge(14, 15));
-        weightMaxEdges.push(new Edge(17, 18));
-        weightMaxEdges.push(new Edge(20, 21));
-        weightMaxEdges.push(new Edge(23, 24));
         for (let i = 0; i < graph.edges.length; i++) {
             if (eqIndexOf(weightMaxEdges, graph.edges[i]) != -1) {
                 wmeColorSet.addEdgeColor(graph.edges[i], "red");
@@ -94,13 +120,14 @@ class MixedMaxCutAlgo extends Algorithm {
             "C' = E' - M is a weight max. 2-factor in G'");
         graph = modifiedGraph;
         let cApostrophe = [];
+        let twoFactorColorSet = new ColorSet();
         for (var i = 0; i < graph.edges.length; i++) {
             if (eqIndexOf(weightMaxEdges, graph.edges[i]) == -1) {
                 cApostrophe.push(graph.edges[i]);
-                graph.edges[i].color = "green";
+                twoFactorColorSet.addEdgeColor(graph.edges[i], "green");
             }
         }
-        redrawAll();
+        redrawAll(twoFactorColorSet);
 
         let cApostropheEq = [];
         $.each(cApostrophe, function (_index, edge) {
@@ -121,45 +148,53 @@ class MixedMaxCutAlgo extends Algorithm {
             "C* = C' n E* is a weight max. even set in G*");
         graph = dualCopy;
         let cStar = [];
+        let evenSetColorSet = new ColorSet();
         for (var i = 0; i < graph.edges.length; i++) {
             if (eqIndexOf(cApostropheEq, graph.edges[i]) != -1) {
                 cStar.push(graph.edges[i]);
-                graph.edges[i].color = "blue";
+                evenSetColorSet.addEdgeColor(graph.edges[i], "blue");
             }
         }
-        redrawAll();
+        redrawAll(evenSetColorSet);
 
         await super.pause("Calculate mixed max cut in G",
             "C = (C*)* is a mixed max cut in G");
         graph = triangulatedGraph;
         let c = [];
         for (var i = 0; i < cStar.length; i++) {
             let cStarEdge = cStar[i];
-            $.each(edgeEqualities, function (_index, edgeEquality) {
+            for (var j = 0; j < edgeEqualities.length; j++) {
+                let edgeEquality = edgeEqualities[j];
                 if (edgeEquality.edge1.eq(cStarEdge)) {
                     c.push(edgeEquality.edge2);
-                    return false;
+                    break;
                 }
-            });
+            }
         }
+        let mixedMaxCutColorSet = new ColorSet();
         for (var i = 0; i < graph.edges.length; i++) {
             if (eqIndexOf(c, graph.edges[i]) != -1) {
-                graph.edges[i].color = "orange";
+                mixedMaxCutColorSet.addEdgeColor(graph.edges[i], "orange");
             }
         }
-        redrawAll();
+        redrawAll(mixedMaxCutColorSet);
 
         await super.pause("Calculate mixed max cut in G_0",
             "C_0 = C n E_0 is a mixed max cut in G_0");
         graph = originalGraph;
+        let mixedMaxCutColorSet0 = new ColorSet();
         for (var i = 0; i < graph.edges.length; i++) {
             if (eqIndexOf(c, graph.edges[i]) != -1) {
-                graph.edges[i].color = "red";
+                mixedMaxCutColorSet0.addEdgeColor(graph.edges[i], "red");
             }
         }
-        redrawAll();
+        redrawAll(mixedMaxCutColorSet0);
 
-        super.onFinished();
+        let weight = 0;
+        for (var i = 0; i < c.length; i++) {
+            weight += parseInt(c[i].weight);
+        }
+        super.onFinished(true, "Mixed max cut with weight " + weight + " calculated");
     }
 
     preconditionsCheck() {
@@ -192,12 +227,13 @@ class MixedMaxCutAlgo extends Algorithm {
             vertexEqualities.push(new VertexEquality(v1.number, vertex.number));
             vertexEqualities.push(new VertexEquality(v2.number, vertex.number));
             vertexEqualities.push(new VertexEquality(v3.number, vertex.number));
+
             newVertices.push(v1);
             newVertices.push(v2);
             newVertices.push(v3);
-            newEdges.push(new Edge(v1.number, v2.number, 0));
-            newEdges.push(new Edge(v2.number, v3.number, 0));
-            newEdges.push(new Edge(v1.number, v3.number, 0));
+            newEdges.push(new Edge(v1.number, v2.number, null, 0));
+            newEdges.push(new Edge(v2.number, v3.number, null, 0));
+            newEdges.push(new Edge(v1.number, v3.number, null, 0));
             let edges = graph.getIncidentEdges(vertex);
             for (let j = 0; j < edges.length; j++) {
                 let edge = edges[j];

diff --git a/js/graphAlgorithms/planarSeparatorAlgo.js b/js/graphAlgorithms/planarSeparatorAlgo.js
@@ -11,7 +11,7 @@ class PlanarSeparatorAlgo extends Algorithm {
         return fulfilled;
     }
 
-    async run(runGraph = graph) {
+    async run() {
         super.numSteps = "X";
 
         if (!this.preconditionsCheck()) {
@@ -29,18 +29,18 @@ class PlanarSeparatorAlgo extends Algorithm {
         await triangulationAlgo.run();
 
         await super.pause("Construct breadth-first search tree", "");
-        let startVertex = runGraph.vertices[0];
+        let startVertex = graph.vertices[0];
         if (!this.isSubAlgo) {
             let startVertexNr = window.prompt("Enter start vertex number", "0");
-            $.each(runGraph.vertices, function (_index, vertex) {
+            $.each(graph.vertices, function (_index, vertex) {
                 if (vertex.number == startVertexNr) {
                     startVertex = vertex;
                     return false;
                 }
             });
         }
         console.log('start vertex: ' + startVertex.print());
-        let bfsLayers = breadthFirstSearchTree(startVertex, runGraph);
+        let bfsLayers = breadthFirstSearchTree(startVertex, graph);
         let beforeTreeGraph = graph.getCopy();
         this.showBFSTree(bfsLayers);
 
@@ -56,7 +56,7 @@ class PlanarSeparatorAlgo extends Algorithm {
             layers[i] = vertexLayer;
         }
 
-        const n = runGraph.vertices.length;
+        const n = graph.vertices.length;
         await super.pause("Find layer μ",
             "Find layer μ so that all layers below together have <= n/2="
             + (n / 2) + " vertices, and together with μ have > n/2 vertices");

diff --git a/js/graphAlgorithms/weightMaxMatchingAlgo.js b/js/graphAlgorithms/weightMaxMatchingAlgo.js
@@ -104,9 +104,10 @@ class WeightMaxMatchingAlgo extends Algorithm {
 
         let weight = 0;
         maxWeightEdges.forEach(function (edge) {
-            weight += edge.weight;
+            weight += parseInt(edge.weight);
         });
         super.onFinished(true, "The weight max matching has weight " + weight);
+        return maxWeightEdges;
     }
 
     async divide(toDivideGraph) {

diff --git a/js/predefined.js b/js/predefined.js