New file |
0,0 → 1,149 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
|
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
|
http://dojotoolkit.org/community/licensing.shtml |
*/ |
|
dojo.provide("dojo.collections.Graph"); |
dojo.require("dojo.collections.Collections"); |
dojo.experimental("dojo.collections.Graph"); |
dojo.collections.Graph = function (nodes) { |
function node(key, data, neighbors) { |
this.key = key; |
this.data = data; |
this.neighbors = neighbors || new adjacencyList(); |
this.addDirected = function () { |
if (arguments[0].constructor == edgeToNeighbor) { |
this.neighbors.add(arguments[0]); |
} else { |
var n = arguments[0]; |
var cost = arguments[1] || 0; |
this.neighbors.add(new edgeToNeighbor(n, cost)); |
} |
}; |
} |
function nodeList() { |
var d = new dojo.collections.Dictionary(); |
function nodelistiterator() { |
var o = []; |
var e = d.getIterator(); |
while (e.get()) { |
o[o.length] = e.element; |
} |
var position = 0; |
this.element = o[position] || null; |
this.atEnd = function () { |
return (position >= o.length); |
}; |
this.get = function () { |
if (this.atEnd()) { |
return null; |
} |
this.element = o[position++]; |
return this.element; |
}; |
this.map = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.map) { |
return Array.map(o, fn, s); |
} else { |
var arr = []; |
for (var i = 0; i < o.length; i++) { |
arr.push(fn.call(s, o[i])); |
} |
return arr; |
} |
}; |
this.reset = function () { |
position = 0; |
this.element = o[position]; |
}; |
} |
this.add = function (node) { |
d.add(node.key, node); |
}; |
this.clear = function () { |
d.clear(); |
}; |
this.containsKey = function (key) { |
return d.containsKey(key); |
}; |
this.getIterator = function () { |
return new nodelistiterator(this); |
}; |
this.item = function (key) { |
return d.item(key); |
}; |
this.remove = function (node) { |
d.remove(node.key); |
}; |
} |
function edgeToNeighbor(node, cost) { |
this.neighbor = node; |
this.cost = cost; |
} |
function adjacencyList() { |
var d = []; |
this.add = function (o) { |
d.push(o); |
}; |
this.item = function (i) { |
return d[i]; |
}; |
this.getIterator = function () { |
return new dojo.collections.Iterator([].concat(d)); |
}; |
} |
this.nodes = nodes || new nodeList(); |
this.count = this.nodes.count; |
this.clear = function () { |
this.nodes.clear(); |
this.count = 0; |
}; |
this.addNode = function () { |
var n = arguments[0]; |
if (arguments.length > 1) { |
n = new node(arguments[0], arguments[1]); |
} |
if (!this.nodes.containsKey(n.key)) { |
this.nodes.add(n); |
this.count++; |
} |
}; |
this.addDirectedEdge = function (uKey, vKey, cost) { |
var uNode, vNode; |
if (uKey.constructor != node) { |
uNode = this.nodes.item(uKey); |
vNode = this.nodes.item(vKey); |
} else { |
uNode = uKey; |
vNode = vKey; |
} |
var c = cost || 0; |
uNode.addDirected(vNode, c); |
}; |
this.addUndirectedEdge = function (uKey, vKey, cost) { |
var uNode, vNode; |
if (uKey.constructor != node) { |
uNode = this.nodes.item(uKey); |
vNode = this.nodes.item(vKey); |
} else { |
uNode = uKey; |
vNode = vKey; |
} |
var c = cost || 0; |
uNode.addDirected(vNode, c); |
vNode.addDirected(uNode, c); |
}; |
this.contains = function (n) { |
return this.nodes.containsKey(n.key); |
}; |
this.containsKey = function (k) { |
return this.nodes.containsKey(k); |
}; |
}; |
|