path growing algorithm (swiss)

1 files changed, 113 insertions, 0 deletions

diff --git a/greedymatching.js b/greedymatching.js
new file mode 100644
index 0000000..432680b
--- /dev/null
+++ b/greedymatching.js
@@ -0,0 +1,113 @@
+// https://sci-hub.hkvisa.net/10.1016/s0020-0190(02)00393-9
+
+/*
+Path Growing Algorithm (G = (V , E), w :E → R+)
+	M1 := ∅, M2 := ∅, i := 1
+	while E = ∅ do begin
+		choose x ∈ V of degree at least 1 arbitrarily
+		while x has a neighbor do begin
+			let {x,y} be the heaviest edge incident to x
+			add {x,y} to Mi
+			i := 3 − i
+			remove x from G
+			x := y
+		end
+	end
+	return max(w(M1), w(M2))
+*/
+
+function path_growing_algorithm(E) {
+	let V = {}
+	for (let edge of E) {
+		let [ x, y, w ] = edge
+		if (x in V)
+			V[x].push(edge)
+		else
+			V[x] = [ edge ]
+		if (y in V)
+			V[y].push(edge)
+		else
+			V[y] = [ edge ]
+	}
+
+	console.log("E0", E)
+	console.log("V0", V)
+
+	function find_best_edge(x) {
+		let max = x[0]
+		for (let i = 1; i < x.length; ++x)
+			if (x[i][2] > max[2])
+				max = x[i]
+		return max
+	}
+
+	function remove_vertex(x) {
+		E = E.filter(e => e[0] !== x && e[1] !== x)
+		for (let v in V)
+			V[v] = V[v].filter(e => e[0] !== x && e[1] !== x)
+		console.log("---", x)
+		console.log("Ex", E)
+		console.log("Vx", V)
+	}
+
+	let M1 = []
+	let M2 = []
+	let i = 1
+	while (E.length > 0) {
+		let x = E[0][0] // choose vertex of degree at least 1 -- TODO
+		console.log("start", x)
+		while (V[x].length > 0) {
+			let edge = find_best_edge(V[x])
+			if (i == 1)
+				M1.push(edge)
+			else
+				M2.push(edge)
+			i = 3 - i
+			remove_vertex(x)
+			if (edge[0] === x)
+				x = edge[1]
+			else
+				x = edge[0]
+			console.log("next", x)
+		}
+	}
+
+	let w1 = M1.reduce((w, e) => w + e[2], 0)
+	let w2 = M2.reduce((w, e) => w + e[2], 0)
+	console.log("M1", M1, w1)
+	console.log("M2", M2, w2)
+
+	return w1 >= w2 ? M1 : M2
+}
+
+//path_growing_algorithm([[1, 2, 10], [3, 2, 11]])
+//path_growing_algorithm([[1, 2, 5], [2, 3, 11], [3, 4, 5]])
+//path_growing_algorithm([[1, 2, 8], [1, 3, 9], [2, 3, 10], [3, 4, 7]])
+//path_growing_algorithm([[1, 2, 1], [1, 3, 1], [2, 3, 1], [3, 4, 1]])
+//path_growing_algorithm([[1, 2, 8], [1, 3, 9], [2, 3, 8], [3, 4, 7]])
+//path_growing_algorithm([[1, 2, 0], [1, 3, 1], [2, 3, 0], [3, 4, 0]])
+
+path_growing_algorithm([
+	[1, 2, 0], [1, 3, 1], [1, 4, 1], [1, 5, 1], //[1,6,1],
+	[2, 3, 1], [2, 4, 1], [2, 5, 1], //[2,6,1],
+	[3, 4, 1], [3, 5, 1], //[3,6,1],
+	[4, 5, 1], //[4, 6, 1],
+	//[5, 6, 1],
+])
+
+/*
+var blossom = require("./blossom.js")
+
+function unblossom(E) {
+	var P = blossom(E)
+	var M = []
+	for (let x = 0; x < P.length; ++x) {
+		let y = P[x]
+		if (x < y)
+			M.push([x, y])
+	}
+	return M
+}
+
+console.log(unblossom([[1, 2, 8], [1, 3, 9], [2, 3, 8], [3, 4, 7]]))
+*/