Merge lp:~stothardj/dracula/nonodelist into lp:dracula

[Jake Stothard]

* Removed redundant nodelist data structure.
* Removed redundant "backedges" when undirected graphs are made. Instead add a reference to the same edge to both nodes. Modified algorithm functions to work with this.
* Made removeNode work.
* Added Topological sort algorithm.
* Added ordered layout to show of topological sort.

[Johann Philipp Strathausen (strathausen)]

Hi there, thanks a lot for the merge request! I was travelling last week, so I didn't have a look at it yet. But I think I'll approve it soon.

[Jake Stothard (stothardj)]

Hey, no problem. Hope you don't mind that a lot of the patch is just from my
text editor tabbing differently. Anyway, I'll be around if you want to ask
me about any of the changes.

On Tue, Nov 2, 2010 at 5:11 AM, Filip <email address hidden> wrote:

> Hi there, thanks a lot for the merge request! I was travelling last week,
> so I didn't have a look at it yet. But I think I'll approve it soon.
> --
> https://code.launchpad.net/~stothardj/dracula/nonodelist/+merge/39216<https://code.launchpad.net/%7Estothardj/dracula/nonodelist/+merge/39216>
> You are the owner of lp:~stothardj/dracula/nonodelist.
>

[Johann Philipp Strathausen (strathausen)]

Yes, I have a first question after a first glance at the diff: Is the jQuery dependency really necessary? I like jQuery and use it for most of my projects anyway, but otherwise I wanted to keep the dependencies as minimal as possible. Like for example, there used to be a Prototype dependency just for using class structures, until I figured out that using plain JavaScript prototype and such would do the same with the same amount of code.

So, if you really think jQuery is a big help here and it's not possible without it, I will leave the jQuery code in Dracula.

[Jake Stothard (stothardj)]

Short answer: No, you can pull it out.

I thought I'd be using jQuery for more in this, but it seems not to be
necessary actually. I was using jQuery.extend to make copies, but I saw you
had a clone function so if that works that can be used. The other thing was
using jQuery to get the window size in the demos, which again is replacable.
That's all I can see that I used.

On Wed, Nov 3, 2010 at 2:34 AM, Filip <email address hidden> wrote:

> Yes, I have a first question after a first glance at the diff: Is the
> jQuery dependency really necessary? I like jQuery and use it for most of my
> projects anyway, but otherwise I wanted to keep the dependencies as minimal
> as possible. Like for example, there used to be a Prototype dependency just
> for using class structures, until I figured out that using plain JavaScript
> prototype and such would do the same with the same amount of code.
>
> So, if you really think jQuery is a big help here and it's not possible
> without it, I will leave the jQuery code in Dracula.
> --
> https://code.launchpad.net/~stothardj/dracula/nonodelist/+merge/39216<https://code.launchpad.net/%7Estothardj/dracula/nonodelist/+merge/39216>
> You are the owner of lp:~stothardj/dracula/nonodelist.
>

[Johann Philipp Strathausen (strathausen)]

Okay, looks fine to me :-) thanks for the work! I will merge it now and remove the dependence of jQuery later...

review: Approve

=== added file 'algorithms.js'
--- algorithms.js	1970-01-01 00:00:00 +0000
+++ algorithms.js	2010-10-24 05:37:41 +0000
@@ -0,0 +1,102 @@
+var redraw;
+
+window.onload = function() {
+    var width = $(document).width();
+    var height = $(document).height() - 100;
+
+    /* Showcase of the Bellman-Ford search algorithm finding shortest paths 
+       from one point to every node */
+    
+    /*  */
+
+    /* We need to write a new node renderer function to display the computed
+       distance.
+       (the Raphael graph drawing implementation of Dracula can draw this shape,
+       please consult the RaphaelJS reference for details http://raphaeljs.com/) */
+    var render = function(r, n) {
+            /* the Raphael set is obligatory, containing all you want to display */
+            var set = r.set().push(
+                /* custom objects go here */
+                r.rect(n.point[0]-30, n.point[1]-13, 60, 44).attr({"fill": "#feb", r : "12px", "stroke-width" : n.distance == 0 ? "3px" : "1px" })).push(
+                r.text(n.point[0], n.point[1] + 10, (n.label || n.id) + "\n(" + (n.distance == undefined ? "Infinity" : n.distance) + ")"));
+            return set;
+        };
+    
+    var g = new Graph();
+    
+    /* modify the edge creation to attach random weights */
+    g.edgeFactory.build = function(source, target) {
+	var e = jQuery.extend(true, {}, this.template);
+	e.source = source;
+	e.target = target;
+	e.style.label = e.weight = Math.floor(Math.random() * 10) + 1;
+	return e;
+    }
+    
+    /* creating nodes and passing the new renderer function to overwrite the default one */
+    g.addNode("New York", {render:render}); // TODO add currying support for nicer code
+    g.addNode("Berlin", {render:render});
+    g.addNode("Tel Aviv", {render:render});
+    g.addNode("Tokyo", {render:render});
+    g.addNode("Roma", {render:render});
+    g.addNode("Madrid", {render:render});
+
+    /* connections */
+    g.addEdge("Tokyo", "Tel Aviv"/*, {weight:9, directed: true, stroke : "#bfa"}*/); // also supports directed graphs, but currently doesn't look that nice
+    g.addEdge("Tokyo", "New York");
+    g.addEdge("Tokyo", "Berlin");
+    g.addEdge("Tel Aviv", "Berlin");
+    g.addEdge("Tel Aviv", "New York");
+    g.addEdge("Tel Aviv", "Roma");
+    g.addEdge("Roma", "New York");
+    g.addEdge("Berlin", "New York");
+    g.addEdge("Madrid", "New York");
+    g.addEdge("Madrid", "Roma");
+    g.addEdge("Madrid", "Tokyo");
+
+    /* random edge weights (our undirected graph is modelled as a bidirectional graph) */
+/*    for(e in g.edges)
+        if(g.edges[e].backedge != undefined) {
+            g.edges[e].weight = Math.floor(Math.random()*10) + 1;
+            g.edges[e].backedge.weight = g.edges[e].weight;
+        }
+*/
+    /* layout the graph using the Spring layout implementation */
+    var layouter = new Graph.Layout.Spring(g);
+    
+    /* draw the graph using the RaphaelJS draw implementation */
+
+    /* calculating the shortest paths via Bellman Ford */
+//    bellman_ford(g, g.nodes["Berlin"]);
+    
+    /* calculating the shortest paths via Dijkstra */
+    dijkstra(g, g.nodes["Berlin"]);
+    
+    /* calculating the shortest paths via Floyd-Warshall */
+    floyd_warshall(g, g.nodes["Berlin"]);
+
+
+    /* colourising the shortest paths and setting labels */
+    for(e in g.edges) {
+        if(g.edges[e].target.predecessor === g.edges[e].source || g.edges[e].source.predecessor === g.edges[e].target) {
+            g.edges[e].style.stroke = "#bfa";
+            g.edges[e].style.fill = "#56f";
+        } else {
+            g.edges[e].style.stroke = "#aaa";
+        }
+    }
+    
+    var renderer = new Graph.Renderer.Raphael('canvas', g, width, height);
+
+    redraw = function() {
+        layouter.layout();
+        renderer.draw();
+    };
+    
+/*    var pos=0;
+    step = function(dir) {
+        pos+=dir;
+        var renderer = new Graph.Renderer.Raphael('canvas', g.snapshots[pos], width, height);
+        renderer.draw();
+    };*/
+};
\ No newline at end of file

