var G = {

  heap: [],

  primitives: [],

  cycles: [],

  vertices: [

    {index: 0, visited: false, edges: [0, 1], adj: [1,5], x: 50, y: 50}, 

    {index: 1, visited: false, edges: [0,2], adj: [0,2], x: 100, y: 30}, 

    {index: 2, visited: false, edges: [2, 3, 4, 5], adj: [1,3,4,5], x: 150, y: 30}, 

    {index: 3, visited: false, edges: [3, 6], adj: [2,4], x: 250, y: 10}, 

    {index: 4, visited: false, edges: [4, 6, 7], adj: [2,3,5], x: 200, y: 100},

    {index: 5, visited: false, edges: [1, 5, 7], adj: [0,2,4], x: 100, y: 100},

    {index: 6, visited: false, edges: [8], adj: [4], x: 150, y: 140}

  ],

  edges: [

    {index: 0, visited: false, isCycle: false, vertices: [0, 1]},

    {index: 1, visited: false, isCycle: false, vertices: [0, 5]},

    {index: 2, visited: false, isCycle: false, vertices: [1, 2]},

    {index: 3, visited: false, isCycle: false, vertices: [2, 3]},

    {index: 4, visited: false, isCycle: false, vertices: [2, 4]},

    {index: 5, visited: false, isCycle: false, vertices: [2, 5]},

    {index: 6, visited: false, isCycle: false, vertices: [3, 4]},

    {index: 7, visited: false, isCycle: false, vertices: [4, 5]},

    {index: 8, visited: false, isCycle: false, vertices: [4, 6]}

  ],

  draw: function(c) {

    c = c || ctx2;

    c.clearRect(0,0,300,150);

    for (var i=0; i<this.vertices.length; i++) {

      var x = this.vertices[i].x;

      var y = this.vertices[i].y;

      c.arc(x, y, 5, 0, 2 * Math.PI, false);

      c.fill();

    }

    for (var i=0; i<this.edges.length; i++) {

      var x1 = this.vertices[this.edges[i].vertices[0]].x;

      var y1 = this.vertices[this.edges[i].vertices[0]].y;

      var x2 = this.vertices[this.edges[i].vertices[1]].x;

      var y2 = this.vertices[this.edges[i].vertices[1]].y;

      c.beginPath();

      c.moveTo(x1, y1);

      c.lineTo(x2, y2);

      switch (this.edges[i].type) {

        case "back_edge":

          c.strokeStyle = "black";

        break;

        case "discovery":

          c.strokeStyle = "red";

        break;  

        default:

          c.strokeStyle = "green";

      }

      c.stroke();

      c.closePath();

    }

  },

};

​

function cloneObject(obj) {

    if (obj === null || typeof obj !== 'object') {

        return obj;

    }

    var temp = obj.constructor(); // give temp the original obj's constructor

    for (var key in obj) {

        temp[key] = cloneObject(obj[key]);

    }

    return temp;

}

​

var canvas = document.getElementById("board");

var ctx = canvas.getContext("2d");

var canvas2 = document.getElementById("board2");

var ctx2 = canvas2.getContext("2d");

​

