include $(TOPDIR)/rules.mk
PKG_NAME:=luci-app-bmx6
-PKG_RELEASE:=2
+PKG_RELEASE:=3
PKG_BUILD_DIR := $(BUILD_DIR)/$(PKG_NAME)
CATEGORY:=LuCI
SUBMENU:=3. Applications
TITLE:= bmx6 configuration, status and visualization module
- DEPENDS:=+luci-lib-json +luci-mod-admin-core +luci-lib-httpclient +bmx6
+ DEPENDS:=+luci-lib-json +luci-mod-admin-full +luci-lib-httpclient +bmx6
MAINTAINER:= Pau Escrich <p4u@dabax.net>
endef
define Package/luci-app-bmx6/description
- bmx6 web module for LuCi web interface
+ bmx6 web application (status and configuration) for LuCi web interface
endef
define Package/luci-app-bmx6/conffiles
entry(place,call("action_status_j"),"Status",0)
table.remove(place)
- -- not visible
- table.insert(place,"nodes_nojs")
- entry(place, call("action_nodes"), nil)
- table.remove(place)
-
--- nodes
table.insert(place,"Nodes")
entry(place,call("action_nodes_j"),"Nodes",1)
entry(place,call("action_tunnels_j"), "Tunnels", 3).leaf = true
table.remove(place)
- -- Gateways (deprecated)
- --table.insert(place,"Gateways")
- --entry(place,call("action_gateways_j"),"Gateways").leaf = true
- --table.remove(place)
-
--- Chat
table.insert(place,"Chat")
entry(place,call("action_chat"),"Chat",5)
end
-function action_status()
- local status = bmx6json.get("status").status or nil
- local interfaces = bmx6json.get("interfaces").interfaces or nil
-
- if status == nil or interfaces == nil then
- luci.template.render("bmx6/error", {txt="Cannot fetch data from bmx6 json"})
- else
- luci.template.render("bmx6/status", {status=status,interfaces=interfaces})
- end
-end
-
function action_status_j()
luci.template.render("bmx6/status_j", {})
end
-function action_nodes()
- local orig_list = bmx6json.get("originators").originators or nil
-
- if orig_list == nil then
- luci.template.render("bmx6/error", {txt="Cannot fetch data from bmx6 json"})
- return nil
- end
-
- local originators = {}
- local desc = nil
- local orig = nil
- local name = ""
- local ipv4 = ""
-
- for _,o in ipairs(orig_list) do
- orig = bmx6json.get("originators/"..o.name) or {}
- desc = bmx6json.get("descriptions/"..o.name) or {}
-
- if string.find(o.name,'.') then
- name = luci.util.split(o.name,'.')[1]
- else
- name = o.name
- end
-
- table.insert(originators,{name=name,orig=orig,desc=desc})
- end
-
- luci.template.render("bmx6/nodes", {originators=originators})
-end
-
function action_nodes_j()
local http = require "luci.http"
local link_non_js = "/cgi-bin/luci" .. http.getenv("PATH_INFO") .. '/nodes_nojs'
luci.template.render("bmx6/tunnels_j", {})
end
-
function action_links(host)
local links = bmx6json.get("links", host)
local devlinks = {}
+++ /dev/null
-<%+header%>
-
- <style type="text/css">
- table.int {
- border-width: 2px;
- border-spacing: ;
- border-style: inset;
- border-color: white;
- border-collapse: collapse;
- background-color: #dadbe6;
- }
- table.int tr {
- border-width: 5px;
- padding: 4px;
- border-style: solid;
- border-color: white;
- background-color: #dadbe9;
- }
- table.int td {
- border-width: 5px;
- padding: 4px;
- border-style: solid;
- border-color: white;
- background-color: #dadbe9;
- text-align: center;
- }
- </style>
-
-<h2><a id="content" name="content"><%:Interfaces%></a></h2>
-Interfaces where bmx6 is running
-<br />
-<br />
-<table class="int">
-<tr>
- <td><strong>Name</strong></td>
- <td><strong>State</strong></td>
- <td><strong>Type</strong></td>
- <td><strong>Rate (Min/Max)</strong></td>
- <td><strong>Local IP</strong></td>
- <td><strong>Global IP</strong></td>
- <td><strong>Multicast IP</strong></td>
- <td><strong>Primary</strong></td>
-</tr>
-<% for i,v in ipairs(data) do %>
- <tr>
- <td><%=v.devName%></td>
- <td><%=v.state%></td>
- <td><%=v.type%></td>
- <td><%=v.rateMin%>/<%=v.rateMax%></td>
- <td><%=v.llocalIp%></td>
- <td><%=v.globalIp%></td>
- <td><%=v.multicastIp%></td>
- <td><%=v.primary%></td>
- </tr>
-<%end%>
-</table>
-
-<br />
-<%+footer%>
+++ /dev/null
-<%+header%>
-<style type="text/css">
-
- table {
- width:90%;
- border-top:1px solid #e5eaf8;
- border-right:1px solid #e5eaf8;
- margin:1em auto;
- border-collapse:collapse;
- }
-
- td {
- color:#678197;
- border-bottom:1px solid #e6eff8;
- border-left:1px solid #e6eff8;
- padding:.3em 1em;
- text-align:center;
- }
- th {
- background:#f4f9fe;
- text-align:center;
- font:bold 1.2em/2em "Century Gothic","Trebuchet MS",Arial,Helvetica,sans-serif;
- color:#66a3d3;
- }
-
-
-#neighbour {
- position:relative;
- margin:5px;
-}
-
-#orig_id {
- background-color: black;
- color: white;
- text-ident:10px;
-}
-</style>
-
-<h2><a id="content" name="content"><%:Neighbours%></a></h2>
-<table>
- <tr>
- <th scope="col">Name</th>
- <th scope="col">IPv4</th>
- <th scope="col">IPv6</th>
- <th scope="col">Via Dev</th>
- <th scope="col">Via IP</th>
- <th scope="col">Routes</th>
- <th scope="col">Metric</th>
- <th scope="col">Last Desc</th>
- <th scope="col">Last Ref</th>
- </tr>
-
-<% for i,o in ipairs(originators) do %>
- <tr>
- <td><%=o.name%></td>
- <td><a href="http://<%=o.ipv4%>"><%=o.ipv4%></a></td>
- <td><a href="http://[<%=o.orig.primaryIp%>]"><%=o.orig.primaryIp%></a></td>
- <td><%=o.orig.viaDev%></td>
- <td><%=o.orig.viaIp%></td>
- <td><%=o.orig.routes%></td>
- <td><%=o.orig.metric%></td>
- <td><%=o.orig.lastDesc%></td>
- <td><%=o.orig.lastRef%></td>
- </tr>
-<%end%>
-</table>
-
-<table>
- <tr>
- <th scope="col">Node</th>
- <th scope="col">Announced networks</th>
- </tr>
-
-<% for i,o in ipairs(originators) do %>
- <tr>
- <td><%=o.name%></td>
- <td style="text-align:left;">
- <% if o.desc.DESC_ADV ~= nil then %>
- <% for j,h in ipairs(o.desc.DESC_ADV.extensions[2].HNA6_EXTENSION) do %>
- <%=h.address%>
- <% end %>
- <% end %>
- </td>
- </tr>
-<% end %>
-</table>
-
-<br />
-<%+footer%>
+++ /dev/null
-<%+header%>
-<script type="text/javascript">//<![CDATA[
-
- var displayExtraInfo = function ( id ) {
-
- document.getElementById('extra-info').innerHTML = document.getElementById(id).innerHTML;
- }
- XHR.poll(5, '/cgi-bin/bmx6-info', { '$neighbours': '' },
- function(x, st)
- {
- var originators = st.neighbours[0].originators;
- var descriptions = st.neighbours[1].descriptions;
-
- var tb = document.getElementById('descriptions_table');
-
- if ( originators.length != descriptions.length )
- {
- var tr = tb.insertRow(-1);
- tr.className = 'cbi-section-table-row';
- var td = tr.insertCell(-1);
- td.colSpan = 7;
- td.innerHTML = '<em><br /><%:Some problem with JSON: lenght of originators and descriptions different. %></em>';
- td.innerHTML += '<em><%: Please perform a manually cache flush from a terminal: bmx6 -c --flushAll %></em>'
- return 1;
- }
-
- if ( originators && descriptions && tb)
- {
- /* clear all rows */
- while( tb.rows.length > 1 )
- tb.deleteRow(1);
-
- for( var i = 0; i < descriptions.length; i++ )
- {
- var tr = tb.insertRow(-1);
- var nodename = descriptions[i].DESC_ADV.globalId.replace(/\.[^\.]+$/,"");
- tr.className = 'cbi-section-table-row cbi-rowstyle-' + ((i % 2) + 1);
- tr.insertCell(-1).innerHTML = '<a onclick="displayExtraInfo(\'ip-'+i+'\')"><img src=\"<%=resource%>/cbi/help.gif\" /></a>';
- tr.insertCell(-1).innerHTML = nodename;
-
- var extensions = descriptions[i].DESC_ADV.extensions;
-
- //Looking for the extensions
- var hna6 = [];
- var tun4in6 = [];
- var tun6 = [];
- for( var e = 0; e < extensions.length; e++)
- {
- if( extensions[e].HNA6_EXTENSION )
- {
- hna6 = extensions[e].HNA6_EXTENSION;
- }
- if ( extensions[e].TUN4IN6_NET_EXTENSION )
- {
- tun4in6 = extensions[e].TUN4IN6_NET_EXTENSION;
- }
- }
-
- var gateways = '<ul>';
- for ( var t = 0; t < tun4in6.length; t++)
- {
- if ( tun4in6[t].networklen == "32" )
- gateways += '<li><a href="http://' + tun4in6[t].network + '">' + tun4in6[t].network + '</a></li>';
- else
- gateways += "<li>"+tun4in6[t].network+'/'+tun4in6[t].networklen + ' | ' + tun4in6[t].bandwidth+'</li>';
- }
- gateways += '</ul>';
-
- //Adding HNAs with prefix=128 as main address
- var ipstxt = '';
- var address;
- var first = 1;
- var ipstxt_hidden = '<ul>';
- var hna6list = '<ul>';
-
- for( var e = 0; e < hna6.length; e++ )
- {
- address = hna6[e].address;
- prefix = hna6[e].prefixlen;
- if ( prefix == '128' )
- {
- if (first)
- {
- ipstxt += address;
- ipstxt_hidden += '<li><a href="http://['+address+']" >'+address+"</a></li>";
- first = 0;
- }
- else {
- ipstxt_hidden += '<li><a href="http://['+address+']" >'+address+"</a></li>";
- }
- }
- else {
- hna6list += '<li>'+address+'/'+prefix+'</li>';
- }
- }
- hna6list += '</ul>';
- ipstxt_hidden += '</ul>';
-
- tr.insertCell(-1).innerHTML = ipstxt;
-
- tr.insertCell(-1).innerHTML = originators[i].viaDev;
- tr.insertCell(-1).innerHTML = originators[i].metric;
- tr.insertCell(-1).innerHTML = originators[i].lastDesc;
- tr.insertCell(-1).innerHTML = originators[i].lastRef;
- tr.insertCell(-1).innerHTML = originators[i].blocked;
- //tr.onclick = displayExtraInfo("ip-"+i);
-
- extrainfo = '<div id="ip-'+ i +'" class="hideme">' + "<div class='inforow'><br /><br /><h4>" + nodename + '</h4></div>\n' + "<div class='inforow'><h5>Available IPs</h5>\n<p>" + ipstxt_hidden + "</p></div>\n" + "<div class='inforow'><h5>Gateways announced</h5>\n<p>" + gateways + "</p></div>\n" + "<div class='inforow'><h5>Networks announced</h5>\n<p>" + hna6list + "</p></div>\n";
-
- extrainfo += "\n</div>";
-
- tr.insertCell(-1).innerHTML = extrainfo;
-
- }
-
- if( tb.rows.length == 1 )
- {
- var tr = tb.insertRow(-1);
- tr.className = 'cbi-section-table-row';
-
- var td = tr.insertCell(-1);
- td.colSpan = 7;
- td.innerHTML = '<em><br /><%:There are no nodes available.%></em>';
- }
- }
- }
- );
-//]]></script>
-
-<style>
-
- div.hideme{
- display: none;
- }
-
- div.info{
- background: #FFF;
- border: solid 1px;
- height: 80px;
- display: block;
- overflow: auto;
- text-align: center;
- }
-
- div.inforow{
- text-align:center;
- display:inline-block;
- width:20%;
- margin:5px;
- vertical-align:top;
- }
-
-#extra-info ul { list-style: none outside none; margin-left: 0em; }
-
-</style>
-<div class="cbi-map">
-
-<h2>Originators</h2>
-<div class="cbi-map-descr"></div>
-<div id="extra-info" class="info">
- <br />
- Click to the icon <img src="<%=resource%>/cbi/help.gif" /> to see individual node information
-</div>
-<fieldset class="cbi-section">
- <legend><%:Mesh nodes%></legend>
- <table class="cbi-section-table" id="descriptions_table">
- <tr class="cbi-section-table-titles">
- <th class="cbi-section-table-cell"></th>
- <th class="cbi-section-table-cell"><%:Hostname%></th>
- <th class="cbi-section-table-cell"><%:Primary IP%></th>
- <th class="cbi-section-table-cell"><%:Via Device%></th>
- <th class="cbi-section-table-cell"><%:Metric%></th>
- <th class="cbi-section-table-cell"><%:Last Desc%></th>
- <th class="cbi-section-table-cell"><%:Last Ref%></th>
- <th class="cbi-section-table-cell"><%:Blocked%></th>
- </tr>
- <tr class="cbi-section-table-row">
- <td colspan="8"><em><br /><%:Collecting data...%></em></td>
- </tr>
- </table>
-</fieldset>
-
-</div>
-<a href="<%=link_non_js%>">Go to non JavaScript view</a>
-
-
-<%+footer%>
-
+++ /dev/null
-<%+header%>
-<style type="text/css">
-
- table {
- width:90%;
- border-top:1px solid #e5eaf8;
- border-right:1px solid #e5eaf8;
- margin:1em auto;
- border-collapse:collapse;
- }
-
- td {
- color:#678197;
- border-bottom:1px solid #e6eff8;
- border-left:1px solid #e6eff8;
- padding:.3em 1em;
- text-align:center;
- }
- th {
- background:#f4f9fe;
- text-align:center;
- font:bold 1.2em/2em "Century Gothic","Trebuchet MS",Arial,Helvetica,sans-serif;
- color:#66a3d3;
- }
-
-
-#neighbour {
- position:relative;
- margin:5px;
-}
-
-#orig_id {
- background-color: black;
- color: white;
- text-ident:10px;
-}
-</style>
-
-<h2><a id="content" name="content"><%:Nodes%></a></h2>
-<table>
- <tr>
- <th scope="col">Name</th>
- <th scope="col">IPv6</th>
- <th scope="col">Via Dev</th>
- <th scope="col">Via IP</th>
- <th scope="col">Routes</th>
- <th scope="col">Metric</th>
- <th scope="col">Last Desc</th>
- <th scope="col">Last Ref</th>
- </tr>
-
-<% for i,o in ipairs(originators) do %>
- <tr>
- <td><%=o.name%></td>
- <td><a href="http://[<%=o.orig.primaryIp%>]"><%=o.orig.primaryIp%></a></td>
- <td><%=o.orig.viaDev%></td>
- <td><%=o.orig.viaIp%></td>
- <td><%=o.orig.routes%></td>
- <td><%=o.orig.metric%></td>
- <td><%=o.orig.lastDesc%></td>
- <td><%=o.orig.lastRef%></td>
- </tr>
-<%end%>
-</table>
-
-<table>
- <tr>
- <th scope="col">Node</th>
- <th scope="col">Announced networks</th>
- </tr>
-
-<% for i,o in ipairs(originators) do %>
- <tr>
- <td><%=o.name%></td>
- <td style="text-align:left;">
- <% if o.desc.DESC_ADV ~= nil then %>
- <% for j,h in ipairs(o.desc.DESC_ADV.extensions[2].HNA6_EXTENSION) do %>
- <%=h.address%>
- <% end %>
- <% end %>
- </td>
- </tr>
-<% end %>
-</table>
-
-<br />
-<%+footer%>
</div>
-<a href="<%=link_non_js%>">Go to non JavaScript view</a>
-
<script type="text/javascript">//<![CDATA[
var displayExtraInfo = function ( id ) {
document.getElementById('extra-info').innerHTML = document.getElementById(id).innerHTML;
+++ /dev/null
-<%+header%>
-<link rel="stylesheet" type="text/css" href="/luci-static/resources/bmx6/style.css" />
-
-<img src="<%=resource%>/bmx6/bmx6logo.png" />
-
-Bmx6 is a routing protocol for Linux based operating systems. Visit <a href="http://bmx6.net">bmx6.net</a> for more info.
-
-<br />
-<br />
-
-<h2>Status of bmx6</h2>
-
-<table>
-<tr>
- <th>Version</th>
- <th>Compatibility</th>
- <th>CodeVersion</th>
- <th>Global Id</th>
- <th>Primary Ip</th>
- <th>Local Id</th>
- <th>Uptime</th>
- <th>CPU</th>
- <th>Nodes</th>
-</tr>
- <tr>
- <td><%=status.version%></td>
- <td><%=status.compatibility%></td>
- <td><%=status.codeVersion%></td>
- <td><%=status.globalId%>/<%=status.rateMax%></td>
- <td><%=status.primaryIp%></td>
- <td><%=status.myLocalId%></td>
- <td><%=status.uptime%></td>
- <td><%=status.cpu%></td>
- <td><%=status.nodes%></td>
- </tr>
-</table>
-
-<br />
-<br />
-
-<h2>Status of interfaces</h2>
-<table>
-<tr>
- <th>Name</th>
- <th>State</th>
- <th>Type</th>
- <th>Rate (Min/Max)</th>
- <th>Local IP</th>
- <th>Global IP</th>
- <th>Multicast IP</th>
- <th>Primary</th>
-</tr>
-<% for i,v in ipairs(interfaces) do %>
- <tr>
- <td><%=v.devName%></td>
- <td><%=v.state%></td>
- <td><%=v.type%></td>
- <td><%=v.rateMin%>/<%=v.rateMax%></td>
- <td><%=v.llocalIp%></td>
- <td><%=v.globalIp%></td>
- <td><%=v.multicastIp%></td>
- <td><%=v.primary%></td>
- </tr>
-<%end%>
-</table>
-
-<br />
-
-<%+footer%>
+++ /dev/null
-<%+header%>
-<h2><a id="content" name="content"><%:Wireless%></a></h2>
-<br />
-<h3>Wireless</h3>
-<%=data%>
-<br />
-<%+footer%>
+++ /dev/null
-/*
- * 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;
-}
+++ /dev/null
-// seedrandom.js
-// Author: David Bau 3/11/2010
-//
-// Defines a method Math.seedrandom() that, when called, substitutes
-// an explicitly seeded RC4-based algorithm for Math.random(). Also
-// supports automatic seeding from local or network sources of entropy.
-//
-// Usage:
-//
-// <script src=http://davidbau.com/encode/seedrandom-min.js></script>
-//
-// Math.seedrandom('yipee'); Sets Math.random to a function that is
-// initialized using the given explicit seed.
-//
-// Math.seedrandom(); Sets Math.random to a function that is
-// seeded using the current time, dom state,
-// and other accumulated local entropy.
-// The generated seed string is returned.
-//
-// Math.seedrandom('yowza', true);
-// Seeds using the given explicit seed mixed
-// together with accumulated entropy.
-//
-// <script src="http://bit.ly/srandom-512"></script>
-// Seeds using physical random bits downloaded
-// from random.org.
-//
-// Examples:
-//
-// Math.seedrandom("hello"); // Use "hello" as the seed.
-// document.write(Math.random()); // Always 0.5463663768140734
-// document.write(Math.random()); // Always 0.43973793770592234
-// var rng1 = Math.random; // Remember the current prng.
-//
-// var autoseed = Math.seedrandom(); // New prng with an automatic seed.
-// document.write(Math.random()); // Pretty much unpredictable.
-//
-// Math.random = rng1; // Continue "hello" prng sequence.
-// document.write(Math.random()); // Always 0.554769432473455
-//
-// Math.seedrandom(autoseed); // Restart at the previous seed.
-// document.write(Math.random()); // Repeat the 'unpredictable' value.
-//
-// Notes:
-//
-// Each time seedrandom('arg') is called, entropy from the passed seed
-// is accumulated in a pool to help generate future seeds for the
-// zero-argument form of Math.seedrandom, so entropy can be injected over
-// time by calling seedrandom with explicit data repeatedly.
-//
-// On speed - This javascript implementation of Math.random() is about
-// 3-10x slower than the built-in Math.random() because it is not native
-// code, but this is typically fast enough anyway. Seeding is more expensive,
-// especially if you use auto-seeding. Some details (timings on Chrome 4):
-//
-// Our Math.random() - avg less than 0.002 milliseconds per call
-// seedrandom('explicit') - avg less than 0.5 milliseconds per call
-// seedrandom('explicit', true) - avg less than 2 milliseconds per call
-// seedrandom() - avg about 38 milliseconds per call
-//
-// LICENSE (BSD):
-//
-// Copyright 2010 David Bau, all rights reserved.
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are met:
-//
-// 1. Redistributions of source code must retain the above copyright
-// notice, this list of conditions and the following disclaimer.
-//
-// 2. Redistributions in binary form must reproduce the above copyright
-// notice, this list of conditions and the following disclaimer in the
-// documentation and/or other materials provided with the distribution.
-//
-// 3. Neither the name of this module nor the names of its contributors may
-// be used to endorse or promote products derived from this software
-// without specific prior written permission.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-//
-/**
- * All code is in an anonymous closure to keep the global namespace clean.
- *
- * @param {number=} overflow
- * @param {number=} startdenom
- */
-(function (pool, math, width, chunks, significance, overflow, startdenom) {
-
-
-//
-// seedrandom()
-// This is the seedrandom function described above.
-//
-math['seedrandom'] = function seedrandom(seed, use_entropy) {
- var key = [];
- var arc4;
-
- // Flatten the seed string or build one from local entropy if needed.
- seed = mixkey(flatten(
- use_entropy ? [seed, pool] :
- arguments.length ? seed :
- [new Date().getTime(), pool, window], 3), key);
-
- // Use the seed to initialize an ARC4 generator.
- arc4 = new ARC4(key);
-
- // Mix the randomness into accumulated entropy.
- mixkey(arc4.S, pool);
-
- // Override Math.random
-
- // This function returns a random double in [0, 1) that contains
- // randomness in every bit of the mantissa of the IEEE 754 value.
-
- math['random'] = function random() { // Closure to return a random double:
- var n = arc4.g(chunks); // Start with a numerator n < 2 ^ 48
- var d = startdenom; // and denominator d = 2 ^ 48.
- var x = 0; // and no 'extra last byte'.
- while (n < significance) { // Fill up all significant digits by
- n = (n + x) * width; // shifting numerator and
- d *= width; // denominator and generating a
- x = arc4.g(1); // new least-significant-byte.
- }
- while (n >= overflow) { // To avoid rounding up, before adding
- n /= 2; // last byte, shift everything
- d /= 2; // right using integer math until
- x >>>= 1; // we have exactly the desired bits.
- }
- return (n + x) / d; // Form the number within [0, 1).
- };
-
- // Return the seed that was used
- return seed;
-};
-
-//
-// ARC4
-//
-// An ARC4 implementation. The constructor takes a key in the form of
-// an array of at most (width) integers that should be 0 <= x < (width).
-//
-// The g(count) method returns a pseudorandom integer that concatenates
-// the next (count) outputs from ARC4. Its return value is a number x
-// that is in the range 0 <= x < (width ^ count).
-//
-/** @constructor */
-function ARC4(key) {
- var t, u, me = this, keylen = key.length;
- var i = 0, j = me.i = me.j = me.m = 0;
- me.S = [];
- me.c = [];
-
- // The empty key [] is treated as [0].
- if (!keylen) { key = [keylen++]; }
-
- // Set up S using the standard key scheduling algorithm.
- while (i < width) { me.S[i] = i++; }
- for (i = 0; i < width; i++) {
- t = me.S[i];
- j = lowbits(j + t + key[i % keylen]);
- u = me.S[j];
- me.S[i] = u;
- me.S[j] = t;
- }
-
- // The "g" method returns the next (count) outputs as one number.
- me.g = function getnext(count) {
- var s = me.S;
- var i = lowbits(me.i + 1); var t = s[i];
- var j = lowbits(me.j + t); var u = s[j];
- s[i] = u;
- s[j] = t;
- var r = s[lowbits(t + u)];
- while (--count) {
- i = lowbits(i + 1); t = s[i];
- j = lowbits(j + t); u = s[j];
- s[i] = u;
- s[j] = t;
- r = r * width + s[lowbits(t + u)];
- }
- me.i = i;
- me.j = j;
- return r;
- };
- // For robust unpredictability discard an initial batch of values.
- // See http://www.rsa.com/rsalabs/node.asp?id=2009
- me.g(width);
-}
-
-//
-// flatten()
-// Converts an object tree to nested arrays of strings.
-//
-/** @param {Object=} result
- * @param {string=} prop */
-function flatten(obj, depth, result, prop) {
- result = [];
- if (depth && typeof(obj) == 'object') {
- for (prop in obj) {
- if (prop.indexOf('S') < 5) { // Avoid FF3 bug (local/sessionStorage)
- try { result.push(flatten(obj[prop], depth - 1)); } catch (e) {}
- }
- }
- }
- return result.length ? result : '' + obj;
-}
-
-//
-// mixkey()
-// Mixes a string seed into a key that is an array of integers, and
-// returns a shortened string seed that is equivalent to the result key.
-//
-/** @param {number=} smear
- * @param {number=} j */
-function mixkey(seed, key, smear, j) {
- seed += ''; // Ensure the seed is a string
- smear = 0;
- for (j = 0; j < seed.length; j++) {
- key[lowbits(j)] =
- lowbits((smear ^= key[lowbits(j)] * 19) + seed.charCodeAt(j));
- }
- seed = '';
- for (j in key) { seed += String.fromCharCode(key[j]); }
- return seed;
-}
-
-//
-// lowbits()
-// A quick "n mod width" for width a power of 2.
-//
-function lowbits(n) { return n & (width - 1); }
-
-//
-// The following constants are related to IEEE 754 limits.
-//
-startdenom = math.pow(width, chunks);
-significance = math.pow(2, significance);
-overflow = significance * 2;
-
-//
-// When seedrandom.js is loaded, we immediately mix a few bits
-// from the built-in RNG into the entropy pool. Because we do
-// not want to intefere with determinstic PRNG state later,
-// seedrandom will not call math.random on its own again after
-// initialization.
-//
-mixkey(math.random(), pool);
-
-// End anonymous scope, and pass initial values.
-})(
- [], // pool: entropy pool starts empty
- Math, // math: package containing random, pow, and seedrandom
- 256, // width: each RC4 output is 0 <= x < 256
- 6, // chunks: at least six RC4 outputs for each double
- 52 // significance: there are 52 significant digits in a double
-);
projects / feed / routing.git / commitdiff