aboutsummaryrefslogtreecommitdiffstats
path: root/lib/appmon/src/appmon_place.erl
diff options
context:
space:
mode:
authorErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
committerErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
commit84adefa331c4159d432d22840663c38f155cd4c1 (patch)
treebff9a9c66adda4df2106dfd0e5c053ab182a12bd /lib/appmon/src/appmon_place.erl
downloadotp-84adefa331c4159d432d22840663c38f155cd4c1.tar.gz
otp-84adefa331c4159d432d22840663c38f155cd4c1.tar.bz2
otp-84adefa331c4159d432d22840663c38f155cd4c1.zip
The R13B03 release.OTP_R13B03
Diffstat (limited to 'lib/appmon/src/appmon_place.erl')
-rw-r--r--lib/appmon/src/appmon_place.erl194
1 files changed, 194 insertions, 0 deletions
diff --git a/lib/appmon/src/appmon_place.erl b/lib/appmon/src/appmon_place.erl
new file mode 100644
index 0000000000..5a6ae6aa48
--- /dev/null
+++ b/lib/appmon/src/appmon_place.erl
@@ -0,0 +1,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??