User Tools

Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
algorithm:dijkstras [2016/05/23 23:44]
will
algorithm:dijkstras [2016/06/28 22:59] (current)
will Fix showing incorrect highlighted edge.
Line 6: Line 6:
 function dijkstra(source) { function dijkstra(source) {
     var distances = new Map();     var distances = new Map();
-    var openQueue = new PriorityQueue(function(a,​b) {return distances.get(a) - distances.get(b);​});​+    var openQueue = new PriorityQueue(function(a,​b) { 
 +        ​return distances.get(a) - distances.get(b);​ 
 +    ​});
     ​     ​
 +    // Add the `source` node with a distance of 0 to the sets.
     distances.set(source,​ 0);     distances.set(source,​ 0);
     openQueue.enqueue(source);​     openQueue.enqueue(source);​
     ​     ​
     while (openQueue.length > 0) {     while (openQueue.length > 0) {
-        var = openQueue.dequeue();​+        ​// Pop the closest node from `openQueue`. 
 +        ​var node = openQueue.dequeue(); 
 +        var nodeDistance = distances.get(node);
         ​         ​
-        for (var i=0, c=u.edges.count; i<c; i++) { +        for (var i=0, c=node.edges.length; i<c; i++) { 
-            var newDistance = distances.get(u) ​u.edges[i].distance;​ +            var newDistance = nodeDistance ​node.edges[i].distance;​ 
-            var target = u.edges.target;​+            var target = node.edges[i].target;
             if (!distances.has(target)) {             if (!distances.has(target)) {
 +                // Enqueue a new node with `newDistance`.
                 distances.set(target,​ newDistance);​                 distances.set(target,​ newDistance);​
-                ​openSet.enqueue(target);​+                ​openQueue.enqueue(target);​
             }             }
             else if (newDistance < distances.get(target)) {             else if (newDistance < distances.get(target)) {
 +                // Update the queue with a new priority for `target`.
                 distances.set(target,​ newDistance);​                 distances.set(target,​ newDistance);​
-                ​openSet.sort();+                ​openQueue.update(target);
             }             }
         }         }
     }     }
 +    ​
 +    return distances;
 }</​syntax>​ }</​syntax>​
  
Line 64: Line 73:
         return result;         return result;
     },     },
-    ​sort: function() {+    ​update: function(x) {
         this.data.sort(this.comparator);​         this.data.sort(this.comparator);​
-    } +    ​}, 
-};</​syntax>​+    get length() { 
 +    return this.data.length;​ 
 +
 +}; 
 + 
 +function run(graph) { 
 +    result = dijkstra(graph);​ 
 +
 +</​syntax>​
  
 ======= Tests ======= ======= Tests =======
Line 75: Line 92:
     var nodeB = {hash:"​B"​};​     var nodeB = {hash:"​B"​};​
     var nodeC = {hash:"​C"​};​     var nodeC = {hash:"​C"​};​
 +    var nodeD = {hash:"​D"​};​
     ​     ​
-    nodeA.edges = [{target:​nodeB,​ distance:20}, {target:​nodeC,​ distance:70}]; +    ​ 
-    nodeB.edges = [{target:​nodeA,​ distance:20}, {target:​nodeC,​ distance:40}]; +    /*  A--2---B 
-    nodeC.edges = [{target:​nodeA,​ distance:70}, {target:​nodeB,​ distance:40}];+        |\    /| 
 +        | \  4 | 
 +        7  \/  2 
 +        |  /\  | 
 +        | /  3 | 
 +        |/    \| 
 +        C---4--D 
 +    */ 
 +     
 +    ​nodeA.edges = [{target:​nodeB,​ distance:2}, {target:​nodeC,​ distance:7}, {target:​nodeD,​ distance:3}]; 
 +    nodeB.edges = [{target:​nodeA,​ distance:2}, {target:​nodeC,​ distance:4}, {target:​nodeD,​ distance:2}]; 
 +    nodeC.edges = [{target:​nodeA,​ distance:7}, {target:​nodeB,​ distance:4}, {target:​nodeD,​ distance:​4}];​ 
 +    nodeD.edges = [{target:​nodeA,​ distance:​3},​ {target:​nodeB,​ distance:​2},​ {target:​nodeC,​ distance:4}];
     ​     ​
     var result = dijkstra(nodeA);​     var result = dijkstra(nodeA);​
-    assert(result.get(nodeA) === 0); +    assert(result.get(nodeA) === 0, "​A->​A = 0"); 
-    assert(result.get(nodeB) === 20); +    assert(result.get(nodeB) === 2, "​A->​B = 2"); 
-    assert(result.get(nodeC) === 60);+    assert(result.get(nodeC) === 6, "​A->​C = 6"); 
 +    assert(result.get(nodeD) === 3, "​A->​D = 3");
 } }
 </​syntax>​ </​syntax>​
