`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 PREVIOUSly-visited indicator. The first vertex visited in a cycle will be flagged the second time as a RECURSIVEly-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 ...
        gscAdd (graph, vertex_A, vertex_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

gsc_util - Graph/Structure Chart Utilities

Public Procedures

Source Files

`gsc_util` - Graph/Structure Chart Utilities