mayblue9/README.md

## README.md

      
    Raw
  

              README.md
            
          
    A simple, step-by-step visualization of Dijkstra's algorithm. Adapted from a previous post by sdjacobs.

  
## dijkstra.js
d3.dijkstra = function () {
    // See, http://bl.ocks.org/sdjacobs/3900867adc06c7680d48
    var dijkstra = {}, nodes, edges, source, go, dispatch = d3.dispatch("start", "tick", "step", "end");
    var color = d3.scale.linear().domain([0, 3, 10]).range(["green", "yellow", "red"]);
    var translate_speed = 5000;

    dijkstra.run = function (src) {
        // clear previous run
        clearInterval(go);

        // reset styles
        d3.selectAll('.node').style('fill', '#fff').attr('r', 15).style('stroke-width', '1.5');
        d3.select('.'+src.name).style('fill', '#fdb03f').style('stroke-width', '0');
        d3.selectAll('.nodetext').text(function(d){ return d.name});
        d3.selectAll('.linktext').style('opacity', '0');

        source = src;
        var unvisited = [];

        nodes.forEach(function (d) {
            if (d != src) {
                d.distance = Infinity;
                unvisited.push(d);
                d.visited = false;
            }
        });

        var current = src;
        current.distance = 0;

        function tick() {
            current.visited = true;
            current.links.forEach(function(link) {

                if (!link.target.visited) {
                    var dist = current.distance + link.value;
                    link.target.distance = Math.min(dist, link.target.distance);
                    d3.select('.'+link.target.name).transition().delay(translate_speed/8).duration(500).attr('r', 15+link.value).style('fill', '#ecf0f1')
                    d3.select('.nodetext.'+link.target.name).transition().delay(translate_speed/8).duration(500).text(link.target.distance)
                    d3.select('.linktext.'+link.id).style('opacity', 1).transition().duration(translate_speed).text(+link.value)
                }
            });
            if (unvisited.length == 0 || current.distance == Infinity) {
                clearInterval(go)
                return true
            }
            unvisited.sort(function(a, b) {
                return b.distance - a.distance
            });

            current = unvisited.pop()

            d3.select('.'+current.name)
                .transition().delay(translate_speed*2/5).duration(translate_speed/5).attr('r', 10)
                .transition().duration(translate_speed/5).attr('r', 15)
                .style("fill", '#D0E1C3')
                .style('stroke-width', '0');

            d3.select('.nodetext.'+current.name)
                .transition().delay(translate_speed*4/5).text(function(d){  return d.distance })

        }

        tick()
        go = setInterval(tick, translate_speed);
    };

   dijkstra.nodes = function (_) {
        if (!arguments.length)
            return nodes;
        else {
            nodes = _;
            return dijkstra;
        }
    };

   dijkstra.edges = function (_) {
        if (!arguments.length)
            return edges;
        else {
            edges = _;
            return dijkstra;
        }
    };

   dijkstra.source = function(_) {
        if (!arguments.length)
            return source;
        else {
            source = _;
            return dijkstra;
        }
    };


   dispatch.on("start.code", dijkstra.run);

   return d3.rebind(dijkstra, dispatch, "on", "end", "start", "tick");
};

## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>

body {
  width: 1024px;
  margin-top: 0;
  margin: auto;
  font-family: "Lato", "PT Serif", serif;
  color: #222222;
  padding: 0;
  font-weight: 300;
  line-height: 33px;
  -webkit-font-smoothing: antialiased;
}

.node {
  stroke: #7f8c8d;
  stroke-width: 1.5px;
  fill: #bdc3c7;
  stroke-dasharray: 2px, 2px;
}


.link {
  stroke: #ecf0f1;
  stroke-opacity: .6;
}

.linktext{
  fill: #95a5a6;
  background-color: #ffffff;
}

text {
    pointer-events: none;
}

</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="dijkstra.js"></script>
<script>

var width = 960,
    height = 500;

var color = d3.scale.category20();

var force = d3.layout.force()
    .charge(-4020)
    .linkDistance(90)
    .size([width, height]);

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);