Line 91: Line 122:
 { {
     "​title":"​Dijkstras",​     "​title":"​Dijkstras",​
-    "​height":"​250px"+    "​height":"​430px"
 } }
 </​syntax>​ </​syntax>​
Line 99: Line 130:
 <​html>​ <​html>​
 <​head>​ <​head>​
 +<style type="​text/​css">​
 +path {
 +  fill: #ddd;
 +  fill-opacity:​ .8;
 +  stroke: #fff;
 +  stroke-width:​ 1px;
 +}
 +circle {
 +  stroke-width:​ 1px;
 +  stroke: #444;
 +}
 +circle.current {
 +  stroke-width:​ 2px;
 +  r: 6;
 +}
 +circle.source {
 +  fill: red;
 +}
 +line {
 +  stroke: #999;
 +}
 +line.notused {
 +  stroke-dasharray:​ 5,5;
 +}
 +line.checking {
 +  stroke: black;
 +  stroke-width:​ 2px;
 +}
 +line.selected {
 +  stroke-width:​ 2px;
 +}
 +</​style>​
 +<script src="​http://​d3js.org/​d3.v3.min.js"></​script>​
 <​script>​ <​script>​
-/* Optional functions+var nodes = []; 
 +var links = []; 
 +var svg; 
 + 
 +function buildGraph() { 
 +    svg = d3.select("​body"​).append("​svg:​svg"​) 
 +            .attr("​width",​ 300) 
 +            .attr("​height",​ 350); 
 + 
 +    newGraph();​ 
 +
 + 
 +function newGraph() { 
 +nodes = []; 
 +links = []; 
 +var numNodes = 7+Math.floor(Math.random()*5);​ 
 +for (var i=0; i<​numNodes;​ i++) { 
 +    var node, isOK; 
 +     
 +    do { 
 +        node = [10+Math.random()*280,​ 30+Math.random()*280];​ 
 +        isOK = true; 
 +        for (var j=0; j<​nodes.length;​ j++) { 
 +            var dx = node[0] - nodes[j][0],​ dy = node[1] - nodes[j][1];​ 
 +            if (dx * dx + dy * dy < 15*15) { 
 +                isOK = false; 
 +                break; 
 +            } 
 +        } 
 +    } 
 +    while (!isOK) 
 +     
 +    node.edges = []; 
 +    node.hash = "​node:"​+i;​ 
 +    nodes.push(node);​ 
 +
 + 
 +var edge = function(a, b) { 
 +  var dx = a[0] - b[0], dy = a[1] - b[1]; 
 +  return { 
 +    source: a, 
 +    target: b, 
 +    distance: Math.sqrt(dx * dx + dy * dy) 
 +  }; 
 +
 +var hasEdge = function(a, b) { 
 +    for (var i=0, c=links.length;​i<​c;​i++) { 
 +        if ((links[i].source === a && links[i].target === b) || (links[i].source === b && links[i].target === a)) 
 +            return true; 
 +    } 
 +    return false; 
 +
 + 
 +d3.geom.delaunay(nodes).forEach(function(d) { 
 +    if (!hasEdge(d[0],​ d[1])) links.push(edge(d[0],​ d[1])); 
 +    if (!hasEdge(d[1],​ d[2])) links.push(edge(d[1],​ d[2])); 
 +    if (!hasEdge(d[2],​ d[0])) links.push(edge(d[2],​ d[0])); 
 +  }); 
 +     
 +    ​// Remove a bunch of random edges. 
 +    var toRemove = 2+Math.random()*numNodes/​2;​ 
 +    for (var i=0; i<​toRemove;​ i++) { 
 +        links.splice(Math.random()*(links.length-1),​ 1); 
 +    } 
 +     
 +    // Add all links to the nodes. 
 +    links.forEach(function(l) { 
 + l.source.edges.push(l);​ 
 +        var inverse = edge(l.target,​l.source);​ 
 +        inverse.inverse = l; 
 +        l.target.edges.push(inverse);​ 
 +    }); 
 + 
 +        svg.selectAll("​line"​).remove();​ 
 +        svg.selectAll("​circle"​).remove();​ 
 +         
 +var link = svg.selectAll("​line"​).data(links);​ 
 +link.enter().append("​svg:​line"​);​ 
 +link 
 +      .attr("​x1",​ function(d) { return d.source[0];​ }) 
 +      .attr("​y1",​ function(d) { return d.source[1];​ }) 
 +      .attr("​x2",​ function(d) { return d.target[0];​ }) 
 +      .attr("​y2",​ function(d) { return d.target[1];​ }); 
 + 
 +  var node = svg.selectAll("​g"​).data(nodes);​ 
 +  node.enter() 
 +      .append("​circle"​) 
 +      .attr("​r",​ 4); 
 + 
 +    node.attr("​cx",​ function(d) { return d[0]; }) 
 +        .attr("​cy",​ function(d) { return d[1]; }); 
 +     
 +    if (window.reset) reset(); 
 +
 + 
 +window.onload = buildGraph;
  
 function globals() { function globals() {
-    return {};+    return {result:​undefined};
 } }
 function args() { function args() {
-    return ​null;+    return ​nodes[0];
 } }
-*/ 
  
 function update(n, x, isRunning, duration, prev) { function update(n, x, isRunning, duration, prev) {
Line 114: Line 272:
         return; // State-less visualisation.         return; // State-less visualisation.
     }     }