function MinimalCycleBasis() {

  function getClockwiseMost(vprev,vcurr){

    var dcurr;

    if (vprev !== null) {

      dcurr = {x:vprev.x - vcurr.x, y:vprev.y - vcurr.y};

    } 

    else {

      dcurr = {x: 0, y: -1};

    }

    var vnext = this.getVnext(vcurr,vprev);

    var dnext = {x:vcurr.x - vnext.x, y:vcurr.y - vnext.y};

    var vcurrIsConvex = this.dotPerp(dnext,dcurr) > 0 ? true : false;

    for (var i=0; i<vcurr.adj.length; i++) {

      var vadj = this.getVertex(vcurr.adj[i]);

      var dadj = {x:vadj.x - vcurr.x, y:vadj.y - vcurr.y};

      if(vcurrIsConvex) {

        if(this.dotPerp(dcurr,dadj) < 0 || this.dotPerp(dnext,dadj) < 0) {

          vnext = vadj;

          dnext = dadj;

          vcurrIsConvex = this.dotPerp(dnext,dcurr) > 0 ? true : false;

        }

      } else {

        if(this.dotPerp(dcurr,dadj) < 0 && this.dotPerp(dnext,dadj) < 0) {

          vnext = vadj;

          dnext = dadj;

          vcurrIsConvex = this.dotPerp(dnext,dcurr) > 0 ? true : fale;

        }

      }

    }

    return vnext;

  }

  function getCounterClockwiseMost(vprev,vcurr) {

    var dcurr = {x:vprev.x - vcurr.x, y:vprev.y - vcurr.y};

    var vnext = this.getVnext(vcurr,vprev);

    var dnext = {x:vcurr.x - vnext.x, y:vcurr.y - vnext.y};

    var vcurrIsConvex = this.dotPerp(dnext,dcurr) > 0 ? true : false;

    for (var i=0; i<vcurr.adj.length; i++) {

      var vadj = this.getVertex(vcurr.adj[i]);

      var dadj = {x:vadj.x - vcurr.x, y:vadj.y - vcurr.y};

      if(vcurrIsConvex) {

        if(this.dotPerp(dcurr,dadj) > 0 && this.dotPerp(dnext,dadj) > 0) {

          vnext = vadj;

          dnext = dadj;

          vcurrIsConvex = this.dotPerp(dnext,dcurr) > 0 ? true : false;

        }

      } else {

        if(this.dotPerp(dcurr,dadj) > 0 || this.dotPerp(dnext,dadj) > 0) {

          vnext = vadj;

          dnext = dadj;

          vcurrIsConvex = this.dotPerp(dnext,dcurr) > 0 ? true : false;

        }

      }

    }

    return vnext;

  }

  function getVertex(index) {

    var v = null;

    this.vertices.forEach(function(el){

      if(el.index === index) {

        v = el;

      }

    });

    return v;

  }

  function getVnext(vcurr,vprev) {

    for (var i=0; i<vcurr.adj.length; i++) {

      if (this.getVertex(vcurr.adj[i]) !== vprev) {

        return this.getVertex(vcurr.adj[i]);

      }

    }

  }

  function getEdge: function(v0,v1) {

    for (var i=0; i<this.edges.length; i++) {

      if((this.edges[i].vertices[0] === v0.index && this.edges[i].vertices[1] === v1.index) || 

         (this.edges[i].vertices[0] === v1.index && this.edges[i].vertices[1] === v0.index)) {

        return this.edges[i];

      }

    }

  }

  function isCycleEdge(v0,v1) {

    var edge = this.getEdge(v0,v1);

    if(edge && edge.isCycle) 

      return true; 

    else 

      return false;

  }

  //removes edge from edges array and adjacent 

  //vertices from adjacents list in the pair of vertices making that edge

  function removeEdge(v0,v1) {

    var edge = this.getEdge(v0,v1);

    this.edges = this.edges.filter(function(el) { return el !== edge; });

    v0.adj.splice(v0.adj.indexOf(v1.index),1);

    v1.adj.splice(v1.adj.indexOf(v0.index),1);

  }

  function dotPerp(a,b) {

    return a.x*b.y - a.y*b.x;

  }

  function extractPrimitives() {

    this.heap = this.vertices.slice();

    // lexicographical sort

    this.heap.sort(function(a,b) {

    if(a.x > b.x) 

        return 1;

    else if(b.x > a.x)

        return -1;

    else

        if(a.y > b.y)

            return 1;

        else if(b.y > a.y)

            return -1;

        else

            return 0;

    });

    while(this.heap.length>0) {

      var v0 = this.heap[0];

      if (v0.adj.length === 0) {

        this.extractIsolatedVertex(v0);

      } 

      else if (v0.adj.length === 1) {

        var v1 = this.getVertex(v0.adj[0]); 

        this.extractFilament(v0,v1);

      } 

      else {

        this.extractPrimitive(v0); // filament or minimal cycle

      }

    }

    return cycles;

  }

  function extractIsolatedVertex(v0) {

    var primitive = [];

    primitive.push(v0);

    this.heap = this.heap.filter(function(el) { return el !== v0; });

    this.vertices = this.vertices.filter(function(el) {return el !== v0; });

    this.primitives.push(primitive);

  }

  function extractFilament(v0,v1) {

    var edge;

    if(this.isCycleEdge(v0,v1)) {

      if(v0.adj.length >= 3) {

        this.removeEdge(v0,v1);

        v0 = v1;

        if(v0.adj.length === 1) {

          v1 = this.getVertex(v0.adj[0]);

        }

      }

      while(v0.adj.length === 1) {

        v1 = this.getVertex(v0.adj[0]);

        if(this.isCycleEdge(v0,v1)) {

          this.heap = this.heap.filter(function(el) { return el !== v0; });

          this.removeEdge(v0,v1);

          this.vertices = this.vertices.filter(function(el) {return el !== v0;});

          v0 = v1;

        }

        else {

          break;

        }

      }

      if (v0.numAdjacent === 0) {

        this.heap = this.heap.filter(function(el) { return el !== v0; });

        this.vertices = this.vertices.filter(function(el) {return el !== v0;});

      }

    }

    else {

      var primitive = [];

      if(v0.adj.length >= 3) {

        primitive.push(v0);

        this.removeEdge(v0,v1);

        v0 = v1;

        if(v0.adj.length === 1) {

          v1 = this.getVertex(v0.adj[0]);

        }

      }

      while (v0.adj.length === 1) {

        primitive.push(v0);

        v1 = this.getVertex(v0.adj[0]);

        this.heap = this.heap.filter(function(el) { return el !== v0; });

        this.removeEdge(v0,v1);

        this.vertices = this.vertices.filter(function(el) {return el !== v0;});

        v0 = v1;

      }

      primitive.push(v0);

      if(v0.adj.length === 0) {

        this.heap = this.heap.filter(function(el) { return el !== v0; });

        edge = this.removeEdge(v0,v1);

        this.vertices = this.vertices.filter(function(el) {return el !== v0;});

      }

      this.primitives.push(primitive);

    }

  }

  function extractPrimitive(v0) {

    var visited = [];

    var sequence = [], primitive = {};

    sequence.push(v0);

    var v1 = this.getClockwiseMost(null,v0);

    var vprev = v0;

    var vcurr = v1;

    while (vcurr !== null && vcurr !== v0 && visited.indexOf(vcurr) === -1) {

      sequence.push(vcurr);

      visited.push(vcurr);

      var vnext = this.getCounterClockwiseMost(vprev,vcurr);

      vprev = vcurr;

      vcurr = vnext;

    }

    if (vcurr === null) {

      // Filament found, not necessarily rooted at v0.

      this.extractFilament(v0,this.getVertex(v0.adj[0]));

    } 

    else if (vcurr === v0) {

      //Minimal cycle found.

      primitive.vertices = sequence.slice();

      sequence.push(vcurr);

      for (var i=0; i<sequence.length-1; i++) {

        var edge = this.getEdge(sequence[i],sequence[i+1]);

        edge.isCycle = true;

      }

      this.removeEdge(v0,v1);

      this.cycles.push(primitive);

      if(v0.adj.length === 1) {

        //remove the filament rooted at v0.

        this.extractFilament(v0,this.getVertex(v0.adj[0]));

      }

      if(v1.adj.length === 1) {

        //remove the filament rooted at v1.

        this.extractFilament(v1,this.getVertex(v1.adj[0]));

      }

    }

    else { //vcurr was visited earlier

      // A cycle has been found, but is not guaranteed to be a minimal

      // cycle. This implies v0 is part of a filament. Locate the

      // starting point for the filament by traversing from v0 away

      // from the initial v1.

      while (v0.adj.length === 2) {

        if (this.getVertex(v0.adj[0]) !== v1) {

          v1 = v0;

          v0 = this.getVertex(v0.adj[0]);

        }

        else {

          v1 = v0;

          v0 = this.getVertex(v0.adj[1]);

        }

      }

      this.extractFilament(v0,v1);

    }

  }

}