mph006/data.js

## readme.md

      
    Raw
  

              readme.md
            
          
    Visualizing depth and breadth first tree traversal algorithims using a d3 dendrogram, chained transitions, and basic js array stack/queue functionality
Vanilla dendrogram taken from http://bl.ocks.org/d3noob/8326869

  
## data.js
//Dummy tree structure
var treeData = [{children:[{children:[{},{},{}]},{children:[{children:[{}]}]},{},{children:[{},{children:[{},{}]}]}]}];

## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<title>Tree Traversals</title>
<!-- stuff for styling -->
<link rel="stylesheet" type="text/css" href="style.css"/>
<!-- stuff for d3 -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js" charset="utf-8"></script>
<!-- data stuff -->
<script src="data.js"></script>

<body>
	<div id="title">Tree Traversals</div>
	<div id="button-wrapper">
		<button id="dft" onclick="dft()">Depth First</button>
		<button id="bft" onclick="bft()">Breadth First</button>
		<button id="reset" onclick="resetTraversal()">Reset</button>
	</div>
	<div id="tree-container"></div>
</body>

<script src="treeTraversal.js"></script>

## style.css

html,body {
  font-family: Helvetica;
}

#title{
	font-size: 20px;
	width: 60%;
	text-align: center;
	margin-left: 20%;
	border-bottom: thin solid black;
}

#button-wrapper{
	position: relative;
	display: block;
	width: 60%;
	text-align: center;
	margin-left: 20%;
	margin-top: 20px;

}

#tree-container{
	display: block;
	position: relative;
	width: 60%;
	margin-left: 28%;
	height: 500px;
	margin-top: 20px;
}

.node {
  fill: #fff;
  stroke: steelblue;
  stroke-width: 1.5px;
}

.link {
  fill: none;
  stroke: #ccc;
  stroke-width: 1.5px;
}

## treeTraversal.js
//http://bl.ocks.org/d3noob/8326869
var margin = {top: 20, right: 0, bottom: 20, left: 0},
  width = document.getElementById("tree-container").offsetWidth - margin.right - margin.left,
  height = document.getElementById("tree-container").offsetHeight - margin.top - margin.bottom;

var i=0, animDuration=500,root;

var tree = d3.layout.tree()
  .size([height, width]);


// https://github.com/wbkd/d3-extended
d3.selection.prototype.moveToFront = function() {
  return this.each(function(){
    this.parentNode.appendChild(this);
  });
};

var svg = d3.select("#tree-container").append("svg")
  .attr("width", width + margin.right + margin.left)
  .attr("height", height + margin.top + margin.bottom)
  .append("g")
  .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

root= treeData[0];
update(treeData[0]);

function resetTraversal(root){
  //d3.selectAll(".node").classed("visited",false);
  d3.selectAll(".node")
    .transition().duration(animDuration)
    .style("fill","#fff")
    .style("stroke","steelblue");

}

function update(root) {

  resetTraversal(root);

  // Compute the new tree layout.
  var nodes = tree.nodes(root).reverse(),
    links = tree.links(nodes);

  // Normalize for fixed-depth.
  nodes.forEach(function(d) { d.y = d.depth *100; });

  // Declare and append the nodes
  var nodeWrapper = svg.append("g").attr("id","nodes").selectAll("g.node")
    .data(nodes, function(d) {return d.id || (d.id = ++i); })
    .enter().append("circle")
    .attr("class", "node")
    //Root is the highest ID
    .attr("id",function(d){return "node-"+d.id})
    .attr("cx",function(d){return d.x;})
    .attr("cy",function(d){return d.y;})
    .attr("r", 10);

  // Declare and append the links
  var linkWrapper = svg.append("g").attr("id","links").selectAll("path.link")
    .data(links, function(d) { return d.target.id; })
    .enter()
    .append("line", "g")
    .attr("class", "link")
    .attr("id",function(d){
      return d.source.id +"->"+ d.target.id;
    })
    .attr('x1', function(d){return d.source.x;})
    .attr('x2',function(d){return d.target.x;})
    .attr('y1',function(d){return d.source.y;})
    .attr('y2',function(d){return d.target.y;});

  //Styling consideration
  d3.select("#nodes").moveToFront();

}
function visitElement(element,animX){
 // d3.select("#node-"+element.id).classed("visited",true);
  d3.select("#node-"+element.id)
    .transition().duration(animDuration).delay(animDuration*animX)
    .style("fill","red").style("stroke","red");
}

function dft(){
  var stack=[];
  var animX=0;
  stack.push(root);
  while(stack.length!==0){
    var element = stack.pop();
    visitElement(element,animX);
    animX=animX+1;
    if(element.children!==undefined){
      for(var i=0; i<element.children.length; i++){
        stack.push(element.children[element.children.length-i-1]);
      }
    }
  }
}

