TrapiLib/lib/helpers/graph.js

//Link is like an Edge in the graph/tree structure
class Link {
  constructor(from, to) {
    this.to = to;
    this.from = from;
  }
}
//Node--> Vertex
class Node {
	constructor(id){
  	this.id = id;
  } 
}


class Graph{
	constructor(){
		this.nodes = {};
		this.links = {}
	}

	addNode(node){
		if(this.nodes[node.id]){
			throw new Error("Node already exists with ID "+node.id);
		}
		this.nodes[node.id] = node;
		if(!this.links[node.id]) this.links[node.id] = this._emptyLink();
	}
	_emptyLink() {
	    return {
	      	out: new Set(),
	      	in: new Set()
	    };
	}
	
	//we give the link we 
	addLink(link){
		let from = link.from;
		let to = link.to;
		if(!this.nodes[from.id] || !this.nodes[to.id]){
			throw new Error("One of the Nodes Doesnt Exist");
		}
		if(this.links[from.id].out.has(link) || this.links[to.id].in.has(link)){
			throw new Error("Link already exists");
		}
		this.links[from.id].out.add(link);
		this.links[to.id].in.add(link);
		return link;
	}

	removeLink(link){
		this.links[link.from.id].out.delete(link);
		this.links[link.to.id].in.delete(link);
	}

	removeNode(node){
		if(!this.nodes[node.id]) return true;
		let outlinks = this.links[node.id].out
		let inlinks = this.links[node.id].in;
		outlinks.forEach( link => this.removeLink(link))
		inlinks.forEach( link => this.removeLink(link))
		delete this.nodes[node.id];
		delete this.links[node.id];
		return node;
	}

	linkNodes(src, dest) {
		return this.addLink(new Link(src, dest));
	}

	has(id) {
		return !!this.nodes[id];
	}
	getNode(id) {
		return this.nodes[id];
	}
	getLinks(nodeid) {
		return this.links[nodeid];
	}

	DFSRecursive(start, cb){
		if(!start) return null;
		var resultList = [];
		var visited = {};
		var links = this.links;
		var found = false;
		(function dfs(vertex){
			visited[vertex.id] = true;
			resultList.push(vertex);
			//console.log(resultList)
			if( cb(vertex) === true ) {
				//console.log("####true")
				found = true;
				return resultList;
			}
			for(var link of links[vertex.id].out) {
				if(!visited[link.to.id]){
					let res = dfs(link.to);
					if(found)return;
					resultList.pop();
				}
			} 
		})(start)
		return resultList;
	}

	//depth first 
	DFS(start,cb){
		var visited = {};
		visited[start.id] = true;
		var stack = [start];
		var stackRes = [[]];
		let vertex;
		while(stack.length){
			vertex  = stack.pop();
			let res = stackRes.pop();
			// console.log(res);
			if( cb(vertex) === true ) {
				return [...res, vertex];
			} 

			for( var link of this.links[vertex.id].out ) {
				if(!visited[link.to.id]){
					visited[link.to.id] = true;
					stack.push(link.to);
					stackRes.push([...res, vertex]);
				}
			}
			// resultList.pop();
		}
		return false;
	}


	BFS(start,cb){
		var visited = {[start.id]:true}
		var stack = [start];
		var stackRes = [[]];
		let vertex;
		while(stack.length){
			vertex  = stack.shift();
			let res = stackRes.shift();
			if( cb(vertex) === true ) {
				return [...res, vertex];
			} 

			for( var link of this.links[vertex.id].out ) {
				if(!visited[link.to.id]){
					visited[link.to.id] = true;
					stack.push(link.to);
					stackRes.push([...res, vertex]);
				}
			}
		}
		return false;
	}



	_debug(){

	}

}



// var graph = new Graph(Node);
// var A = new Node("A");
// var B = new Node('B');
// var C = new Node('C');
// var D = new Node('D');
// var E = new Node('E');
// var F = new Node("F");

// var AB = new Link(A,B);
// var AD = new Link(A,D);
// var BC = new Link(B,C);
// var CF = new Link(C,F);
// var DB = new Link(D,B);
// var DE = new Link(D,E);
// var EF = new Link(E,F);
// var FE = new Link(F,E);
/*
graph.addNode(A);
graph.addNode(B);
graph.addNode(C);
graph.addNode(D);
graph.addNode(E);
graph.addNode(F);
graph.addLink(AB);
graph.addLink(AD);
graph.addLink(BC);
graph.addLink(CF);
graph.addLink(DB);
graph.addLink(DE);
graph.addLink(EF);
graph.addLink(FE);
*/

//let recur = graph.DFS(A,(node) => node.id === E.id);
//let bfs = graph.BFS(A,(node) => node.id === C.id);


module.exports = {
	Node,
	Link,
	Graph
};