=== added file 'classes.html'
--- classes.html	1970-01-01 00:00:00 +0000
+++ classes.html	2010-10-24 05:37:41 +0000
@@ -0,0 +1,18 @@
+<html>
+<head>
+    <script type="text/javascript" src="js/raphael-min.js"></script>
+    <script type="text/javascript" src="js/dracula_graffle.js"></script>
+    <script type="text/javascript" src="js/jquery-1.4.2.min.js"></script>
+    <script type="text/javascript" src="js/dracula_graph.js"></script>
+    <script type="text/javascript" src="js/dracula_algorithms.js"></script>
+    <script type="text/javascript" src="classes.js"></script>
+    <style type="text/css">
+      body {
+      overflow: hidden;
+      }
+    </style>
+</head>
+<body>
+<div id="canvas"></div>
+</body>
+</html>

=== added file 'classes.js'
--- classes.js	1970-01-01 00:00:00 +0000
+++ classes.js	2010-10-24 05:37:41 +0000
@@ -0,0 +1,23 @@
+//Show UCLA CS class dependencies (not complete)
+$(document).ready(function() {
+    var width = $(document).width();
+    var height = $(document).height();
+    var g = new Graph();
+    g.edgeFactory.template.style.directed = true;
+    g.addEdge("CS 31","CS 32");
+    g.addEdge("CS 32","CS 33");
+    g.addEdge("CS 33","CS 35L");
+    g.addNode("CS M51A");
+    g.addEdge("CS 32", "CS 111");
+    g.addEdge("CS 33", "CS 111");
+    g.addEdge("CS 35L", "CS 111");
+    g.addEdge("CS 32", "CS 118");
+    g.addEdge("CS 33", "CS 118");
+    g.addEdge("CS 35L", "CS 118");
+    g.addEdge("CS 111", "CS 118");
+    g.addEdge("CS 32", "CS 131");
+    g.addEdge("CS 33", "CS 131");
+    g.addEdge("CS 35L", "CS 131");
+    var layouter = new Graph.Layout.Ordered(g, topological_sort(g));
+    var renderer = new Graph.Renderer.Raphael('canvas', g, width, height);
+});
\ No newline at end of file

=== modified file 'dracula_algorithms.html'
--- dracula_algorithms.html	2010-09-17 18:04:25 +0000
+++ dracula_algorithms.html	2010-10-24 05:37:41 +0000
@@ -1,122 +1,20 @@
 <html>
-<head>
-<!-- jQuery -->
+  <head>
+    <!-- jQuery -->
     <script type="text/javascript" src="js/jquery-1.4.2.min.js"></script>
-<!--  The Raphael JavaScript library for vector graphics display  -->
+    <!--  The Raphael JavaScript library for vector graphics display  -->
     <script type="text/javascript" src="js/raphael-min.js"></script>
-<!--  Dracula  -->
-<!--  An extension of Raphael for connecting shapes -->
+    <!--  Dracula  -->
+    <!--  An extension of Raphael for connecting shapes -->
     <script type="text/javascript" src="js/dracula_graffle.js"></script>
-<!--  Graphs  -->
+    <!--  Graphs  -->
     <script type="text/javascript" src="js/dracula_graph.js"></script>
     <script type="text/javascript" src="js/dracula_algorithms.js"></script>
