Categories
Javascript

How to Implement a Graph Class in Javascript

The following code snippet shows an implementation of a Graph in JS

class Graph {
	verticies = {};

	add(vertix, adjacencies) {
		if (!this.verticies[vertix]) this.verticies[vertix] = new Set();

		for (const adjacent of adjacencies) {
			if (vertix == adjacent) continue;
			if (!this.verticies[adjacent]) this.verticies[adjacent] = new Set();
			this.verticies[vertix].add(adjacent);
			this.verticies[adjacent].add(vertix);
		}
	}
}
Categories
Algorithms Javascript

Union Find in JS

Union Find is an algorithm that can be used to find disjoint sets, and cycles in a graph. Below are two implementations of this algorithm.

  1. Un-optimized
class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false; // Cycle
		this.root[u] = v;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}

2. Optimized (Ranked)

class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
		this.rank = new Array(n).fill(1);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false;
		if (this.rank[u] > this.rank[v]) {
			this.root[v] = u;
			this.rank[u] += this.rank[v];
		} else {
			this.root[u] = v;
			this.rank[v] += this.rank[u];
		}
		return true;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}

Categories
Javascript

4 Ways To Check If A Variable Is A Number In JS + Comparison

Comparison Table

Case/^\d+$/
.test(variable)
/^[0-9]+$/
.test(variable)
!isNaN
(variable)
typeof
variable
“123”TrueTrueTruestring
” “FalseFalseTruestring
123TrueTrueTruenumber
“1.23”FalseFalseTruestring
1.23FalseFalseTruenumber
“abc”FalseFalseFalsestring
Comparison of Different Methods to Find Out if a Variable Is a Number in JS