Graceful Tree Conjecture

The graceful tree conjecture states that every tree has a graceful label. Although proven for some simple cases, the general case remains open.

This program can be used to draw a tree and generate all graceful labels (except for certain trivial variations) for the tree. The visualization also shows the adjacency matrix with respect to the graceful label.

Instructions:

Build tree by clicking on vertices to add leafs to it. Once the desired tree is built, click on 'Generate labels' button to find all graceful labels. The labels shown are unique with respect to adjacency matrix. This reduces many trivial variations in labels, for example if two branches from a vertex are isomorphic, then their labels can be swapped to get another graceful label. Also if (i) is a gaceful labeling, so is (n-i), one of these labelings have 0 and n-1 adjacent. Only labels where 0 and n-1 are adjacent are shown.

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

body{
	width:960px;
	margin:10px auto;
}
circle{
  fill:white;
  stroke:steelblue;  
  stroke-width:2px;
}
line{
  stroke:grey;
  stroke-width:3px;
}
.incRect{
	stroke:grey;
	shape-rendering:crispEdges;
}
#incMatx text{
	text-anchor:middle;
	cursor:default;
}
#treesvg g text:hover, #treesvg g circle:hover{
	cursor:pointer;
}
#navdiv{
	background:#555;
}
#treesvg{
	border:1px solid grey;
}
#labelpos{
	color:white;
}
#navdiv button, #navdiv textarea{
	vertical-align:middle;
}
#g_labels text{
	text-anchor:middle;
}
#g_elabels text{
	text-anchor:middle;
	fill:red;
	font-weight:bold;
}
</style>
<body>
<script src="https://d3js.org/d3.v3.min.js"></script>

