1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 1996-2009. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
%%------------------------------------------------------------
%%
%% Places a Digraph in a tree-like manner. The vertices in the digraph
%% is updated with x and y positions. The operation is not atomic. The
%% digraph may be cyclic but edges must then have been labeled primary
%% or secondary and the set of primary links must make up a non-cyclic
%% graph (a tree).
%%
%%
%% IMPLEMENTATION DETAIL
%% ---------------------
%%
%% The placement algorithm is straightforward, place the
%% nodes in the vertical plane (y-plane) and then place
%% nodes in the horisontal plane (x-plane).
%%
%% First all nodes are placed in the y (vertical) plane
%% by a standard traversing of the tree. We then place
%% the tree in the x (horisontal) plane. Each node is
%% placed in the middle of its children as far to the
%% left as possible, preferably at the left margin. Two
%% things can make a node not be placed at the left
%% margin and that is the case when a previous node has
%% been placed at the same vertical level as the node we
%% are trying to place (thus forcing a placement further
%% to the right), and the second case is when the middle
%% of the subtree of the node is not at the left margin
%% (which it only is when the subtree is empty). The
%% algorithm obviously depends on keeping track of the
%% rightmost positions at all depths, and this
%% information is also usefull when calculating the width
%% of the tree.
%%
%%
%%
%%------------------------------------------------------------
-module(appmon_place).
-export([place/2]).
-include("appmon_dg.hrl").
-import(lists, [foreach/2, foldl/3]).
place(DG, Root) ->
case appmon_dg:get(data, DG, Root) of
false -> [0];
_Other ->
placey(DG, Root, 1),
placex(DG, Root, [])
end.
%%------------------------------------------------------------
%%
%%
%% Placing a graph in y plane
%% --------------------------
%%
%% Place nodes in the graph in the y plane rather stupidly
%%
placey(DG, V, Y) ->
appmon_dg:set(y, DG, V, Y),
Y1 = Y+1,
foreach(fun(C) -> placey(DG, C, Y1) end, appmon_dg:get(out, DG, V)).
%%------------------------------------------------------------
%%
%%
%% Place a tree in the x plane
%% ---------------------------
%%
%% Place nodes in the tree in the x plane. The goal of the x
%% placement is to place all nodes as far to the left as possible
%% while maintaining a nice tree shape.
%%
%% To place a node we must first place its children, the
%% intention is to place the current node in the middle and above
%% its children. The calc_mid function will place the node in the
%% middle of its children. If the node should be placed further
%% to the right than the middle of its children, then its
%% children are moved DeltaX positions to be balanced under the
%% node. Thus at the end the node and its children form a nice
%% looking tree.
%%
%% The function also maintains the 'rightmost x on each level'
%% list LastX by putting its own position on top of the list
%%
%%
placex(DG, V, LastX) ->
Ch = appmon_dg:get(out, DG, V),
ChLX = foldl(fun(C, Accu) -> placex(DG, C, Accu) end,
tll(LastX),
Ch),
Width = appmon_dg:get(w, DG, V),
MyX = calc_mid(DG, Width, Ch),
DeltaX = calc_delta(MyX, hdd(LastX)+spacex()),
appmon_dg:set(x, DG, V, MyX),
move(DG, V, [MyX+Width | ChLX], DeltaX).
%%------------------------------------------------------------
%%
%%
%% Move a subtree DeltaX positions to the right
%% --------------------------------------------
%%
%% Used when moving children to balance under an already placed
%% parent. Note that the correct LastX depends on the ordering of
%% the children which must be the same as when the children were
%% first placed. It must be ensured that hdd(NewLastX) is the
%% same as hdd(NewLastX)+DeltaX. If the order of children is
%% preserved then so is hdd(LastX). Another solution would be to
%% set hdd(LastX) from the parent
%%
%% Note the two base clauses, one for the no-children case and
%% one optimisation clause (unneccessary perhaps) for DeltaX==0
%%
move(_DG, _L, LastX, 0) -> LastX;
move(DG, V, LastX, DeltaX) -> move2(DG, V, LastX, DeltaX).
move2(DG, V, LastX, DeltaX) ->
NewX = appmon_dg:get(x, DG, V)+DeltaX,
appmon_dg:set(x, DG, V, NewX),
ChLX = foldl(fun(C, LX) -> move2(DG, C, LX, DeltaX) end,
tll(LastX),
appmon_dg:get(out, DG, V)),
[max(NewX+appmon_dg:get(w, DG, V), hdd(LastX)) | ChLX].
max(A, B) when A>B -> A;
max(_, B) -> B.
%%------------------------------------------------------------
%%
%%
%% Calculate the middle position of the children
%% ---------------------------------------------
%%
%% Calculates the mid x position for a list of children. This
%% position is later compared to the position dictated by LastX
%% in calc_delta.
calc_mid(_DG, _Width, []) -> 0;
calc_mid(DG, Width, ChList) ->
LeftMostX = appmon_dg:get(x, DG, hd(ChList)),
Z2 = lists:last(ChList),
RightMostX = appmon_dg:get(x, DG, Z2)+appmon_dg:get(w, DG, Z2),
trunc((LeftMostX+RightMostX)/2)-trunc(Width/2).
calc_delta(Mid, Right) ->
if Right>Mid -> Right-Mid;
true -> 0
end.
%% Special head and tail
%% Handles empty list in a non-standard way
tll([]) -> [];
tll([_|T]) -> T.
hdd([]) -> 0;
hdd([H|_]) -> H.
spacex() -> 20. % Should be macro??
|
