starcalibre/.gitignore

## .gitignore
.idea/
*.iml

## README.md

      
    Raw
  

              README.md
            
          
    It's a Small World, After All..
A small world network is a type of graph such that most nodes are not
connected to each other, but each node can be reached with only a few steps.
Create your own small world network by clicking on nodes and creating new edges.
Notice how the average shortest path length gets smaller when edges connecting
distant nodes are created.
The average shortest paths lengths is calculated using the Floyd-Warshall algorithm.

  
## graph.js
function Graph(numberNodes) {
    this.nodes = this._initNodes(numberNodes);
    this.edges = this._initMatrix(numberNodes);
}

Graph.prototype._initMatrix = function(numberNodes) {
    var i, j, newRow;
    var matrix = new Array(numberNodes);

    for(i = 0; i < numberNodes; i++) {
        newRow = new Array(numberNodes);
        for(j = 0; j < numberNodes; j++) {
            newRow[j] = 0;
        }
        matrix[i] = newRow;
    }

    return matrix;
};

Graph.prototype._initNodes = function(numberNodes) {
    var i;
    var nodes = new Array(numberNodes);

    for(i = 0; i < numberNodes; i++) {
        nodes[i] = new Node(i);
    }

    return nodes;
};

Graph.prototype.numberEdges = function() {
    var edgeCount = this.edges.map(function(d) {
        return d.reduce(add)
    }).reduce(add);
    return edgeCount / 2;
};

Graph.prototype.numberNodes = function() {
    return this.nodes.length;
};

Graph.prototype.addEdge = function(i, j) {
    this.edges[i][j] = 1;
    this.edges[j][i] = 1;
};

Graph.prototype.averagePathLength = function() {
    var numberNodes = this.numberNodes();
    var dist = this._shortestPathsMatrix();

    var sum = dist.map(function(d) {
        return d.reduce(add)
    }).reduce(add);

    return (1 / (numberNodes * (numberNodes - 1))) * sum;
};

Graph.prototype.edgeList = function() {
    var i, j;
    var numberNodes = this.numberNodes();
    var edges = [];

    for(i = 0; i < numberNodes; i++) {
        for(j = 0; j < i; j++) {
            if(this.edges[i][j] > 0) {
                edges.push([j, i]);
            }
        }
    }

    return edges;
};

Graph.prototype.hasEdge = function(i, j) {
    return this.edges[i][j] > 0;
};

Graph.prototype._shortestPathsMatrix = function() {
    var i, j, k, edges;
    var numberNodes = this.numberNodes();

    var dist = new Array(numberNodes);

    // init dist array
    for(i = 0; i < numberNodes; i++) {
        dist[i] = new Array(numberNodes);
    }

    // dist[v][v] = 0, infinity otherwise
    for(i  = 0; i < numberNodes; i++) {
        for(j = 0; j < numberNodes; j++) {
            if(i === j) {
                dist[i][j] = 0;
            }
            else {
                dist[i][j] = Number.POSITIVE_INFINITY;
            }
        }
    }

    // dist d[u][v] for all u, v sharing edge
    for(i = 0; i < numberNodes; i++) {
        edges = this.nodes[i].edges;
        for(j = 0; j < numberNodes; j++) {
            if(this.edges[i][j] > 0) {
                dist[i][j] = 1;
            }
        }
    }

    // get the shortest paths
    for(i = 0; i < numberNodes; i++) {
        for(j = 0; j < numberNodes; j++) {
            for(k = 0; k < numberNodes; k++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    return dist;
};

function Node(id) {
    this.id = id;
    this.edges = [];
}

function add(a, b) {
    return a + b;
}

## index.html
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title></title>
    <style>
        svg {
            background: #01243B;
        }

        p, h1 {
            font-family: Arial, Helvetica, sans-serif;
        }

        #container {
            width: 80%;
        }

        #left, #right {
            float: left;
        }

        #right {
            margin-left: 20px;
        }

        .node {
            fill: #336699;
        }

        .node.hover {
            fill: #5288DB;
        }

        .edge {
            stroke: #C5C5C5;
            stroke-width: 2;
            shape-rendering: geometricPrecision;
        }

        .edge.drag {
            opacity: 0.75;

        }

        .hidden {
            visibility: hidden;
        }
    </style>
</head>
<body>
<div id="container">
    <div id="left">

    </div>
    <div id="right">
        <p>Number Of Nodes: <span id="number-nodes"></span></p>
        <p>Number Of Edges: <span id="number-edges"></span></p>
        <p>Average Path Length: <span id="avg-path-length"></span></p>
    </div>
