Next: Input Graph Language
Up: Graph
Previous: Graph
Before describing the Graph methods, it is necessary to give a description
of the subgraph mechanism used in LINK.
In applications
which manipulate extremely large graphs, it is often a practical necessity
to present the graph as a small, ``coarse'' graph in which certain areas
of interest to the end user can be expanded to reveal finer detail.
LINK's subgraph mechanism allows the
user or programmer to identify the vertices of any induced subgraph of
G
and replaced it
with a single vertex, called a supervertex. This supervertex can
later be expanded to reveal the hidden detail.
This subgraph contraction in LINK is hierarchical, i.e., the programmer or
user can create arbitrary numbers of subgraph layers (subgraphs contracted
within subgraphs).
An induced subgraph of a graph G = (V,E) is contracted by selecting a subset
of vertices V' and calling the addSubgraph(...) method defined
below. When contracted, the vertices of V' and the edges of
E' are (apparently to the user or programmer) removed from the graph and
replaced by a supervertex, which behaves as a normal vertex when processed
by a graph algorithm. However, the subgraph information is maintained as
an attribute of the supervertex. This attribute is itself an object from
the Graph hierarchy of the same type as its parent graph.
An important restriction to keep in mind when creating subgraphs is the
following:
Every vertex which is put into a subgraph must have the same parent.
In other words, two vertices which reside on different levels of the
implicit subgraph hierarchy cannot be placed together into a new subgraph.
One might ask how this situation could ever arise in the first place,
since the user would not be able to see vertices at different levels
simultaneously. It is possible for this to happen, however.
Once created, subgraphs may be ``opened'' without being ``dissolved.''
The user may want to view the expanded graph momentarily, then hide
the subgraph again. The methods implementing this functionality are
described in Section
below.
Next: Input Graph Language
Up: Graph
Previous: Graph
RHS Linux User
1/26/1998