Download GHS Graph Handling System User Manual GHScore

6.2. FORMATS AND DATA STRUCTURES
67
Survey of Functions:
The main function of this chapter is astd. It constructs the biblock decomposition of a general
graph. Function aprstd is used to write the biblock decomposition of a general graph. Function aprstdvt writes a list of vertices. The biblock graph corresponding to a general graph is
constructed by function generateblbgraph. To generate a subgraph from an a-decomposition
element (peripheral tree, stopfree kernel, subcoponent, internal tree, biblock) use the function
generatefromcomp of chapter 4, page 47.
6.2
Formats and Data Structures
For a general description and basic data types see section 2.2, page 11.
The data structures used with the biblock decomposition functions are described in subsection
C.8, page 176. The main record for each stopfree kernel is of type WCOMP, i. e. a record describing
a weak component. This record also describes the stopfree kernel and has pointers to lists of
PT records (peripheral trees), SUB records (subcomponents), IT records (internal trees), and BLB
records (biblocks). With data type AVTSTD biblock decomposition properties of a vertex (e. g.
kind of attachment point) are recorded. In the same way, records of type AEDSTD are used for
edges/arcs. Edges/arcs a vertex is incident with may belong to more than one biblock (hinge
point). Records of type INCSQR indicate the biblocks a vertex is element of. Several enumeration
types are used by the biblock decomposition functions, mostly for internal purposes.
Remark 6.1 Peripheral trees within a weak component are numbered2 . These numbers are used
as identifiers. The same applies to subcomponents and internal trees. Within a subcomponent
the biblocks are numbered2 . These numbers are used as internal identifiers. The complete
identification of an element of the biblock composition is its name as specified in table 4.1,
page 44.
2
6.3
6.3.1
Functions
astd
Program Author: Günther Stiege, Universität Oldenburg
Syntax:
void
astd(GRAPH *graph)
Description: Finds the biblock decomposition of a general graph (of any type). Sets the values
for the decomposition elements (stopfree kernel, peripheral tree, internal trees, subcomponents,
biblocks) in the corresponding WCOMP records and creates complementary records. After
successful termination, the field grastd of the graph’s GRAPH record is set TRUE.
Error Exits:
Graph pointer NULL. Biblock decomposition already exists.
Remarks: To find the biblock decomposition of a general graph the weak components must
be known. If they are not, function gcomponents, page 56, is called implicitly before the adecomposition analysis is done.
2
The numbering depends on the specific run of the decomposition algorithms.