| /* |
| 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); |
| }; |
| }; |
| |