gsc_util
- Graph/Structure Chart UtilitiesA->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 ... 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.
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.
gsc_util.c
gsc_util.h
(See libgpl
for the
complete source, including support routines and build files.)