d3.csv("network.csv", function(error, data) {

  var nodes = [], nodesByName = {}, links = [];
  function addNodeByName(fullname) {
    var name = fullname.split(',')[0];
    if (!nodesByName[name]) {
      var node = {"name":name, "links":[]}
      nodesByName[name] = node;
      nodes.push(node);
      return node;
    }
    else
      return nodesByName[name];
  }

  data.forEach(function(d) {
    for (k in d) {
      if (d.hasOwnProperty(k) && k != "nodes" && d[k] < 750) {
        links.push({"source": addNodeByName(d["nodes"]), "target": addNodeByName(k), "value": parseInt(Math.random()*d[k]*5+1), 'id':addNodeByName(d["nodes"]).name+addNodeByName(k).name })
      }
    }
  });

  force
      .nodes(nodes)
      .links(links)
      .start();

  var glink = svg.append('g').selectAll(".link")
      .data(links).enter()

  var link = glink.append("line")
      .attr("class", function(d){ return "link "+d.id})
      .style("stroke-width", 2);

  var linktext = glink.append('text')
      .attr("class", function(d){ return "linktext "+d.id})
      .attr('text-anchor', 'middle')
      .style('opacity', 0)
      .text(function(d){ return d.value})

  var gnode = svg.append('g').selectAll(".node")
      .data(nodes).enter()

  var node = gnode.append("circle")
      .attr("class", function(d){ return 'node '+d.name})
      .attr("r", 15)
      .call(force.drag);

  var nodetext = gnode.append('text')
      .attr('text-anchor', 'middle')
      .attr('dy', '0.35em')
      .attr("class", function(d){ return "nodetext "+d.name})
      .text(function(d){ return d.name})


  link.each(function(d) {
      d.source.links.push(d);
      d.selection = d3.select(this);
  });

  node.each(function(d) {
      d.selection = d3.select(this);
  });

  force.on("tick", function() {
    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; });

    linktext.attr("x", function(d) { return (d.source.x + d.target.x)/2 ; })
        .attr("y", function(d) { return (d.source.y + d.target.y)/2; })

    nodetext.attr("x", function(d) { return d.x ; })
        .attr("y", function(d) { return d.y; })

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


  node.on("mouseover", function(d) {
      d3.select(this).attr('r', 16.5);

  });

  node.on("mouseout", function(d) {
      d3.select(this).attr('r', 15);
  });

  var dijkstra = d3.dijkstra()
    .nodes(nodes)
    .edges(links);

  node.on("click", dijkstra.start);

 });

</script>

## network.csv
nodes,A,B,C,D,E,F,G,H
A,-,1,-,-,-,1,-,1,-
B,1,-,1,1,-,1,-,-,-
C,-,1,-,-,-,-,1,1,-
D,-,1,-,-,-,-,1,-,-
E,-,-,-,-,-,-,-,-,1
F,1,1,-,-,-,-,-,-,-
G,-,-,1,1,-,-,-,-,-
H,1,-,1,-,-,-,-,-,1

