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
18static 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 */
49int
50compute_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 }
129finish:
130 if (!given_coords) {
131 free(y);
132 }
133
134 return rv;
135}
136
137#endif /* DIGCOLA */
138