1 2 //////////////////////////////////////////////////////////////////////////////// 3 4 /** 5 * @fileoverview Copyright (C) 2009 www.webis.de 6 * @author Christof Braeutigam christof.braeutigam@uni-weimar.de 7 * @author Christian Fricke christian.fricke@uni-weimar.de 8 * @version 0.1 9 */ 10 11 /** 12 * Graph procedure for sorting edges. 13 * @class Graph procedure for sorting edges 14 * @constructor 15 * @param {Number} A nodeId 16 * @see de.aitools.js.KNNGraph 17 * @author Christof Braeutigam christof.braeutigam@uni-weimar.de 18 * @author Christian Fricke christian.fricke@uni-weimar.de 19 */ 20 de.aitools.js.SortedEdges = function (node) { 21 /** 22 * @private 23 * @type Number 24 */ 25 var nodeId; 26 if (node !== undefined) { nodeId = node; } else { nodeId = undefined; } 27 28 /** 29 * Sorting a tuple by element, descendent or ascendent. 30 * @private 31 * @param {Array} tuplesArr An array of arrays of values 32 * @param {Number} byElement The element of a tuple to sort 33 * @param {Boolean} descOrder Ascendent or descendent order type 34 */ 35 var tupleSort = function (tuplesArr, byElement, descOrder) { 36 if (typeof(byElement) === "undefined") { byElement = 0; } 37 if (typeof(descOrder) === "undefined") { descOrder = true; } 38 tuplesArr.sort(function (a,b) { 39 return (descOrder) ? b[byElement] - a[byElement] 40 : a[byElement] - b[byElement]; 41 }); 42 }; 43 44 /** 45 * Method for sorting edges in regard to their weight. 46 * @public 47 * @param {de.aitools.js.Graph} graph The graph to be sorted 48 * @returns {Number} Sorted edges of a node 49 */ 50 this.execute = function (graph) { 51 if (nodeId === undefined) { 52 // TODO: implement for all edges... 53 throw new Error("SortedEdges.execute: no nodeId set..."); 54 } 55 var adjNodes = graph.getAdjacentNodes(nodeId); 56 var sortedEdges = []; 57 for (var i = 0; i < adjNodes.length; ++i) { 58 sortedEdges.push(// array: fromNode, toNode, weight 59 [nodeId, adjNodes[i], graph.getEdgeWeight(nodeId, adjNodes[i])] 60 ); 61 } 62 tupleSort(sortedEdges, 2, true); 63 return sortedEdges; 64 }; 65 }; 66 67 //////////////////////////////////////////////////////////////////////////////// 68 69 //////////////////////////////////////////////////////////////////////////////// 70 71 /** 72 * The k-nearest neighbor graph (k-NNG) is a graph in which two vertices 73 * p and q are connected by an edge, if the distance between p and q is among 74 * the k-th smallest distances from p to other objects from P. 75 * @class Graph procedure for local optimization 76 * @constructor 77 * @param {Number} kval The approximate number of edges to be left per node 78 * @param {String} modeval The kind of computation, either normal or mutual 79 * @author Christof Braeutigam christof.braeutigam@uni-weimar.de 80 * @author Christian Fricke christian.fricke@uni-weimar.de 81 */ 82 de.aitools.js.KNNGraph = function (kval, modeval) { 83 84 /** 85 * @private 86 * @type Number 87 */ 88 var k; 89 if (kval !== undefined) { k = kval; } else { k = 10; } 90 91 /** 92 * @private 93 * @type String 94 */ 95 var mode; 96 if (modeval === "mutual") { mode = modeval; } else { mode = "normal"; } 97 98 /** 99 * Remove all edges that are weaker than BOTH of their defining nodes' 100 * thresholds. 101 * @private 102 * @param {de.aitools.js.Graph} graph The graph to be sorted 103 * @param {Array} thresholds 104 * @returns {Number} Sorted edges of a node 105 */ 106 var computeKNNGraph = function (graph, thresholds) { 107 var nodes = graph.getNodes(); 108 for (var i = 0; i < nodes.length; ++i) { 109 var adjacentNodes = graph.getAdjacentNodes(nodes[i]); 110 for (var j = 0; j < adjacentNodes.length; ++j) { 111 var weight = graph.getEdgeWeight(nodes[i], adjacentNodes[j]); 112 if (weight < thresholds[nodes[i]] && 113 weight < thresholds[adjacentNodes[j]]) { 114 graph.removeEdge(nodes[i], adjacentNodes[j]); 115 } 116 } 117 } 118 }; 119 120 /** 121 * Remove all edges that are weaker than ONE of their defining nodes' 122 * thresholds. 123 * @private 124 * @param {de.aitools.js.Graph} graph The graph to be sorted 125 * @param {Array} thresholds A map that contains the threshold for each node. 126 * @returns {Number} Sorted edges of a node 127 */ 128 var computeMutualKNNGraph = function (graph, thresholds) { 129 var nodes = graph.getNodes(); 130 for (var i = 0; i < nodes.length; ++i) { 131 var adjacentNodes = graph.getAdjacentNodes(nodes[i]); 132 for (var j = 0; j < adjacentNodes.length; ++j) { 133 var weight = graph.getEdgeWeight(nodes[i], adjacentNodes[j]); 134 if (weight < thresholds[nodes[i]] || 135 weight < thresholds[adjacentNodes[j]]) { 136 graph.removeEdge(nodes[i], adjacentNodes[j]); 137 } 138 } 139 } 140 }; 141 142 /** 143 * Computes the threshold which determines which edge to remove. 144 * @private 145 * @param {de.aitools.js.Graph} graph The graph to be sorted 146 * @param {Number} kval The approximate number of edges to be left per node 147 * @returns {Array} A map that contains the threshold for each node. 148 */ 149 var computeThresholds = function (graph, kval) { 150 var thresholds = []; // TODO: das sollte besser ein {} sein... 151 var nodes = graph.getNodes(); 152 for (var i = 0; i < nodes.length; ++i) { 153 var se = new de.aitools.js.SortedEdges(nodes[i]); 154 var edges = graph.compute(se); 155 if (edges.length > k) { thresholds[nodes[i]] = edges[k][2]; } 156 else { thresholds[nodes[i]] = -1.0; } 157 } 158 return thresholds; 159 }; 160 161 /** 162 * Procedure called by the graph {@link de.aitools.js.Graph} that uses the 163 * appropriate computation. 164 * @public 165 * @param {de.aitools.js.Graph} graph The graph to be sorted 166 */ 167 this.execute = function (graph) { 168 var thresholds = computeThresholds(graph, k); 169 if (mode === "normal") { computeKNNGraph(graph, thresholds); } 170 else { computeMutualKNNGraph(graph, thresholds); } 171 }; 172 }; 173 174 //////////////////////////////////////////////////////////////////////////////// 175