interview-questions/graph/cyclic-graph.js

// Testing setup.
mocha.setup('bdd');
var expect = chai.expect;

// The implementation. 
function Obj() {
  this.links = [];
  this.isLinkedToSelf = false;
  this.visited_nodes = [];
};

Obj.prototype.linkTo = function(to) {
  if (this.links.indexOf(to) === -1) {
    if (this === to) {
        this.isLinkedToSelf = true;
    } else this.links.push(to);
  }
};

Obj.prototype.resetMem = function() {
  // clear visited nodes memory
  this.visited_nodes = []
  this.links.forEach((link) => link.visited_nodes = [])
}

Obj.prototype.isLinkedTo = function(to) {
  // is linked to self
  if (this === to && this.isLinkedToSelf) return true;
  // is linked to neighbours
  for (var i = 0; i < this.links.length; i++) {
    var link = this.links[i];
    // if a cycle is reached while searching, return false
    if (this.visited_nodes.includes(link)) {
      // reset memory
      break;
    }
    // still searching, then add current node to memory
    this.visited_nodes.push(link)
    // find the node, return true
    if (link === to || link.isLinkedTo(to)) {
      // reset memory
      this.resetMem();
      return true;
    }
  }
  this.resetMem();
  return false;
};

// The tests.
describe("Obj", function() {

  it("can link to itself", function() {
    var foo = new Obj;
    foo.linkTo(foo);
    expect(foo.isLinkedTo(foo)).to.equal(true);
  });

  it("does not link to itself", function() {
    var foo = new Obj;
    expect(foo.isLinkedTo(foo)).to.equal(false);
  });

  it("has unidirectional link to neighbour", function() {
    var foo = new Obj;
    var bar = new Obj;
    bar.linkTo(foo);
    expect(bar.isLinkedTo(foo)).to.equal(true);
    expect(foo.isLinkedTo(bar)).to.equal(false);
  });

  it("has neighbours with connections to themselves", function() {
    var foo = new Obj;
    var bar = new Obj;
    var baz = new Obj;

    // Connect the Objs to themselves.
    foo.linkTo(foo);
    bar.linkTo(bar);
    baz.linkTo(baz);

    // Connect baz => bar => foo.
    baz.linkTo(bar);
    bar.linkTo(foo);

    expect(baz.isLinkedTo(foo)).to.equal(true);
    expect(baz.isLinkedTo(bar)).to.equal(true);
    expect(bar.isLinkedTo(foo)).to.equal(true);
  });

  it("can be a cyclic graph", function() {
    var foo = new Obj;
    var bar = new Obj;
    var baz = new Obj;

    // Connect the nodes baz => bar => foo => baz.
    baz.linkTo(bar);
    bar.linkTo(foo);
    foo.linkTo(baz);

    expect(baz.isLinkedTo(foo)).to.equal(true);
    expect(baz.isLinkedTo(bar)).to.equal(true);
    expect(baz.isLinkedTo(baz)).to.equal(true);
  });

  it("can have neighbours in cyclic graph", function() {
    var foo = new Obj;
    var bar = new Obj;
    var baz = new Obj;

    // Connect the nodes baz => bar <=> foo.
    baz.linkTo(bar);
    bar.linkTo(foo);
    foo.linkTo(bar);

    expect(baz.isLinkedTo(foo)).to.equal(true);
    expect(baz.isLinkedTo(bar)).to.equal(true);
    expect(baz.isLinkedTo(baz)).to.equal(false);
  });


  it("can have a cycle of more than 2 Objs", function() {
    var foo = new Obj;
    var bar = new Obj;
    var baz = new Obj;
    var qux = new Obj;

    // Connect the nodes baz => bar => foo => qux => bar.
    baz.linkTo(bar);
    bar.linkTo(foo);
    foo.linkTo(qux);
    qux.linkTo(bar);

    expect(qux.isLinkedTo(baz)).to.equal(false);
    expect(baz.isLinkedTo(foo)).to.equal(true);
    expect(baz.isLinkedTo(bar)).to.equal(true);
    expect(baz.isLinkedTo(qux)).to.equal(true);
    expect(baz.isLinkedTo(baz)).to.equal(false);
  });

});

// Run the suite.
mocha.run();