Next: Input Graph Language Up: Graph Previous: Graph

### Subgraphs

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