Graphviz  2.41.20170921.2350
compute_hierarchy.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 "kkutils.h"
17 
18 static int *given_levels = NULL;
19 /*
20  * This function partitions the graph nodes into levels
21  * according to the minimizer of the hierarchy energy.
22  *
23  * To allow more flexibility we define a new level only
24  * when the hierarchy energy shows a significant jump
25  * (to compensate for noise).
26  * This is controlled by two parameters: 'abs_tol' and
27  * 'relative_tol'. The smaller these two are, the more
28  * levels we'll get.
29  * More speciffically:
30  * We never consider gaps smaller than 'abs_tol'
31  * Additionally, we never consider gaps smaller than 'abs_tol'*<avg_gap>
32  *
33  * The output is an ordering of the nodes according to
34  * their levels, as follows:
35  * First level:
36  * ordering[0],ordering[1],...ordering[levels[0]-1]
37  * Second level:
38  * ordering[levels[0]],ordering[levels[0]+1],...ordering[levels[1]-1]
39  * ...
40  * Last level:
41  * ordering[levels[num_levels-1]],ordering[levels[num_levels-1]+1],...ordering[n-1]
42  *
43  * Hence, the nodes were partitioned into 'num_levels'+1
44  * levels.
45  *
46  * Please note that 'ordering[levels[i]]' contains the first node at level i+1,
47  * and not the last node of level i.
48  */
49 int
50 compute_hierarchy(vtx_data * graph, int n, double abs_tol,
51  double relative_tol, double *given_coords,
52  int **orderingp, int **levelsp, int *num_levelsp)
53 {
54  double *y;
55  int i, rv=0;
56  double spread;
57  int use_given_levels = FALSE;
58  int *ordering;
59  int *levels;
60  double tol; /* node 'i' precedes 'j' in hierarchy iff y[i]-y[j]>tol */
61  double hierarchy_span;
62  int num_levels;
63 
64  /* compute optimizer of hierarchy energy: 'y' */
65  if (given_coords) {
66  y = given_coords;
67  } else {
68  y = N_GNEW(n, double);
69  if (compute_y_coords(graph, n, y, n)) {
70  rv = 1;
71  goto finish;
72  }
73  }
74 
75  /* sort nodes accoridng to their y-ordering */
76  *orderingp = ordering = N_NEW(n, int);
77  for (i = 0; i < n; i++) {
78  ordering[i] = i;
79  }
80  quicksort_place(y, ordering, 0, n - 1);
81 
82  spread = y[ordering[n - 1]] - y[ordering[0]];
83 
84  /* after spread is computed, we may take the y-coords as the given levels */
85  if (given_levels) {
86  use_given_levels = TRUE;
87  for (i = 0; i < n; i++) {
88  use_given_levels = use_given_levels && given_levels[i] >= 0;
89  }
90  }
91  if (use_given_levels) {
92  for (i = 0; i < n; i++) {
93  y[i] = given_levels[i];
94  ordering[i] = i;
95  }
96  quicksort_place(y, ordering, 0, n - 1);
97  }
98 
99  /* compute tolerance
100  * take the maximum between 'abs_tol' and a fraction of the average gap
101  * controlled by 'relative_tol'
102  */
103  hierarchy_span = y[ordering[n - 1]] - y[ordering[0]];
104  tol = MAX(abs_tol, relative_tol * hierarchy_span / (n - 1));
105  /* 'hierarchy_span/(n-1)' - average gap between consecutive nodes */
106 
107 
108  /* count how many levels the hierarchy contains (a SINGLE_LINK clustering */
109  /* alternatively we could use COMPLETE_LINK clustering) */
110  num_levels = 0;
111  for (i = 1; i < n; i++) {
112  if (y[ordering[i]] - y[ordering[i - 1]] > tol) {
113  num_levels++;
114  }
115  }
116  *num_levelsp = num_levels;
117  if (num_levels == 0) {
118  *levelsp = levels = N_GNEW(1, int);
119  levels[0] = n;
120  } else {
121  int count = 0;
122  *levelsp = levels = N_GNEW(num_levels, int);
123  for (i = 1; i < n; i++) {
124  if (y[ordering[i]] - y[ordering[i - 1]] > tol) {
125  levels[count++] = i;
126  }
127  }
128  }
129 finish:
130  if (!given_coords) {
131  free(y);
132  }
133 
134  return rv;
135 }
136 
137 #endif /* DIGCOLA */
#define MAX(a, b)
Definition: agerror.c:17
#define N_NEW(n, t)
Definition: memory.h:36
void quicksort_place(double *place, int *ordering, int first, int last)
Definition: kkutils.c:219
Agraph_t * graph(char *name)
Definition: gv.cpp:38
#define NULL
Definition: logic.h:39
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:35
#define TRUE
Definition: cgraph.h:38