Skip to content

Instantly share code, notes, and snippets.

@jamestrimble

jamestrimble/ Development project experiments

Last active August 29, 2015 13:57
Show Gist options
  • Save jamestrimble/9505933 to your computer and use it in GitHub Desktop.
Save jamestrimble/9505933 to your computer and use it in GitHub Desktop.
Download ZIP
Development project experiments
Raw
README.md

An attempt at implementing Johnson's algorithm for finding elementary circuits (1975) and Tarjan's algorithm for finding strongly-connected components (1972).

Raw
digraphs_main.js
$('.btn').button();
var //width = 960,
height = 350,
radius = 12,
loopSize = 20, // Width in pixels of loop edges
colourScale = d3.scale.category10(),
edgeColour = d3.scale.linear().domain([0,10]).range(["#ccc", "black"]),
drawingArrow = false, // Set to true if one end of an arrow has been drawn
arrowStart, // Start position of the arrow that's being drawn
arrowStartNodeGlobal; // The arrow's starting node
var svg = d3.select("#svg-div")
.append("svg")
//.attr("width", width)
.attr("height", height);
// Arrow end marker
// http://bl.ocks.org/rkirsling/5001347
var arrowHead = function(element) {
element
.attr("class", "arrow-head")
.attr('viewBox', '0 -5 10 10')
.attr('refX', 6)
.attr('markerWidth', 5)
.attr('markerHeight', 5)
.attr('orient', 'auto')
.append('svg:path')
.attr('d', 'M0,-5L10,0L0,5')
.attr('fill', '#000');
}
var svgDefs = svg.append('svg:defs');
svgDefs.append('svg:marker')
.attr('id', 'end-arrow')
.call(arrowHead);
// Light arrow end marker for un-highlighted circuits
svgDefs.append('svg:marker')
.attr('id', 'end-arrow-muted')
.call(arrowHead)
.classed("arrow-head-muted", true);
// Just shown when an arrow is being drawn
var dashedArrow = svg.append("path")
.attr('class', 'dashed-arrow')
.style('marker-end', 'url(#end-arrow)');
// The graph (in standard JSON format, with extra elements for the d3 circle selectors)
var G = {};
var fullJson = {"data" : G};
// Display the pretty-printed JSON,
// highlight the connected components,
// and show the list of circuits
var displayJson = function() {
$('#circuit-output').show();
$('#json-output').show();
$('.initially-hidden').show();
var fullJson_clone = JSON.parse(JSON.stringify(fullJson)); // Clone graph for printing
for (v in fullJson_clone.data) {
delete fullJson_clone.data[v].svgCircle;
delete fullJson_clone.data[v].number;
delete fullJson_clone.data[v].lowLink;
delete fullJson_clone.data[v].id;
delete fullJson_clone.data[v].onStack;
}
$('#json-output').html(JSON.stringify(fullJson_clone, undefined, 4));
connectedComps = tarjan(G).components;
console.log(connectedComps);
var colourDomain = [];
for (var i=0; i<connectedComps.length; i++) {
colourDomain.push(i);
}
colourScale.domain(colourDomain);
for (var i=0; i<connectedComps.length; i++) {
for (var j=0; j<connectedComps[i].length; j++) {
connectedComps[i][j].svgCircle
.style("fill", colourScale(i));
}
}
circuits = johnson(G);
d3.select('#circuit-output').selectAll('pre, p').remove();
// Add circuits, with listeners for highlighting on mouse-over
if (circuits.length > 0) {
d3.select('#circuit-output')
.selectAll('pre')
.data(circuits).enter()
.append('pre')
.attr('class', 'circuit-pre')
.text(function(d) {return JSON.stringify(d)})
.on('mouseover', function(d) {
for (v in G) {
if (d.indexOf(+v) != -1 ) { // if this node is in the circuit
G[v].svgCircle.classed('full-opacity', true);
} else {
G[v].svgCircle.classed('muted-circle', true);
}
}
d3.selectAll(".arrow").classed("arrow-muted", true)
.style('marker-end', 'url(#end-arrow-muted)');
for (var i=0; i<d.length-1; i++) {
var arrowStartId = d[i];
var arrowEndId = d[i+1];
d3.selectAll(".arrow")
.filter(function() {return d3.select(this).attr("data-start-node") == arrowStartId})
.filter(function() {return d3.select(this).attr("data-end-node") == arrowEndId})
.classed("arrow-highlight", true)
.classed("arrow-muted", false)
.style('marker-end', 'url(#end-arrow)');
}
})
.on('mouseout', function(d) {
d3.selectAll("circle").classed('muted-circle', false);
d3.selectAll('.node').classed('full-opacity', false);
d3.selectAll(".arrow")
.classed("arrow-highlight", false)
.classed("arrow-muted", false)
.style('marker-end', 'url(#end-arrow)');
});
} else {
// If there are no circuits, show a short message
d3.select('#circuit-output').append('p').text('None');
}
}
// When the SVG is clicked on, add a circle
svg.on("click", function() {
// If the Erase button is selected, don't do anything
if ($("#erase").parent().hasClass("active")) {
return;
}
drawingArrow = false; // We're not drawing an arrow (even if we had selected one point)
dashedArrow.style("visibility", "hidden");
$("#message").css("visibility", "hidden");
d3.selectAll(".node").classed("node-highlight", false);
var coords = d3.mouse(svg[0][0]); // Mouse position on SVG
var node = svg.append("circle")
.attr("cx", coords[0])
.attr("cy", coords[1])
.attr("r", radius)
.attr("class", "node");
var maxNodeId = 0;
for (v in G) {
maxNodeId = Math.max(maxNodeId, +v); // Max ID of nodes created so far
}
var nodeId = maxNodeId + 1;
node.attr('data-nodeid', nodeId);
var graphNode = {"matches": [], "svgCircle": node}; // Add to the "JSON" graph
G['' + nodeId] = graphNode;
var nodeNumSvg = svg.append("text")
.attr("x", coords[0])
.attr("y", coords[1])
.text(nodeId)
.attr("class", "node-num");
displayJson(); // Re-run the algorithms with the new circle
node.on("click", function() {
d3.event.stopPropagation(); // If a circle has been clicked, don't create a new circle
if ($("#add_elements").parent().hasClass("active")) { // If we're in drawing mode, start creating an arrow
if (!drawingArrow) { // If first node of edge hasn't been clicked...
dashedArrow.style("visibility", "visible");
arrowStartNodeGlobal = graphNode;
drawingArrow = true;
arrowStart = coords;
$("#message").text("Click endpoint of edge");
$("#message").css("visibility", "visible");
node.classed("node-highlight", true);
} else { // Finish off edge
dashedArrow.style("visibility", "hidden");
var arrowStartNode = arrowStartNodeGlobal;
existingLinksHere = arrowStartNode.matches.filter(function(x) {
return x.recipient==nodeId;
}).length;
if ( (!existingLinksHere) ) {
drawingArrow = false;
$("#message").css("visibility", "hidden");
d3.selectAll(".node").classed("node-highlight", false);
var arrowEnd = coords;
if (arrowStartNode != graphNode) { // If edge isn't a loop
var lineLength = Math.sqrt( Math.pow(arrowEnd[0]-arrowStart[0],2)
+ Math.pow(arrowEnd[1]-arrowStart[1],2));
var lineUnitVectorX = (arrowEnd[0]-arrowStart[0]) / lineLength;
var lineUnitVectorY = (arrowEnd[1]-arrowStart[1]) / lineLength;
var arrowStartX = arrowStart[0] + radius * lineUnitVectorX;
var arrowStartY = arrowStart[1] + radius * lineUnitVectorY;
var arrowEndX = arrowEnd[0] - radius * lineUnitVectorX;
var arrowEndY = arrowEnd[1] - radius * lineUnitVectorY;
var arrowPath = 'M' + arrowStartX + ',' + arrowStartY
+ 'L' + arrowEndX + ',' + arrowEndY;
} else { // If edge is a loop
var arrowStartX = arrowStart[0] + radius;
var arrowStartY = arrowStart[1];
var arrowEndX = arrowStart[0] + Math.sqrt(radius*radius);
var arrowEndY = arrowStart[1] + Math.sqrt(radius*radius);
var arrowPath = 'M' + arrowStartX + ',' + arrowStartY
+ 'L' + (arrowStartX + loopSize) + ',' + arrowStartY
+ 'L' + (arrowStartX + loopSize/2) + ',' + (arrowStartY + loopSize)
+ 'L' + arrowEndX + ',' + arrowEndY
}
var edgeWeight = +$("#weight-input").val();
var arrow = svg.append("path")
.style("stroke", edgeColour(edgeWeight))
.style('marker-end', 'url(#end-arrow)')
.attr('d', arrowPath)
.attr("class", "arrow")
.attr("data-start-node", arrowStartNode.id)
.attr("data-end-node", graphNode.id);
arrowStartNode.matches.push({"recipient": nodeId, "score": edgeWeight});
displayJson();
arrow.on("click", function() {
if ($("#erase").parent().hasClass("active")) {
d3.event.stopPropagation();
arrow.style("visibility", "hidden");
for (var i=0; i<arrowStartNode.matches.length; i++) {
if (arrowStartNode.matches[i].recipient==nodeId) {
arrowStartNode.matches.splice(i, 1);
break;
}
}
displayJson();
}
});
}
}
} else { // Delete node
node.style("visibility", "hidden");
nodeNumSvg.style("visibility", "hidden");
delete G['' + nodeId];
for (v in G) {
for (var i=0; i<G[v].matches.length; i++) {
if (G[v].matches[i].recipient==nodeId) {
G[v].matches.splice(i, 1);
i--;
}
}
}
displayJson();
}
});
});
svg.on("mousemove", function() {
if (drawingArrow) { // Move the dashed arrow
var coords = d3.mouse(svg[0][0]);
var edgeWeight = +$("#weight-input").val();
dashedArrow
.style("stroke", edgeColour(edgeWeight))
.attr('d', 'M' + arrowStart[0] + ',' + arrowStart[1]
+ 'L' + coords[0] + ',' + coords[1]);
}
});
// Run the algorithms on the second (paste JSON) tab
$('#json-button').click(function() {
var json = $('#json-input').val();
try {
var inputG = JSON.parse(json);
$('#invalid-json-message').css('visibility', 'hidden');
var validJson = true;
} catch (e) {
$('#invalid-json-message').css('visibility', 'visible');
var validJson = false;
}
if (validJson) {
var components = tarjan(inputG.data).components;
var simpleComponents = components
.map(function(x) {
return x.map(function(y) {
return +y.id;
})
});
var circuits = johnson(inputG.data);
var adjacencies = {};
for (v_id in inputG.data) {
if (inputG.data[v_id].hasOwnProperty("matches")) {
adjacencies[v_id] = inputG.data[v_id].matches.map(function(x) {
return x.recipient;
});
} else {
adjacencies[v_id] = [];
}
}
$('#json-adjacency-list').text(JSON.stringify(adjacencies).replace(/,"/g, ',\n "'));
$('#json-components').text(JSON.stringify(simpleComponents).replace(/,\[/g, ',\n [').replace("]]", "]\n]"));
$('#json-circuits').text(JSON.stringify(circuits).replace(/,\[/g, ',\n [').replace("]]", "]\n]"));
}
});
/*d3.json("input_modified.json", function(data) {
var G2 = data.data;
})*/
Raw
index.html
<html>
<head>
<meta charset="UTF-8">
<script src="tarjan.js"></script>
<script src="subgraph.js"></script>
<script src="johnson.js"></script>
<script src="http://d3js.org/d3.v3.min.js" charset="utf-8"></script>
<link rel="stylesheet" href="http://netdna.bootstrapcdn.com/bootstrap/3.1.1/css/bootstrap.min.css">
<link rel="stylesheet" href="http://netdna.bootstrapcdn.com/bootstrap/3.1.1/css/bootstrap-theme.min.css">
<link href="style.css" rel="stylesheet" type="text/css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script>
<script src="http://netdna.bootstrapcdn.com/bootstrap/3.1.1/js/bootstrap.min.js"></script>
</head>
<body>
<div class="container">
<!-- Nav tabs -->
<ul class="nav nav-tabs">
<li class="active"><a href="#editor" data-toggle="tab">Directed graph editor</a></li>
<li><a href="#paste-json" data-toggle="tab">Paste JSON</a></li>
</ul>
<!-- Tab panes -->
<div class="tab-content">
<div class="tab-pane active" id="editor">
<h2>Directed graph editor</h2>
<p>
The vertices of each strongly connected component are displayed in a single colour.
Elementary circuits are listed below the graph.
</p>
<div class="row">
<div class="col-sm-4">
<div class="btn-group" data-toggle="buttons">
<label class="btn btn-primary active">
<input type="radio" name="options" id="add_elements"> Add
</label>
<label class="btn btn-primary">
<input type="radio" name="options" id="erase"> Erase
</label>
</div>
</div>
<div class="col-sm-8">
<div class="form-group">
<label for="weight-input" class="col-sm-3 control-label">Weight for new edges (1-10):</label>
<div class="col-sm-2">
<input class="form-control" id="weight-input" value="5"></input>
</div>
</div>
</div>
</div>
<div id="svg-div"></div>
<div class="alert alert-info" id="message"></div>
<h4 class="initially-hidden">Elementary circuits (mouse over list to highlight on graph)</h4>
<div id="circuit-output"></div>
<h4 class="initially-hidden">Graph in JSON format</h4>
<pre id="json-output"></pre>
</div>
<div class="tab-pane" id="paste-json">
<h2>Paste JSON</h2>
<p>
Paste input below in JSON format (<a href="http://kidney.optimalmatching.com/api/input_format#json">API documentation</a>).
</p>
<textarea class="form-control" id="json-input" rows="10"></textarea>
<button type="button" class="btn btn-primary" id='json-button'>Find strongly connected components and circuits</button>
<div class="alert alert-warning" id="invalid-json-message">Invalid JSON</div>
<h4>Adjacency list</h4>
<p>An edge is added to each altruistic donor from each vertex not labelled as altruistic.</p>
<pre id='json-adjacency-list'></pre>
<h4>Strongly connected components</h4>
<pre id='json-components'></pre>
<h4>Elementary circuits</h4>
<pre id='json-circuits'></pre>
</div>
</div>
</div>
<script src="digraphs_main.js"></script>
</body>
</html>
Raw
input_modified.json
{
"data": {
"1": {
"matches": [
{
"recipient": 4,
"score": 1
}
]
},
"2": {
"matches": [
{
"recipient": 1,
"score": 1
}
]
},
"3": {
"matches": [
{
"recipient": 2,
"score": 1
}
]
},
"4": {
"matches": [
{
"recipient": 3,
"score": 1
},
{
"recipient": 5,
"score": 1
}
]
},
"5": {
"matches": [
{
"recipient": 6,
"score": 1
},
{
"recipient": 4,
"score": 1
}
]
},
"6": {
"matches": [
{
"recipient": 5,
"score": 1
}
]
}
}
}
Raw
johnson.js
var adjacencyStructure = function(cc) {
// Parameter G: a connected componenent (array of arrays from the tarjan() function)
// Returns an object A of adjacency lists.
// The first n-1 elements of A will be empty if G is a subgraph.
var A = {},
vertex_ids = [];
for(var i=0; i<cc.length; i++) {
vertex_ids.push(+cc[i].id);
}
for(var i=0; i<cc.length; i++) {
v_id = vertex_ids[i];
A[v_id] = [];
for (var j=0,last=cc[i].matches.length; j<last; j++) {
recipient = cc[i].matches[j].recipient;
if (vertex_ids.indexOf(recipient) != -1) { // if recipient vertex is in the graph
A[v_id].push(recipient);
}
}
}
//console.log("A")
//console.log(JSON.stringify(A, undefined,2));
return A;
}
var johnson = function(G) {
console.log("starting Johnson's algorithm")
var A_K, // an object of arrays
B = {}, // B will be an object of arrays
blocked = [],
stack = [],
s = 1,
circuits = []; // The function's return value
console.log("abc")
var circuit = function(v) {
var unblock = function(u) {
blocked[u] = false;
for (var i=0,last=B[u].length; i<last; i++) {
w = B[u][i];
console.log("w " + w)
console.log("B[u] before " + JSON.stringify(B[u]))
B[u].splice(i, 1); // delete w from B[u]
console.log("B[u] after " + JSON.stringify(B[u]))
if (blocked[w]) { unblock(w); }
}
}
var f = false;
stack.push(v);
blocked[v] = true;
console.log("A_K");
console.log(A_K);
A_K[v].forEach(function(w) {
if (w==s) {
circuitOut = stack.slice(0); // copy stack
circuitOut.push(s);
circuits.push(circuitOut);
f = true;
} else if (!blocked[w] && circuit(w)) {
f = true;
}
});
if (f) {
unblock(v);
} else {
A_K[v].forEach(function(w) {
console.log("B[w]");
console.log(JSON.stringify(B[w]));
if (B[w].indexOf(v) == -1) {
B[w].push(v);
}
});
}
// UNSTACK V
testVar = stack.pop();
if (testVar != v) {alert("check unstack v");}
return f;
}
var n = 0; // number of vertices
for (v_id in G) {
if (G.hasOwnProperty(v_id)) {
n += 1;
} else {
alert("The graph object has inherited properties. The algorithm may not work correctly");
}
}
while (s < n) {
//var subgraph_s = subgraph(G, s);
var cc = tarjan(subgraph(G, s));
/*console.log("G2 :-)")
console.log(G);
console.log("subgraph...")
console.log(s);
console.log(subgraph(G, s));*/
console.log("cc")
console.log(JSON.stringify(cc, undefined,2));
if (cc.compWithLeastVertex != null) {
var smallestCC = cc.components[cc.compWithLeastVertex];
A_K = adjacencyStructure(smallestCC);
console.log(" A_K");
console.log(A_K);
s = cc.leastVertexInAComp;
for (v_id in A_K) {
blocked[+v_id] = false;
B[v_id] = [];
}
//console.log(s);
circuit(s);
s += 1;
} else {
s = n;
}
}
console.log(JSON.stringify(circuits));
return circuits;
}
Raw
style.css
body {
padding-top: 8px;
}
#svg-div {
margin-top: 12px;
margin-bottom: 12px;
background: #eee;
}
#invalid-json-message {
visibility: hidden;
}
.initially-hidden {
display: none;
}
svg {
border: 1px solid #aaa;
width:100%;
}
.node {
stroke-width: 1px;
stroke: #444;
fill: steelblue;
fill-opacity: 0.45;
cursor: pointer;
}
.node:hover {
fill-opacity: 0.7;
}
circle.node-highlight {
fill-opacity: 0.7;
}
circle.full-opacity {
fill-opacity: 1;
}
circle.muted-circle {
fill-opacity: 0.15;
stroke-opacity: 0.4;
}
path {
fill: none;
stroke: black;
stroke-width: 2px;
cursor: pointer;
}
#end-arrow {
opacity:1;
}
.arrow-head-muted {
opacity: 0.15;
}
.dashed-arrow {
stroke-dasharray: 5, 5;
visibility: hidden;
}
.arrow-muted {
stroke-opacity: 0.3;
}
.arrow-highlight {
/* stroke-opacity: 1;*/
}
#message {
visibility:hidden;
}
#json-output {
display: none;
}
#circuit-output {
min-height: 40px;
}
.circuit-pre {
display: inline-block;
margin-right: 10px;
}
.node-num {
dominant-baseline: central;
text-anchor: middle;
pointer-events: none;
}
#json-button {
margin-top:8px;
margin-bottom:8px;
}
Raw
subgraph.js
var subgraph = function(G, minId) {
var subG = {};
for(v_id in G) {
if (+v_id >= minId) {
subG[v_id] = {}; //splice(G[v_id], 0); // Copy object
//console.log(G[v_id]);
if (G[v_id].hasOwnProperty('matches')) {
subG[v_id].matches = G[v_id].matches.filter(function(x) {
return x.recipient >= minId;
});
} else {
subG[v_id].matches = [];
}
}
}
//console.log(JSON.stringify(subG));
return subG;
}
Raw
tarjan.js
// Returns an object with fields:
// components: an array of components (with each component as an array)
// compWithLeastVertex: the index of the component with least vertex
var tarjan = function(G) {
var sccList = [],
compWithLeastVertex = null, // The index of the strong component with at least
// two vertices with the least vertex (for Johnson)
leastVertexInAComponentSoFar = Infinity;
for(v_id in G) {
G[v_id].id = v_id;
G[v_id].matches = G[v_id].matches || [];
G[v_id].number = null;
G[v_id].onStack = false;
}
for(v_id in G) {
if (G[v_id].altruistic) {
for (w in G) {
if (w != v_id && !G[w].altruistic) {
G[w].matches.push({"recipient":+v_id, "score":-1});
}
}
}
}
var i=0;
var stack = [];
var strongConnect = function(v) {
i += 1;
v.lowLink = v.number = i;
if (stack.indexOf(v) != -1) alert("Possible error!");
stack.push(v);
v.onStack = true;
for (var j=0; j<v.matches.length; j++) {
var w = G[v.matches[j].recipient + ''];
if (w.number === null) {
strongConnect(w);
v.lowLink = Math.min(v.lowLink, w.lowLink);
} else if (w.onStack) {
// Using Wikipedia version (since the test for w.number < v.number seems unnecessary)
v.lowLink = Math.min(v.lowLink, w.number);
}
}
if (v.lowLink === v.number) {
var component = [];
sccList.push(component);
var leastVertexInThisComponent = Infinity;
while (stack.length && stack[stack.length-1].number >= v.number ) {
stack[stack.length-1].onStack = false;
leastVertexInThisComponent = Math.min(leastVertexInThisComponent,
+stack[stack.length-1].id);
component.push(stack.pop());
}
// Save index of component with least vertex
if (component.length > 1
&& leastVertexInThisComponent < leastVertexInAComponentSoFar) {
leastVertexInAComponentSoFar = leastVertexInThisComponent;
compWithLeastVertex = sccList.length - 1;
}
}
}
for(v_id in G) {
//console.log("node " + v_id);
if (!G[v_id].number) {
strongConnect(G[v_id]);
}
//console.log(G[v].id);
}
//console.log({components: sccList, compWithLeastVertex: compWithLeastVertex});
return {components: sccList,
compWithLeastVertex: compWithLeastVertex,
leastVertexInAComp: leastVertexInAComponentSoFar
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment