1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15/************************************************
16
17 Functions for computing the high-dimensional
18 embedding and the PCA projection.
19
20************************************************/
21
22
23#include "dijkstra.h"
24#include "bfs.h"
25#include "kkutils.h"
26#include "embed_graph.h"
27#include <stdlib.h>
28#include <stdio.h>
29#include <time.h>
30/* #include <math.h> */
31
32void embed_graph(vtx_data * graph, int n, int dim, DistType *** Coords,
33 int reweight_graph)
34{
35/* Compute 'dim'-dimensional high-dimensional embedding (HDE) for the 'n' nodes
36 The embedding is based on chossing 'dim' pivots, and associating each
37 coordinate with a unique pivot, assigning it to the graph-theoretic distances
38 of all nodes from the pivots
39*/
40
41 int i, j;
42 int node;
43 DistType *storage = N_GNEW(n * dim, DistType);
44 DistType **coords = *Coords;
45 DistType *dist = N_GNEW(n, DistType); /* this vector stores the distances of
46 each nodes to the selected "pivots" */
47 float *old_weights = graph[0].ewgts;
48 Queue Q;
49 DistType max_dist = 0;
50
51 if (coords != NULL) {
52 free(coords[0]);
53 free(coords);
54 }
55
56 /* this matrix stores the distance between each node and each "pivot" */
57 *Coords = coords = N_GNEW(dim, DistType *);
58 for (i = 0; i < dim; i++)
59 coords[i] = storage + i * n;
60
61 if (reweight_graph) {
62 compute_new_weights(graph, n);
63 }
64
65 /* select the first pivot */
66 node = rand() % n;
67
68 mkQueue(&Q, n);
69 if (reweight_graph) {
70 dijkstra(node, graph, n, coords[0]);
71 } else {
72 bfs(node, graph, n, coords[0], &Q);
73 }
74
75 for (i = 0; i < n; i++) {
76 dist[i] = coords[0][i];
77 if (dist[i] > max_dist) {
78 node = i;
79 max_dist = dist[i];
80 }
81 }
82
83 /* select other dim-1 nodes as pivots */
84 for (i = 1; i < dim; i++) {
85 if (reweight_graph) {
86 dijkstra(node, graph, n, coords[i]);
87 } else {
88 bfs(node, graph, n, coords[i], &Q);
89 }
90 max_dist = 0;
91 for (j = 0; j < n; j++) {
92 dist[j] = MIN(dist[j], coords[i][j]);
93 if (dist[j] > max_dist) {
94 node = j;
95 max_dist = dist[j];
96 }
97 }
98
99 }
100
101 free(dist);
102
103 if (reweight_graph) {
104 restore_old_weights(graph, n, old_weights);
105 }
106
107}
108
109 /* Make each axis centered around 0 */
110void center_coordinate(DistType ** coords, int n, int dim)
111{
112 int i, j;
113 double sum, avg;
114 for (i = 0; i < dim; i++) {
115 sum = 0;
116 for (j = 0; j < n; j++) {
117 sum += coords[i][j];
118 }
119 avg = sum / n;
120 for (j = 0; j < n; j++) {
121 coords[i][j] -= (DistType) avg;
122 }
123 }
124}
125