Example: Generic Graph Algorithms
|
Introduction
|
|
|
The following example uses simple graph algorithms to illustrate generic programming.
|
|
|
Mathematical Description
|
|
|
A directed graph can be thought of as an object that consists of a set V of vertices and a set of ordered pairs of vertices, called edges. Graphs can be visualized by diagrams like the following.
|
|
This diagram represents a graph with vertex set , and edge set .
|
|
|
Software Models
|
|
|
Graphs can be represented in a variety of ways. The choice of storage mechanism depends on the expected applications of the graph. Three possibilities for representing graphs in software are:
|
1.
|
Store the set V of vertices and the set E of edges explicitly.
|
2.
|
Store the "adjacency matrix" of the graph.
|
3.
|
Store, for each vertex of the graph, the set of all its neighbors.
|
|
(The adjacency matrix is a square matrix whose rows and columns are indexed by the vertices of the graph; the (i,j)-entry is equal to 1 if there is an edge from i to j, and is equal to 0 otherwise.) You can write software that manipulates a graph independent of representation.
|
|
|
Designing a Graph Interface
|
|
|
To demonstrate how this can be achieved, consider graphs as objects that implement the methods listed in the following table.
|
Table 1: Graph Methods |
vertices
|
Returns the set of vertices of the graph
|
edges
|
Returns the set of edges of the graph
|
addedge
|
Allows one to add a new edge to a graph
|
order
|
Returns the number of vertices of the graph
|
size
|
Returns the number of edges of the graph
|
|
|
Then, represent the abstract interface of a graph by a Maple type.
|
>
|
`type/Graph` := '`module`( vertices, edges, addedge, order,
size )':
|
|
An object implements the graph interface if it is of type Graph.
|
|
|
Computing Vertex Degrees Generically
|
|
|
If an object implements this interface, then you can write generic code based on that interface. For example, you can write the following procedure to compute the in-degree and out-degree of a vertex of a given graph.
|
>
|
vdeg := proc( G::Graph, v )
local vs, vt;
description "compute the in- and out-degrees "
"of a vertex in a graph";
if member( v, G:-vertices() ) then
vs := select( e -> evalb( v = e:-source() ),
G:-edges() );
vt := select( e -> evalb( v = e:-target() ),
G:-edges() );
nops( vs ), nops( vt );
else
0, 0;
end if;
end proc:
|
|
You can write this procedure even though, at this point, you do not know the graph implementation. This capability is very important when you are designing a large software system.
|
|
|
Edge Object Representation
|
|
|
Assume that edges are represented as objects that implement the interface `module`( source, target ). The interface provides methods for extracting the source and target vertices from an edge. Writing a constructor Edge for edges is easy.
|
>
|
Edge := proc( src, targ )
module()
local the_source, the_target;
export source, target, setsource, settarget;
the_source := src;
the_target := targ;
source := () -> the_source;
target := () -> the_target;
setsource := proc( v )
the_source := v;
end proc;
settarget := proc( v )
the_target := v;
end proc;
end module;
end proc:
|
|
|
First Graph Constructor
|
|
|
At first, you might choose to adopt a graph representation that is simple to implement. Here is a graph constructor that produces graphs represented by storing the vertex and edge sets explicitly as part of the state of a module.
|
>
|
Graph1 := proc()
local vertex_set, edge_set;
description "graph constructor";
edge_set := { args };
if not andmap( type, edge_set, '[ anything, anything ]' )
then
error "graph must be specified by a sequence of edges";
end if;
if not andmap( edge -> evalb( nops ( edge )= 2), edge_set )
then
error "each edge must be specified "
"as a [ source, target ] pair";
end if;
vertex_set := map( op, edge_set );
edge_set := map( Edge@op, edge_set );
module()
export order, size,
vertices, edges,
addedge; # required exports
vertices := () -> vertex_set;
edges := () -> edge_set;
addedge := proc( src, targ )
edge_set := { Edge( src, targ ) }
union edge_set;
vertex_set := { src, targ }
union vertex_set;
NULL;
end proc;
order := () -> nops( vertices() );
size := () -> nops( edges() );
end module;
end proc:
|
|
If you create a small graph using this constructor
|
>
|
g1 := Graph1( [ a, b ], [ a, c ], [ b, c ] ):
|
|
you can use the routine vdeg with the graph g1, since graphs produced by Graph1 implement the Graph interface.
|
|
The important feature of the procedure vdeg is its generic quality. It can be used with any implementation of graphs that implements the Graph interface previously specified.
|
|
|
Second Graph Constructor
|
|
|
Here is another, different implementation of the Graph interface. The graph is represented by using a table N in which the neighbors of each vertex are stored.
|
>
|
Graph2 := proc()
local vertex_set, edge_set;
description "graph constructor";
edge_set := { args };
vertex_set := map( op, edge_set );
if not andmap( type, edge_set, 'list' ) then
error "graph must be specified by a sequence of edges";
end if;
if not andmap( edge -> evalb( nops ( edge )= 2), edge_set )
then
error "each edge must be specified "
"as a [ source, target ] pair";
end if;
module()
export order, size,
vertices, edges,
addedge;
local N, e, v, n, edge_pairs;
N := table();
edge_pairs := () -> { seq(
seq( [ v, n ], n = N[ v ] ),
v = map( op, { indices( N ) } )
) };
vertices := () -> map( op, edge_pairs() );
edges := () -> map( Edge@op, edge_pairs() );
addedge := proc( src, targ )
if assigned( N[ src ] )
and not member( targ, N[ src ] ) then
N[ src ] := { op( N[ src ] ), targ };
else
N[ src ] := { targ };
end if;
NULL;
end proc;
order := () -> nops( vertices() );
size := () -> nops( edges() );
for e in edge_set do
addedge( op( 1, e ), op( 2, e ) );
end do;
end module;
end proc:
|
|
A graph returned by the constructor Graph2 also satisfies the Graph interface.
|
>
|
g2 := Graph2( [ a, b ], [ a, c ], [ b, c ] ):
|
|
Therefore, the generic procedure vdeg works equally well with it.
|
|
Note: The full source code for these procedures is available in the samples/ProgrammingGuide/graph directory of the Maple installation.
|
|
|
Generic Computation of Adjacency Matrices
|
|
|
Another example of a generic procedure over the Graph interface is the following routine for computing the adjacency matrix of a graph.
|
>
|
AdjacencyMatrix := proc( g::Graph )
local a, # the adjacency matrix; returned
n, # the order of the graph g
V, # the vertex set of the graph
E, # the edge set of the graph
row, # row index for matrix
col, # column index for matrix
e; # induction variable for loop
n := g:-order();
a := Matrix( n, n, 'storage' = 'sparse' );
V := sort( convert( g:-vertices(), 'list' ) );
E := g:-edges();
for e in E do
if not member( e:-source(), V, 'row' )
or not member( e:-target(), V, 'col' ) then
error "inconsistent graph structure detected";
end if;
a[ row, col ] := 1;
end do;
a;
end proc:
|
Return to the Index of Example Worksheets.
|
|