karaf-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ldywi...@apache.org
Subject svn commit: r1165446 [1/3] - in /karaf/sandbox/webconsole/trunk/blueprint/src/main: java/org/apache/karaf/webconsole/blueprint/internal/details/ resources/org/apache/karaf/webconsole/blueprint/internal/details/
Date Mon, 05 Sep 2011 23:04:33 GMT
Author: ldywicki
Date: Mon Sep  5 23:04:33 2011
New Revision: 1165446

URL: http://svn.apache.org/viewvc?rev=1165446&view=rev
Log:
Dependency graph for blueprint containers. Only depends-on attribute is honoured

Added:
    karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/MetadataModel.java
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/Curry-1.0.1.js
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/details.js
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_algorithms.js
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graffle.js
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graph.js
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/jquery-1.4.2.min.js
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/raphael-min.js
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/seedrandom.js
Modified:
    karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.java
    karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.html

Modified: karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.java
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.java?rev=1165446&r1=1165445&r2=1165446&view=diff
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.java (original)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.java Mon Sep  5 23:04:33 2011
@@ -16,25 +16,19 @@
  */
 package org.apache.karaf.webconsole.blueprint.internal.details;
 
-import java.io.Serializable;
-import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.Collection;
 import java.util.List;
 
 import org.apache.karaf.webconsole.core.page.SinglePage;
 import org.apache.wicket.PageParameters;
+import org.apache.wicket.markup.html.JavascriptPackageResource;
 import org.apache.wicket.markup.html.basic.Label;
 import org.apache.wicket.markup.html.list.ListItem;
 import org.apache.wicket.markup.html.list.ListView;
 import org.apache.wicket.model.IModel;
-import org.apache.wicket.model.LoadableDetachableModel;
 import org.ops4j.pax.wicket.api.PaxWicketBean;
 import org.ops4j.pax.wicket.api.PaxWicketMountPoint;
-import org.osgi.framework.Bundle;
 import org.osgi.framework.BundleContext;
