TrapiLib/lib/helpers/graph.js

//Link is like an Edge in the graph/tree structure
class Link {
	constructor(src, dest) {
		this.to = dest;
	    this.from = src;
	}

	import(data) {
		for(var i in data) {
			this[i] = data[i];
		}
		return this;
	}

	export() {
		return this;
	}
}

//Node--> Vertex
class Node {
	constructor(id){
  		this.id = id;
  	}

  	import(data) {
  		for(var i in data) {
  			this[i] = data[i];
  		}
  		return this;
  	}

  	export() {
  		return this;
  	}
}


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 dest = link.from;
		let to = link.to;

		if(!this.nodes[dest] || !this.nodes[to]){
			throw new Error("One of the Nodes Doesnt Exist");
		}
		if(this.links[dest].out.has(link) || this.links[to].in.has(link)){
			throw new Error("Link already exists");
		}
		this.links[dest].out.add(link);
		this.links[to].in.add(link);
		return link;
	}

	removeLink(link){
		this.links[link.from].out.delete(link);
		this.links[link.to].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){ // needs correction because of link change to id
		if(!start) return null;
		var resultList = [];
		var visited = {};
		var links = this.links;
		var found = false;
		let self = this;
		(function dfs(vertex){
			visited[vertex.id] = true;
			resultList.push(vertex);
			if( cb(vertex) === true ) {
				found = true;
				return resultList;
			}
			for(var link of links[vertex.id].out) {
				let destNode = self.getNode(link.to);
				if(!visited[destNode]){
					let res = dfs(destNode);
					if(found)return;
					resultList.pop();
				}
			} 
		})(start)
		return resultList;
	}

	//depth first 
	DFS(start,cb){ // needs correction because of link change to id
		var visited = {};
		visited[start.id] = true;
		var stack = [start];
		var stackRes = [[]];
		let vertex;
		while(stack.length){
			vertex  = stack.pop();
			let res = stackRes.pop();
			if( cb(vertex) === true ) {
				return [...res, vertex];
			}
			for( var link of this.links[vertex.id].out ) {
				let destNode = link.to;
				if(!visited[destNode]){
					visited[destNode] = true;
					stack.push(link.to);
					stackRes.push([...res, vertex]);
				}
			}
			// resultList.pop();
		}
		return false;
	}


	BFS(start,cb){ // needs correction because of link change to id
		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]){
					visited[link.to] = true;
					stack.push(link.to);
					stackRes.push([...res, vertex]);
				}
			}
		}
		return false;
	}


	export() {
		let { nodes, links } = this;

		// export Links care with SETS
		let ln = {};
		for(let i in links) {
			ln[i] = {
				out: Array.from(links[i].out).map(link => link.export()),
				in : Array.from(links[i].in ).map(link => link.export())
			}
		}
		// export nodes
		let nod = {};
		for(let i in nodes) {
			nod[i] = nodes[i].export()
		}

		return {
			nodes: nod,
			links: ln
		};
	}

	_loadLink(item) {
		if(!this.cacheSet) this.cacheSet = {};

		let data = this.cacheSet["from" + item.from + "to" + item.to];
		if(data) {
			return data;
		} else {
			return this.cacheSet["from" + item.from + "to" + item.to] = new Link().import(item);
		}
		
	}

	import(data, nodeType = Node) {
		let { nodes, links } = data;

		for (let i in nodes) {
			this.nodes[i] = new nodeType().import(nodes[i]);
		}


		for (let i in links) {
			this.links[i] = {
				out: new Set(links[i].out.map(item => this._loadLink(item))),
				in : new Set(links[i].in.map(item => this._loadLink(item)))
			}
		}
	}
	_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
};