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 */ |
138 | |