Bron-Kerbosch-algorithm

index.js

#!/usr/bin/node

// - A group is an array of player names who have recently played with each other.
// - Each member in a group must have played with each other member.
// - Each group must have at least two names, and duplicate groups must be discarded.
// - If a group is entirely contained in a larger group, it must be discarded in favor of the larger group.

/**
 * A brutal force solution to this problem is as follows
 * 1.find all of the subset of the given players list with minimum size of 2
 * 2.discard subsets contains players who didn't play with all others players in this subset
 * 3.discard subsets that is contained by another bigger subset
 *
 * Let `N` be the # players in the given list, if we use backtracking to find all subsets,
 * the time complexity is O(N * 2^N), since there are 2^N - N - 1 total subsets, (exclude size 1 and empty)
 * and space complexity is O(N), which is used to maintaining the `N` current subset
 *
 * ---
 *
 * Use players as vertices, and edges if two players played with each other
 * "Each member in a group must have played with each other member" implies a completed graph
 *
 * My solution is as follows
 *
 * 1.remove the players in `recentlyPlayedWith` what is not in the given user list
 * 2.build an undirected graph, where players as vertices, there is a edge if two players played with each other
 * 3.return all of the maximal cliques in such graph, since clique problem is a known NP-complete problem,
 * there is no known polynomial solution, the Bron–Kerbosch algorithm with pivoting takes O(3^{n/3})
 */

// JavaScript only!
function groupPlayers(players) {
	// return a 2D array
	const g = adjacencyList(players);

	const r = new Set();
	const p = new Set(g.keys());
	const x = new Set();
	const cliques = [];

	bk_pivot(g, r, p, x, cliques);

	return cliques;
}

/**
 * transform given list to Adjacency List graph
 * @param {Array} data
 * @returns
 */
function adjacencyList(data) {
	const graph = new Map();
	const all_players = new Set();

	for (let i in data) {
		// keep a players set
		all_players.add(data[i].name);
		// hashmap of sets
		graph.set(data[i].name, new Set(data[i].recentlyPlayedWith));
	}

	for (let i in data) {
		// discard players who is not in the players list
		graph.set(
			data[i].name,
			intersection(graph.get(data[i].name), all_players)
		);
	}

	return graph;
}

/**
 *
 * @param {Array} graph
 * @param {Set} r
 * @param {Set} p
 * @param {Set} x
 * @param {Array} cliques
 */
function bk_pivot(graph, r, p, x, cliques) {
	// it finds the maximal cliques that include all of the vertices in R,
	// some of the vertices in P, and none of the vertices in X

	// In each call to the algorithm,
	// P and X are disjoint sets whose union consists of those vertices that form cliques when added to R.
	if (p.size == 0 && x.size == 0) {
		// report R as a maximal clique
		// return a 2D array
		if (r.size > 1) {
			cli = Array.from(r);
			cli.sort();
			cliques.push(cli);
		}
	} else {
		// without pivoting is inefficient in the case of graphs with many non-maximal cliques:
		// it makes a recursive call for every clique, maximal or not.
		// choose a pivot vertex u in P ⋃ X
		u = union(p, x).entries().next().value[0];

		// for vertices in P \ N(u)
		for (let v of difference(p, graph.get(u))) {
			neighbors = graph.get(v);
			// recursive backtracking
			// R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)
			bk_pivot(
				graph,
				union(r, new Set([v])),
				intersection(p, neighbors),
				intersection(x, neighbors),
				cliques
			);
			// P := P \ {v}
			p.delete(v);
			// X := X ⋃ {v}
			x.add(v);
		}
	}
}

/**
 * find intersction of two sets
 * @param {Set} setA
 * @param {Set} setB
 * @returns {Set}
 */
function intersection(setA, setB) {
	let _intersection = new Set();
	for (let elem of setB) {
		if (setA.has(elem)) {
			_intersection.add(elem);
		}
	}
	return _intersection;
}

