JSFiddle - React, Tailwind, and code Playground

by Gowtham Rangarajan

HTML

<head>
<div class="headl">     
<hgroup>
<h1>Kargers minimum cut for dummies- Gowtham Rangarajan</h1>
</hgroup>
</head>
<body>
<div id = "container">

<div id = "top"></div>
<div id = "side"></div>

<div id = "middle">
<p> Karger's minimum cut algorithm provides a simple and fantastic introduction to randomised algorithms!<br>
It was my first encounter with a non trivial algorithm that devised a probabilistic solution !!! ie., it can guarentee that a significant repetitions of a certain method
would be highly likely yield the answer we were looking for! Certainly a refreshing change of pace from strong binary proofs !!! smoooth, I liked it a lot :-) <br><br>
Ok Lets dive in to the problem. Proceed only if you understand basic sorting algorithms and are willing to spend 15 minutes or so to understand this one.<br> </p>
<p><h2>Problem Statement</h2> Given an undirected graph G, we can bifurcate the nodes into 2 groups A,B. Of all the bifurcations possible we have to find one bifurcation
which has the least number of edges (cuts) from A to B.</p>
<img src="https://poochi.github.io/projects/kargers/karger.png" alt="Bifurcation" style="width:250px;height:100px" >





<h2>Solution</h2>
<p>Let the number of nodes be indicated by <b>nodecnt</b>  and the number of edges be <b>edgecnt</b>.
<pre>
----------------------------------------------
begin loop1
The Graph G that has to be bifurcated is initialised.
begin loop2
Pick a (uniformly) random edge in the graph
merge (contract) its endpoints to a single 'super node' (ignore self loops)
end loop2 (Repeat untill we have 2 nodes)
Check the nodes that have contributed in creating the 'supernode' and calculate the number of edges (cut) between the supernodes.
end loop1 (Repeat until we for nodecnt^2 times atleast)
-----------------------------------------------
</pre>
The algorithm's provides a proababilistic guarentee that you ll encounter a minimum cut/ minimum configuration if you perform loop2 sufficient number of...

CSS

.node {
        
        stroke-width: 2px;
    }

    .link {
        stroke-opacity: .3;
    }
	
#container 
{
border-style:solid;
border-width:medium;
}

#top 
{
float:left;
border-style:ridge;
border-width:medium;
}
#side 
{
float:right;
border-style:ridge;
border-width:medium;
}
#middle
{
margin-left:100px;
margin-left:100px;

}

JavaScript

//stroke: #fff;
console.clear()
var width = 400,
    height = 500;
	
var w =width/3,h =height/3;

var colorStep =93;
var svg = d3.select("#middle")
		.append("svg")
		.attr("width",width)
		.attr("height",height);
		
var svg1 = d3.select("#top")
		.append("svg")
		.attr("width",w)
		.attr("height",h);

var svg2 = d3.select("#side")
		.append("svg")
		.attr("width",w)
		.attr("height",h);
		
		



		
// ??
svg.append("g").attr("class", "links");
svg.append("g").attr("class", "nodes");

svg1.append("g").attr("class", "links");
svg1.append("g").attr("class", "nodes");

svg2.append("g").attr("class", "links");
svg2.append("g").attr("class", "nodes");

		

var parentnode = [];

//var bestsofarlink = [];
var higlightedges=[];

var problemnodes = [],deepcopynodes=[];
var problemlinks = [],deepcopylinks=[];

var nodecnt =5;
var edgecnt= 8;
var mini = edgecnt+1;


var mark=[];
function generategraph() {		 
	for(i=0;i<nodecnt;i++) {
		var x = width/2- Math.random()*width/2;
		var y =height/2- Math.random()*height/2;
		problemnodes.push({id:i,x:x,y:y,r:5,color:"hsl("+(colorStep*i)%360+", 83%, 60%)"});
		deepcopynodes.push({id:i,x:x,y:y,r:5,color:"hsl("+(colorStep*i)%360+", 83%, 60%)"});
		mark.push(0);
	}
	
	for(i=0;i<edgecnt;i++) {
		var a =Math.floor((Math.random())*nodecnt);
		var b =Math.floor((Math.random())*nodecnt);

	while(a%nodecnt==b%nodecnt){
		b =Math.floor((Math.random())*nodecnt);
	}
		problemlinks.push({id:i,source :problemnodes[a%nodecnt] ,target:problemnodes[b%nodecnt],color:"#ccc",srcind:a,dstind:b});
		deepcopylinks.push({id:i,source :deepcopynodes[a%nodecnt] ,target:deepcopynodes[b%nodecnt],color:"#ccc",srcind:a,dstind:b});
		mark[a%nodecnt] = mark[b%nodecnt] = 1;
	}

	for(i=0;i<problemnodes.length;i++) {
		if(mark[i] == 0){
			var a =Math.floor((Math.random())*nodecnt);
			while(a==i){
			a =Math.floor((Math.random())*nodecnt);
			}

			problemlinks.push({id:edgecnt,source :problemnodes[a%nodecnt]...