-    var out = x.lookupInScope("​out"); +    ​ 
-    ​document.body.innerHTML ​= "out = "+JSON.stringify(out);+    ​var distances ​= x.lookupInScope("​distances"​) || x.lookupInScope("​result"); 
 +    ​var sourceNode = x.lookupInScope("​source"​) || nodes[0]; 
 +     
 +    // Update nodes. 
 +    var circle ​svg.selectAll("circle"​).data(nodes);​ 
 +    if (distances) { 
 +        circle.style("​fill",​ function(d) { 
 +            if (distances.has(d)) { 
 +                return "hsl("+(distances.get(d)/​3)+",​100%,​50%)";​ 
 +            } 
 +            else if (d !== sourceNode) { 
 +                return "​black";​ 
 +            } 
 +        }); 
 +    } 
 +    else { 
 +        circle.style("​fill",​ null); 
 +    } 
 +     
 +    // Highlight current node. 
 +    var currentNode = x.lookupInScope("​node"​);​ 
 +    circle.classed("​current",​ function(d) {return d === currentNode;​});​ 
 +     
 +    // Highlight source node. 
 +    circle.classed("​source",​ function(d) {return d === sourceNode;​});​ 
 +     
 +    // Highlight current edge. 
 +    var i = x.lookupInScope("​i"​);​ 
 +    var inInnerLoop = n && n.lineno >= 17 && n.lineno <= 28; 
 +    var link = svg.selectAll("​line"​).data(links);​ 
 +    link.classed("​checking",​ function(d) { 
 +        return (typeof i === "​number"​ && inInnerLoop && currentNode && currentNode.edges.length > i) &&​ 
 +            (currentNode.edges[i] === d || currentNode.edges[i].inverse === d); 
 +    });
 } }
 </​script>​ </​script>​
 </​head>​ </​head>​
 <​body>​ <​body>​
 +<button onclick="​newGraph()"​ style="​position:​absolute;​left:​0px;​top:​0px">​New Graph</​button>​
 </​body>​ </​body>​
 </​html>​ </​html>​
 </​syntax>​ </​syntax>​
 </​nowiki>​ </​nowiki>​
algorithm/dijkstras.1464072262.txt.gz · Last modified: 2016/05/23 23:44 by will