</div>
</body>
<script src="./graph.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.14/d3.js"></script>
<script>
    // see https://stackoverflow.com/questions/14167863/how-can-i-bring-a-circle-to-the-front-with-d3
    // call this method on a selection to move an SVG element to the front of the draw stack
    d3.selection.prototype.moveToFront = function() {
        return this.each(function(){
            this.parentNode.appendChild(this);
        });
    };

    var width = 500;
    var height = 500;

    var ringRadius = 225;

    var graph = new Graph(60);
    var numberNodes = graph.numberNodes();

    var nodes = new Array(numberNodes);
    var edges = [];

    var SELECTING = false;
    var nodeFrom = null;
    var nodeTo = null;

    // create node layout
    var delta = 2 * Math.PI / graph.numberNodes();
    graph.nodes.forEach(function(d, i) {
        var coord = polarToCartesian(ringRadius, delta * i);
        d.x = width/2 + coord[0];
        d.y = height/2 + coord[1];
    });

    // add edges between nodes
    for(var i = 0; i < numberNodes; i++) {
        graph.addEdge(i, (i + 1) % numberNodes);
    }

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

    svg.on('mousemove', function() {
        var mouse = d3.mouse(this);
        if(SELECTING) {
            dragLine
                .attr('x2', mouse[0])
                .attr('y2', mouse[1])
                .classed('hidden', false)
                .classed('drag', true);
        }
    });

    // create edges
    svg.selectAll('.edge')
        .data(graph.edgeList())
        .enter()
        .append('line')
        .attr('class', 'edge')
        .attr('x1', function(d) {
            var node = graph.nodes[d[0]];
            return node.x;
        })
        .attr('y1', function(d) {
            var node = graph.nodes[d[0]];
            return node.y;
        })
        .attr('x2', function(d) {
            var node = graph.nodes[d[1]];
            return node.x;
        })
        .attr('y2', function(d) {
            var node = graph.nodes[d[1]];
            return node.y;
        });

    // create drag line
    // this is hidden when a new edge is not being created
    var dragLine = svg.append('line')
        .classed('edge', true)
        .classed('hidden', true)
        .attr('x1', 0)
        .attr('y1', 0)
        .attr('x2', 0)
        .attr('y2', 0)
        .attr('stroke-dasharray', '5, 5');

    // create nodes
    svg.selectAll('.node')
        .data(graph.nodes)
        .enter()
        .append('circle')
        .attr('class', 'node')
        .attr('cx', function(d) { return d.x })
        .attr('cy', function(d) { return d.y })
        .attr('r', 8)
        .on('mouseover', function() {
            d3.selectAll('.node')
                .classed('hover', false);

            d3.select(this)
                .classed('hover', true);
        })
        .on('mouseleave', function() {
            d3.select(this)
                .classed('hover', false);
        })
        .on('click', function(d) {
            if(!SELECTING) {
                nodeFrom = d3.select(this).moveToFront();
                SELECTING = true;
                dragLine
                    .attr('x1', d.x)
                    .attr('y1', d.y)
                    .attr('x2', d.x)
                    .attr('y2', d.y)
                    .classed('hidden', false);

            }
            else {
                nodeTo = d3.select(this);

                dragLine
                    .classed('hidden', true);

                var fromId = nodeFrom.data()[0].id;
                var toId = nodeTo.data()[0].id;

                if(!graph.hasEdge(fromId, toId)) {
                    svg.append('line')
                        .attr('class', 'edge')
                        .attr('x1', nodeFrom.data()[0].x)
                        .attr('y1', nodeFrom.data()[0].y)
                        .attr('x2', nodeTo.data()[0].x)
                        .attr('y2', nodeTo.data()[0].y);

                    graph.addEdge(fromId, toId);
                }

                nodeFrom.moveToFront();
                nodeTo.moveToFront();

                nodeFrom = false;
                nodeTo = false;
                SELECTING = false;

                updateDisplay();
            }
        });

    updateDisplay();

    function updateDisplay() {
        document.getElementById('number-nodes').innerHTML =
            graph.numberNodes().toString();
        document.getElementById('number-edges').innerHTML =
            graph.numberEdges().toString();
        document.getElementById('avg-path-length').innerHTML =
            d3.round(graph.averagePathLength(), 2).toString();
    }

    function polarToCartesian(r, theta) {
        var x = r * Math.cos(theta);
        var y = r * Math.sin(theta);
        return [x, y];
    }
</script>
</html>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	function Graph(numberNodes) {
	this.nodes = this._initNodes(numberNodes);
	this.edges = this._initMatrix(numberNodes);
	}

	Graph.prototype._initMatrix = function(numberNodes) {
	var i, j, newRow;
	var matrix = new Array(numberNodes);

	for(i = 0; i < numberNodes; i++) {
	newRow = new Array(numberNodes);
	for(j = 0; j < numberNodes; j++) {
	newRow[j] = 0;
	}
	matrix[i] = newRow;
	}

	return matrix;
	};

	Graph.prototype._initNodes = function(numberNodes) {
	var i;
	var nodes = new Array(numberNodes);

	for(i = 0; i < numberNodes; i++) {
	nodes[i] = new Node(i);
	}

	return nodes;
	};

	Graph.prototype.numberEdges = function() {
	var edgeCount = this.edges.map(function(d) {
	return d.reduce(add)
	}).reduce(add);
	return edgeCount / 2;
	};

	Graph.prototype.numberNodes = function() {
	return this.nodes.length;
	};

	Graph.prototype.addEdge = function(i, j) {
	this.edges[i][j] = 1;
	this.edges[j][i] = 1;
	};

	Graph.prototype.averagePathLength = function() {
	var numberNodes = this.numberNodes();
	var dist = this._shortestPathsMatrix();

	var sum = dist.map(function(d) {
	return d.reduce(add)
	}).reduce(add);

	return (1 / (numberNodes * (numberNodes - 1))) * sum;
	};

	Graph.prototype.edgeList = function() {
	var i, j;
	var numberNodes = this.numberNodes();
	var edges = [];

	for(i = 0; i < numberNodes; i++) {
	for(j = 0; j < i; j++) {
	if(this.edges[i][j] > 0) {
	edges.push([j, i]);
	}
	}
	}

	return edges;
	};

	Graph.prototype.hasEdge = function(i, j) {
	return this.edges[i][j] > 0;
	};

	Graph.prototype._shortestPathsMatrix = function() {
	var i, j, k, edges;
	var numberNodes = this.numberNodes();

	var dist = new Array(numberNodes);

	// init dist array
	for(i = 0; i < numberNodes; i++) {
	dist[i] = new Array(numberNodes);
	}

	// dist[v][v] = 0, infinity otherwise
	for(i = 0; i < numberNodes; i++) {
	for(j = 0; j < numberNodes; j++) {
	if(i === j) {
	dist[i][j] = 0;
	}
	else {
	dist[i][j] = Number.POSITIVE_INFINITY;
	}
	}
	}

	// dist d[u][v] for all u, v sharing edge
	for(i = 0; i < numberNodes; i++) {
	edges = this.nodes[i].edges;
	for(j = 0; j < numberNodes; j++) {
	if(this.edges[i][j] > 0) {
	dist[i][j] = 1;
	}
	}
	}

	// get the shortest paths
	for(i = 0; i < numberNodes; i++) {
	for(j = 0; j < numberNodes; j++) {
	for(k = 0; k < numberNodes; k++) {
	if (dist[i][j] > dist[i][k] + dist[k][j]) {
	dist[i][j] = dist[i][k] + dist[k][j]
	}
	}
	}
	}

	return dist;
	};

	function Node(id) {
	this.id = id;
	this.edges = [];
	}

	function add(a, b) {
	return a + b;
	}
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<meta charset="UTF-8">
	<title></title>
	<style>
	svg {
	background: #01243B;
	}

	p, h1 {
	font-family: Arial, Helvetica, sans-serif;
	}

	#container {
	width: 80%;
	}

	#left, #right {
	float: left;
	}

	#right {
	margin-left: 20px;
	}

	.node {
	fill: #336699;
	}

	.node.hover {
	fill: #5288DB;
	}

	.edge {
	stroke: #C5C5C5;
	stroke-width: 2;
	shape-rendering: geometricPrecision;
	}

	.edge.drag {
	opacity: 0.75;

	}

	.hidden {
	visibility: hidden;
	}
	</style>
	</head>
	<body>
	<div id="container">
	<div id="left">

	</div>
	<div id="right">
	<p>Number Of Nodes: <span id="number-nodes"></span></p>
	<p>Number Of Edges: <span id="number-edges"></span></p>
	<p>Average Path Length: <span id="avg-path-length"></span></p>
	</div>
	</div>
	</body>
	<script src="./graph.js"></script>
	<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.14/d3.js"></script>
	<script>
	// see https://stackoverflow.com/questions/14167863/how-can-i-bring-a-circle-to-the-front-with-d3
	// call this method on a selection to move an SVG element to the front of the draw stack
	d3.selection.prototype.moveToFront = function() {
	return this.each(function(){
	this.parentNode.appendChild(this);
	});
	};

	var width = 500;
	var height = 500;

	var ringRadius = 225;

	var graph = new Graph(60);
	var numberNodes = graph.numberNodes();

	var nodes = new Array(numberNodes);
	var edges = [];

	var SELECTING = false;
	var nodeFrom = null;
	var nodeTo = null;

	// create node layout
	var delta = 2 * Math.PI / graph.numberNodes();
	graph.nodes.forEach(function(d, i) {
	var coord = polarToCartesian(ringRadius, delta * i);
	d.x = width/2 + coord[0];
	d.y = height/2 + coord[1];
	});

	// add edges between nodes
	for(var i = 0; i < numberNodes; i++) {
	graph.addEdge(i, (i + 1) % numberNodes);
	}

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

	svg.on('mousemove', function() {
	var mouse = d3.mouse(this);
	if(SELECTING) {
	dragLine
	.attr('x2', mouse[0])
	.attr('y2', mouse[1])
	.classed('hidden', false)
	.classed('drag', true);
	}
	});

	// create edges
	svg.selectAll('.edge')
	.data(graph.edgeList())
	.enter()
	.append('line')
	.attr('class', 'edge')
	.attr('x1', function(d) {
	var node = graph.nodes[d[0]];
	return node.x;
	})
	.attr('y1', function(d) {
	var node = graph.nodes[d[0]];
	return node.y;
	})
	.attr('x2', function(d) {
	var node = graph.nodes[d[1]];
	return node.x;
	})
	.attr('y2', function(d) {
	var node = graph.nodes[d[1]];
	return node.y;
	});

	// create drag line
	// this is hidden when a new edge is not being created
	var dragLine = svg.append('line')
	.classed('edge', true)
	.classed('hidden', true)
	.attr('x1', 0)
	.attr('y1', 0)
	.attr('x2', 0)
	.attr('y2', 0)
	.attr('stroke-dasharray', '5, 5');

	// create nodes
	svg.selectAll('.node')
	.data(graph.nodes)
	.enter()
	.append('circle')
	.attr('class', 'node')
	.attr('cx', function(d) { return d.x })
	.attr('cy', function(d) { return d.y })
	.attr('r', 8)
	.on('mouseover', function() {
	d3.selectAll('.node')
	.classed('hover', false);

	d3.select(this)
	.classed('hover', true);
	})
	.on('mouseleave', function() {
	d3.select(this)
	.classed('hover', false);
	})
	.on('click', function(d) {
	if(!SELECTING) {
	nodeFrom = d3.select(this).moveToFront();
	SELECTING = true;
	dragLine
	.attr('x1', d.x)
	.attr('y1', d.y)
	.attr('x2', d.x)
	.attr('y2', d.y)
	.classed('hidden', false);

	}
	else {
	nodeTo = d3.select(this);

	dragLine
	.classed('hidden', true);

	var fromId = nodeFrom.data()[0].id;
	var toId = nodeTo.data()[0].id;

	if(!graph.hasEdge(fromId, toId)) {
	svg.append('line')
	.attr('class', 'edge')
	.attr('x1', nodeFrom.data()[0].x)
	.attr('y1', nodeFrom.data()[0].y)
	.attr('x2', nodeTo.data()[0].x)
	.attr('y2', nodeTo.data()[0].y);

	graph.addEdge(fromId, toId);
	}

	nodeFrom.moveToFront();
	nodeTo.moveToFront();

	nodeFrom = false;
	nodeTo = false;
	SELECTING = false;

	updateDisplay();
	}
	});

	updateDisplay();

	function updateDisplay() {
	document.getElementById('number-nodes').innerHTML =
	graph.numberNodes().toString();
	document.getElementById('number-edges').innerHTML =
	graph.numberEdges().toString();
	document.getElementById('avg-path-length').innerHTML =
	d3.round(graph.averagePathLength(), 2).toString();
	}

	function polarToCartesian(r, theta) {
	var x = r * Math.cos(theta);
	var y = r * Math.sin(theta);
	return [x, y];
	}
	</script>
	</html>