algorithms/lib/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(NodeType) {
    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()
    };
  } //double directionLink


  addDoubleLink(v1, v2) {
    let l1 = new Link(v1.id, v2.id);
    let l2 = new Link(v2.id, v1.id);
    this.nodes[v1.id].add(l1);
    this.nodes[v2.id].add(l2);
  }

  addOneWayLink(from, to) {
    let link = new Link(from.id, to.id);
    this.nodes[from.id].add(link);
  } //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);
  }

  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;
  }

  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.id);
          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;
  }

}

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
}; //console.log(tree.links)