-import org.osgi.framework.ServiceReference;
-import org.osgi.service.blueprint.container.BlueprintContainer;
 import org.osgi.service.blueprint.reflect.ComponentMetadata;
 
 /**
@@ -47,94 +41,33 @@ public class DetailsPage extends SingleP
     private BundleContext context;
 
     public DetailsPage(PageParameters params) {
-        IModel<List<MetadataWrappper>> model = new MetadataModel(params);
-        if (model.getObject() == null) {
-            fillEmptyListView();
-            return;
-        }
-        fillListViewWithMetaModel(model);
-    }
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "jquery-1.4.2.min.js"));
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "Curry-1.0.1.js"));
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "seedrandom.js"));
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "raphael-min.js"));
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "dracula_graph.js"));
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "dracula_graffle.js"));
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "dracula_algorithms.js"));
+        add(JavascriptPackageResource.getHeaderContribution(DetailsPage.class, "details.js"));
 
-    private void fillEmptyListView() {
-        add(new ListView("components") {
-            @Override
-            protected void populateItem(ListItem item) {
-                // do nothing :)
-            }
-        });
-    }
+        IModel<List<ComponentMetadata>> model = new MetadataModel(context, params.getInt("bundleId"));
 
-    private void fillListViewWithMetaModel(IModel<List<MetadataWrappper>> model) {
-        add(new ListView<MetadataWrappper>("components", model) {
+        add(new ListView<ComponentMetadata>("components", model) {
             @Override
-            protected void populateItem(ListItem<MetadataWrappper> item) {
-                MetadataWrappper metadata = item.getModelObject();
-                item.add(new Label("componentId", metadata.id));
-                item.add(new Label("type", metadata.interfaces));
-            }
-        });
-    }
-
-    private class MetadataModel extends LoadableDetachableModel<List<MetadataWrappper>> {
-
-        private PageParameters pageParams;
-
-        public MetadataModel(PageParameters pageParams) {
-            this.pageParams = pageParams;
-        }
-
-        @Override
-        protected List<MetadataWrappper> load() {
-            ServiceReference reference = null;
-            try {
-                reference = retrieveReference();
-                if (reference == null) {
-                    return null;
-                }
-                return extractMetadata(reference);
-            } finally {
-                if (reference != null) {
-                    context.ungetService(reference);
-                }
-            }
-        }
-
-        private List<MetadataWrappper> extractMetadata(ServiceReference reference) {
-            BlueprintContainer container = (BlueprintContainer) context.getService(reference);
-            List<MetadataWrappper> extractedMetadata = new ArrayList<DetailsPage.MetadataWrappper>();
-            Collection<ComponentMetadata> metadata = container.getMetadata(ComponentMetadata.class);
-            for (ComponentMetadata originalMetadata : metadata) {
-                extractedMetadata.add(new MetadataWrappper(originalMetadata));
-            }
-            return extractedMetadata;
-        }
-
-        private ServiceReference retrieveReference() {
-            ServiceReference reference = null;
-            Bundle bundle = context.getBundle(pageParams.getLong("bundleId"));
-            ServiceReference[] references = bundle.getRegisteredServices();
-            for (ServiceReference ref : references) {
-                String[] classes = (String[]) ref.getProperty("objectClass");
-                for (String clazz : classes) {
-                    if ("org.osgi.service.blueprint.container.BlueprintContainer".equals(clazz)) {
-                        reference = ref;
-                        break;
+            @SuppressWarnings("unchecked")
+            protected void populateItem(ListItem<ComponentMetadata> item) {
+                ComponentMetadata metadata = item.getModelObject();
+                item.add(new Label("componentId", metadata.getId()));
+                item.add(new Label("type", Arrays.toString(metadata.getClass().getInterfaces())));
+                //item.add(new Label("dependencies", "" + metadata.getDependsOn()));
+                item.add(new ListView<String>("dependencies", metadata.getDependsOn()) {
+                    @Override
+                    protected void populateItem(ListItem<String> item) {
+                        item.add(new Label("dependency", item.getModelObject()).setRenderBodyOnly(true));
                     }
-                }
+                });
             }
-            return reference;
-        }
-    }
-
-    private static class MetadataWrappper implements Serializable {
-        private String id;
-        private String interfaces;
-
-        public MetadataWrappper(ComponentMetadata metadata) {
-            id = metadata.getId();
-            interfaces = Arrays.toString(metadata.getClass().getInterfaces());
-        }
-
+        });
     }
 
 }

Added: karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/MetadataModel.java
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/MetadataModel.java?rev=1165446&view=auto
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/MetadataModel.java (added)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/java/org/apache/karaf/webconsole/blueprint/internal/details/MetadataModel.java Mon Sep  5 23:04:33 2011
@@ -0,0 +1,49 @@
+package org.apache.karaf.webconsole.blueprint.internal.details;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.wicket.model.LoadableDetachableModel;
+import org.osgi.framework.Bundle;
+import org.osgi.framework.BundleContext;
+import org.osgi.framework.ServiceReference;
+import org.osgi.service.blueprint.container.BlueprintContainer;
+import org.osgi.service.blueprint.reflect.ComponentMetadata;
+
+class MetadataModel extends LoadableDetachableModel<List<ComponentMetadata>> {
+
+    private final int bundleId;
+    private final BundleContext context;
+    private ServiceReference reference;
+
+    public MetadataModel(BundleContext context, int bundleId) {
+        this.context = context;
+        this.bundleId = bundleId;
+    }
+
+    @Override
+    protected List<ComponentMetadata> load() {
+        Bundle bundle = context.getBundle(bundleId);
+
+        ServiceReference[] references = bundle.getRegisteredServices();
+        for (ServiceReference ref : references) {
+            String[] classes = (String[]) ref.getProperty("objectClass");
+            for (String clazz : classes) {
+                if ("org.osgi.service.blueprint.container.BlueprintContainer".equals(clazz)) {
+                    reference = ref;
+                    List<ComponentMetadata> metas = new ArrayList<ComponentMetadata>();
+                    metas.addAll(((BlueprintContainer) context.getService(ref)).getMetadata(ComponentMetadata.class));
+                    return metas;
+                }
+            }
+        }
+        throw new IllegalArgumentException("Cannot find blueprint container for bundle " + bundleId);
+    }
+
+    @Override
+    public void detach() {
+        if (reference != null) {
+            context.ungetService(reference);
+        }
+    }
+}
\ No newline at end of file

Added: karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/Curry-1.0.1.js
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/Curry-1.0.1.js?rev=1165446&view=auto
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/Curry-1.0.1.js (added)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/Curry-1.0.1.js Mon Sep  5 23:04:33 2011
@@ -0,0 +1,29 @@
+/**
+ * Curry - Function currying
+ * Copyright (c) 2008 Ariel Flesler - aflesler(at)gmail(dot)com | http://flesler.blogspot.com
+ * Licensed under BSD (http://www.opensource.org/licenses/bsd-license.php)
+ * Date: 10/4/2008
+ *
+ * @author Ariel Flesler
+ * @version 1.0.1
+ */
+
+function curry( fn ){
+	return function(){
+		var args = curry.args(arguments),
+			master = arguments.callee,
+			self = this;
+
+		return args.length >= fn.length ? fn.apply(self,args) :	function(){
+			return master.apply( self, args.concat(curry.args(arguments)) );
+		};
+	};
+};
+
+curry.args = function( args ){
+	return Array.prototype.slice.call(args);
+};
+
+Function.prototype.curry = function(){
+	return curry(this);
+};
\ No newline at end of file

Modified: karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.html
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.html?rev=1165446&r1=1165445&r2=1165446&view=diff
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.html (original)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/DetailsPage.html Mon Sep  5 23:04:33 2011
@@ -24,24 +24,25 @@
        <wicket:extend>
             <h1>Blueprint container details</h1>
 
-            <table>
-                <tr>
-                    <th>Id</th>
-                    <th>Component type</th>
-                    <th>Operations</th>
-                </tr>
-                <tr wicket:id="components">
+            <table class="dataview grid_12">
+                <tr wicket:id="components" class="component">
                     <td>
-                        <span wicket:id="componentId">component-id</span>
+                        <span wicket:id="componentId">.component-1</span>
                     </td>
                     <td>
                         <span wicket:id="type">org.osgi.service.blueprint.reflect.ComponentMetadata</span>
                     </td>
                     <td>
-<!--                         <a wicket:id="details">Details</a> -->
+                        <ul>
+                            <li wicket:id="dependencies">
+                                <span wicket:id="dependency">.component-12</span>
+                            </li>
+                        </ul>
                     </td>
                 </tr>
             </table>
+
+            <div id="graph" class="grid_12" style="height: 550px"></div>
         </wicket:extend>
     </body>
 </html>

Added: karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/details.js
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/details.js?rev=1165446&view=auto
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/details.js (added)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/details.js Mon Sep  5 23:04:33 2011
@@ -0,0 +1,17 @@
+$(function() {
+  var graph = new Graph();
+  $("tr.component").each(function(key, value) {
+    name = $(value).find("td").eq(0).text().trim();
+    graph.addNode(name, {label: name});
+
+    deps = $(value).find("ul li");
+    $(deps).each(function(index, dependency) {
+      graph.addEdge(name, $(dependency).text().trim())
+    })
+  });
+
+  var layouter = new Graph.Layout.Spring(graph);
+  //layouter.layout();
+  renderer = new Graph.Renderer.Raphael('graph', graph, $("#graph").width(), $("#graph").height());
+  //renderer.draw();
+})
\ No newline at end of file

