Graphviz  2.41.20170921.2350
embed_graph.c
Go to the documentation of this file.
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
32 void 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 */
110 void 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 }
void restore_old_weights(vtx_data *graph, int n, float *old_weights)
Definition: kkutils.c:279
#define MIN(a, b)
Definition: arith.h:35
void center_coordinate(DistType **coords, int n, int dim)
Definition: embed_graph.c:110
void bfs(int vertex, vtx_data *graph, int n, DistType *dist, Queue *Q)
Definition: bfs.c:27
Definition: bfs.h:69
void dijkstra(int vertex, vtx_data *graph, int n, DistType *dist)
Definition: dijkstra.c:155
void mkQueue(Queue *qp, int size)
Definition: bfs.c:122
Agraph_t * graph(char *name)
Definition: gv.cpp:38
int DistType
Definition: sparsegraph.h:92
void compute_new_weights(vtx_data *graph, int n)
Definition: kkutils.c:242
void embed_graph(vtx_data *graph, int n, int dim, DistType ***Coords, int reweight_graph)
Definition: embed_graph.c:32
#define NULL
Definition: logic.h:39
float * ewgts
Definition: sparsegraph.h:82
Agnode_t * node(Agraph_t *g, char *name)
Definition: gv.cpp:103
double dist(Site *s, Site *t)
Definition: site.c:41
#define N_GNEW(n, t)
Definition: agxbuf.c:20