/**
 * union of two sets
 * @param {Set} setA
 * @param {Set} setB
 * @returns {Set}
 */
function union(setA, setB) {
	let _union = new Set(setA);
	for (let elem of setB) {
		_union.add(elem);
	}
	return _union;
}

/**
 * items in A but not in B
 * @param {Set} setA
 * @param {Set} setB
 * @returns {Set}
 */
function difference(setA, setB) {
	let _difference = new Set(setA);
	for (let elem of setB) {
		_difference.delete(elem);
	}
	return _difference;
}

/*************** algorithm correctness proof and testing ***************/

/**
 * True if `set` contains `subset`, otherwise False
 * @param {Set} set
 * @param {Set} subset
 * @returns {boolean}
 */
function isSuperset(set, subset) {
	for (let elem of subset) {
		if (!set.has(elem)) {
			return false;
		}
	}
	return true;
}

function randomArraySlice(arr) {
	const rand1 = Math.floor(Math.random() * arr.length);
	const rand2 = Math.floor(Math.random() * arr.length);

	return rand2 > rand1 ? arr.slice(rand1, rand2) : arr.slice(rand2, rand1);
}

/**
 * tests
 * @param {int} n
 * @param {Array} test_case
 */
function Tests(n, test_case) {
	if (test_case) {
		this.input = test_case;

		this.players_set = new Set();
		this.input_dict = {};

		for (let i = 0; i < this.input.length; i++) {
			this.input_dict[this.input[i].name] = new Set(
				this.input[i].recentlyPlayedWith
			);

			this.players_set.add(this.input[i].name);
		}

		this.players_arr = Array.from(this.players_set);

		// console.log(this.input_dict, this.players_arr);
	} else {
		this.gen_random(n);
	}
}

/**
 * generate random test case of size ~0.8*n
 * @param {int} n
 */
Tests.prototype.gen_random = function (n) {
	this.players_set = new Set();
	extra_players_set = new Set();

	for (let i = 0; i < n; i++) {
		let rand = Math.random();

		let name = rand.toString(36).slice(2);

		if (rand < 0.8) {
			if (!extra_players_set.has(name)) {
				this.players_set.add(name);
			}
		} else {
			if (!this.players_set.has(name)) {
				extra_players_set.add(name);
			}
		}
	}

	console.log(
		"Gnerated " +
			this.players_set.size +
			" players, and " +
			extra_players_set.size +
			" extra players"
	);

	dict = {};
	// `dict` like {name: set(recentlyPlayedWith)}
	this.players_set.forEach((v) => {
		dict[v] = new Set();
	});

	this.players_arr = Array.from(this.players_set);
	extra_players_arr = Array.from(extra_players_set);

	for (let k in dict) {
		played_with = new Set(randomArraySlice(this.players_arr));

		dict[k] = union(dict[k], played_with);

		played_with.forEach((v) => {
			dict[v].add(k);
		});
	}

	this.input = [];

	for (let k in dict) {
		// player himself not in `recentlyPlayedWith`
		if (dict[k].has(k)) {
			dict[k].delete(k);
		}
		// transform to the given format
		// add some extra players
		this.input.push({
			name: k,
			recentlyPlayedWith: Array.from(dict[k]).concat(
				randomArraySlice(extra_players_arr)
			),
		});
	}

	this.input_dict = {};

	for (let v of this.input) {
		this.input_dict[v.name] = new Set(v.recentlyPlayedWith);
	}

	console.log("Gnerated input data of size " + this.input.length);
	// console.log(this.input);
};

/**
 * get all possible subsets of arr of minimum size 2
 * @param {*} subarr
 * @param {*} ind
 */
Tests.prototype.bt = function (subarr, ind) {
	if (subarr.length > 1) {
		this.all_subsets.push(subarr);
	}

	for (let i = ind; i < this.players_arr.length; i++) {
		this.bt([...subarr, this.players_arr[i]], i + 1);
	}
};