Added: karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_algorithms.js
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_algorithms.js?rev=1165446&view=auto
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_algorithms.js (added)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_algorithms.js Mon Sep  5 23:04:33 2011
@@ -0,0 +1,599 @@
+/*
+ * Various algorithms and data structures, licensed under the MIT-license.
+ * (c) 2010 by Johann Philipp Strathausen <strathausen@gmail.com>
+ * http://strathausen.eu
+ *
+ */
+
+
+
+/*
+        Bellman-Ford
+    
+    Path-finding algorithm, finds the shortest paths from one node to all nodes.
+    
+    
+        Complexity
+        
+    O( |E| · |V| ), where E = edges and V = vertices (nodes)
+    
+    
+        Constraints
+    
+    Can run on graphs with negative edge weights as long as they do not have
+    any negative weight cycles.
+    
+ */
+function bellman_ford(g, source) {
+
+    /* STEP 1: initialisation */
+    for(var n in g.nodes)
+        g.nodes[n].distance = Infinity;
+        /* predecessors are implicitly null */
+    source.distance = 0;
+    
+    step("Initially, all distances are infinite and all predecessors are null.");
+    
+    /* STEP 2: relax each edge (this is at the heart of Bellman-Ford) */
+    /* repeat this for the number of nodes minus one */
+    for(var i = 1; i < g.nodes.length; i++)
+        /* for each edge */
+        for(var e in g.edges) {
+            var edge = g.edges[e];
+            if(edge.source.distance + edge.weight < edge.target.distance) {
+                step("Relax edge between " + edge.source.id + " and " + edge.target.id + ".");
+                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;
+		}
+	    }
+        }
+    step("Ready.");
+    
+    /* STEP 3: TODO Check for negative cycles */
+    /* For now we assume here that the graph does not contain any negative
+       weights cycles. (this is left as an excercise to the reader[tm]) */
+}
+
+
+
+/*
+   Path-finding algorithm Dijkstra
+   
+   - worst-case running time is O((|E| + |V|) · log |V| ) thus better than
+     Bellman-Ford for sparse graphs (with less edges), but cannot handle
+     negative edge weights
+ */
+function dijkstra(g, source) {
+
+    /* initially, all distances are infinite and all predecessors are null */
+    for(var n in g.nodes)
+        g.nodes[n].distance = Infinity;
+        /* predecessors are implicitly null */
+
+    g.snapShot("Initially, all distances are infinite and all predecessors are null.");
+
+    source.distance = 0;
+    /* set of unoptimized nodes, sorted by their distance (but a Fibonacci heap
+       would be better) */
+    var q = new BinaryMinHeap(g.nodes, "distance");
+
+    /* pointer to the node in focus */
+    var node;
+
+    /* get the node with the smallest distance
+       as long as we have unoptimized nodes. q.min() can have O(log n). */
+    while(q.min() != undefined) {
+        /* remove the latest */
+        node = q.extractMin();
+        node.optimized = true;
+
+        /* no nodes accessible from this one, should not happen */
+        if(node.distance == Infinity)
+            throw "Orphaned node!";
+
+        /* for each neighbour of node */
+        for(e in node.edges) {
+	    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 < other.distance) {
+            
+                /* update distance of neighbour */
+                other.distance = alt;
+
+                /* update priority queue */
+                q.heapify();
+
+                /* update path */
+                other.predecessor = node;
+                g.snapShot("Enhancing node.")
+            }
+        }
+    }
+}
+
+
+/* All-Pairs-Shortest-Paths */
+/* Runs at worst in O(|V|³) and at best in Omega(|V|³) :-)
+   complexity Sigma(|V|²) */
+/* This implementation is not yet ready for general use, but works with the
+   Dracula graph library. */
+function floyd_warshall(g, source) {
+
+    /* Step 1: initialising empty path matrix (second dimension is implicit) */
+    var path = [];
+    var next = [];
+    var n = g.nodes.length;
+
+    /* construct path matrix, initialize with Infinity */
+    for(j in g.nodes) {
+        path[j] = [];
+        next[j] = [];
+        for(i in g.nodes)
+            path[j][i] = j == i ? 0 : Infinity;
+    }   
+    
+    /* initialize path with edge weights */
+    for(e in g.edges)
+        path[g.edges[e].source.id][g.edges[e].target.id] = g.edges[e].weight;
+    
+    /* Note: Usually, the initialisation is done by getting the edge weights
+       from a node matrix representation of the graph, not by iterating through
+       a list of edges as done here. */
+    
+    /* Step 2: find best distances (the heart of Floyd-Warshall) */
+    for(k in g.nodes){
+        for(i in g.nodes) {
+            for(j in g.nodes)
+                if(path[i][j] > path[i][k] + path[k][j]) {
+                    path[i][j] = path[i][k] + path[k][j];
+                    /* Step 2.b: remember the path */
+                    next[i][j] = k;
+                }
+        }
+    }
+
+    /* Step 3: Path reconstruction, get shortest path */
+    function getPath(i, j) {
+        if(path[i][j] == Infinity)
+            throw "There is no path.";
+        var intermediate = next[i][j];
+        if(intermediate == undefined)
+            return null;
+        else
+            return getPath(i, intermediate)
+                .concat([intermediate])
+                .concat(getPath(intermediate, j));
+    }
+
+    /* TODO use the knowledge, e.g. mark path in graph */
+}
+
+/*
+        Ford-Fulkerson
+    
+    Max-Flow-Min-Cut Algorithm finding the maximum flow through a directed
+    graph from source to sink.
+    
+    
+        Complexity
+
+    O(E * max(f)), max(f) being the maximum flow
+    
+    
+        Description
+
+    As long as there is an open path through the residual graph, send the
+    minimum of the residual capacities on the path.
+    
+    
+        Constraints
+    
+    The algorithm works only if all weights are integers. Otherwise it is
+    possible that the Ford–Fulkerson algorithm will not converge to the maximum
+    value.
+    
+    
+        Input
+    
+    g - Graph object
+    s - Source ID
+    t - Target (sink) ID
+    
+    
+        Output
+    
+    Maximum flow from Source s to Target t
+
+ */
+/*
+        Edmonds-Karp
+    
+    Max-Flow-Min-Cut Algorithm finding the maximum flow through a directed
+    graph from source to sink. An implementation of the Ford-Fulkerson
+    algorithm.
+    
+    
+        Complexity
+    
+    O(|V|*|E|²)
+    
+    
+        Input
+        
+    g - Graph object (with node and edge lists, capacity is a property of edge)
+    s - source ID
+    t - sink ID
+    
+ */
+function edmonds_karp(g, s, t) {
+
+}
+
+/*
+   A simple binary min-heap serving as a priority queue
+   - takes an array as the input, with elements having a key property
+   - elements will look like this:
+        {
+            key: "... key property ...", 
+            value: "... element content ..."
+        }
+    - provides insert(), min(), extractMin() and heapify()
+    - example usage (e.g. via the Firebug or Chromium console):
+        var x = {foo: 20, hui: "bla"};
+        var a = new BinaryMinHeap([x,{foo:3},{foo:10},{foo:20},{foo:30},{foo:6},{foo:1},{foo:3}],"foo");
+        console.log(a.extractMin());
+        console.log(a.extractMin());
+        x.foo = 0; // update key
+        a.heapify(); // call this always after having a key updated
+        console.log(a.extractMin());
+        console.log(a.extractMin());
+    - can also be used on a simple array, like [9,7,8,5]
+ */
+function BinaryMinHeap(array, key) {
+    
+    /* Binary tree stored in an array, no need for a complicated data structure */
+    var tree = [];
+    
+    var key = key || 'key';
+    
+    /* Calculate the index of the parent or a child */
+    var parent = function(index) { return Math.floor((index - 1)/2); };
+    var right = function(index) { return 2 * index + 2; };
+    var left = function(index) { return 2 * index + 1; };
+
+    /* Helper function to swap elements with their parent 
+       as long as the parent is bigger */
+    function bubble_up(i) {
+        var p = parent(i);
+        while((p >= 0) && (tree[i][key] < tree[p][key])) {
+            /* swap with parent */
+            tree[i] = tree.splice(p, 1, tree[i])[0];
+            /* go up one level */
+            i = p;
+            p = parent(i);
+        }
+    }
+
+    /* Helper function to swap elements with the smaller of their children
+       as long as there is one */
+    function bubble_down(i) {
+        var l = left(i);
+        var r = right(i);
+        
+        /* as long as there are smaller children */
+        while(tree[l] && (tree[i][key] > tree[l][key]) || tree[r] && (tree[i][key] > tree[r][key])) {
+            
+            /* find smaller child */
+            var child = tree[l] ? tree[r] ? tree[l][key] > tree[r][key] ? r : l : l : l;
+            
+            /* swap with smaller child with current element */
+            tree[i] = tree.splice(child, 1, tree[i])[0];
+            
+            /* go up one level */
+            i = child;
+            l = left(i);
+            r = right(i);
+        }
+    }
+    
+    /* Insert a new element with respect to the heap property
+       1. Insert the element at the end
+       2. Bubble it up until it is smaller than its parent */
+    this.insert = function(element) {
+    
+        /* make sure there's a key property */
+        (element[key] == undefined) && (element = {key:element});
+        
+        /* insert element at the end */
+        tree.push(element);
+
+        /* bubble up the element */
+        bubble_up(tree.length - 1);
+    }
+    
+    /* Only show us the minimum */
+    this.min = function() {
+        return tree.length == 1 ? undefined : tree[0];
+    }
+    
+    /* Return and remove the minimum
+       1. Take the root as the minimum that we are looking for
+       2. Move the last element to the root (thereby deleting the root) 
+       3. Compare the new root with both of its children, swap it with the
+          smaller child and then check again from there (bubble down)
+    */
+    this.extractMin = function() {
+        var result = this.min();
+        
+        /* move the last element to the root or empty the tree completely */
+        /* bubble down the new root if necessary */
+        (tree.length == 1) && (tree = []) || (tree[0] = tree.pop()) && bubble_down(0);
+        
+        return result;        
+    }
+    
+    /* currently unused, TODO implement */
+    this.changeKey = function(index, key) {
+        throw "function not implemented";
+    }
+
+    this.heapify = function() {
+        for(var start = Math.floor((tree.length - 2) / 2); start >= 0; start--) {
+            bubble_down(start);
+        }
+    }
+    
+    /* insert the input elements one by one only when we don't have a key property (TODO can be done more elegant) */
+    for(i in (array || []))
+        this.insert(array[i]);
+}
+
+
+
+/*
+    Quick Sort:
+        1. Select some random value from the array, the median.
+        2. Divide the array in three smaller arrays according to the elements
+           being less, equal or greater than the median.
+        3. Recursively sort the array containg the elements less than the
+           median and the one containing elements greater than the median.
+        4. Concatenate the three arrays (less, equal and greater).
+        5. One or no element is always sorted.
+    TODO: This could be implemented more efficiently by using only one array object and several pointers.
+*/
+function quickSort(arr) {
+    /* recursion anchor: one element is always sorted */
+    if(arr.length <= 1) return arr;
+    /* randomly selecting some value */
+    var median = arr[Math.floor(Math.random() * arr.length)];
+    var arr1 = [], arr2 = [], arr3 = [];
+    for(var i in arr) {
+        arr[i] < median && arr1.push(arr[i]);
+        arr[i] == median && arr2.push(arr[i]);
+        arr[i] > median && arr3.push(arr[i]);
+    }
+    /* recursive sorting and assembling final result */
+    return quickSort(arr1).concat(arr2).concat(quickSort(arr3));
+}
+
+/*
+    Selection Sort:
+        1. Select the minimum and remove it from the array
+        2. Sort the rest recursively
+        3. Return the minimum plus the sorted rest
+        4. An array with only one element is already sorted
+*/
+function selectionSort(arr) {
+    /* recursion anchor: one element is always sorted */
+    if(arr.length == 1) return arr;
+    var minimum = Infinity;
+    var index;
+    for(var i in arr) {
+        if(arr[i] < minimum) {
+            minimum = arr[i];
+            index = i; /* remember the minimum index for later removal */
+        }
+    }
+    /* remove the minimum */
+    arr.splice(index, 1);
+    /* assemble result and sort recursively (could be easily done iteratively as well)*/
+    return [minimum].concat(selectionSort(arr));
+}
+
+/*
+    Merge Sort:
+        1. Cut the array in half
+        2. Sort each of them recursively
+        3. Merge the two sorted arrays
+        4. An array with only one element is considered sorted
+
+*/
+function mergeSort(arr) {
+    /* merges two sorted arrays into one sorted array */
+    function merge(a, b) {
+        /* result set */
+        var c = [];
+        /* as long as there are elements in the arrays to be merged */
+        while(a.length > 0 || b.length > 0){
+            /* are there elements to be merged, if yes, compare them and merge */
+            var n = a.length > 0 && b.length > 0 ? a[0] < b[0] ? a.shift() : b.shift() : b.length > 0 ? b.shift() : a.length > 0 ? a.shift() : null;
+            /* always push the smaller one onto the result set */
+            n != null && c.push(n);
+        }
+        return c;
+    }
+    /* this mergeSort implementation cuts the array in half, wich should be fine with randomized arrays, but introduces the risk of a worst-case scenario */
+    median = Math.floor(arr.length / 2);
+    var part1 = arr.slice(0, median); /* for some reason it doesn't work if inserted directly in the return statement (tried so with firefox) */
+    var part2 = arr.slice(median - arr.length);
+    return arr.length <= 1 ? arr : merge(
+        mergeSort(part1), /* first half */
+        mergeSort(part2) /* second half */
+    );
+}
+
+/* Balanced Red-Black-Tree */
+function RedBlackTree(arr) {
+    
+}
+
+function BTree(arr) {
+    
+}
+
+function NaryTree(n, arr) {
+    
+}
+
+/**
+ * Knuth-Morris-Pratt string matching algorithm - finds a pattern in a text.
+ * FIXME: Doesn't work correctly yet.
+ */
+function kmp(p, t) {
+
+    /**
+     * PREFIX, OVERLAP or FALIURE function for KMP. Computes how many iterations
+     * the algorithm can skip after a mismatch.
+     *
+     * @input p - pattern (string)
+     * @result array of skippable iterations
+     */
+    function prefix(p) {
+        /* pi contains the computed skip marks */
+        var pi = [0], k = 0;
+        for(q = 1; q < p.length; q++) {
+            while(k > 0 && (p.charAt(k) != p.charAt(q)))
+                k = pi[k-1];
+            
+            (p.charAt(k) == p.charAt(q)) && k++;
+            
+            pi[q] = k;
+        }
+        return pi;
+    }
+    
+    /* The actual KMP algorithm starts here. */
+    
+    var pi = prefix(p), q = 0, result = [];
+    
+    for(var i = 0; i < t.length; i++) {
+        /* jump forward as long as the character doesn't match */
+        while((q > 0) && (p.charAt(q) != t.charAt(i)))
+            q = pi[q];
+        
+        (p.charAt(q) == t.charAt(i)) && q++;
+        
+        (q == p.length) && result.push(i - p.length) && (q = pi[q]);
+    }
+    
+    return result;
+}
+
+/* step for algorithm visualisation */
+function step(comment, funct) {
+    //wait for input
+    //display comment (before or after waiting)
+//    next.wait();
+    /* execute callback function */
+    funct();
+}
+
+/**
+ * Curry - Function currying
+ * Copyright (c) 2008 Ariel Flesler - aflesler(at)gmail(dot)com | http://flesler.blogspot.com
+ * Licensed under BSD (http://www.opensource.org/licenses/bsd-license.php)
+ * Date: 10/4/2008
+ *
+ * @author Ariel Flesler
+ * @version 1.0.1
+ */
+function curry( fn ){
+	return function(){
+		var args = curry.args(arguments),
+			master = arguments.callee,
+			self = this;
+
+		return args.length >= fn.length ? fn.apply(self,args) :	function(){
+			return master.apply( self, args.concat(curry.args(arguments)) );
+		};
+	};
+};
+
+curry.args = function( args ){
+	return Array.prototype.slice.call(args);
+};
+
+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;
+}

