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/24 00:05]
will Working code.
algorithm:dijkstras [2016/06/28 22:59] (current)
will Fix showing incorrect highlighted edge.
Line 10: Line 10:
     });     });
     ​     ​
 +    // 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) {
 +        // Pop the closest node from `openQueue`.
         var node = openQueue.dequeue();​         var node = openQueue.dequeue();​
 +        var nodeDistance = distances.get(node);​
         ​         ​
         for (var i=0, c=node.edges.length;​ i<c; i++) {         for (var i=0, c=node.edges.length;​ i<c; i++) {
-            var newDistance = distances.get(node) ​+ node.edges[i].distance;​+            var newDistance = nodeDistance ​+ node.edges[i].distance;​
             var target = node.edges[i].target;​             var target = node.edges[i].target;​
             if (!distances.has(target)) {             if (!distances.has(target)) {
Line 25: Line 28:
             }             }
             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);​
-                openQueue.sort(); // Resort the priority queue.+                openQueue.update(target);
             }             }
         }         }
     }     }
 +    ​
     return distances;     return distances;
 }</​syntax>​ }</​syntax>​
Line 68: Line 73:
         return result;         return result;
     },     },
-    ​sort: function() {+    ​update: function(x) {
         this.data.sort(this.comparator);​         this.data.sort(this.comparator);​
     },     },
Line 74: Line 79:
     return this.data.length;​     return this.data.length;​
  }  }
-};</​syntax>​+}; 
 + 
 +function run(graph) { 
 +    result = dijkstra(graph);​ 
 +
 +</​syntax>​
  
 ======= Tests ======= ======= Tests =======
Line 112: Line 122:
 { {
     "​title":"​Dijkstras",​     "​title":"​Dijkstras",​
-    "​height":"​360px"+    "​height":"​430px"
 } }
 </​syntax>​ </​syntax>​
Line 120: 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 135: 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.1464073516.txt.gz · Last modified: 2016/05/24 00:05 by will