Graphviz  2.35.20130930.0449
opt_arrangement.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 #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 */