/**
 * check if Each member in a group must have played with each other member.
 * @param {Array} arr
 * @returns {boolean}
 */
Tests.prototype.isSetValid = function (arr) {
	for (let i = 0; i < arr.length; i++) {
		for (let j = i + 1; j < arr.length; j++) {
			// console.log(arr[i], arr[j], this.input_dict[arr[i]]);

			if (!this.input_dict[arr[i]].has(arr[j])) {
				return false;
			}
		}
	}

	return true;
};

/**
 * brutal force solution
 * @returns {Array}
 */
Tests.prototype.brutal = function () {
	this.all_subsets = [];

	dup_sets = [];
	// find all possible subsets
	this.bt([], 0);
	// console.log("input_dict", this.input_dict);
	for (let s of this.all_subsets) {
		if (this.isSetValid(s)) {
			dup_sets.push(s.sort());
		}
	}

	valid_sets = new Set();
	for (let i = 0; i < dup_sets.length; i++) {
		let has_super = false;

		for (let j = 0; j < dup_sets.length; j++) {
			if (
				i != j &&
				isSuperset(new Set(dup_sets[j]), new Set(dup_sets[i]))
			) {
				has_super = true;
				break;
			}
		}

		if (!has_super) {
			valid_sets.add(dup_sets[i]);
		}
	}

	return Array.from(valid_sets);
};

/**
 * run tests
 */
Tests.prototype.run = function () {
	// console.log("input: ", this.input);

	bru = this.brutal();
	true_sets = [];

	for (let v of bru) {
		true_sets.push(v.join(" "));
	}

	true_sets.sort();
	// console.log("true_sets: ", true_sets);

	test = groupPlayers(this.input);
	test_sets = [];

	for (let v of test) {
		v.sort();
		test_sets.push(v.join(" "));
	}
	test_sets.sort();
	// console.log("test_sets: ", test_sets);

	if (true_sets.length != test_sets.length) {
		throw ("Test failed!!!!", this.input, true_sets, test_sets);
	}

	for (let i = 0; i < true_sets.length; i++) {
		if (true_sets[i] !== test_sets[i]) {
			throw ("Test failed!!!!", this.input, true_sets, test_sets);
		}
	}

	console.log("Test case passed, size:" + this.input.length);
};

/**
 * monitor algorithm performance
 */
Tests.prototype.performance = function () {
	// console.log("input: ", this.input);

	const start = Date.now();
	groupPlayers(this.input);
	const end = Date.now();

	console.log(
		"Finished size:" + this.input.length,
		", time spent: " + (end - start).toString() + "ms"
	);
};

round = 5;
testsize = 21;
performancesize = 100;

// compare solution and brutal force results
// brutal force start to get slow after 20
for (let i = 0; i < round; i++) {
	for (let j = 2; j < testsize; j++) {
		tt = new Tests(j);
		tt.run();
	}
}

// review performance, approx 80 players and 20 extra players
for (let j = 20; j < performancesize; j++) {
	tt = new Tests(j);
	tt.performance();
}

console.log(
	"Awnser of example is: ",
	groupPlayers([
		{
			name: "Adil",
			recentlyPlayedWith: [
				"Ben",
				"Andy",
				"Rio",
				"Nader",
				"Giuliano",
				"Walter",
				"Dali",
			],
		},
		{
			name: "Andy",
			recentlyPlayedWith: ["Adil", "Walter", "Chris", "Dan", "Ben"],
		},
		{
			name: "Dan",
			recentlyPlayedWith: [
				"Andy",
				"Rio",
				"Dennis",
				"John",
				"Bernard",
				"Ben",
			],
		},
		{
			name: "Ben",
			recentlyPlayedWith: [
				"Nader",
				"Dali",
				"Dan",
				"Carter",
				"Bruno",
				"Andy",
				"Adil",
			],
		},
		{ name: "Nader", recentlyPlayedWith: ["Adil", "Ben", "Arthur"] },
	])
);