( function(){

  var nodeTotal = 50;
  var edgeTotal = nodeTotal * 1.25;

  var graph = {
    nodes: [],
    edges: [],
    adjacent: []
  };

  graph.nodes = d3.range(nodeTotal).map(function(i) {
    var node = { id : i };
    return node;
  });

  graph.edges = d3.range(edgeTotal).map(function(i) {
    var source = i < nodeTotal ? i : Math.floor(Math.random() * nodeTotal);
    var target = Math.floor(Math.random() * nodeTotal);

    var edge = {
      source: source,
      target: target
    };

    if (graph.adjacent[source] === undefined) {
      graph.adjacent[source] = [];
    }
    if (graph.adjacent[target] === undefined) {
      graph.adjacent[target] = [];
    }

    graph.adjacent[source].push(target);
    graph.adjacent[target].push(source);

    return edge;
  });

  var svg = d3.select("svg"),
    width = document.getElementById('width').clientWidth,
    height = width;

  svg.attr('width', width)
    .attr('height', height);

  var simulation = d3.forceSimulation()
    .force("link", d3.forceLink().id(function(d) { return d.id; }))
    .force("charge", d3.forceManyBody())
    .force("center", d3.forceCenter(width / 2, height / 2));

  var link = svg.append("g")
    .attr("class", "links")
    .selectAll("line")
    .data(graph.edges)
    .enter().append("line");

  var node = svg.append("g")
    .attr("class", "nodes")
    .selectAll("circle")
    .data(graph.nodes, function(d) { return d.id; })
    .enter().append("circle")
    .attr("r", 5);

  node.append("title")
    .text(function(d) { return d.id; });

  simulation.nodes(graph.nodes)
    .on("tick", ticked);

  simulation.force("link")
    .links(graph.edges);

  function ticked() {
    link.attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

    node.attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });
  }

  var DepthFirstSearch = {
    marked: [],
    edgeTo: [],
    source: 0,
    count: 0,
    dfs: function(graphObject, nodeIndex) {

      var self = DepthFirstSearch;

      dfs(graphObject, nodeIndex);

      function dfs(graphObject, nodeIndex) {

        self.marked[nodeIndex] = true;
        self.count++;

        graphObject.adjacent[nodeIndex].forEach(function(d){

          if (!self.marked[d]) {
            self.edgeTo[d] = nodeIndex;
            dfs(graphObject, d);
          }

        });

        return;

      }

      return;
    },
    hasPathTo: function(endIndex) {
      var self = DepthFirstSearch;

      return self.marked[endIndex];
    },
    pathTo: function(graphObject, startIndex, endIndex) {
      var self = DepthFirstSearch;

      self.dfs(graphObject, startIndex);

      if (!self.hasPathTo(endIndex)) {
        return null;
      }

      var path = [];
      for (var i = endIndex; i != startIndex; i = self.edgeTo[i]) {
        path.push(i);
      }
      path.push(startIndex);
      return path.reverse();
    }
  };

  var BreadthFirstSearch = {
    marked: [],
    edgeTo: [],
    count: 0,
    bfs: function(graphObject, nodeIndex) {
      var self = BreadthFirstSearch;
      var queue = [];

      self.marked[nodeIndex] = true;
      queue.push(nodeIndex);

      while (queue.length > 0) {
        var v = queue.shift();
        graphObject.adjacent[v].forEach(markedAdjacent);
      }

      function markedAdjacent(d) {
        if (!self.marked[d]) {
          self.edgeTo[d] = v;
          self.marked[d] = true;
          queue.push(d);
        }
      }

    },
    hasPathTo: function(endIndex){
      var self = BreadthFirstSearch;
      return self.marked[endIndex];
    },
    pathTo: function(graphObject, startIndex, endIndex) {
      var self = BreadthFirstSearch;

      self.bfs(graphObject, startIndex);

      if (!self.hasPathTo(endIndex)) {
        return null;
      }
      var path = [];
      for (var i = endIndex; i != startIndex; i = self.edgeTo[i]) {
        path.push(i);
      }
      path.push(startIndex);
      return path.reverse();
    }
  };

  var start = Math.floor(Math.random() * nodeTotal);
  var end = Math.floor(Math.random() * nodeTotal);

  var dfpath = DepthFirstSearch.pathTo(graph, start, end);
  var path = BreadthFirstSearch.pathTo(graph, start, end);

  if (path !== null) {

    var pathNodes = node.filter(function(d){ return path.indexOf(d.id) > -1; })
      .style('fill', '#000000');

    var pathEdges = link.filter(function(d){
      if (path.indexOf(d.source.id) < 0 || path.indexOf(d.target.id) < 0) {
        return false;
      } else {
        var sourceIndex = path.indexOf(d.source.id);
        var targetIndex = path.indexOf(d.target.id);
        var check = path[sourceIndex - 1] == d.target.id || path[sourceIndex + 1] == d.target.id;
        return check;
      }
    }).style('stroke', '#000000');

  }

} )();