export default interface Edge {
u: number;
v: number;
w: number;
}
import Edge from './edge';
class Graph {
nodeCount: number;
edgeList: Edge[];
constructor(nodeCount: number, edgeList: Edge[]) {
this.nodeCount = nodeCount;
this.edgeList = edgeList;
}
get adjecencyList(): number[][] {
const adj:number[][] = new Array(this.nodeCount);
for(let i=0; i<this.nodeCount; i++)
adj[i] = [];
for(let i=0; i<this.edgeList.length; i++) {
const { u, v, w } = this.edgeList[i];
adj[u].push(v);
}
return adj;
}
get adjecencyMatrix(): number[][] {
const mat: number[][] = new Array(this.nodeCount);
for(let i=0; i<this.nodeCount; i++) {
mat[i] = new Array(this.nodeCount).fill(0);
}
this.edgeList.forEach((edge) => {
const { u, v, w } = edge;
mat[u][v] = w;
});
return mat;
}
get indegree(): number[] {
const indegree: number[] = Array(this.nodeCount).fill(0);
this.edgeList.forEach((edge) => {
indegree[edge[0]]++;
});
return indegree;
}
get outdegree(): number[] {
const outdegree: number[] = Array(this.nodeCount).fill(0);
this.edgeList.forEach((edge) => {
outdegree[edge[1]]++;
});
return outdegree;
}
}
export default Graph;
import Graph from "../graph";
export default function dfs(graph: Graph, visited: boolean[], node: number): number[] {
if(graph.nodeCount == 0)
return [];
if(visited[node])
return undefined;
visited[node] = true;
const trav = [node]
graph.adjecencyList[node].forEach((neighbour) => {
const res = dfs(graph, visited, neighbour);
if(res !== undefined)
res.forEach((val) => trav.push(val));
});
return trav;
}
import Graph from "../graph";
export default function bfs(graph: Graph, startNode: number): number[] {
if(graph.nodeCount === 0)
return [];
const visited: boolean[] = Array(graph.nodeCount).fill(false);
const trav: number[] = [];
const q: number[] = [];
visited[startNode] = true;
q.push(startNode);
while(q.length > 0) {
const node = q.shift();
trav.push(node);
graph.adjecencyList[node].forEach((neighbour) => {
if(!visited[neighbour]) {
q.push(neighbour);
visited[neighbour] = true;
}
});
}
return trav;
}
import Graph from "../graph";
function _dfs(graph: Graph, startNode: number, visited: boolean[], stack: number[]) {
visited[startNode] = true;
graph.adjecencyList[startNode].forEach((neighbour) => {
if(!visited[neighbour])
_dfs(graph, neighbour, visited, stack);
});
stack.push(startNode);
}
export default function dfs(graph: Graph) {
if(graph.nodeCount === 0)
return [];
const visited: boolean[] = Array(graph.nodeCount).fill(false);
const stack: number[] = []
for(let i=0; i<graph.nodeCount; i++)
if(!visited[i])
_dfs(graph, i, visited, stack);
return stack.reverse();
}
import Graph from "../graph";
export default function bfs(graph: Graph) {
if(graph.nodeCount === 0)
return [];
const q: number[] = [];
const indegree = graph.indegree;
const visited = Array(graph.nodeCount).fill(false);
const toposort = [];
indegree.forEach((val, index) => {
if(val === 0)
q.push(index);
});
while(q.length > 0) {
const node = q.shift();
visited[node] = true;
toposort.push(node);
graph.adjecencyList[node].forEach((neighbour) => {
indegree[neighbour]--;
if(indegree[neighbour] === 0)
q.push(neighbour);
});
}
return toposort;
}
import Graph from '../src/graph';
describe('testing creation of empty graph', () => {
const graph = new Graph(0, []);
test('node count should be 0', () => {
expect(graph.nodeCount).toBe(0);
});
test('edge list should be empty', () => {
expect(graph.edgeList).toEqual([]);
});
test('adjecency list should be empty', () => {
expect(graph.adjecencyList).toEqual([]);
});
test('adjecency matrix should be empty', () => {
expect(graph.adjecencyMatrix).toEqual([]);
});
});
describe('testing creating of single node graph', () => {
const graph = new Graph(1, []);
test('node count should be 1', () => {
expect(graph.nodeCount).toBe(1);
});
test('edge list should be empty', () => {
expect(graph.edgeList).toEqual([]);
});
test('adjecency list have one element which is empty', () => {
expect(graph.adjecencyList).toEqual([[]]);
});
test('adjecency matrix should have one element which is [0]', () => {
expect(graph.adjecencyMatrix).toEqual([[0]]);
});
});
describe('testing creation of single node graph with self loop', () => {
const graph = new Graph(1, [{u: 0, v: 0, w: 1}]);
test('node count should be 1', () => {
expect(graph.nodeCount).toBe(1);
});
test('edge list should have {u: 0, v: 0, w: 1}', () => {
expect(graph.edgeList).toEqual([{u: 0, v: 0, w: 1}]);
});
test('adjecency list have one element which is [0]', () => {
expect(graph.adjecencyList).toEqual([[0]]);
});
test('adjecency matrix should have one element which is [1]', () => {
expect(graph.adjecencyMatrix).toEqual([[1]]);
});
});
describe('testing creation of two node graph with no edges', () => {
const graph = new Graph(2, []);
test('node count should be 2', () => {
expect(graph.nodeCount).toBe(2);
});
test('edge list should be empty', () => {
expect(graph.edgeList).toEqual([]);
});
test('adjecency list have two elements which are empty', () => {
expect(graph.adjecencyList).toEqual([[], []]);
});
test('adjecency matrix should have two elements which are [0, 0]', () => {
expect(graph.adjecencyMatrix).toEqual([[0, 0], [0, 0]]);
});
});
describe('testing creation of two node graph with one edge', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}]);
test('node count should be 2', () => {
expect(graph.nodeCount).toBe(2);
});
test('edge list should have {u: 0, v: 1, w: 1}', () => {
expect(graph.edgeList).toEqual([{u: 0, v: 1, w: 1}]);
});
test('adjecency list should be [[1], []]', () => {
expect(graph.adjecencyList).toEqual([[1], []]);
});
test('adjecency matrix should be [[0, 1], [0, 0]]', () => {
expect(graph.adjecencyMatrix).toEqual([[0, 1], [0, 0]]);
});
});
describe('testing creation of two node graph with two edges', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}]);
test('node count should be 2', () => {
expect(graph.nodeCount).toBe(2);
});
test('edge list should have {u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}', () => {
expect(graph.edgeList).toEqual([{u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}]);
});
test('adjecency list should be [[1], [0]]', () => {
expect(graph.adjecencyList).toEqual([[1], [0]]);
});
test('adjecency matrix should be [[0, 1], [1, 0]]', () => {
expect(graph.adjecencyMatrix).toEqual([[0, 1], [1, 0]]);
});
});
describe('testing creation of two node graph with three edges', () => {
const graph = new Graph(2, [{u: 0, v: 0, w: 1}, {u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}]);
test('node count should be 2', () => {
expect(graph.nodeCount).toBe(2);
});
test('edge list should have {u: 0, v: 1, w: 1}, {u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}', () => {
expect(graph.edgeList).toEqual([{u: 0, v: 0, w: 1}, {u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}]);
});
test('adjecency list should be [[0, 1], [0]]', () => {
expect(graph.adjecencyList).toEqual([[0, 1], [0]]);
});
test('adjecency matrix should be [[1, 1], [1, 0]]', () => {
expect(graph.adjecencyMatrix).toEqual([[1, 1], [1, 0]]);
});
});
describe('testing creation of two node graph with four edges', () => {
const graph = new Graph(2, [{u: 0, v: 0, w: 1}, {u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}, {u: 1, v: 1, w: 1}]);
test('node count should be 2', () => {
expect(graph.nodeCount).toBe(2);
});
test('edge list should have {u: 0, v: 1, w: 1}, {u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}, {u: 1, v: 1, w: 1}', () => {
expect(graph.edgeList).toEqual([{u: 0, v: 0, w: 1}, {u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}, {u: 1, v: 1, w: 1}]);
});
test('adjecency list should be [[0, 1], [0]]', () => {
expect(graph.adjecencyList).toEqual([[0, 1], [0, 1]]);
});
test('adjecency matrix should be [[1, 1], [1, 0]]', () => {
expect(graph.adjecencyMatrix).toEqual([[1, 1], [1, 1]]);
});
});
import Graph from "../src/graph";
import dfs from "../src/traversals/dfs";
describe('testing empty graph', () => {
const graph = new Graph(0, []);
test('dfs should be empty', () => {
expect(dfs(graph, Array(0).fill(false), 0)).toEqual([]);
});
});
describe('testing single node graph with no edges', () => {
const graph = new Graph(1, []);
test('dfs should be [0]', () => {
expect(dfs(graph, Array(1).fill(false), 0)).toEqual([0]);
});
});
describe('testing single node graph with self loop', () => {
const graph = new Graph(1, [{u: 0, v: 0, w: 1}]);
test('dfs should be [0]', () => {
expect(dfs(graph, Array(1).fill(false), 0)).toEqual([0]);
});
});
describe('testing two node graph with no edges', () => {
const graph = new Graph(2, []);
test('dfs starting from 0 should be [0]', () => {
expect(dfs(graph, Array(2).fill(false), 0)).toEqual([0]);
});
test('dfs starting from 1 should be [1]', () => {
expect(dfs(graph, Array(2).fill(false), 1)).toEqual([1]);
});
});
describe('testing two node graph with one edge', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}]);
test('dfs starting from 0 should be [0, 1]', () => {
expect(dfs(graph, Array(2).fill(false), 0)).toEqual([0, 1]);
});
test('dfs starting from 1 should be [1]', () => {
expect(dfs(graph, Array(2).fill(false), 1)).toEqual([1]);
});
});
describe('testing two node graph with two edges', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}]);
test('dfs starting from 0 should be [0, 1]', () => {
expect(dfs(graph, Array(2).fill(false), 0)).toEqual([0, 1]);
});
test('dfs starting from 1 should be [1, 0]', () => {
expect(dfs(graph, Array(2).fill(false), 1)).toEqual([1, 0]);
});
});
describe('testing four node graph with six edges', () => {
const graph = new Graph(4, [
{u: 0, v: 1, w: 1},
{u: 0, v: 2, w: 1},
{u: 1, v: 2, w: 1},
{u: 2, v: 0, w: 1},
{u: 2, v: 3, w: 1},
{u: 3, v: 3, w: 1},
]);
test('dfs starting from 0 should be [0, 1, 2, 3]', () => {
expect(dfs(graph, Array(4).fill(false), 0)).toEqual([0, 1, 2, 3]);
});
test('dfs starting from 1 should be [1, 2, 0, 3]', () => {
expect(dfs(graph, Array(4).fill(false), 1)).toEqual([1, 2, 0, 3]);
});
test('dfs starting from 2 should be [2, 0, 1, 3]', () => {
expect(dfs(graph, Array(4).fill(false), 2)).toEqual([2, 0, 1, 3]);
});
test('dfs starting from 3 should be [3]', () => {
expect(dfs(graph, Array(4).fill(false), 3)).toEqual([3]);
});
});
import Graph from "../src/graph"
import bfs from "../src/traversals/bfs";
describe('testing empty graph', () => {
const graph = new Graph(0, []);
test('bfs should be empty', () => {
expect(bfs(graph, 0)).toEqual([]);
});
});
describe('testing single node graph with no edges', () => {
const graph = new Graph(1, []);
test('bfs should be [0]', () => {
expect(bfs(graph, 0)).toEqual([0]);
});
});
describe('testing single node graph with self loop', () => {
const graph = new Graph(1, [{u: 0, v: 0, w: 1}]);
test('bfs should be [0]', () => {
expect(bfs(graph, 0)).toEqual([0]);
});
});
describe('testing two node graph with no edges', () => {
const graph = new Graph(2, []);
test('bfs starting from 0 should be [0]', () => {
expect(bfs(graph, 0)).toEqual([0]);
});
test('bfs starting from 1 should be [1]', () => {
expect(bfs(graph, 1)).toEqual([1]);
});
});
describe('testing two node graph with one edge', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}]);
test('bfs starting from 0 should be [0, 1]', () => {
expect(bfs(graph, 0)).toEqual([0, 1]);
});
test('bfs starting from 1 should be [1]', () => {
expect(bfs(graph, 1)).toEqual([1]);
});
});
describe('testing two node graph with two edges', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}, {u: 1, v: 0, w: 1}]);
test('bfs starting from 0 should be [0, 1]', () => {
expect(bfs(graph, 0)).toEqual([0, 1]);
});
test('bfs starting from 1 should be [1, 0]', () => {
expect(bfs(graph, 1)).toEqual([1, 0]);
});
});
describe('testing four node graph with six edges', () => {
const graph = new Graph(4, [
{u: 0, v: 1, w: 1},
{u: 0, v: 2, w: 1},
{u: 1, v: 2, w: 1},
{u: 2, v: 0, w: 1},
{u: 2, v: 3, w: 1},
{u: 3, v: 3, w: 1},
]);
test('dfs starting from 0 should be [0, 1, 2, 3]', () => {
expect(bfs(graph, 0)).toEqual([0, 1, 2, 3]);
});
test('dfs starting from 1 should be [1, 2, 0, 3]', () => {
expect(bfs(graph, 1)).toEqual([1, 2, 0, 3]);
});
test('dfs starting from 2 should be [2, 0, 1, 3]', () => {
expect(bfs(graph, 2)).toEqual([2, 0, 3, 1]);
});
test('dfs starting from 3 should be [3]', () => {
expect(bfs(graph, 3)).toEqual([3]);
});
});
import Graph from "../src/graph";
import dfs from "../src/toposort/dfs";
describe('testing empty graph', () => {
const graph = new Graph(0, []);
test('toposort dfs should be empty', () => {
expect(dfs(graph)).toEqual([]);
});
});
describe('testing single node graph with no edges', () => {
const graph = new Graph(1, []);
test('toposort dfs should be [0]', () => {
expect(dfs(graph)).toEqual([0]);
});
});
describe('testing two node graph with no edges', () => {
const graph = new Graph(2, []);
test('toposort dfs should be [1, 0]', () => {
expect(dfs(graph)).toEqual([1, 0]);
});
});
describe('testing two node graph with one edge', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}]);
test('toposort dfs should be [0, 1]', () => {
expect(dfs(graph)).toEqual([0, 1]);
});
});
describe('testing four node graph with five edges', () => {
const graph = new Graph(4, [
{u: 0, v: 1, w: 1},
{u: 0, v: 2, w: 1},
{u: 1, v: 2, w: 1},
{u: 2, v: 3, w: 1},
{u: 3, v: 3, w: 1},
]);
test('toposort dfs should be [0, 1, 2, 3]', () => {
expect(dfs(graph)).toEqual([0, 1, 2, 3]);
});
});
import Graph from "../src/graph";
import bfs from "../src/toposort/bfs";
describe('testing empty graph', () => {
const graph = new Graph(0, []);
test('toposort bfs should be empty', () => {
expect(bfs(graph)).toEqual([]);
});
});
describe('testing single node graph with no edges', () => {
const graph = new Graph(1, []);
test('toposort bfs should be [0]', () => {
expect(bfs(graph)).toEqual([0]);
});
});
describe('testing two node graph with no edges', () => {
const graph = new Graph(2, []);
test('toposort bfs should be [0, 1]', () => {
expect(bfs(graph)).toEqual([0, 1]);
});
});
describe('testing two node graph with one edge', () => {
const graph = new Graph(2, [{u: 0, v: 1, w: 1}]);
test('toposort bfs should be [0, 1]', () => {
expect(bfs(graph)).toEqual([0, 1]);
});
});
describe('testing four node graph with six edges', () => {
const graph = new Graph(4, [
{u: 0, v: 1, w: 1},
{u: 0, v: 2, w: 1},
{u: 1, v: 2, w: 1},
{u: 2, v: 0, w: 1},
{u: 2, v: 3, w: 1},
{u: 3, v: 3, w: 1},
]);
test('toposort bfs should be [0, 1, 2, 3]', () => {
expect(bfs(graph)).toEqual([0, 1, 2, 3]);
});
});