function bft(){
  var queue=[];
  var animX=0;
  queue.push(root);
  while(queue.length!==0){
    var element = queue.shift();
    visitElement(element,animX);
    animX= animX+1;
    if(element.children!==undefined){
      for(var i=0; i<element.children.length; i++){
        queue.push(element.children[i]);
      }
    }
  }
}
	//Dummy tree structure
	var treeData = [{children:[{children:[{},{},{}]},{children:[{children:[{}]}]},{},{children:[{},{children:[{},{}]}]}]}];
	<!DOCTYPE html>
	<meta charset="utf-8">
	<title>Tree Traversals</title>
	<!-- stuff for styling -->
	<link rel="stylesheet" type="text/css" href="style.css"/>
	<!-- stuff for d3 -->
	<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js" charset="utf-8"></script>
	<!-- data stuff -->
	<script src="data.js"></script>

	<body>
	<div id="title">Tree Traversals</div>
	<div id="button-wrapper">
	<button id="dft" onclick="dft()">Depth First</button>
	<button id="bft" onclick="bft()">Breadth First</button>
	<button id="reset" onclick="resetTraversal()">Reset</button>
	</div>
	<div id="tree-container"></div>
	</body>

	<script src="treeTraversal.js"></script>

	html,body {
	font-family: Helvetica;
	}

	#title{
	font-size: 20px;
	width: 60%;
	text-align: center;
	margin-left: 20%;
	border-bottom: thin solid black;
	}

	#button-wrapper{
	position: relative;
	display: block;
	width: 60%;
	text-align: center;
	margin-left: 20%;
	margin-top: 20px;

	}

	#tree-container{
	display: block;
	position: relative;
	width: 60%;
	margin-left: 28%;
	height: 500px;
	margin-top: 20px;
	}

	.node {
	fill: #fff;
	stroke: steelblue;
	stroke-width: 1.5px;
	}

	.link {
	fill: none;
	stroke: #ccc;
	stroke-width: 1.5px;
	}
	//http://bl.ocks.org/d3noob/8326869
	var margin = {top: 20, right: 0, bottom: 20, left: 0},
	width = document.getElementById("tree-container").offsetWidth - margin.right - margin.left,
	height = document.getElementById("tree-container").offsetHeight - margin.top - margin.bottom;

	var i=0, animDuration=500,root;

	var tree = d3.layout.tree()
	.size([height, width]);


	// https://github.com/wbkd/d3-extended
	d3.selection.prototype.moveToFront = function() {
	return this.each(function(){
	this.parentNode.appendChild(this);
	});
	};

	var svg = d3.select("#tree-container").append("svg")
	.attr("width", width + margin.right + margin.left)
	.attr("height", height + margin.top + margin.bottom)
	.append("g")
	.attr("transform", "translate(" + margin.left + "," + margin.top + ")");

	root= treeData[0];
	update(treeData[0]);

	function resetTraversal(root){
	//d3.selectAll(".node").classed("visited",false);
	d3.selectAll(".node")
	.transition().duration(animDuration)
	.style("fill","#fff")
	.style("stroke","steelblue");

	}

	function update(root) {

	resetTraversal(root);

	// Compute the new tree layout.
	var nodes = tree.nodes(root).reverse(),
	links = tree.links(nodes);

	// Normalize for fixed-depth.
	nodes.forEach(function(d) { d.y = d.depth *100; });

	// Declare and append the nodes
	var nodeWrapper = svg.append("g").attr("id","nodes").selectAll("g.node")
	.data(nodes, function(d) {return d.id \|\| (d.id = ++i); })
	.enter().append("circle")
	.attr("class", "node")
	//Root is the highest ID
	.attr("id",function(d){return "node-"+d.id})
	.attr("cx",function(d){return d.x;})
	.attr("cy",function(d){return d.y;})
	.attr("r", 10);

	// Declare and append the links
	var linkWrapper = svg.append("g").attr("id","links").selectAll("path.link")
	.data(links, function(d) { return d.target.id; })
	.enter()
	.append("line", "g")
	.attr("class", "link")
	.attr("id",function(d){
	return d.source.id +"->"+ d.target.id;
	})
	.attr('x1', function(d){return d.source.x;})
	.attr('x2',function(d){return d.target.x;})
	.attr('y1',function(d){return d.source.y;})
	.attr('y2',function(d){return d.target.y;});

	//Styling consideration
	d3.select("#nodes").moveToFront();

	}
	function visitElement(element,animX){
	// d3.select("#node-"+element.id).classed("visited",true);
	d3.select("#node-"+element.id)
	.transition().duration(animDuration).delay(animDuration*animX)
	.style("fill","red").style("stroke","red");
	}

	function dft(){
	var stack=[];
	var animX=0;
	stack.push(root);
	while(stack.length!==0){
	var element = stack.pop();
	visitElement(element,animX);
	animX=animX+1;
	if(element.children!==undefined){
	for(var i=0; i<element.children.length; i++){
	stack.push(element.children[element.children.length-i-1]);
	}
	}
	}
	}

	function bft(){
	var queue=[];
	var animX=0;
	queue.push(root);
	while(queue.length!==0){
	var element = queue.shift();
	visitElement(element,animX);
	animX= animX+1;
	if(element.children!==undefined){
	for(var i=0; i<element.children.length; i++){
	queue.push(element.children[i]);
	}
	}
	}
	}