-    <script type="text/javascript">
-<!--
-
-var redraw;
-var height = 300;
-var width = 400;
-
-window.onload = function() {
-
-    /* Showcase of the Bellman-Ford search algorithm finding shortest paths 
-       from one point to every node */
-    
-    /*  */
-
-    /* We need to write a new node renderer function to display the computed
-       distance.
-       (the Raphael graph drawing implementation of Dracula can draw this shape,
-       please consult the RaphaelJS reference for details http://raphaeljs.com/) */
-    var render = function(r, n) {
-            /* the Raphael set is obligatory, containing all you want to display */
-            var set = r.set().push(
-                /* custom objects go here */
-                r.rect(n.point[0]-30, n.point[1]-13, 60, 44).attr({"fill": "#feb", r : "12px", "stroke-width" : n.distance == 0 ? "3px" : "1px" })).push(
-                r.text(n.point[0], n.point[1] + 10, (n.label || n.id) + "\n(" + (n.distance == undefined ? "Infinity" : n.distance) + ")"));
-            return set;
-        };
-    
-    var g = new Graph();
-    /* creating nodes and passing the new renderer function to overwrite the default one */
-    g.addNode("New York", {render:render}); // TODO add currying support for nicer code
-    g.addNode("Berlin", {render:render});
-    g.addNode("Tel Aviv", {render:render});
-    g.addNode("Tokyo", {render:render});
-    g.addNode("Roma", {render:render});
-    g.addNode("Madrid", {render:render});
-
-    /* modify the addEdge function to attach random weights */
-    g.addEdge2 = g.addEdge;
-    g.addEdge = function(from, to, style) { !style && (style={}); style.weight = Math.floor(Math.random()*10) + 1; g.addEdge2(from, to, style); };
-    
-    /* connections */
-    g.addEdge("Tokyo", "Tel Aviv"/*, {weight:9, directed: true, stroke : "#bfa"}*/); // also supports directed graphs, but currently doesn't look that nice
-    g.addEdge("Tokyo", "New York");
-    g.addEdge("Tokyo", "Berlin");
-    g.addEdge("Tel Aviv", "Berlin");
-    g.addEdge("Tel Aviv", "New York");
-    g.addEdge("Tel Aviv", "Roma");
-    g.addEdge("Roma", "New York");
-    g.addEdge("Berlin", "New York");
-    g.addEdge("Madrid", "New York");
-    g.addEdge("Madrid", "Roma");
-    g.addEdge("Madrid", "Tokyo");
-
-    /* random edge weights (our undirected graph is modelled as a bidirectional graph) */
-/*    for(e in g.edges)
-        if(g.edges[e].backedge != undefined) {
-            g.edges[e].weight = Math.floor(Math.random()*10) + 1;
-            g.edges[e].backedge.weight = g.edges[e].weight;
-        }
-*/
-    /* layout the graph using the Spring layout implementation */
-    var layouter = new Graph.Layout.Spring(g);
-    
-    /* draw the graph using the RaphaelJS draw implementation */
-
-    /* calculating the shortest paths via Bellman Ford */
-//    bellman_ford(g, g.nodes["Berlin"]);
-    
-    /* calculating the shortest paths via Dijkstra */
-    dijkstra(g, g.nodes["Berlin"]);
-    
-    /* calculating the shortest paths via Floyd-Warshall */
-    floyd_warshall(g, g.nodes["Berlin"]);
-
-
-    /* colourising the shortest paths and setting labels */
-    for(e in g.edges) {
-        g.edges[e].style = { label : g.edges[e].weight };
-        if(g.edges[e].target.predecessor === g.edges[e].source || g.edges[e].source.predecessor === g.edges[e].target) {
-            g.edges[e].style.stroke = "#bfa";
-            g.edges[e].style.fill = "#56f";
-        } else {
-            g.edges[e].style.stroke = "#aaa";
-        }
-    }
-    
-    var renderer = new Graph.Renderer.Raphael('canvas', g, width, height);
-
-    redraw = function() {
-        layouter.layout();
-        renderer.draw();
-    };
-    
-/*    var pos=0;
-    step = function(dir) {
-        pos+=dir;
-        var renderer = new Graph.Renderer.Raphael('canvas', g.snapshots[pos], width, height);
-        renderer.draw();
-    };*/
-};
-
--->
-    </script>
-</head>
-<body>
-<div id="canvas"></div>
-Looks ugly? Hit <button id="redraw" onclick="redraw();">redraw</button>!<br>
-<!--<button onclick="step(-1)">Previous step</button> - <button onclick="step(1)">Next step</button>-->
-</body>
+    <script type="text/javascript" src="algorithms.js"></script>
+  </head>
+  <body>
+    <div id="canvas"></div>
+    Looks ugly? Hit <button id="redraw" onclick="redraw();">redraw</button>!<br>
+    <!--<button onclick="step(-1)">Previous step</button> - <button onclick="step(1)">Next step</button>-->
+  </body>
 </html>