circles.transition().duration(500).attr('cx',function(d){ return d.p.x;}).attr('cy',function(d){ return d.p.y;});
		
		circles.enter().append('circle').attr('cx',function(d){ return d.f.p.x;}).attr('cy',function(d){ return d.f.p.y;}).attr('r',vRad)
			.on('click',function(d){return tree.addLeaf(d.v);})
			.transition().duration(500).attr('cx',function(d){ return d.p.x;}).attr('cy',function(d){ return d.p.y;});
			
		var labels = d3.select("#g_labels").selectAll('text').data(tree.getVertices());
		
		labels.text(function(d){return d.l;}).transition().duration(500)
			.attr('x',function(d){ return d.p.x;}).attr('y',function(d){ return d.p.y+5;});
			
		labels.enter().append('text').attr('x',function(d){ return d.f.p.x;}).attr('y',function(d){ return d.f.p.y+5;})
			.text(function(d){return d.l;}).on('click',function(d){return tree.addLeaf(d.v);})
			.transition().duration(500)
			.attr('x',function(d){ return d.p.x;}).attr('y',function(d){ return d.p.y+5;});		
			
		var elabels = d3.select("#g_elabels").selectAll('text').data(tree.getEdges());
					
		elabels
			.attr('x',function(d){ return (d.p1.x+d.p2.x)/2+(d.p1.x < d.p2.x? 8: -8);}).attr('y',function(d){ return (d.p1.y+d.p2.y)/2;})
			.text(function(d){return tree.glabels.length==0? '': Math.abs(d.l1 -d.l2);});	
			
		elabels.enter().append('text')
			.attr('x',function(d){ return (d.p1.x+d.p2.x)/2+(d.p1.x < d.p2.x? 8: -8);}).attr('y',function(d){ return (d.p1.y+d.p2.y)/2;})
			.text(function(d){return tree.glabels.length==0? '': Math.abs(d.l1 -d.l2);});	
			
		
		d3.select('#incMatx').selectAll(".incrow").data(tree.incMatx)
			.enter().append('g').attr('class','incrow');
			
		d3.select('#incMatx').selectAll(".incrow").selectAll('.incRect')
			.data(function(d,i){ return getIncMatxRow(i).map(function(v,j){return {y:i, x:j, f:v};})})
			.enter().append('rect').attr('class','incRect');
			
		d3.select('#incMatx').selectAll('.incRect')
			.attr('x',function(d,i){ return (d.x+d.y)*tree.incS;}).attr('y',function(d,i){ return d.y*tree.incS;})
			.attr('width',function(){ return tree.incS;}).attr('height',function(){ return tree.incS;})
			.attr('fill',function(d){ return d.f == 1? 'black':'white'});
			
		d3.select("#incMatx").selectAll('.incrowlabel').data(d3.range(0,tree.size)).enter()
			.append('text').attr('class','incrowlabel');
			
		d3.select("#incMatx").selectAll('.incrowlabel').text(function(d){ return d;})
			.attr('x',function(d,i){ return (i-0.5)*tree.incS}).attr('y',function(d,i){ return (i+0.8)*tree.incS});
	}
	
	getLeafCount = function(_){
		if(_.c.length ==0) return 1;
		else return _.c.map(getLeafCount).reduce(function(a,b){ return a+b;});
	}
	
	reposition = function(v){
		var lC = getLeafCount(v), left=v.p.x - tree.w*(lC-1)/2;
		v.c.forEach(function(d){
			var w =tree.w*getLeafCount(d); 
			left+=w; 
			d.p = {x:left-(w+tree.w)/2, y:v.p.y+tree.h};
			reposition(d);
		});		
	}	
	
	initialize = function(){
		d3.select("body").append("div").attr('id','navdiv');
		
		d3.select("#navdiv").append("button").attr('type','button').text('Generate labels')
			.on('click',function(d){return tree.gracefulLabels();});
		
		d3.select("#navdiv").append("nav").attr('id','labelnav').style('display','inline-block').style('visibility','hidden');
		
		d3.select("#labelnav").append("button").attr('type','button').text('<').attr('id','prevlabel')
			.on('click',function(d){return tree.showLabel(tree.currLbl == 1? tree.glabels.length: tree.currLbl-1);});
			
		d3.select("#labelnav").append("text").text('').attr('id','labelpos');

d3.select("#labelnav").append("button").attr('type','button').text('>').attr('id','nextlabel')
			.on('click',function(){return tree.showLabel(tree.currLbl == tree.glabels.length? 1: tree.currLbl+1);});			
						
		d3.select("body").append("svg").attr("width", svgW).attr("height", svgH).attr('id','treesvg');

d3.select("#treesvg").append('g').attr('id','g_lines').selectAll('line').data(tree.getEdges()).enter().append('line')
			.attr('x1',function(d){ return d.p1.x;}).attr('y1',function(d){ return d.p1.y;})
			.attr('x2',function(d){ return d.p2.x;}).attr('y2',function(d){ return d.p2.y;});

d3.select("#treesvg").append('g').attr('id','g_circles').selectAll('circle').data(tree.getVertices()).enter()
			.append('circle').attr('cx',function(d){ return d.p.x;}).attr('cy',function(d){ return d.p.y;}).attr('r',vRad)
			.on('click',function(d){return tree.addLeaf(d.v);});
			
		d3.select("#treesvg").append('g').attr('id','g_labels').selectAll('text').data(tree.getVertices()).enter().append('text')
			.attr('x',function(d){ return d.p.x;}).attr('y',function(d){ return d.p.y+5;}).text(function(d){return d.l;})
			.on('click',function(d){return tree.addLeaf(d.v);});	
			
		d3.select("#treesvg").append('g').attr('id','g_elabels').selectAll('text').data(tree.getEdges()).enter().append('text')
			.attr('x',function(d){ return (d.p1.x+d.p2.x)/2+(d.p1.x < d.p2.x? 8: -8);}).attr('y',function(d){ return (d.p1.y+d.p2.y)/2;})
			.text(function(d){return tree.glabels.length==0? '': Math.abs(d.l1 -d.l2);});	
			
		d3.select("body").select("svg").append('g').attr('transform',function(){ return 'translate('+tree.incX+','+tree.incY+')';})
			.attr('id','incMatx').selectAll('.incrow')
			.data(tree.incMatx.map(function(d,i){ return {i:i, r:d};})).enter().append('g').attr('class','incrow');

d3.select("#incMatx").selectAll('.incrowlabel').data(d3.range(0,tree.size)).enter()
			.append('text').attr('class','incrowlabel').text(function(d){ return d;})
			.attr('x',function(d,i){ return (i-0.5)*tree.incS}).attr('y',function(d,i){ return (i+.8)*tree.incS});
		
		tree.addLeaf(0);
		tree.addLeaf(0);
	}
	initialize();

return tree;
}
var tree= tree();
</script>

Modified http://d3js.org/d3.v3.min.js to a secure url

https://d3js.org/d3.v3.min.js