## thumbnail.png

      
    Raw
  

              thumbnail.png
	d3.dijkstra = function () {
	// See, http://bl.ocks.org/sdjacobs/3900867adc06c7680d48
	var dijkstra = {}, nodes, edges, source, go, dispatch = d3.dispatch("start", "tick", "step", "end");
	var color = d3.scale.linear().domain([0, 3, 10]).range(["green", "yellow", "red"]);
	var translate_speed = 5000;

	dijkstra.run = function (src) {
	// clear previous run
	clearInterval(go);

	// reset styles
	d3.selectAll('.node').style('fill', '#fff').attr('r', 15).style('stroke-width', '1.5');
	d3.select('.'+src.name).style('fill', '#fdb03f').style('stroke-width', '0');
	d3.selectAll('.nodetext').text(function(d){ return d.name});
	d3.selectAll('.linktext').style('opacity', '0');

	source = src;
	var unvisited = [];

	nodes.forEach(function (d) {
	if (d != src) {
	d.distance = Infinity;
	unvisited.push(d);
	d.visited = false;
	}
	});

	var current = src;
	current.distance = 0;

	function tick() {
	current.visited = true;
	current.links.forEach(function(link) {

	if (!link.target.visited) {
	var dist = current.distance + link.value;
	link.target.distance = Math.min(dist, link.target.distance);
	d3.select('.'+link.target.name).transition().delay(translate_speed/8).duration(500).attr('r', 15+link.value).style('fill', '#ecf0f1')
	d3.select('.nodetext.'+link.target.name).transition().delay(translate_speed/8).duration(500).text(link.target.distance)
	d3.select('.linktext.'+link.id).style('opacity', 1).transition().duration(translate_speed).text(+link.value)
	}
	});
	if (unvisited.length == 0 \|\| current.distance == Infinity) {
	clearInterval(go)
	return true
	}
	unvisited.sort(function(a, b) {
	return b.distance - a.distance
	});

	current = unvisited.pop()

	d3.select('.'+current.name)
	.transition().delay(translate_speed*2/5).duration(translate_speed/5).attr('r', 10)
	.transition().duration(translate_speed/5).attr('r', 15)
	.style("fill", '#D0E1C3')
	.style('stroke-width', '0');

	d3.select('.nodetext.'+current.name)
	.transition().delay(translate_speed*4/5).text(function(d){ return d.distance })

	}

	tick()
	go = setInterval(tick, translate_speed);
	};

	dijkstra.nodes = function (_) {
	if (!arguments.length)
	return nodes;
	else {
	nodes = _;
	return dijkstra;
	}
	};

	dijkstra.edges = function (_) {
	if (!arguments.length)
	return edges;
	else {
	edges = _;
	return dijkstra;
	}
	};

	dijkstra.source = function(_) {
	if (!arguments.length)
	return source;
	else {
	source = _;
	return dijkstra;
	}
	};


	dispatch.on("start.code", dijkstra.run);

	return d3.rebind(dijkstra, dispatch, "on", "end", "start", "tick");
	};
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	body {
	width: 1024px;
	margin-top: 0;
	margin: auto;
	font-family: "Lato", "PT Serif", serif;
	color: #222222;
	padding: 0;
	font-weight: 300;
	line-height: 33px;
	-webkit-font-smoothing: antialiased;
	}

	.node {
	stroke: #7f8c8d;
	stroke-width: 1.5px;
	fill: #bdc3c7;
	stroke-dasharray: 2px, 2px;
	}


	.link {
	stroke: #ecf0f1;
	stroke-opacity: .6;
	}

	.linktext{
	fill: #95a5a6;
	background-color: #ffffff;
	}

	text {
	pointer-events: none;
	}

	</style>
	<body>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<script src="dijkstra.js"></script>
	<script>

	var width = 960,
	height = 500;

	var color = d3.scale.category20();

	var force = d3.layout.force()
	.charge(-4020)
	.linkDistance(90)
	.size([width, height]);

	var svg = d3.select("body").append("svg")
	.attr("width", width)
	.attr("height", height);

	d3.csv("network.csv", function(error, data) {

	var nodes = [], nodesByName = {}, links = [];
	function addNodeByName(fullname) {
	var name = fullname.split(',')[0];
	if (!nodesByName[name]) {
	var node = {"name":name, "links":[]}
	nodesByName[name] = node;
	nodes.push(node);
	return node;
	}
	else
	return nodesByName[name];
	}

	data.forEach(function(d) {
	for (k in d) {
	if (d.hasOwnProperty(k) && k != "nodes" && d[k] < 750) {
	links.push({"source": addNodeByName(d["nodes"]), "target": addNodeByName(k), "value": parseInt(Math.random()d[k]5+1), 'id':addNodeByName(d["nodes"]).name+addNodeByName(k).name })
	}
	}
	});

	force
	.nodes(nodes)
	.links(links)
	.start();

	var glink = svg.append('g').selectAll(".link")
	.data(links).enter()

	var link = glink.append("line")
	.attr("class", function(d){ return "link "+d.id})
	.style("stroke-width", 2);

	var linktext = glink.append('text')
	.attr("class", function(d){ return "linktext "+d.id})
	.attr('text-anchor', 'middle')
	.style('opacity', 0)
	.text(function(d){ return d.value})

	var gnode = svg.append('g').selectAll(".node")
	.data(nodes).enter()

	var node = gnode.append("circle")
	.attr("class", function(d){ return 'node '+d.name})
	.attr("r", 15)
	.call(force.drag);

	var nodetext = gnode.append('text')
	.attr('text-anchor', 'middle')
	.attr('dy', '0.35em')
	.attr("class", function(d){ return "nodetext "+d.name})
	.text(function(d){ return d.name})


	link.each(function(d) {
	d.source.links.push(d);
	d.selection = d3.select(this);
	});

	node.each(function(d) {
	d.selection = d3.select(this);
	});

	force.on("tick", function() {
	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; });

	linktext.attr("x", function(d) { return (d.source.x + d.target.x)/2 ; })
	.attr("y", function(d) { return (d.source.y + d.target.y)/2; })

	nodetext.attr("x", function(d) { return d.x ; })
	.attr("y", function(d) { return d.y; })

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


	node.on("mouseover", function(d) {
	d3.select(this).attr('r', 16.5);

	});

	node.on("mouseout", function(d) {
	d3.select(this).attr('r', 15);
	});

	var dijkstra = d3.dijkstra()
	.nodes(nodes)
	.edges(links);

	node.on("click", dijkstra.start);

	});

	</script>
	nodes,A,B,C,D,E,F,G,H
	A,-,1,-,-,-,1,-,1,-
	B,1,-,1,1,-,1,-,-,-
	C,-,1,-,-,-,-,1,1,-
	D,-,1,-,-,-,-,1,-,-
	E,-,-,-,-,-,-,-,-,1
	F,1,1,-,-,-,-,-,-,-
	G,-,-,1,1,-,-,-,-,-
	H,1,-,1,-,-,-,-,-,1