=== added file 'example.js'
--- example.js	1970-01-01 00:00:00 +0000
+++ example.js	2010-10-24 05:37:41 +0000
@@ -0,0 +1,109 @@
+
+var redraw, g, renderer;
+
+/* only do all this when document has finished loading (needed for RaphaelJS) */
+window.onload = function() {
+    
+    var width = $(document).width() - 20;
+    var height = $(document).height() - 60;
+    
+    g = new Graph();
+
+    /* add a simple node */
+    g.addNode("strawberry");
+    g.addNode("cherry");
+
+    /* add a node with a customized label */
+    g.addNode("1", { label : "Tomato" });
+
+    /* add a node with a customized shape 
+       (the Raphael graph drawing implementation can draw this shape, please 
+       consult the RaphaelJS reference for details http://raphaeljs.com/) */
+    var render = function(r, n) {
+        var label = r.text(0, 30, n.label).attr({opacity:0});
+        /* the Raphael set is obligatory, containing all you want to display */
+        var set = r.set().push(
+            r.rect(-30, -13, 62, 86).attr({"fill": "#fa8", "stroke-width": 2, r : "9px"}))
+            .push(label);
+        /* make the label show only on hover */
+        set.hover(function(){ label.animate({opacity:1,"fill-opacity":1}, 500); }, function(){ label.animate({opacity:0},300); });
+
+        tooltip = r.set()
+            .push(
+                r.rect(0, 0, 90, 30).attr({"fill": "#fec", "stroke-width": 1, r : "9px"})
+            ).push(
+                r.text(25, 15, "overlay").attr({"fill": "#000000"})
+            );
+        for(i in set.items) {
+            set.items[i].tooltip(tooltip);
+        };
+	//            set.tooltip(r.set().push(r.rect(0, 0, 30, 30).attr({"fill": "#fec", "stroke-width": 1, r : "9px"})).hide());
+        return set;
+    };
+    g.addNode("id35", {
+        label : "meat\nand\ngreed" ,
+        /* filling the shape with a color makes it easier to be dragged */
+        /* arguments: r = Raphael object, n : node object */
+        render : render
+    });
+    //    g.addNode("Wheat", {
+    /* filling the shape with a color makes it easier to be dragged */
+    /* arguments: r = Raphael object, n : node object */
+    //        shapes : [ {
+    //                type: "rect",
+    //                x: 10,
+    //                y: 10,
+    //                width: 25,
+    //                height: 25,
+    //                stroke: "#f00"
+    //            }, {
+    //                type: "text",
+    //                x: 30,
+    //                y: 40,
+    //                text: "Dump"
+    //            }],
+    //        overlay : "<b>Hello <a href=\"http://wikipedia.org/\">World!</a></b>"
+    //    });
+
+    st = { directed: true, label : "Label"};
+    g.addEdge("kiwi", "penguin", st);
+
+    /* connect nodes with edges */
+    g.addEdge("strawberry", "cherry");
+    g.addEdge("cherry", "apple");
+    g.addEdge("cherry", "apple")
+    g.addEdge("1", "id35");
+    g.addEdge("penguin", "id35");
+    g.addEdge("penguin", "apple");
+    g.addEdge("kiwi", "id35");
+
+    /* a directed connection, using an arrow */
+    g.addEdge("1", "cherry", { directed : true } );
+    
+    /* customize the colors of that edge */
+    g.addEdge("id35", "apple", { stroke : "#bfa" , fill : "#56f", label : "Meat-to-Apple" });
+    
+    /* add an unknown node implicitly by adding an edge */
+    g.addEdge("strawberry", "apple");
+
+    g.removeNode("1");
+
+    /* layout the graph using the Spring layout implementation */
+    var layouter = new Graph.Layout.Spring(g);
+    
+    /* draw the graph using the RaphaelJS draw implementation */
+    renderer = new Graph.Renderer.Raphael('canvas', g, width, height);
+    
+    redraw = function() {
+        layouter.layout();
+        renderer.draw();
+    };
+    hide = function(id) {
+        g.nodes[id].hide();
+    };
+    show = function(id) {
+        g.nodes[id].show();
+    };
+    //    console.log(g.nodes["kiwi"]);
+};
+

=== modified file 'index.html'
--- index.html	2010-09-20 18:56:38 +0000
+++ index.html	2010-10-24 05:37:41 +0000
@@ -2,118 +2,9 @@
 <head>
     <script type="text/javascript" src="js/raphael-min.js"></script>
     <script type="text/javascript" src="js/dracula_graffle.js"></script>
+    <script type="text/javascript" src="js/jquery-1.4.2.min.js"></script>
     <script type="text/javascript" src="js/dracula_graph.js"></script>
-    <script type="text/javascript">
-<!--
-
-var redraw, g, renderer;
-var height = 300;
-var width = 400;
-
-/* only do all this when document has finished loading (needed for RaphaelJS) */
-window.onload = function() {
-
-    g = new Graph();
-
-    /* add a simple node */
-    g.addNode("strawberry");
-    g.addNode("cherry");
-
-    /* add a node with a customized label */
-    g.addNode("1", { label : "Tomato" });
-
-    /* add a node with a customized shape 
-       (the Raphael graph drawing implementation can draw this shape, please 
-       consult the RaphaelJS reference for details http://raphaeljs.com/) */
-    var render = function(r, n) {
-            var label = r.text(0, 30, n.label).attr({opacity:0});
-            /* the Raphael set is obligatory, containing all you want to display */
-            var set = r.set().push(
-                r.rect(-30, -13, 62, 86).attr({"fill": "#fa8", "stroke-width": 2, r : "9px"}))
-                    .push(label);
-            /* make the label show only on hover */
-            set.hover(function(){ label.animate({opacity:1,"fill-opacity":1}, 500); }, function(){ label.animate({opacity:0},300); });
-
-            tooltip = r.set()
-                        .push(
-                            r.rect(0, 0, 90, 30).attr({"fill": "#fec", "stroke-width": 1, r : "9px"})
-                        ).push(
-                            r.text(25, 15, "overlay").attr({"fill": "#000000"})
-                        );
-            for(i in set.items) {
-                    set.items[i].tooltip(tooltip);
-                };
-//            set.tooltip(r.set().push(r.rect(0, 0, 30, 30).attr({"fill": "#fec", "stroke-width": 1, r : "9px"})).hide());
-            return set;
-        };
-    g.addNode("id35", {
-        label : "meat\nand\ngreed" ,
-        /* filling the shape with a color makes it easier to be dragged */
-        /* arguments: r = Raphael object, n : node object */
-        render : render
-    });
-//    g.addNode("Wheat", {
-        /* filling the shape with a color makes it easier to be dragged */
-        /* arguments: r = Raphael object, n : node object */
-//        shapes : [ {
-//                type: "rect",
-//                x: 10,
-//                y: 10,
-//                width: 25,
-//                height: 25,
-//                stroke: "#f00"
-//            }, {
-//                type: "text",
-//                x: 30,
-//                y: 40,
-//                text: "Dump"
-//            }],
-//        overlay : "<b>Hello <a href=\"http://wikipedia.org/\">World!</a></b>"
-//    });
-
-    st = { directed: true, label : "Label"};
-    g.addEdge("kiwi", "penguin", st);
-
-    /* connect nodes with edges */
-    g.addEdge("strawberry", "cherry");
-    g.addEdge("cherry", "apple");
-    g.addEdge("1", "id35");
-    g.addEdge("penguin", "id35");
-    g.addEdge("penguin", "apple");
-    g.addEdge("kiwi", "id35");
-
-    /* a directed connection, using an arrow */
-    g.addEdge("1", "cherry", { directed : true } );
-    
-    /* customize the colors of that edge */
-    g.addEdge("id35", "apple", { stroke : "#bfa" , fill : "#56f", label : "Meat-to-Apple" });
-    
-    /* add an unknown node implicitly by adding an edge */
-    g.addEdge("strawberry", "apple");
-
-    g.removeNode("apple");
-
-    /* layout the graph using the Spring layout implementation */
-    var layouter = new Graph.Layout.Spring(g);
-    
-    /* draw the graph using the RaphaelJS draw implementation */
-    renderer = new Graph.Renderer.Raphael('canvas', g, width, height);
-    
-    redraw = function() {
-        layouter.layout();
-        renderer.draw();
-    };
-    hide = function(id) {
-        g.nodes[id].hide();
-    };
-    show = function(id) {
-        g.nodes[id].show();
-    };
-//    console.log(g.nodes["kiwi"]);
-};
-
--->
-    </script>
+    <script type="text/javascript" src="example.js"></script>
 </head>
 <body>
 <div id="canvas"></div>