Added: karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graffle.js
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graffle.js?rev=1165446&view=auto
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graffle.js (added)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graffle.js Mon Sep  5 23:04:33 2011
@@ -0,0 +1,106 @@
+/**
+ * Originally grabbed from the official RaphaelJS Documentation
+ * http://raphaeljs.com/graffle.html
+ * Adopted (arrows) and commented by Philipp Strathausen http://blog.ameisenbar.de
+ * Licenced under the MIT licence.
+ */
+
+/**
+ * Usage:
+ * connect two shapes
+ * parameters: 
+ *      source shape [or connection for redrawing], 
+ *      target shape,
+ *      style with { fg : linecolor, bg : background color, directed: boolean }
+ * returns:
+ *      connection { draw = function() }
+ */
+Raphael.fn.connection = function (obj1, obj2, style) {
+    var selfRef = this;
+    /* create and return new connection */
+    var edge = {/*
+        from : obj1,
+        to : obj2,
+        style : style,*/
+        draw : function() {
+            /* get bounding boxes of target and source */
+            var bb1 = obj1.getBBox();
+            var bb2 = obj2.getBBox();
+            var off1 = 0;
+            var off2 = 0;
+            /* coordinates for potential connection coordinates from/to the objects */
+            var p = [
+                {x: bb1.x + bb1.width / 2, y: bb1.y - off1},              /* NORTH 1 */
+                {x: bb1.x + bb1.width / 2, y: bb1.y + bb1.height + off1}, /* SOUTH 1 */
+                {x: bb1.x - off1, y: bb1.y + bb1.height / 2},             /* WEST  1 */
+                {x: bb1.x + bb1.width + off1, y: bb1.y + bb1.height / 2}, /* EAST  1 */
+                {x: bb2.x + bb2.width / 2, y: bb2.y - off2},              /* NORTH 2 */
+                {x: bb2.x + bb2.width / 2, y: bb2.y + bb2.height + off2}, /* SOUTH 2 */
+                {x: bb2.x - off2, y: bb2.y + bb2.height / 2},             /* WEST  2 */
+                {x: bb2.x + bb2.width + off2, y: bb2.y + bb2.height / 2}  /* EAST  2 */
+            ];
+            
+            /* distances between objects and according coordinates connection */
+            var d = {}, dis = [];
+
+            /*
+             * find out the best connection coordinates by trying all possible ways
+             */
+            /* loop the first object's connection coordinates */
+            for (var i = 0; i < 4; i++) {
+                /* loop the seond object's connection coordinates */
+                for (var j = 4; j < 8; j++) {
+                    var dx = Math.abs(p[i].x - p[j].x),
+                        dy = Math.abs(p[i].y - p[j].y);
+                    if ((i == j - 4) || (((i != 3 && j != 6) || p[i].x < p[j].x) && ((i != 2 && j != 7) || p[i].x > p[j].x) && ((i != 0 && j != 5) || p[i].y > p[j].y) && ((i != 1 && j != 4) || p[i].y < p[j].y))) {
+                        dis.push(dx + dy);
+                        d[dis[dis.length - 1].toFixed(3)] = [i, j];
+                    }
+                }
+            }
+            var res = dis.length == 0 ? [0, 4] : d[Math.min.apply(Math, dis).toFixed(3)];
+            /* bezier path */
+            var x1 = p[res[0]].x,
+                y1 = p[res[0]].y,
+                x4 = p[res[1]].x,
+                y4 = p[res[1]].y,
+                dx = Math.max(Math.abs(x1 - x4) / 2, 10),
+                dy = Math.max(Math.abs(y1 - y4) / 2, 10),
+                x2 = [x1, x1, x1 - dx, x1 + dx][res[0]].toFixed(3),
+                y2 = [y1 - dy, y1 + dy, y1, y1][res[0]].toFixed(3),
+                x3 = [0, 0, 0, 0, x4, x4, x4 - dx, x4 + dx][res[1]].toFixed(3),
+                y3 = [0, 0, 0, 0, y1 + dy, y1 - dy, y4, y4][res[1]].toFixed(3);
+            /* assemble path and arrow */
+            var path = ["M", x1.toFixed(3), y1.toFixed(3), "C", x2, y2, x3, y3, x4.toFixed(3), y4.toFixed(3)].join(",");
+            /* arrow */
+            if(style && style.directed) {
+                /* magnitude, length of the last path vector */
+                var mag = Math.sqrt((y4 - y3) * (y4 - y3) + (x4 - x3) * (x4 - x3));
+                /* vector normalisation to specified length  */
+                var norm = function(x,l){return (-x*(l||5)/mag);};
+                /* calculate array coordinates (two lines orthogonal to the path vector) */
+                var arr = [
+                    {x:(norm(x4-x3)+norm(y4-y3)+x4).toFixed(3), y:(norm(y4-y3)+norm(x4-x3)+y4).toFixed(3)},
+                    {x:(norm(x4-x3)-norm(y4-y3)+x4).toFixed(3), y:(norm(y4-y3)-norm(x4-x3)+y4).toFixed(3)}
+                ];
+                path = path + ",M"+arr[0].x+","+arr[0].y+",L"+x4+","+y4+",L"+arr[1].x+","+arr[1].y; 
+            }
+            /* function to be used for moving existent path(s), e.g. animate() or attr() */
+            var move = "attr";
+            /* applying path(s) */
+            edge.fg && edge.fg[move]({path:path}) 
+                || (edge.fg = selfRef.path(path).attr({stroke: style && style.stroke || "#000", fill: "none"}).toBack());
+            edge.bg && edge.bg[move]({path:path})
+                || style && style.fill && (edge.bg = style.fill.split && selfRef.path(path).attr({stroke: style.fill.split("|")[0], fill: "none", "stroke-width": style.fill.split("|")[1] || 3}).toBack());
+            /* setting label */
+            style && style.label 
+                && (edge.label && edge.label.attr({x:(x1+x4)/2, y:(y1+y4)/2}) 
+                    || (edge.label = selfRef.text((x1+x4)/2, (y1+y4)/2, style.label).attr({fill: "#000", "font-size": style["font-size"] || "12px"})));
+            style && style.label && style["label-style"] && edge.label && edge.label.attr(style["label-style"]);
+            style && style.callback && style.callback(edge);
+        }
+    }
+    edge.draw();
+    return edge;
+};
+//Raphael.prototype.set.prototype.dodo=function(){console.log("works");};

