Next: Options of the graph
Up: Implementation
Previous: Implementation
Contents
The current implementation of the algorithm uses the
following concepts for calculating
evolutionary layout of graph transformation sequences:
- Attracting forces which are described by edge length.
- Repulsive forces which are calculated by
|
(1) |
where is the actual distance and is the minimal distance to
other nodes.
- Temperature to express the position flexibility of each node.
- Cooling function to reduce this temperature in each iteration
of the algorithm.
This cooling function of the temperature is described by
|
(2) |
for the iterations with , and by an initial temperature
for the initial layout.
- Aging concept is used to reduce the mental difference between
two layouts, if the same node has similar positions in both layouts.
The older a node is, the less it should be moved.
If possible, a younger node is moved instead.
Therefore, the cooling function is extend to
|
(3) |
where is the specific temperature for each node in iteration
step by integrating its age and the actual age of the graph.
This way, the older nodes have less movement flexibility. Since the
nodes contained in the initially layouted graph are the eldest ones,
they nearly do not have any move flexibility.
- Shock-aging is used to reduce dramatic changes in the layout
when one node is taken away and its former neighbors have abruptly
much more move flexibility. This process can be smoothed by giving
adjacent nodes some extra age, by so-called shock-aging.
Thus an extension was integrated not to stop, but to slow
down the general development of occupying the space left behind by
deleted nodes.
- Freezing age concept is integrated to stop mobility of a node.
The position of the node stays constant during graph evolution over time.
- Layout patterns are used to support the user`s recognition of
changes by a transformation rule in the instance view.
The patterns are mainly realized by the Edge Patterns.
A layout pattern is defined as a smaller graph with its layout and
can influence the layout of a larger graph.
For example, an edge pattern may be defined by a graph as a pair of parent
and child nodes and an edge inbetween,
and its layout can be defined by placing a child node
always below its parent node. This layout pattern forces a larger graph to
grow downward, and the typical appearance of a tree evolves over
time.
Because the original AGG graph structure model contained very simple
layout information only,
this layout data had been enriched by the following items: node age,
preferred edge length, edge-binding force (resulting from the node
forces), and a kind of bounding box around each node to indicate
where other nodes may not be placed.
Next: Options of the graph
Up: Implementation
Previous: Implementation
Contents
Olga Runge
2006-08-16