1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
/*************************************************************************
* Copyright (c) 2011 AT&T Intellectual Property
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/legal/epl-v10.html
*
* Contributors: Details at https://graphviz.org
*************************************************************************/
#include <neatogen/digcola.h>
#include <util/alloc.h>
#ifdef DIGCOLA
#include <neatogen/matrix_ops.h>
#include <neatogen/conjgrad.h>
#include <stddef.h>
static void construct_b(vtx_data * graph, int n, double *b)
{
/* construct a vector - b s.t. -b[i]=\sum_j -w_{ij}*\delta_{ij}
* (the "balance vector")
* Note that we build -b and not b, since our matrix is not the
* real laplacian L, but its negation: -L.
* So instead of solving Lx=b, we will solve -Lx=-b
*/
int i;
double b_i = 0;
for (i = 0; i < n; i++) {
b_i = 0;
if (graph[0].edists == NULL) {
continue;
}
for (size_t j = 1; j < graph[i].nedges; j++) { // skip the self loop
b_i += graph[i].ewgts[j] * graph[i].edists[j];
}
b[i] = b_i;
}
}
#define hierarchy_cg_tol 1e-3
int
compute_y_coords(vtx_data * graph, int n, double *y_coords,
int max_iterations)
{
/* Find y coords of a directed graph by solving L*x = b */
int i, rv = 0;
double *b = gv_calloc(n, sizeof(double));
double tol = hierarchy_cg_tol;
size_t nedges = 0;
float *old_ewgts = graph[0].ewgts;
construct_b(graph, n, b);
init_vec_orth1(n, y_coords);
for (i = 0; i < n; i++) {
nedges += graph[i].nedges;
}
/* replace original edge weights (which are lengths) with uniform weights */
/* for computing the optimal arrangement */
float *uniform_weights = gv_calloc(nedges, sizeof(float));
for (i = 0; i < n; i++) {
graph[i].ewgts = uniform_weights;
uniform_weights[0] = -(float)(graph[i].nedges - 1);
for (size_t j = 1; j < graph[i].nedges; j++) {
uniform_weights[j] = 1;
}
uniform_weights += graph[i].nedges;
}
if (conjugate_gradient(graph, y_coords, b, n, tol, max_iterations) < 0) {
rv = 1;
}
/* restore original edge weights */
free(graph[0].ewgts);
for (i = 0; i < n; i++) {
graph[i].ewgts = old_ewgts;
old_ewgts += graph[i].nedges;
}
free(b);
return rv;
}
#endif /* DIGCOLA */
|
