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