| 1 |
- "use strict";var _interopRequireDefault=require("@babel/runtime/helpers/interopRequireDefault");var _defineProperty2=_interopRequireDefault(require("@babel/runtime/helpers/defineProperty"));var _toConsumableArray2=_interopRequireDefault(require("@babel/runtime/helpers/toConsumableArray"));var _classCallCheck2=_interopRequireDefault(require("@babel/runtime/helpers/classCallCheck"));var _createClass2=_interopRequireDefault(require("@babel/runtime/helpers/createClass"));var Link=function(){function Link(src,dest){(0,_classCallCheck2["default"])(this,Link);this.to=dest;this.from=src;}(0,_createClass2["default"])(Link,[{key:"import",value:function _import(data){for(var i in data){this[i]=data[i];}return this;}},{key:"export",value:function _export(){return this;}}]);return Link;}();var Node=function(){function Node(id){(0,_classCallCheck2["default"])(this,Node);this.id=id;}(0,_createClass2["default"])(Node,[{key:"import",value:function _import(data){for(var i in data){this[i]=data[i];}return this;}},{key:"export",value:function _export(){return this;}}]);return Node;}();var Graph=function(){function Graph(){(0,_classCallCheck2["default"])(this,Graph);this.nodes={};this.links={};}(0,_createClass2["default"])(Graph,[{key:"addNode",value:function 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();}},{key:"_emptyLink",value:function _emptyLink(){return{out:new Set(),"in":new Set()};}},{key:"addLink",value:function addLink(link){var dest=link.from;var to=link.to;if(!this.nodes[dest]||!this.nodes[to]){console.log(this.nodes,dest,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;}},{key:"removeLink",value:function removeLink(link){this.links[link.from].out["delete"](link);this.links[link.to]["in"]["delete"](link);}},{key:"removeNode",value:function removeNode(node){var _this=this;if(!this.nodes[node.id])return true;var outlinks=this.links[node.id].out;var inlinks=this.links[node.id]["in"];outlinks.forEach(function(link){return _this.removeLink(link);});inlinks.forEach(function(link){return _this.removeLink(link);});delete this.nodes[node.id];delete this.links[node.id];return node;}},{key:"linkNodes",value:function linkNodes(src,dest){return this.addLink(new Link(src,dest));}},{key:"has",value:function has(id){return!!this.nodes[id];}},{key:"getNode",value:function getNode(id){return this.nodes[id];}},{key:"getLinks",value:function getLinks(nodeid){return this.links[nodeid];}},{key:"DFSRecursive",value:function DFSRecursive(start,cb){if(!start)return null;var resultList=[];var visited={};var links=this.links;var found=false;var self=this;(function dfs(vertex){visited[vertex.id]=true;resultList.push(vertex);if(cb(vertex)===true){found=true;return resultList;}var _iteratorNormalCompletion=true;var _didIteratorError=false;var _iteratorError=undefined;try{for(var _iterator=links[vertex.id].out[typeof Symbol==="function"?Symbol.iterator:"@@iterator"](),_step;!(_iteratorNormalCompletion=(_step=_iterator.next()).done);_iteratorNormalCompletion=true){var link=_step.value;var destNode=self.getNode(link.to);if(!visited[destNode]){var res=dfs(destNode);if(found)return;resultList.pop();}}}catch(err){_didIteratorError=true;_iteratorError=err;}finally{try{if(!_iteratorNormalCompletion&&_iterator["return"]!=null){_iterator["return"]();}}finally{if(_didIteratorError){throw _iteratorError;}}}})(start);return resultList;}},{key:"DFS",value:function DFS(start,cb){var visited={};visited[start.id]=true;var stack=[start];var stackRes=[[]];var vertex;while(stack.length){vertex=stack.pop();var res=stackRes.pop();if(cb(vertex)===true){return[].concat((0,_toConsumableArray2["default"])(res),[vertex]);}var _iteratorNormalCompletion2=true;var _didIteratorError2=false;var _iteratorError2=undefined;try{for(var _iterator2=this.links[vertex.id].out[typeof Symbol==="function"?Symbol.iterator:"@@iterator"](),_step2;!(_iteratorNormalCompletion2=(_step2=_iterator2.next()).done);_iteratorNormalCompletion2=true){var link=_step2.value;var destNode=link.to;if(!visited[destNode]){visited[destNode]=true;stack.push(link.to);stackRes.push([].concat((0,_toConsumableArray2["default"])(res),[vertex]));}}}catch(err){_didIteratorError2=true;_iteratorError2=err;}finally{try{if(!_iteratorNormalCompletion2&&_iterator2["return"]!=null){_iterator2["return"]();}}finally{if(_didIteratorError2){throw _iteratorError2;}}}}return false;}},{key:"BFS",value:function BFS(start,cb){var visited=(0,_defineProperty2["default"])({},start.id,true);var stack=[start];var stackRes=[[]];var vertex;while(stack.length){vertex=stack.shift();var res=stackRes.shift();if(cb(vertex)===true){return[].concat((0,_toConsumableArray2["default"])(res),[vertex]);}var _iteratorNormalCompletion3=true;var _didIteratorError3=false;var _iteratorError3=undefined;try{for(var _iterator3=this.links[vertex.id].out[typeof Symbol==="function"?Symbol.iterator:"@@iterator"](),_step3;!(_iteratorNormalCompletion3=(_step3=_iterator3.next()).done);_iteratorNormalCompletion3=true){var link=_step3.value;if(!visited[link.to]){visited[link.to]=true;stack.push(link.to);stackRes.push([].concat((0,_toConsumableArray2["default"])(res),[vertex]));}}}catch(err){_didIteratorError3=true;_iteratorError3=err;}finally{try{if(!_iteratorNormalCompletion3&&_iterator3["return"]!=null){_iterator3["return"]();}}finally{if(_didIteratorError3){throw _iteratorError3;}}}}return false;}},{key:"export",value:function _export(){var nodes=this.nodes,links=this.links;var ln={};for(var i in links){ln[i]={out:Array.from(links[i].out).map(function(link){return link["export"]();}),"in":Array.from(links[i]["in"]).map(function(link){return link["export"]();})};}var nod={};for(var _i in nodes){nod[_i]=nodes[_i]["export"]();}return{nodes:nod,links:ln};}},{key:"_loadLink",value:function _loadLink(item){if(!this.cacheSet)this.cacheSet={};var 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);}}},{key:"import",value:function _import(data){var _this2=this;var nodeType=arguments.length>1&&arguments[1]!==undefined?arguments[1]:Node;var nodes=data.nodes,links=data.links;for(var i in nodes){this.nodes[i]=new nodeType()["import"](nodes[i]);}for(var _i2 in links){this.links[_i2]={out:new Set(links[_i2].out.map(function(item){return _this2._loadLink(item);})),"in":new Set(links[_i2]["in"].map(function(item){return _this2._loadLink(item);}))};}}},{key:"_debug",value:function _debug(){}}]);return Graph;}();module.exports={Node:Node,Link:Link,Graph:Graph};
|
