GEONius.com 6-Jan-2004

# `gsc_util` - Graph/Structure Chart Utilities

The Graph/Structure Chart Utilities provide a simple means of constructing and traversing directed graphs. A graph is web of connected points. Each point is known as a vertex; the connection between two points is known as an edge. In a directed graph, edges have a direction. An edge, `A->B`, goes from vertex `A` to vertex `B`, and not in the reverse direction (although there could be another edge, `B->A`). Given an edge, `A->B`, vertex `B` is said to be adjacent to `A`. A simple example of a directed graph is a program's structure chart, where each edge represents the "calls" relationship between a routine and a subroutine. (See npath, a program which collects C source code metrics and uses the `gsc_util` package to generate cflow(1)-style structure charts.)

Usually, graphs are built in order to traverse or search them, to step from vertex to vertex in a certain order. The vertex at which a traversal starts is called the root vertex. The main routine of a program would be the root of a structure chart; an arbitrary graph might have more than one possible root vertex. There are two basic traversal/search strategies for graphs: depth-first and breadth-first. A depth-first traversal descends into lower levels of a graph whenever it can; a breadth-first traversal visits each vertex at a given level before descending to the next lower level.

The classical graph search algorithms only visit each vertex in a graph once during the search. The GSC utilities use these same algorithms, but, when stepping through the vertices using `gscFirst()` and `gscNext()` (see below), vertices with multiple incoming edges will be "visited" multiple times. For example, given two edges, `A->C` and `B->C`, vertex C will be returned twice by `gscNext()`: the first time with a `FIRST` visit indicator and the second time with a `PREVIOUS`ly-visited indicator. The first vertex visited in a cycle will be flagged the second time as a `RECURSIVE`ly-visited vertex. If you only want to visit each vertex once, simply ignore the `PREVIOUS` and `RECURSIVE` vertices returned by `gscFirst()` and `gscNext()`.

The GSC utilities are easy to use:

```    #include  "gsc_util.h"		-- Graph/structure chart definitions.
int  i ;
char  *name, *vertex_A, *vertex_B ;
Graph  graph ;

gscCreate (..., &graph) ;		-- Create an empty graph.
while (more_edges) {		-- Add edges to the graph.
... get edge A->B ...
}

for (i = 1 ;  ;  i++) {		-- For each possible root vertex ...

name = gscRoot (graph, i) ;
if (name == NULL)  break;

gscMark (graph, name, 0) ;	-- Mark graph starting at root.

gscFirst (graph, &name, ...) ;	-- Traverse the graph.
while (name != NULL) {
... process vertex name ...
gscNext (graph, &name, ...) ;
}

}
```
Vertex names are normal ASCII strings. You can use other types of "names", but, to do so, you need to supply `gscCreate()` with the following functions for your name type: `compare()`, `delete()`, `display()`, and `duplicate()`. See `gscCreate()` for more information about how to do this.

## Public Procedures

`gscAdd()` - adds an edge to a graph.
`gscCreate()` - creates an empty graph.
`gscDelete()` - deletes a graph.
`gscDump()` - dumps a graph.
`gscFirst()` - begins a caller traversal of a graph and returns the root vertex of the graph.
`gscMark()` - performs a complete traversal of a graph, marking it in preparation for a caller's traversal.
`gscNext()` - returns the next vertex in a caller traversal of a graph.
`gscRoot()` - returns potential root nodes in a graph.

## Source Files

`gsc_util.c`
`gsc_util.h`

(See `libgpl` for the complete source, including support routines and build files.)

Alex Measday  /  E-mail