=== modified file 'js/dracula_algorithms.js'
--- js/dracula_algorithms.js	2010-09-22 20:09:16 +0000
+++ js/dracula_algorithms.js	2010-10-24 05:37:41 +0000
@@ -35,6 +35,14 @@
                 edge.target.distance = edge.source.distance + edge.weight;
                 edge.target.predecessor = edge.source;
             }
+	    //Added by Jake Stothard (Needs to be tested)
+	    if(!edge.style.directed) {
+		if(edge.target.distance + edge.weight < edge.source.distance) {
+                    g.snapShot("Relax edge between "+edge.target.id+" and "+edge.source.id+".");
+                    edge.source.distance = edge.target.distance + edge.weight;
+                    edge.source.predecessor = edge.target;
+		}
+	    }
         }
     
     g.snapShot("Ready.");
@@ -79,23 +87,25 @@
 
         /* for each neighbour of node */
         for(e in node.edges) {
-            if(node.edges[e].target.optimized)
+	    var other = (node == node.edges[e].target) ? node.edges[e].source : node.edges[e].target;
+		
+            if(other.optimized)
                 continue;
 
             /* look for an alternative route */
             var alt = node.distance + node.edges[e].weight;
             
             /* update distance and route if a better one has been found */
-            if (alt < node.edges[e].target.distance) {
+            if (alt < other.distance) {
             
                 /* update distance of neighbour */
-                node.edges[e].target.distance = alt;
+                other.distance = alt;
 
                 /* update priority queue */
                 q.heapify();
 
                 /* update path */
-                node.edges[e].target.predecessor = node;
+                other.predecessor = node;
                 g.snapShot("Enhancing node.")
             }
         }
@@ -456,3 +466,60 @@
 Function.prototype.curry = function(){
 	return curry(this);
 };
+
+/**
+ * Topological Sort
+ *
+ * Sort a directed graph based on incoming edges
+ *
+ * Coded by Jake Stothard
+ */
+function topological_sort(g) {
+    //Mark nodes as "deleted" instead of actually deleting them
+    //That way we don't have to copy g
+
+    for(i in g.nodes)
+	g.nodes[i].deleted = false;
+    
+    var ret = topological_sort_helper(g);
+
+    //Cleanup: Remove the deleted property
+    for(i in g.nodes)
+	delete g.nodes[i].deleted
+
+    return ret;
+}
+function topological_sort_helper(g) {
+    //Find node with no incoming edges
+    var node;
+    for(i in g.nodes) {
+	if(g.nodes[i].deleted)
+	    continue; //Bad style, meh
+	
+	var incoming = false;
+	for(j in g.nodes[i].edges) {
+	    if(g.nodes[i].edges[j].target == g.nodes[i]
+	      && g.nodes[i].edges[j].source.deleted == false) {
+		incoming = true;
+		break;
+	    }
+	}
+	if(!incoming) {
+	    node = g.nodes[i];
+	    break;
+	}
+    }
+
+    // Either unsortable or done. Either way, GTFO
+    if(node == undefined)
+	return [];
+
+    //"Delete" node from g
+    node.deleted = true;
+    
+    var tail = topological_sort_helper(g);
+
+    tail.unshift(node);
+
+    return tail;
+}

=== modified file 'js/dracula_graph.js'
--- js/dracula_graph.js	2010-09-22 20:09:16 +0000
+++ js/dracula_graph.js	2010-10-24 05:37:41 +0000
@@ -28,18 +28,44 @@
  *  Original usage example:
  *      http://ajaxian.com/archives/new-javascriptcanvas-graph-library
  *
-/*--------------------------------------------------------------------------*/
-
-
+ /*--------------------------------------------------------------------------*/
+
+// Branched by Jake Stothard <[e-mail]>.
+
+/*
+ * Edge Factory
+ */
+var AbstractEdge = function() {
+}
+AbstractEdge.prototype = {
+    hide: function() {
+	this.connection.fg.hide();
+	this.connection.bg && this.bg.connection.hide();
+    }
+};
+var EdgeFactory = function() {
+    this.template = new AbstractEdge();
+    this.template.style = new Object();
+    this.template.style.directed = false;
+    this.template.weight = 1;
+};
+EdgeFactory.prototype = {
+    build: function(source, target) {
+	var e = jQuery.extend(true, {}, this.template);
+	e.source = source;
+	e.target = target;
+	return e;
+    }
+};
 
 /*
  * Graph
  */
 var Graph = function() {
-    this.nodes = [];
-    this.nodelist = []; // nodes by index number, only used once TODO use only one node container
+    this.nodes = new Object();
     this.edges = [];
     this.snapshots = []; // previous graph states TODO to be implemented
+    this.edgeFactory = new EdgeFactory();
 };
 Graph.prototype = {
     /* 
@@ -52,25 +78,20 @@
     addNode: function(id, content) {
         /* testing if node is already existing in the graph */
         if(this.nodes[id] == undefined) {
-                this.nodes[id] = new Graph.Node(id, content || {"id" : id}); /* nodes indexed by node id */
-                this.nodelist.push(this.nodes[id]); /* node list indexed by numbers */
+	    this.nodes[id] = new Graph.Node(id, content);
         }
         return this.nodes[id];
     },
 
-    // TODO rename style to content
     addEdge: function(source, target, style) {
         var s = this.addNode(source);
         var t = this.addNode(target);
-        var edge = { source: s, target: t, style: style, weight: style&&style.weight||1, hide: function() { this.connection.fg.hide(); this.connection.bg && this.bg.connection.hide(); } }; // TODO tidy up here
+	var edge = this.edgeFactory.build(s, t);
+	jQuery.extend(edge.style,style);
         s.edges.push(edge);
         this.edges.push(edge);
-        /* add an edge back if graph undirected */
-        if(!style || !style.directed) {
-            var backedge = { source: t, target: s, style: style, weight : style&&style.weight||1, backedge : edge }; // TODO tidy up here
-            this.edges.push(backedge);
-            t.edges.push(backedge);
-        }
+	// NOTE: Even directed edges are added to both nodes.
+	t.edges.push(edge);
     },
     
     /* TODO to be implemented
@@ -78,20 +99,21 @@
      * @comment     a comment describing the state
      */
     snapShot: function(comment) {
+	/* FIXME
         var graph = new Graph();
-//        graph.nodes = clone(this.nodes);
-//        graph.nodelist = clone(this.nodelist);
-//        graph.edges = clone(this.edges);
-        graph.snapShot = null;
+	graph.nodes = jQuery.extend(true, {}, this.nodes);
+	graph.edges = jQuery.extend(true, {}, this.edges);
         this.snapshots.push({comment: comment, graph: graph});
+	*/
     },
-    /* FIXME doesn't work properly yet */
     removeNode: function(id) {
-        var i = 0;
-        for(n in this.nodes)
-            (n == id) && this.nodes.splice(i, 1) && this.nodelist.splice(i, 1) | i++;
-        for(i in this.edges)
-            (this.edges[i].source.id == id || this.edges[i].target == id) && this.edges.splice(i, 1);
+	delete this.nodes[id];
+        for(var i = 0; i < this.edges.length; i++) {
+            if (this.edges[i].source.id == id || this.edges[i].target.id == id) {
+		this.edges.splice(i, 1);
+		i--;
+	    }
+	}
     }
 };
 
