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
19static 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
45int
46compute_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