Generic Graph Algorithms - Maple Help

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 $E\subseteq V×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\}$.

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 ] ):
 > type( g1, 'Graph' );
 ${\mathrm{true}}$ (1)
 you can use the routine vdeg with the graph g1, since graphs produced by Graph1 implement the Graph interface.
 > vdeg( g1, a );
 ${2}{,}{0}$ (2)
 > vdeg( g1, b );
 ${1}{,}{1}$ (3)
 > vdeg( g1, c );
 ${0}{,}{2}$ (4)
 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 ] ):
 > type( g2, 'Graph' );
 ${\mathrm{true}}$ (5)
 Therefore, the generic procedure vdeg works equally well with it.
 > vdeg( g2, a );
 ${2}{,}{0}$ (6)
 > vdeg( g2, b );
 ${1}{,}{1}$ (7)
 > vdeg( g2, c );
 ${0}{,}{2}$ (8)
 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:
 $\left[\begin{array}{ccc}{0}& {1}& {1}\\ {0}& {0}& {1}\\ {0}& {0}& {0}\end{array}\right]$ (9)
 $\left[\begin{array}{ccc}{0}& {1}& {1}\\ {0}& {0}& {1}\\ {0}& {0}& {0}\end{array}\right]$ (10)