The following example uses simple graph algorithms to illustrate generic programming.

A directed graph can be thought of as an object that consists of a set V of vertices and a set $E\subseteq V\times V$ of ordered pairs of vertices, called edges. Graphs can be visualized by diagrams like the following.

This diagram represents a graph with vertex set $V=\left\{a\,b\,c\,d\,e\,f\right\}$, and edge set $E=\left\{\left(a\,b\right)\,\left(a\,c\right)\,\left(b\,d\right)\,\left(b\,e\right)\,\left(c\,b\right)\,\left(c\,d\right)\,\left(c\,f\right)\,\left(d\,e\right)\,\left(f\,d\right)\right\}$.

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:

Store the set V of vertices and the set E of edges explicitly.

Store the "adjacency matrix" of the graph.

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.

To demonstrate how this can be achieved, consider graphs as objects that implement the methods listed in the following table.

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.

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.

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:

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 ] ):

type( g1, 'Graph' );

$\mathrm{true}$

you can use the routine vdeg with the graph g1, since graphs produced by Graph1 implement the Graph interface.

vdeg( g1, a );

$2,0$

vdeg( g1, b );

$1,1$

vdeg( g1, c );

$0,2$

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.

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 ] ):

type( g2, 'Graph' );

$\mathrm{true}$

Therefore, the generic procedure vdeg works equally well with it.

vdeg( g2, a );

$2,0$

vdeg( g2, b );

$1,1$

vdeg( g2, c );

$0,2$

Note: The full source code for these procedures is available in the samples/ProgrammingGuide/graph directory of the Maple installation.

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:

AdjacencyMatrix( g1 );

$\left[\begin{array}{ccc}0& 1& 1\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]$

AdjacencyMatrix( g2 );

$\left[\begin{array}{ccc}0& 1& 1\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]$