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 | #include "digcola.h" |
15 | #ifdef DIGCOLA |
16 | #include "matrix_ops.h" |
17 | #include "conjgrad.h" |
18 | |
19 | static void construct_b(vtx_data * graph, int n, double *b) |
20 | { |
21 | /* construct a vector - b s.t. -b[i]=\sum_j -w_{ij}*\delta_{ij} |
22 | * (the "balance vector") |
23 | * Note that we build -b and not b, since our matrix is not the |
24 | * real laplacian L, but its negation: -L. |
25 | * So instead of solving Lx=b, we will solve -Lx=-b |
26 | */ |
27 | int i, j; |
28 | |
29 | double b_i = 0; |
30 | |
31 | for (i = 0; i < n; i++) { |
32 | b_i = 0; |
33 | if (graph[0].edists == NULL) { |
34 | continue; |
35 | } |
36 | for (j = 1; j < graph[i].nedges; j++) { /* skip the self loop */ |
37 | b_i += graph[i].ewgts[j] * graph[i].edists[j]; |
38 | } |
39 | b[i] = b_i; |
40 | } |
41 | } |
42 | |
43 | #define hierarchy_cg_tol 1e-3 |
44 | |
45 | int |
46 | compute_y_coords(vtx_data * graph, int n, double *y_coords, |
47 | int max_iterations) |
48 | { |
49 | /* Find y coords of a directed graph by solving L*x = b */ |
50 | int i, j, rv = 0; |
51 | double *b = N_NEW(n, double); |
52 | double tol = hierarchy_cg_tol; |
53 | int nedges = 0; |
54 | float *uniform_weights; |
55 | float *old_ewgts = graph[0].ewgts; |
56 | |
57 | construct_b(graph, n, b); |
58 | |
59 | init_vec_orth1(n, y_coords); |
60 | |
61 | for (i = 0; i < n; i++) { |
62 | nedges += graph[i].nedges; |
63 | } |
64 | |
65 | /* replace original edge weights (which are lengths) with uniform weights */ |
66 | /* for computing the optimal arrangement */ |
67 | uniform_weights = N_GNEW(nedges, float); |
68 | for (i = 0; i < n; i++) { |
69 | graph[i].ewgts = uniform_weights; |
70 | uniform_weights[0] = (float) -(graph[i].nedges - 1); |
71 | for (j = 1; j < graph[i].nedges; j++) { |
72 | uniform_weights[j] = 1; |
73 | } |
74 | uniform_weights += graph[i].nedges; |
75 | } |
76 | |
77 | if (conjugate_gradient(graph, y_coords, b, n, tol, max_iterations) < 0) { |
78 | rv = 1; |
79 | } |
80 | |
81 | /* restore original edge weights */ |
82 | free(graph[0].ewgts); |
83 | for (i = 0; i < n; i++) { |
84 | graph[i].ewgts = old_ewgts; |
85 | old_ewgts += graph[i].nedges; |
86 | } |
87 | |
88 | free(b); |
89 | return rv; |
90 | } |
91 | |
92 | #endif /* DIGCOLA */ |
93 | |