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