@@ -99,6 +121,7 @@
  * Node
  */
 Graph.Node = function(id, node){
+    node = node || {};
     node.id = id;
     node.edges = [];
     node.hide = function() {
@@ -165,7 +188,7 @@
             var clientX = e.clientX - (newX < 20 ? newX - 20 : newX > selfRef.width - 20 ? newX - selfRef.width + 20 : 0);
             var clientY = e.clientY - (newY < 20 ? newY - 20 : newY > selfRef.height - 20 ? newY - selfRef.height + 20 : 0);
             selfRef.isDrag.set.translate(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
-//            console.log(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
+	    //            console.log(clientX - Math.round(selfRef.isDrag.dx), clientY - Math.round(selfRef.isDrag.dy));
             for (var i in selfRef.graph.edges) {
                 selfRef.graph.edges[i].connection && selfRef.graph.edges[i].connection.draw();
             }
@@ -249,7 +272,7 @@
 
         var box = shape.getBBox();
         shape.translate(Math.round(point[0])-(box.x+box.width/2)+0.5,Math.round(point[1]-(box.y+box.height/2)))
-//console.log(box,point);
+	//console.log(box,point);
         node.hidden || shape.show();
         node.shape = shape;
     },
@@ -275,132 +298,184 @@
 };
 Graph.Layout = {};
 Graph.Layout.Spring = function(graph) {
-                this.graph = graph;
-                this.iterations = 500;
-                this.maxRepulsiveForceDistance = 6;
-                this.k = 2;
-                this.c = 0.01;
-                this.maxVertexMovement = 0.5;
-                this.layout();
-        };
+    this.graph = graph;
+    this.iterations = 500;
+    this.maxRepulsiveForceDistance = 6;
+    this.k = 2;
+    this.c = 0.01;
+    this.maxVertexMovement = 0.5;
+    this.layout();
+};
 Graph.Layout.Spring.prototype = {
-        layout: function() {
-                this.layoutPrepare();
-            for (var i = 0; i < this.iterations; i++) {
-                        this.layoutIteration();
-                }
-                this.layoutCalcBounds();
-        },
-       
-        layoutPrepare: function() {
-            for (i in this.graph.nodes) {
-                    var node = this.graph.nodes[i];
-                        node.layoutPosX = 0;
-                        node.layoutPosY = 0;
-                        node.layoutForceX = 0;
-                        node.layoutForceY = 0;
-                }
-                
-        },
-       
-        layoutCalcBounds: function() {
-                var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;
-
-            for (i in this.graph.nodes) {
-                        var x = this.graph.nodes[i].layoutPosX;
-                        var y = this.graph.nodes[i].layoutPosY;
-                                               
-                        if(x > maxx) maxx = x;
-                        if(x < minx) minx = x;
-                        if(y > maxy) maxy = y;
-                        if(y < miny) miny = y;
-                }
-
-                this.graph.layoutMinX = minx;
-                this.graph.layoutMaxX = maxx;
-                this.graph.layoutMinY = miny;
-                this.graph.layoutMaxY = maxy;
-        },
-       
-        layoutIteration: function() {
-                // Forces on nodes due to node-node repulsions
-            for (var i = 0; i < this.graph.nodelist.length; i++) {
-                    var node1 = this.graph.nodelist[i];
-                    for (var j = i + 1; j < this.graph.nodelist.length; j++) {
-                            var node2 = this.graph.nodelist[j];
-                                this.layoutRepulsive(node1, node2);
-                        }
-                }
-                // Forces on nodes due to edge attractions
-            for (var i = 0; i < this.graph.edges.length; i++) {
-                    var edge = this.graph.edges[i];
-                        this.layoutAttractive(edge);             
-                }
-               
-                // Move by the given force
-            for (i in this.graph.nodes) {
-                    var node = this.graph.nodes[i];
-                    var xmove = this.c * node.layoutForceX;
-                    var ymove = this.c * node.layoutForceY;
-
-                    var max = this.maxVertexMovement;
-                    if(xmove > max) xmove = max;
-                    if(xmove < -max) xmove = -max;
-                    if(ymove > max) ymove = max;
-                    if(ymove < -max) ymove = -max;
-                   
-                    node.layoutPosX += xmove;
-                    node.layoutPosY += ymove;
-                    node.layoutForceX = 0;
-                    node.layoutForceY = 0;
-                }
-        },
-
-        layoutRepulsive: function(node1, node2) {
-                var dx = node2.layoutPosX - node1.layoutPosX;
-                var dy = node2.layoutPosY - node1.layoutPosY;
-                var d2 = dx * dx + dy * dy;
-                if(d2 < 0.01) {
-                        dx = 0.1 * Math.random() + 0.1;
-                        dy = 0.1 * Math.random() + 0.1;
-                        var d2 = dx * dx + dy * dy;
-                }
-                var d = Math.sqrt(d2);
-                if(d < this.maxRepulsiveForceDistance) {
-                        var repulsiveForce = this.k * this.k / d;
-                        node2.layoutForceX += repulsiveForce * dx / d;
-                        node2.layoutForceY += repulsiveForce * dy / d;
-                        node1.layoutForceX -= repulsiveForce * dx / d;
-                        node1.layoutForceY -= repulsiveForce * dy / d;
-                }
-        },
-
-        layoutAttractive: function(edge) {
-                var node1 = edge.source;
-                var node2 = edge.target;
-               
-                var dx = node2.layoutPosX - node1.layoutPosX;
-                var dy = node2.layoutPosY - node1.layoutPosY;
-                var d2 = dx * dx + dy * dy;
-                if(d2 < 0.01) {
-                        dx = 0.1 * Math.random() + 0.1;
-                        dy = 0.1 * Math.random() + 0.1;
-                        var d2 = dx * dx + dy * dy;
-                }
-                var d = Math.sqrt(d2);
-                if(d > this.maxRepulsiveForceDistance) {
-                        d = this.maxRepulsiveForceDistance;
-                        d2 = d * d;
-                }
-                var attractiveForce = (d2 - this.k * this.k) / this.k;
-                if(edge.attraction == undefined) edge.attraction = 1;
-                attractiveForce *= Math.log(edge.attraction) * 0.5 + 1;
-               
-                node2.layoutForceX -= attractiveForce * dx / d;
-                node2.layoutForceY -= attractiveForce * dy / d;
-                node1.layoutForceX += attractiveForce * dx / d;
-                node1.layoutForceY += attractiveForce * dy / d;
-        }
+    layout: function() {
+        this.layoutPrepare();
+        for (var i = 0; i < this.iterations; i++) {
+            this.layoutIteration();
+        }
+        this.layoutCalcBounds();
+    },
+    
+    layoutPrepare: function() {
+        for (i in this.graph.nodes) {
+            var node = this.graph.nodes[i];
+            node.layoutPosX = 0;
+            node.layoutPosY = 0;
+            node.layoutForceX = 0;
+            node.layoutForceY = 0;
+        }
+        
+    },
+    
+    layoutCalcBounds: function() {
+        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;
+
+        for (i in this.graph.nodes) {
+            var x = this.graph.nodes[i].layoutPosX;
+            var y = this.graph.nodes[i].layoutPosY;
+            
+            if(x > maxx) maxx = x;
+            if(x < minx) minx = x;
+            if(y > maxy) maxy = y;
+            if(y < miny) miny = y;
+        }
+
+        this.graph.layoutMinX = minx;
+        this.graph.layoutMaxX = maxx;
+        this.graph.layoutMinY = miny;
+        this.graph.layoutMaxY = maxy;
+    },
+    
+    layoutIteration: function() {
+        // Forces on nodes due to node-node repulsions
+
+	var prev = new Array();
+	for(var c in this.graph.nodes) {
+	    var node1 = this.graph.nodes[c];
+            for (var d in prev) {
+                var node2 = this.graph.nodes[prev[d]];
+                this.layoutRepulsive(node1, node2);
+		
+            }
+	    prev.push(c);
+	}
+	
+        // Forces on nodes due to edge attractions
+        for (var i = 0; i < this.graph.edges.length; i++) {
+            var edge = this.graph.edges[i];
+            this.layoutAttractive(edge);             
+        }
+        
+        // Move by the given force
+        for (i in this.graph.nodes) {
+            var node = this.graph.nodes[i];
+            var xmove = this.c * node.layoutForceX;
+            var ymove = this.c * node.layoutForceY;
+
+            var max = this.maxVertexMovement;
+            if(xmove > max) xmove = max;
+            if(xmove < -max) xmove = -max;
+            if(ymove > max) ymove = max;
+            if(ymove < -max) ymove = -max;
+            
+            node.layoutPosX += xmove;
+            node.layoutPosY += ymove;
+            node.layoutForceX = 0;
+            node.layoutForceY = 0;
+        }
+    },
+
+    layoutRepulsive: function(node1, node2) {
+        var dx = node2.layoutPosX - node1.layoutPosX;
+        var dy = node2.layoutPosY - node1.layoutPosY;
+        var d2 = dx * dx + dy * dy;
+        if(d2 < 0.01) {
+            dx = 0.1 * Math.random() + 0.1;
+            dy = 0.1 * Math.random() + 0.1;
+            var d2 = dx * dx + dy * dy;
+        }
+        var d = Math.sqrt(d2);
+        if(d < this.maxRepulsiveForceDistance) {
+            var repulsiveForce = this.k * this.k / d;
+            node2.layoutForceX += repulsiveForce * dx / d;
+            node2.layoutForceY += repulsiveForce * dy / d;
+            node1.layoutForceX -= repulsiveForce * dx / d;
+            node1.layoutForceY -= repulsiveForce * dy / d;
+        }
+    },
+
+    layoutAttractive: function(edge) {
+        var node1 = edge.source;
+        var node2 = edge.target;
+        
+        var dx = node2.layoutPosX - node1.layoutPosX;
+        var dy = node2.layoutPosY - node1.layoutPosY;
+        var d2 = dx * dx + dy * dy;
+        if(d2 < 0.01) {
+            dx = 0.1 * Math.random() + 0.1;
+            dy = 0.1 * Math.random() + 0.1;
+            var d2 = dx * dx + dy * dy;
+        }
+        var d = Math.sqrt(d2);
+        if(d > this.maxRepulsiveForceDistance) {
+            d = this.maxRepulsiveForceDistance;
+            d2 = d * d;
+        }
+        var attractiveForce = (d2 - this.k * this.k) / this.k;
+        if(edge.attraction == undefined) edge.attraction = 1;
+        attractiveForce *= Math.log(edge.attraction) * 0.5 + 1;
+        
+        node2.layoutForceX -= attractiveForce * dx / d;
+        node2.layoutForceY -= attractiveForce * dy / d;
+        node1.layoutForceX += attractiveForce * dx / d;
+        node1.layoutForceY += attractiveForce * dy / d;
+    }
+};
+
+Graph.Layout.Ordered = function(graph, order) {
+    this.graph = graph;
+    this.order = order;
+    this.layout();
+};
+Graph.Layout.Ordered.prototype = {
+    layout: function() {
+        this.layoutPrepare();
+        this.layoutCalcBounds();
+    },
+    
+    layoutPrepare: function(order) {
+        for (i in this.graph.nodes) {
+            var node = this.graph.nodes[i];
+            node.layoutPosX = 0;
+            node.layoutPosY = 0;
+        }
+	var counter = 0;
+	for (i in this.order) {
+	    var node = this.order[i];
+	    node.layoutPosX = counter;
+	    node.layoutPosY = Math.random();
+	    counter++;
+	}
+    },
+    
+    layoutCalcBounds: function() {
+        var minx = Infinity, maxx = -Infinity, miny = Infinity, maxy = -Infinity;
+
+        for (i in this.graph.nodes) {
+            var x = this.graph.nodes[i].layoutPosX;
+            var y = this.graph.nodes[i].layoutPosY;
+            
+            if(x > maxx) maxx = x;
+            if(x < minx) minx = x;
+            if(y > maxy) maxy = y;
+            if(y < miny) miny = y;
+        }
+
+        this.graph.layoutMinX = minx;
+        this.graph.layoutMaxX = maxx;
+
+        this.graph.layoutMinY = miny;
+        this.graph.layoutMaxY = maxy;
+    },
 };
 
 /*
@@ -409,23 +484,6 @@
 
 function log(a) {console.log&&console.log(a);}
 
-function clone(obj){
-    if(obj == null || typeof(obj) != 'object')
-        return obj;
-
-    var temp = obj.constructor(); // changed
-
-    for(var key in obj)
-        temp[key] = clone(obj[key]);
-    return temp;
-}
-
-// this will eventually mess up array usage with for-in-loops
-//Array.prototype.onEach = function(f, arg) {
-//     var l = this.length;
-//     for( var i = 0; i < l; i++) this[i][f]( arg );
-//}
-
 /*
  * Raphael Tooltip Plugin
  * - attaches an element as a tooltip to another element
@@ -445,7 +503,7 @@
         function(event){ 
             this.mousemove(function(event){ 
                 this.tp.translate(event.clientX - 
-                    this.tp.o.x,event.clientY - this.tp.o.y);
+				  this.tp.o.x,event.clientY - this.tp.o.y);
                 this.tp.o = {x: event.clientX, y: event.clientY};
             });
             this.tp.show().toFront();
@@ -453,6 +511,6 @@
         function(event){
             this.tp.hide();
             this.unmousemove();
-            });
+        });
     return this;
 };