Information Technology Reference
In-Depth Information
Fig. 7.8 A tree is obtained from a DAG by duplicating nodes (and labels) with multiple ancestors.
( a ) Two sibling nodes share a common subgraph. ( b ) The subgraph is duplicated to recover a tree
structure
(denote
T
) bottom-up from the sink nodes to the sources will eventually produce a
tree T
.
Conversely, let T
= T (
G
)
=(
V
,
E
)
be a tree where the nodes have labels, that is, T comes
equipped with the label
λ
: V
→ L
. If two nodes u
,
v
V in T have equal labels
λ (
extending from u and v
are isomorphic (the subtrees have the same tree structure) and the corresponding
nodes have equal labels. Thus, a bijective correspondence
u
)= λ (
v
)
, then the subtrees T u =(
V u ,
E u )
, T v =(
V v ,
E v )
φ
: V u
V v satisfies
λ (
x
)= λ ( φ (
x
))
for all x
V u . There is also a correspondence for preserving edges:
(
x
,
y
)
is an edge in E u if and only if
( φ (
x
) , φ (
y
))
is an edge in E v . We can then define
on T an equivalence relation for nodes where u
v
⇐⇒ λ (
u
)= λ (
v
)
. The quotient
set V
/ ≡
can then be equipped with a graph structure G , where the classes
[
u
]
,
[
v
]
connect (in G ) if two nodes x
connect in T . As can be easily seen, the
graph computed from T is a DAG and the previous unfolding process unfolds G
back into T (see Fig. 7.8 ).
This bijective correspondence must be implemented in order to track user
interaction on the DAGMap and to map the user interaction back to the original
DAG (or over the Sugiyama layout when synchronizing views).
The TreeMap algorithm proceeds recursively, dividing the cell associated with
a node into sub-cells for each of the child nodes, ordering the child nodes u 1 , ...,
u k according to their number of leaf nodes (in T u 1 , ..., T u k ). This also holds true
with the DAGMap: the number of sink nodes accessible from node u (in G ) equals
the number of leaf nodes in the subtree T u (in T
[
u
] ,
y
[
v
]
). Consequently, cells with
greater area are placed in the top left part of the TreeMap because companies with
many subsidiaries are expected to have greater assets.
= T (
G
)
7.5
Exploring the Hierarchy: Coordinating DAGMaps
with the Classical Sugiyama Layout
We explain below that using a DAGMap alone is not sufficient to explore the entire
hierarchy of companies and subsidiaries. The exploration focuses on the discovery
Search WWH ::




Custom Search