Example: Generic Graph Algorithms - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Applications and Example Worksheets : Language and System : examples/GenericGraphAlgorithms

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 EV×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=a,b,c,d,e,f, and edge set E=a,b,a,c,b,d,b,e,c,b,c,d,c,f,d,e,f,d.

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' );

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' );

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.

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:

AdjacencyMatrix( g1 );

011001000

(9)

AdjacencyMatrix( g2 );

011001000

(10)

Return to the Index of Example Worksheets.

See Also

examples/GenericGroups, examples/QuotientFields