1 
  2 ////////////////////////////////////////////////////////////////////////////////
  3 
  4 /**
  5  * @fileOverview Copyright (C) 2009 www.webis.de
  6  * @author Christian Fricke christian.fricke@uni-weimar.de
  7  * @version 0.1
  8  */
  9 
 10 /**
 11  * A graph consists of vertices and edges. Nodes represent single document ids
 12  * and edges contain the respective similarity.
 13  * @class Implementation of a graph data structure
 14  * @constructor
 15  * @author Christian Fricke christian.fricke@uni-weimar.de
 16  */
 17 
 18 de.aitools.js.Graph = function () {
 19 	/**
 20    * @private
 21    * @type Number
 22    */
 23   var uId_ = 0;
 24 	/**
 25    * @private
 26    * @type Object
 27    */
 28   var adjMap_ = {};
 29   
 30   /**
 31 	 * Method to clone the graph. It is not yet fully implemented - the adjMap_ is
 32 	 * not copied in the process.
 33 	 * @public
 34 	 * @returns {de.aitools.js.Graph} A cloned graph
 35 	 */
 36   this.clone = function () {
 37     var clone = new de.aitools.js.Graph();
 38 		for (var i in adjMap_) {
 39       if (adjMap_.hasOwnProperty(i)) {
 40         clone.addNode(i);
 41         for (var j in adjMap_[i]) {
 42           if (adjMap_[i].hasOwnProperty(j)) {
 43             clone.setEdge(i, j, adjMap_[i][j]);
 44           }
 45         }
 46       }
 47     }
 48     return clone;
 49   };
 50 
 51   /**
 52 	 * Method for adding nodes to the graph. arguments[0] is fetched in order
 53 	 * for clone() to work. This feature is not supposed to be used elsewhere.
 54 	 * Note: uId_ will always be set to last (highest) node id.
 55 	 * @public
 56 	 * @returns {Number} Id of a the added node
 57 	 */
 58   this.addNode = function () {
 59 		if (arguments[0] !== undefined) {
 60 			adjMap_[arguments[0]] = {};
 61 			uId_ = arguments[0];
 62 			return arguments[0];
 63 		} else {
 64     	adjMap_[uId_] = {};
 65   		return uId_++;
 66 		}
 67   };
 68 
 69   /**
 70 	 * Method to check whether or not the graph contains a certain node id.
 71 	 * @public
 72 	 * @param {Number} nodeId The node id to be checked
 73 	 * @returns {Boolean} True or false
 74 	 */
 75   this.containsNode = function (nodeId) {
 76     if (typeof(adjMap_[nodeId]) !== 'undefined') { return true; }
 77     else { return false; }
 78   };
 79   
 80   /**
 81 	 * Method to get all node ids contained within the graph.
 82 	 * @public
 83 	 * @returns {Array} An array of all node ids contained within the graph
 84 	 */
 85   this.getNodes = function () {
 86     var index = [];
 87     for (var i in adjMap_) {
 88       if (adjMap_.hasOwnProperty(i)) { index.push(i); }
 89     }
 90     return index;
 91   };
 92   
 93   /**
 94 	 * Method to get all node ids adjacent to the given node id.
 95 	 * @public
 96 	 * @param {Number} nodeId The node id to be used
 97 	 * @returns {Array} An array of all adjacent node ids
 98 	 */
 99   this.getAdjacentNodes = function (nodeId) {
100     CHECK_NOT_UNDEFINED(adjMap_[nodeId], "nodeId doesn't exist.");
101     var index = [];
102     for (var i in adjMap_[nodeId]) {
103       if (adjMap_[nodeId].hasOwnProperty(i)) { index.push(i); }
104     }
105     return index;
106   };
107   
108   /**
109 	 * Method to remove a certain node id from the graph.
110 	 * @public
111 	 * @param {Number} nodeId The node id to be removed
112 	 */
113   this.removeNode = function (nodeId) {
114     CHECK_NOT_UNDEFINED(adjMap_[nodeId], "nodeId doesn't exist.");
115     for (var i in adjMap_) {
116       if (adjMap_[i].hasOwnProperty(nodeId)) {
117         delete adjMap_[i][nodeId];
118       }
119     }
120     delete adjMap_[nodeId];
121   };
122   
123   /**
124 	 * Method to count the number of nodes within the graph.
125 	 * @public
126 	 * @returns {Number} The amount of nodes within the graph
127 	 */
128   this.getNodeCount = function () {
129     var count = 0;
130     for (var i in adjMap_) {
131       if (adjMap_.hasOwnProperty(i)) { ++count; }
132     }
133     return count;
134   };
135   
136   /**
137 	 * Method to set an edge between to given nodes.
138 	 * @public
139 	 * @param {Number} fromNodeId A unique node id
140 	 * @param {Number} toNodeId Another unique node id
141 	 * @param {Number} weight The edge weight to be set
142 	 */
143   this.setEdge = function (fromNodeId, toNodeId, weight) {
144     CHECK_NOT_UNDEFINED(adjMap_[fromNodeId], "fromNodeId doesn't exist.");
145     CHECK_NOT_UNDEFINED(adjMap_[toNodeId], "toNodeId doesn't exist.");
146     if (adjMap_[fromNodeId] !== adjMap_[toNodeId]) {
147       adjMap_[fromNodeId][toNodeId] = weight;
148       adjMap_[toNodeId][fromNodeId] = weight;
149     } else { throw new Error("fromNodeId must be different from toNodeId."); }
150   };
151   
152   /**
153 	 * Method to check whether or not an edge exists between two nodes.
154 	 * @public
155 	 * @param {Number} fromNodeId A unique node id
156 	 * @param {Number} toNodeId Another unique node id
157 	 * @returns {Boolean} True or false
158 	 */
159   this.containsEdge = function (fromNodeId, toNodeId) {
160     if (this.containsNode(fromNodeId) && this.containsNode(toNodeId)) {
161       if (adjMap_[fromNodeId][toNodeId]) { return true; }
162     } else { return false; }
163   };
164   
165   /**
166 	 * Method to get the weight of an edge of two nodes.
167 	 * @public
168 	 * @param {Number} fromNodeId A unique node id
169 	 * @param {Number} toNodeId Another unique node id
170 	 * @returns {Number} The edge weight
171 	 */
172   this.getEdgeWeight = function (fromNodeId, toNodeId) {
173     if (this.containsEdge(fromNodeId, toNodeId)) {
174       return adjMap_[fromNodeId][toNodeId];
175     } else { return 0; }
176   };
177   
178   /**
179 	 * Method to remove a certain edge from the graph.
180 	 * @public
181 	 * @param {Number} fromNodeId A unique node id
182 	 * @param {Number} toNodeId Another unique node id
183 	 */
184   this.removeEdge = function (fromNodeId, toNodeId) {
185     if (this.containsEdge(fromNodeId, toNodeId)) {
186       delete adjMap_[fromNodeId][toNodeId];
187       delete adjMap_[toNodeId][fromNodeId];
188     }
189   };
190   
191   /**
192 	 * Method to count the number of edges within the graph.
193 	 * @public
194 	 * @returns {Number} The amount of edges within the graph
195 	 */
196   this.getEdgeCount = function () {
197     var count = 0;
198     for (var i in adjMap_) {
199       if (adjMap_.hasOwnProperty(i)) {
200         for (var j in adjMap_[i]) {
201           if (adjMap_[i].hasOwnProperty(j)) {
202             ++count;
203           }
204         }
205       }
206     }
207     // edges are traversed twice
208     return (count / 2);
209   };
210   
211   /**
212 	 * Method to calculate the mass of a graph or certain given nodes:
213 	 * If nodeId is not given as an argument, the mass of the whole graph is
214 	 * calculated. Otherwise getMass(nodeIds) calculates the mass of a given
215 	 * set of nodes contained within the graph.
216 	 * @public
217 	 * @param {Array} nodeIds An array of node ids
218 	 * @returns {Number} The mass of the entire graph or certain nodes
219 	 */
220   this.getMass = function (nodeIds) {
221     var mass = 0;
222     if (nodeIds instanceof Array) {
223       for (var k = 0; k < nodeIds.length; k++) {
224         for (var i in adjMap_) {
225           if (adjMap_.hasOwnProperty(i) && i == k) {
226             for (var j in adjMap_[i]) {
227               if (adjMap_[i].hasOwnProperty(j)) {
228                 mass += adjMap_[i][j];
229               }
230             }
231           }
232         }
233       }
234     } else if (!nodeIds) {
235       for (var m in adjMap_) {
236         if (adjMap_.hasOwnProperty(m)) {
237           for (var n in adjMap_[m]) {
238             if (adjMap_[m].hasOwnProperty(n)) {
239               mass += adjMap_[m][n];
240             }
241           }
242         }
243       }
244     } else { throw new Error("nodeIds is of wrong type."); }
245     // edges are traversed twice
246     return (mass / 2);
247   };
248   
249   /**
250 	 * Generic method for graph procedures (like normalization).
251 	 * @public
252 	 * @returns {Object} Depends on the generic method.
253 	 */
254   this.compute = function (graphProcedure) {
255     return graphProcedure.execute(this);
256   };
257 };
258 
259 ////////////////////////////////////////////////////////////////////////////////
260