Added: karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graph.js
URL: http://svn.apache.org/viewvc/karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graph.js?rev=1165446&view=auto
==============================================================================
--- karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graph.js (added)
+++ karaf/sandbox/webconsole/trunk/blueprint/src/main/resources/org/apache/karaf/webconsole/blueprint/internal/details/dracula_graph.js Mon Sep  5 23:04:33 2011
@@ -0,0 +1,527 @@
+/*
+ *  Dracula Graph Layout and Drawing Framework 0.0.3alpha
+ *  (c) 2010 Philipp Strathausen <strathausen@gmail.com>, http://strathausen.eu
+ *  Contributions by Jake Stothard <stothardj@gmail.com>.
+ *
+ *  based on the Graph JavaScript framework, version 0.0.1
+ *  (c) 2006 Aslak Hellesoy <aslak.hellesoy@gmail.com>
+ *  (c) 2006 Dave Hoover <dave.hoover@gmail.com>
+ *
+ *  Ported from Graph::Layouter::Spring in
+ *    http://search.cpan.org/~pasky/Graph-Layderer-0.02/
+ *  The algorithm is based on a spring-style layouter of a Java-based social
+ *  network tracker PieSpy written by Paul Mutton <paul@jibble.org>.
+ *
+ *  This code is freely distributable under the MIT license. Commercial use is
+ *  hereby granted without any cost or restriction.
+ *
+ *  Links:
+ *
+ *  Graph Dracula JavaScript Framework:
+ *      http://graphdracula.net
+ *
+ /*--------------------------------------------------------------------------*/
+
+/*
+ * 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.edges = [];
+    this.snapshots = []; // previous graph states TODO to be implemented
+    this.edgeFactory = new EdgeFactory();
+};
+Graph.prototype = {
+    /* 
+     * add a node
+     * @id          the node's ID (string or number)
+     * @content     (optional, dictionary) can contain any information that is
+     *              being interpreted by the layout algorithm or the graph
+     *              representation
+     */
+    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);
+        }
+        return this.nodes[id];
+    },
+
+    addEdge: function(source, target, style) {
+        var s = this.addNode(source);
+        var t = this.addNode(target);
+        var edge = this.edgeFactory.build(s, t);
+        jQuery.extend(edge.style,style);
+        s.edges.push(edge);
+        this.edges.push(edge);
+        // NOTE: Even directed edges are added to both nodes.
+        t.edges.push(edge);
+    },
+    
+    /* TODO to be implemented
+     * Preserve a copy of the graph state (nodes, positions, ...)
+     * @comment     a comment describing the state
+     */
+    snapShot: function(comment) {
+        /* FIXME
+        var graph = new Graph();
+        graph.nodes = jQuery.extend(true, {}, this.nodes);
+        graph.edges = jQuery.extend(true, {}, this.edges);
+        this.snapshots.push({comment: comment, graph: graph});
+        */
+    },
+    removeNode: function(id) {
+        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--;
+            }
+        }
+    }
+};
+
+/*
+ * Node
+ */
+Graph.Node = function(id, node){
+    node = node || {};
+    node.id = id;
+    node.edges = [];
+    node.hide = function() {
+        this.hidden = true;
+        this.shape && this.shape.hide(); /* FIXME this is representation specific code and should be elsewhere */
+        for(i in this.edges)
+            (this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].hide && this.edges[i].hide();
+    };
+    node.show = function() {
+        this.hidden = false;
+        this.shape && this.shape.show();
+        for(i in this.edges)
+            (this.edges[i].source.id == id || this.edges[i].target == id) && this.edges[i].show && this.edges[i].show();
+    };
+    return node;
+};
+Graph.Node.prototype = {
+};
+
+/*
+ * Renderer base class
+ */
+Graph.Renderer = {};
+
+/*
+ * Renderer implementation using RaphaelJS
+ */
+Graph.Renderer.Raphael = function(element, graph, width, height) {
+    this.width = width || 400;
+    this.height = height || 400;
+    var selfRef = this;
+    this.r = Raphael(element, this.width, this.height);
+    this.radius = 40; /* max dimension of a node */
+    this.graph = graph;
+    this.mouse_in = false;
+
+    /* TODO default node rendering function */
+    if(!this.graph.render) {
+        this.graph.render = function() {
+            return;
+        }
+    }
+    
+    /*
+     * Dragging
+     */
+    this.isDrag = false;
+    this.dragger = function (e) {
+        this.dx = e.clientX;
+        this.dy = e.clientY;
+        selfRef.isDrag = this;
+        this.set && this.set.animate({"fill-opacity": .1}, 200) && this.set.toFront();
+        e.preventDefault && e.preventDefault();
+    };
+    
+    var d = document.getElementById(element);
+    d.onmousemove = function (e) {
+        e = e || window.event;
+        if (selfRef.isDrag) {
+            var bBox = selfRef.isDrag.set.getBBox();
+            // TODO round the coordinates here (eg. for proper image representation)
+            var newX = e.clientX - selfRef.isDrag.dx + (bBox.x + bBox.width / 2);
+            var newY = e.clientY - selfRef.isDrag.dy + (bBox.y + bBox.height / 2);
+            /* prevent shapes from being dragged out of the canvas */
+            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));
+            for (var i in selfRef.graph.edges) {
+                selfRef.graph.edges[i].connection && selfRef.graph.edges[i].connection.draw();
+            }
+            //selfRef.r.safari();
+            selfRef.isDrag.dx = clientX;
+            selfRef.isDrag.dy = clientY;
+        }
+    };
+    d.onmouseup = function () {
+        selfRef.isDrag && selfRef.isDrag.set.animate({"fill-opacity": .6}, 500);
+        selfRef.isDrag = false;
+    };
+    this.draw();
+};
+Graph.Renderer.Raphael.prototype = {
+    translate: function(point) {
+        return [
+            (point[0] - this.graph.layoutMinX) * this.factorX + this.radius,
+            (point[1] - this.graph.layoutMinY) * this.factorY + this.radius
+        ];
+    },
+
+    rotate: function(point, length, angle) {
+        var dx = length * Math.cos(angle);
+        var dy = length * Math.sin(angle);
+        return [point[0]+dx, point[1]+dy];
+    },
+
+    draw: function() {
+        this.factorX = (this.width - 2 * this.radius) / (this.graph.layoutMaxX - this.graph.layoutMinX);
+        this.factorY = (this.height - 2 * this.radius) / (this.graph.layoutMaxY - this.graph.layoutMinY);
+        for (i in this.graph.nodes) {
+            this.drawNode(this.graph.nodes[i]);
+        }
+        for (var i = 0; i < this.graph.edges.length; i++) {
+            this.drawEdge(this.graph.edges[i]);
+        }
+    },
+
+    drawNode: function(node) {
+        var point = this.translate([node.layoutPosX, node.layoutPosY]);
+        node.point = point;
+
+        /* if node has already been drawn, move the nodes */
+        if(node.shape) {
+            var oBBox = node.shape.getBBox();
+            var opoint = { x: oBBox.x + oBBox.width / 2, y: oBBox.y + oBBox.height / 2};
+            node.shape.translate(Math.round(point[0] - opoint.x), Math.round(point[1] - opoint.y));
+            this.r.safari();
+            return node;
+        }/* else, draw new nodes */
+
+        var shape;
+
+        /* if a node renderer function is provided by the user, then use it 
+           or the default render function instead */
+        if(!node.render) {
+            node.render = function(r, node) {
+                /* the default node drawing */
+                var color = Raphael.getColor();
+                var ellipse = r.ellipse(0, 0, 30, 20).attr({fill: color, stroke: color, "stroke-width": 2});
+                /* set DOM node ID */
+                ellipse.node.id = node.label || node.id;
+                shape = r.set().
+                    push(ellipse).
+                    push(r.text(0, 30, node.label || node.id));
+                return shape;
+            }
+        }
+        /* or check for an ajax representation of the nodes */
+        if(node.shapes) {
+            // TODO ajax representation evaluation
+        }
+
+        shape = node.render(this.r, node).hide();
+
+        shape.attr({"fill-opacity": .6});
+        /* re-reference to the node an element belongs to, needed for dragging all elements of a node */
+        shape.items.forEach(function(item){ item.set = shape; item.node.style.cursor = "move"; });
+        shape.mousedown(this.dragger);
+
+        var box = shape.getBBox();
+        shape.translate(Math.round(point[0]-(box.x+box.width/2)),Math.round(point[1]-(box.y+box.height/2)))
+        //console.log(box,point);
+        node.hidden || shape.show();
+        node.shape = shape;
+    },
+    drawEdge: function(edge) {
+        /* if this edge already exists the other way around and is undirected */
+        if(edge.backedge)
+            return;
+        if(edge.source.hidden || edge.target.hidden) {
+            edge.connection && edge.connection.fg.hide() | edge.connection.bg && edge.connection.bg.hide();
+            return;
+        }
+        /* if edge already has been drawn, only refresh the edge */
+        if(!edge.connection) {
+            edge.style && edge.style.callback && edge.style.callback(edge); // TODO move this somewhere else
+            edge.connection = this.r.connection(edge.source.shape, edge.target.shape, edge.style);
+            return;
+        }
+        //FIXME showing doesn't work well
+        edge.connection.fg.show();
+        edge.connection.bg && edge.connection.bg.show();
+        edge.connection.draw();
+    }
+};
+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();
+};
+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
+
+        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) {
+        if (typeof node1 == 'undefined' || typeof node2 == 'undefined')
+            return;
+        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;
+    }
+};
+
+/*
+ * usefull JavaScript extensions, 
+ */
+
+function log(a) {console.log&&console.log(a);}
+
+/*
+ * Raphael Tooltip Plugin
+ * - attaches an element as a tooltip to another element
+ *
+ * Usage example, adding a rectangle as a tooltip to a circle:
+ *
+ *      paper.circle(100,100,10).tooltip(paper.rect(0,0,20,30));
+ *
+ * If you want to use more shapes, you'll have to put them into a set.
+ *
+ */
+Raphael.el.tooltip = function (tp) {
+    this.tp = tp;
+    this.tp.o = {x: 0, y: 0};
+    this.tp.hide();
+    this.hover(
+        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.clientX, y: event.clientY};
+            });
+            this.tp.show().toFront();
+        }, 
+        function(event){
+            this.tp.hide();
+            this.unmousemove();
+        });
+    return this;
+};
+
+/* For IE */
+if (!Array.prototype.forEach)
+{
+  Array.prototype.forEach = function(fun /*, thisp*/)
+  {
+    var len = this.length;
+    if (typeof fun != "function")
+      throw new TypeError();
+
+    var thisp = arguments[1];
+    for (var i = 0; i < len; i++)
+    {
+      if (i in this)
+        fun.call(thisp, this[i], i, this);
+    }
+  };
+}



Mime
View raw message