CDMTCS
Research
ReportSeriesAn initial-algebra approachto directed acyclic graphs
Jeremy Gibbons

Department of Computer Science
University of Auckland
CDMTCS-001
April 1995

Centre for Discrete Mathematics andTheoretical Computer ScienceAn initial-algebra approach to directed acyclic
graphsJeremy Gibbons

Department of Computer Science
University of Auckland
Private Bag 92019, Auckland, New Zealand.
Email: jeremy@cs.auckland.ac.nz
Abstract. The initial-algebra approach to modelling datatypes consists of giving constructors

for building larger objects of that type from smaller ones, and laws identifying di erent waysof constructing the same object. The recursive decomposition of objects of the datatype leads
directly to a recursive pattern of computation on those objects, which is very helpful for both
functional and parallel programming.
We show how to model a particular kind of directed acyclic graph using this initial-algebra
approach.

Keywords. Graphs, data types, catamorphisms, initial algebras, Bird-Meertens Formalism,
program derivation.

1 Introduction

It is now widely recognized that the traditional ad-hoc approaches to program
construction do not yield reliable software; a more systematic and formal approachis required. One such approach consists of program veri cation|proving after thefact that a given program satis es its formal speci cation. This approach turns out
to be dicult to implement, not least because the vast majority of programs would
not satisfy their speci cation, even if they had one, but more importantly, because
program veri cation gives no direct help in actually constructing the program in
the rst place.
An alternative approach is provided by program derivation, whereby a program is
calculated from its formal speci cation by the application of a series of correctnesspreserving transformations. The resulting program is guaranteed to satisfy its speci cation (assuming that the calculation is carried out correctly), but now its construction and veri cation are performed together, allowing insights from each to
Copyright c 1994 Jeremy Gibbons. In LNCS 947, Mathematics of Program Construction, ed.
B. Moller, p. 282{303, 1995. This work has been partially supported by University of Auckland
Research Committee grant numbers A18/XXXXX/62090/3414013, /3414019 and /3414024.

An initial-algebra approach to directed acyclic graphs2

help with the other.
Such a calculational approach necessitates having a body of notations for writing
programs and theorems for proving equalities between them|that is, a calculus ofprograms. The Bird-Meertens Formalism (Meertens, 1986; Bird, 1987; Backhouse,1989) is one such calculus; it relies on tightly-coupled notions of data and program
structure to yield its notations and theorems. In particular, datatypes are de ned as
extreme (initial or terminal) objects in categories of algebras|equivalently, extreme
solutions of recursive systems of equations|and various morphisms representing
common patterns of computation on those datatypes de ned as the corresponding
unique arrows from or to those objects. In this paper, we consider only initial
algebras and catamorphisms, the corresponding morphisms; how well the ideas
translate to nal algebras and other morphisms remains to be seen.
De ning a datatype as an initial algebra essentially consists of giving two kindsof object:
constructors for building larger elements of that type from smaller elements,
andlaws identifying syntactically di erent but semantically equivalent ways of constructing an element of that type.
Studying the initial algebra corresponding to a datatype gives new ways of implementing that datatype, and new insight into old algorithms|and sometimes
even new algorithms|on that datatype. Moreover, the initial-algebra approachto datatypes appears to be particularly suitable for implementation in functional
languages and in languages for parallel execution (Skillicorn, 1994).
We have a good understanding of initial algebras corresponding to many common
datatypes, such as lists (Bird, 1987), sets and bags (Backhouse, 1989; Hoogendijk,
1993; Bunkenburg, 1993), trees (Meertens, 1988; Jeuring, 1989; Gibbons, 1991),
and arrays (Wright, 1988; Bird, 1988; Jeuring, 1991). One datatype ubiquitous incomputing but conspicuous by its absence from this collection is that of graphs. The
reason for this absence is that in order to model graphs, it appears that some meansof `naming' subcomponents is required. In contrast, the initial-algebra approachpermits only `structural' references to subcomponents.
In this paper we take steps towards remedying this absence, by de ning andexploring an initial algebra corresponding to directed acyclic graphs. We showthat naming is not necessary for modelling directed acyclic graphs. However, theseare only the rst steps; for one thing, the algebra does not correspond exactly
to directed acyclic graphs, and for another, there are other kinds of graphs (forexample, undirected graphs and directed cyclic graphs) to consider. These are
topics for further study.
The rest of this paper is organized as follows. In Section 2, we review the initialalgebra approach to modelling datatypes. In Section 3, we present an initial-algebraAn initial-algebra approach to directed acyclic graphs

3

Figure 1: An unlabelled join list
de nition of unlabelled directed acyclic graphs. In Section 4, we discuss catamorphisms on graphs. In Section 5, we generalize the construction of Section 3 tolabelled directed acyclic graphs. In Section 6, we discuss other approaches to representing graphs in a style suitable for functional programming. Finally, Section 7
summarizes and presents directions for further work.
Throughout this paper, we write ` . ' for function application, which associates tothe right, and `  ' for function composition, which is associative:(g  f ).a = g.(f.a) = g.f.a
We write ` a : A ' for ` a has type A ', and ` ' for the type of natural numbers including zero. For associative operator ( , we write copy(n, (, x) as an abbreviation
for x ( x ( ( x with n occurrences of x . For any x , copy(0, (, x) is the unitof ( if it exists.
N

2 Initial Algebras and Catamorphisms

We introduce the initial-algebra approach to datatypes by way of a simple familiar
example, the algebra of join lists. We use what may seem like unnecessarily heavymachinery for this simple example; the reason is that the machinery is necessary
for the more complex algebra of directed acyclic graphs that is the subject of thispaper.
2.1 Unlabelled Join Lists
We start by considering `unlabelled join lists' (ujls), which are nite possiblyempty chains of unlabelled nodes. For example, the ujl with three nodes might
be drawn as in Figure 1. Ujls are built using three constructors: the constants
null and node , respectively representing the empty list and the list with one node,and the binary operator ++ (pronounced `join') which joins two lists to make a(usually) longer list.
These constructors obey some laws, identifying di erent ways of building thesame list. These laws are that ++ is associative and has unit null . (In other words,
the constructors form a monoid.) For example, the list in Figure 1 is representedby (among others) the expression
node ++ node ++ nodeBecause of associativity, no parentheses are needed.
Ujls can be modelled as a category. Recall that a category consists of a collectionof objects and a collection of arrows between objects. We write ` x : m n ' to!

An initial-algebra approach to directed acyclic graphs
3

1

4

6

Figure 2: A labelled join list
indicate that arrow x goes from object m to object n . Compatible arrows canbe composed; if x : m n and y : n p then x ; y : m p . Composition isassociative, and for every object m there is an identity arrow idm : m m whichis the unit of composition to or from that object.
In the case of ujls, the category has a single object, corresponding to the type of
all ujls, and arrows corresponding to the lists themselves. Composition of arrows
corresponds to joining lists; since there is but a single object, all pairs of arrows arecomposable. The identity arrow corresponds to the empty list. We require an arrowcorresponding to the list node with a single element; since the collection of arrows
is closed under composition, there is then necessarily an arrow corresponding toevery ujl.
If we now consider those categories with a single object, they in turn form acategory , with objects the categories in question and arrows the functors between
these categories. (A functor F from category B to category C is a morphism on
categories taking objects of B to objects of C and arrows of B to arrows of C suchthat, if x : m n in B then F.x : F.m F.n in C , and moreover F.idm = idF.mand F.(x ; y) = F.x ; F.y .) We de ne the algebra of ujls to be the initial object
in , that is, the object in from which there is a unique arrow to any otherobject in . (The initial object is unique up to isomorphism, and can be shown toexist.) Informally, this states that ujls form the smallest algebra closed under theconstructors in which the given laws hold, and no other laws do.
2.2 Labelled Join Lists
Of course, the type of ujls is not very interesting; it is isomorphic to the natural
numbers. We presented it simply because it happens to be the list-like algebra
closest to the unlabelled directed acyclic graphs that we introduce later.
We can generalize ujls to labelled join lists (ljls) with nodes labelled by elementsof some type A . The node constructor changes, so that now node.a is a ljl forevery a : A , but the two constructors null and ++ and the laws do not change. For
example, the ljl in Figure 2 is represented by the expression
node.3 ++ node.1 ++ node.6
where the label type is .
Ljls with labels of type A are by de nition the initial object in the category
consisting of categories with just one object and an arrow corresponding to every
element of type A .
!

!

!

!

L

!

!

L

L

L

N

An initial-algebra approach to directed acyclic graphs

5

Ujls are isomorphic to ljls with labels drawn from the unit type (the type withexactly one element), so from now on we will use the term `join lists' to refer toljls.
2.3 Catamorphisms on Join Lists
Since the algebra of join lists was de ned to be the initial object in the appropriate
category, there is by de nition a unique morphism from that algebra to any target
algebra in the category. Such a morphism is called a join list catamorphism, and is
uniquely determined by that target algebra.
Put another way, a function h from join lists with labels of type A to anothertype B is a join list catamorphism i there exist a constant b : B , a function
f : A B and a binary operator ( : B B B such thath.null = b
h.node.a = f.ah.(x ++ y) = h.x ( h.yand such that ( is associative and has unit b . (The target category in this casehas a single object B and arrows corresponding to elements of B ; composition ofarrows corresponds to ( , and the identity arrow is b .) We write ` hb, f, (i ' forsuch an h .
There are many examples of interesting join list catamorphisms. A few simple
ones are as follows. The identity function on join lists is hnull, node, ++i . The
function length , returning the number of nodes in a list, is h0, f, +i where f.a = 1
for each a . The function reversel , which reverses a join list, is hnull, node, (i wheret ( u = u ++ t .
!

!

3 Unlabelled Directed Acyclic Graphs

In this section, the main part of the paper, we present an initial-algebra de nitionof a particular kind of directed acyclic graph.
3.1 Directed Acyclic Multigraphs
The particular kind of graph we will model is that of directed acyclic graphs, butwith a few unconventional aspects:
there may be more than one edge between a given pair of vertices (thus, theseare multigraphs rather than simply graphs)
the incoming and outgoing edges of a vertex are ordered (that is, they form asequence, rather than a bag or set)
the graph as a whole has a sequence of incoming edges (`entries') with targets
but no sources, and a sequence of outgoing edges (`exits') with sources but notargets; entries and exits are collectively called `connections'
We call such a graph a directed acyclic multigraph, or damg (pronounced `damage')for short.
An initial-algebra approach to directed acyclic graphs

6

Figure 3: The form of a graph of type G3,4

Figure 4: The vertex vert3,2
For m, n : , the type Gm,n consists of damgs with m entries and n exits. Thus,
a graph of type G3,4 has the form pictured in Figure 3. We write G for the typeof all damgs.
3.2 Constructors
Damgs are built from six constructors, as explained below.
Vertices
Vertices are represented by a set vert indexed by pairs of natural numbers, suchthat vertm,n : Gm,n for m, n : . The intention is that vertm,n represents a single
vertex with m entries and n exits. For example, vert3,2 might be drawn as in
Figure 4.
Edges
The constant edge : G1,1 is simply an edge, with a single entry and a single exit. It
would be drawn as in Figure 5.
BesideIf x : Gm,n and y : Gp,q then x y (pronounced ` x beside y ') is of type Gm+p,n+q .
Informally, x y consists of x `in parallel with' y ; for example, vert1,2 vert2,1(of type G3,3 ) might be drawn as in Figure 6. (In drawings of graphs, we orderconnections from top to bottom, and direct them from left to right.)
The constructor is associative, so x (y z) = (x y) z . We write ` m x ' as
N

N

|

|

|

|

|

|

Figure 5: An edge

|

|



An initial-algebra approach to directed acyclic graphs

7

Figure 6: vert1,2 vert2,1|

Figure 7: vert0,1 vert1,0;

an abbreviation for copy(m, , x) ; we see later that has a unit, so 0 x is de ned.
BeforeIf x : Gm,n and y : Gn,p , then x y (pronounced ` x before y ') has type Gm,p , and isformed by connecting the exits of x to the entries of y . For example, vert0,1 vert1,0
might be drawn as in Figure 7.
The constructor is associative; that is, x (y z) = (x y) z if both expressions
are correctly typed. (Note that if either expression is incorrectly typed, then bothare.)
We write ` m ' for the restriction of to pairs of damgs with exactly m intermediate connections. Note that m has unit m edge .
A further property enjoyed by and is the so-called abiding law. If w : Gm,n ,x : Gn,p , y : Gq,r and z : Gr,s , then(w n x) (y r z) = (w y) n+r (x z)
For example,(vert2,1 vert1,1) (vert1,1 vert1,2) = (vert2,1 vert1,1) (vert1,1 vert1,2)|in pictures, both sides might be drawn as in Figure 8. Notice that the type
information is important here; without it, (w y) (x z) may be well-typed when(w x) (y z) is not.
The name `abiding' is due to Bird (1988). He coined it as a contraction of`above' and `beside', operators which he used for building a larger array by putting
one smaller array above or beside another.
Empty
We introduce a constructor empty for the empty graph, largely because of theelegant properties that it enjoys. It would be drawn as a blank picture. The empty
graph satis es the following two laws.
|

|



;

;

;

;

;

;

;

|

|

;

|

;

;

;

|

;

|

;

|

;



|

|

;

;

;

;

;

;

|

|

An initial-algebra approach to directed acyclic graphs

8

Figure 8: An instance of the abiding law

Figure 9: An instance of the dislocation law
empty is the unit of | (and so, for any x , 0  x = empty ) empty (being 0  edge ) is also the unit of ;0
From these we can conclude that, if x : Gm,0 and y : G0,n , then x ;0 y = x | y , since
x ;0 yno=empty is the unit of |(x | empty) ;0 (empty | y)


n

=

o

abiding(x 0 empty) (empty 0 y)no=empty is the unit of 0
;

|

;

;

x|y

For example, both vert2,0 0 vert0,1 and vert2,0 vert0,1 could be drawn as in Figure 9.
We call this the dislocation law. Symmetrically, x 0 y = y x .
Swap
The ve constructors we have seen so far can construct only planar graphs. The constructor swap escapes from planarity. For m, n
, swapm,n has type Gm+n,n+m ,and consists of m edges connecting the rst m entries to the last m exits, and nedges connecting the last n entries to the rst n exits. For example, swap3,2 has
type G5,5 , and might be drawn as in Figure 10.
Swaps satisfy a number of laws. The rst of these laws states that swapping zeroconnections makes no di erence:swapm,0 = m edge
;

|

;

2 N



|

An initial-algebra approach to directed acyclic graphs

9

Figure 10: swap3,2

Figure 11: Breaking down a larger swap
The second law shows that swapping n + p connections can be done by swappingn connections and then swapping p connections:swapm,n+p = (swapm,n (p edge)) ((n edge) swapm,p )The right-hand side of this equation is illustrated in Figure 11, in the case whenm = 1 , n = 2 and p = 3 . We call these last two laws the swap simpli cation laws.
|



;



|

The third law relates swaps to other constructs. If x : Gn,p and y : Gm,q thenswapm,n (x y) swapp,q = y x
We call this the swap law. The left-hand side of this equation is illustrated in
Figure 12, in the case when x = vert2,1 and y = vert1,2 ; then the right-hand side is
as in Figure 6.
In the special case when n = p , x = n edge , m = q and y = m edge , theswap law simpli es toswapm,n swapn,m = (m + n) edge
From this law and the earlier simpli cation laws we can deduce simpli cation laws
for the rst index too:swap0,n = n edge
;

|

;

|



;





Figure 12: An instance of the swap lawAn initial-algebra approach to directed acyclic graphs

10

Figure 13: An example graph

Figure 14: An `exploded view' of the graph in Figure 13
andswapm+n,p = ((m  edge) | swapn,p ) ; (swapm,p | (n  edge))

Note that, in view of the swap simpli cation laws, any swap can be built fromswap1,1 and edges using and , so in that sense we could replace the family ofswap constructors with just swap1,1 . However, it appears that the general form of
the swap law is then dicult to express.
3.3 An Example Graph
As an example, we show how to construct the graph in Figure 13.
`Teasing' apart the edges, we see that this graph is equivalent to the exploded
graph in Figure 14. Hence the graph is represented by the expression(3 vert0,2) (edge ((2 swap1,1) (edge swap1,1 edge)) edge) (2 vert3,0)
|



;

|

;



;

|

|

|

;



3.4 Damgs As Symmetric Strict Monoidal Categories
It turns out that the algebra of damgs is essentially a symmetric strict monoidal
category (Mac Lane, 1971) enriched with objects representing vertices. We expand
here on this observation.
A strict monoidal category (smc) (B, +, e) is a category B in which:the objects of B form a monoid with respect to + (as a binary operation on
objects of B ) and e (as an object of B )An initial-algebra approach to directed acyclic graphs11

the operator + also acts on arrows of B ; if x : m n and y : p q thenx + y : m + p n + q ; moreover, + satis es the laws
(x + y) + z = x + (y + z)
ide + x = x
x + ide = x
idm + idn = idm+n(w + x) ; (y + z) = (w ; y) + (x ; z)provided in the last case that all the compositions are de ned.
A symmetric strict monoidal category (ssmc) (B, +, e, ) is a smc (B, +, e) witha family of arrows m,n : m + n n + m for all objects m and n of B , for which
the following laws hold:m,0 = idm
m,n+p = ( m,n + idp ) ; (idn + m,p )m,n ; (x + y) ; p,q = y + x
provided in the last case that x : n p and y : m q .
Clearly, the algebra of damgs forms a ssmc (B, , empty, swap) in which the category B has as objects the natural numbers, and arrows x : m n corresponding
to damgs x in Gm,n . Composition of arrows is , and the identity object on m is
m edge .
Now consider ssmcs in which the objects of the base category B are the natural
numbers, and the collection of arrows of B also contains arrows vm,n : m n foreach pair of naturals m, n . We call such a ssmc an enriched ssmc, and write forthe category of all enriched ssmcs (with functors between ssmcs as arrows). We
de ne the algebra of damgs to be the initial ssmc in the category . Informally,
this says that damgs form the smallest algebra closed under the constructors inwhich all and only the damg laws hold.
3.5 Soundness and Completeness of the Laws
When axiomatizing a datatype, it is usually obvious whether sucient constructors
have been chosen to represent all elements of the intended model. If there are notenough constructors, extra ones can be added as necessary, and the worst that canhappen is some redundancy in the resulting datatype.
It is more dicult to tell whether the right collection of laws has been chosen,
since this collection must be neither too strong nor too weak. The collection mustsatisfy the following two properties.
Soundness: The given collection of laws must certainly be true of the intended
model. That is, the laws must not be too strong, identifying distinct elementsof the intended model.
Completeness: Soundness can be attained simply by having no laws at all. The
competing requirement is that the collection of laws must be complete. That


!

!

!

!

!

!

|

!

;



!

G

G

An initial-algebra approach to directed acyclic graphs

12

is, the laws must be sucient to identify any two representations of the sameelement in the intended model. In other words, the collection of laws must also
not be too weak.
We have just seen that the ve constructors edge , , , empty and swap , together with all the laws (that is, the whole algebra except the vertices), form
exactly a ssmc in which the objects are the natural numbers. Cazanescu andStefanescu (1991) show that such a category axiomatizes bijective relations; bijective relations are the initial algebra with those ve constructors and those laws.
Since none of the laws involve the vertices, the whole algebra (all six constructors
together with the laws) axiomatizes vertices with bijections for `plumbing' between
them. This is clearly exactly the datatype of directed acyclic multigraphs; the laws
we have de ned are indeed sound and complete.
;|

4

Damg Catamorphisms
We de ned the algebra of damgs to be the initial object in the category G ofenriched ssmcs. By de nition, therefore, there is a unique morphism from thealgebra of damgs to any other enriched ssmc. Such a morphism is called a damg
catamorphism, and is uniquely determined by that other enriched ssmc.
Put another way, a function h : G ! B is a damg catamorphism i there exist

constants a, b : B , families of constants vm,n : B and sm,n : B indexed by pairs ofnaturals m, n , and binary operators ( : B B B and ) : B B B such thath.empty = ah.edge = bh.vertm,n = vm,nh.swapm,n = sm,nh.(x y) = h.x ( h.yh.(x y) = h.x ) h.y(in fact, h.x ) h.y need only be de ned when x and y are compatible) and suchthat these constants and functions form an enriched ssmc in the obvious way. We
write ` ha, b, v, s, (, )i ' for such an h ; these six items uniquely determine h .
4.1 Examples of Damg Catamorphisms
Some simple examples of damg catamorphisms are as follows. The identity function
on G is hempty, edge, vert, swap, , i . The function nvertices , which returns thenumber of vertices, is h0, 0, 1, 0, +, +i . (We write simply ` 1 ' for the family of
constants indexed by pairs of naturals, each member of which is 1 .) The function
reverseg , which reverses a damg, is hempty, edge, vert, s, , )i where sm,n = swapn,mand t ) u = u t .
A more interesting example is the function sp , which returns the length of theshortest path from each entry to each exit; sp takes a damg of type Gm,n andreturns an m n matrix of values in. We have


!



|
;

| ;

|

;



N [ f1g!

An initial-algebra approach to directed acyclic graphs

13

Figure 15: Another example graphsp = ha, b, v, s, (, )i

where

a is the 0  0 matrix
 b is the 1  1 matrix containing a 0
 vm,n is the m  n matrix consisting entirely of 1 sAB sm,n is the (m + n)  (n + m) matrix of the form
C D in which A and
D are m  n and n  m submatrices consisting entirely of 1 s, and B and C
are m  m and n  n submatrices with zeroes on the leading diagonals ands elsewhere
if t and u are m n and p qmatrices, respectively, then t ( u is the(m + p) (n + q) matrix 1t 1u |that is, with elements from t and u in
the top left and bottom right quadrants, andlling the other two quadrants
if t and u are m n and n p matrices, respectively, then t ) u is thematrix product of t and u in the closed semiring (min, +) |that is,(t ) u)i,j = 1min(ti,k + uk,j ) for 1 i m, 1 j pkn
where is the zero of addition and the unit of min .
For example, the damg in Figure 15 is represented by the expression:vert1,2 ((vert1,1 vert1,1) vert1,1) vert2,1
and one way of computing its single shortest path could be as illustrated in Figure 16. Thus, the shortest path between the connections of vert1,1 has just one
vertex, and that between the connections of vert1,1 vert1,1 has two; the shortest
paths between the four possible pairs of connections of (vert1,1 vert1,1) vert1,1 havelengths 2 , , and 1 . The shortest path from the only entry to the only exitof the whole graph has three vertices.
We should check that sp really is a damg catamorphism, that is, that the six
components really do form an enriched ssmc. We leave it to the reader to verify(writing im for copy(m, (, b) , the m m matrix with 0 s on the leading diagonal
and s elsewhere) that:
1









1















1

;

;

|

;

;

;

1

1



1

|

An initial-algebra approach to directed acyclic graphs

14

vert
1,2 ; ( (vert1,1 ; vert1,1) | vert1,1 ) ; vert2,1| {z } | {z } | {z }| {z }| {z }
1 1



|

1



{z

2

|



1

}


{z

2 1
1
1
{z


|

3 2

|

1



3

1
1



}



}



{z



}



Figure 16: The shortest path between connections of the graph in Figure 15( is associative, and has unit a) is associative, and has unit im (for suitable value of m )(w ) x) ( (y ) z) = (w ( y) ) (x ( z) for compatible matrices w, x and y, z

sm,0 = im sm,n+p = (sm,n ( ip ) ) (in ( sm,p ) sm,n ) (x ( y ) ) sp,q = y ( x for n  p matrix x and m  q matrix y

If still keen after doing so, the reader may also wish to verify that the function thatcomputes the longest path between any pair of connections is also a catamorphism.

5 Labelled Damgs

In this section we discuss labelling the vertices and edges of a damg.
5.1 Vertex-Labelled Damgs
We can generalize to vertex-labelled damgs easily. We write Gm,n.A for the type ofdamgs with m entries and n exits and vertices labelled with elements of A , andG.A for the type of vertex-labelled damgs with any number of connections. Then,for a of type A , vertm,n.a is of type Gm,n.A , and consists of a single vertex withm entries and n exits and label a . The other ve constructors and all the laws
remain unchanged.
Thus, the expression
vert1,2.3 ((vert1,1.2 vert1,1.5) vert1,1.9) vert2,1.7
represents the vertex-labelled damg of type G1,1. in Figure 17.
5.2 Edge-Labelled Damgs
It is more dicult to model edge-labelled damgs satisfactorily. For example, should
we label all connections? If so, what happens when connections matched by do nothave the same label? Should be a partial operator, unde ned in such cases? Or
;

;

|

;

N

;

;

An initial-algebra approach to directed acyclic graphs
2

3

5

15

7

9

Figure 17: A vertex-labelled damg
should it be asymmetric, taking (say) the labels from its rst argument? Alternatively, we could label only `complete edges'|edges with a vertex at each end|andleave `dangling' connections unlabelled; then could take also a list of of the appropriate number of labels with which to label connections. Another alternative
would be to label the connections with elements of a monoid (for example, lists),
and combine the labels on matched connections using the binary operation of themonoid.
It is not at all clear which is the best approach to take.
5.3 Topological Sort
One operation suitable for vertex-labelled damgs is topological sort; given a damg,
return the vertex labels as a list whose ordering respects the edge ordering of thegraph. Is topological sort a catamorphism?
It would appear so. Topological sort ts satis es the following properties.
ts.empty , ts.edge and ts.swapm,n are all just null , since these graphs have no
vertices
ts.vertm,n.a is node.ats.(x y) is ts.x ++ ts.yts.(x y) is any interleaving of ts.x and ts.y |for example, ts.x ++ ts.y
In other words, we can topologically sort a damg by deleting from the expression
by which it was constructed everything except the labels; this necessarily gives thecorrect labels in a correct order.
Unfortunately, things are not so straightforward. In general, a damg has many
topological sorts, but the function ts can return only one of them. Moreover, withthe way we have de ned ts above, the particular topological sort returned will
depend on the way that the graph was constructed. For example, suppose that wetake ts.(x y) = ts.x ++ ts.y , as suggested above. Then the two graphs(vert1,1.1 vert1,1.2) (vert1,1.3 vert1,1.4)
and(vert1,1.1 vert1,1.3) (vert1,1.2 vert1,1.4)(which by the abiding law are equal) will have di erent images, [1, 2, 3, 4] and
;






;



|

|

;

|

;

|

;

|

An initial-algebra approach to directed acyclic graphs

16[1, 3, 2, 4] , under ts . Both images are valid topological sorts of the graph, but if ts
is to be well-de ned it must return exactly the same topological sort as result given
the same graph as argument.
Put another way, the sextuple of components (null, null, node, null, ++ , ++) does
not form an enriched ssmc, since it does not satisfy all the damg laws. Neither
does (null, null, node, null, (, ++) for any ( such that x ( y is an interleaving of x
and y ; in particular, ++ does not abide with any deterministic interleave operator.
The problem is that a single topological sort of each of x and y is sucient information to compute one topological sort of x y , but not in general to compute all
topological sorts. Topological sort is not a damg catamorphism.
(The problem appears to do with the deterministic interleaving for ts.(x y) ,which suggests that although topological sort is not a functional catamorphism, it
might be a relational catamorphism (Backhouse et al., 1991). The topological sortsof x y would be any interleaving of the topological sorts of x and of y . Unfortunately, given topological sorts s and t of x and y , still the only list guaranteed
to be a topological sort of x y is s ++ t |although other interleavings of s and t
may also be. The two di erent representations of the same graph above will still
have di erent topological sort relations|the rst representation allows [1, 2, 3, 4]
whereas the second does not. Intuitively, the non-determinism is `too local'; itturns out that `more global' non-determinism is needed. In fact, the function that
returns the set of all topological sorts of a damg is a functional catamorphism(Paige, 1994).)
;

|

|

;

6 Other Approaches to Modelling Graphs

In this section we discuss a number of other approaches to modelling graphs, andcompare them to the initial-algebra approach presented here.
6.1 Traditional Representations
Graphs are traditionally represented in one of three ways:
a set of vertices and a set of edges
a collection of adjacency lists
an adjacency matrix
None of these representations are particularly suitable for implementing graph algorithms in a functional language. More to the point, however, none of these representations recursively composes larger graphs out of smaller ones, and so none of themprovides for free a pattern of computation on graphs that recursively decomposes
its argument into smaller graphs. Such patterns of computation|catamorphisms|
seem very useful for functional and parallel programming.
6.2 Graphs in Functional Languages
Directed graphs can be represented in a lazy functional language using cyclic data
structures (Bird, 1984). For example, the Gofer de nitionAn initial-algebra approach to directed acyclic graphs
1

17

2
3

Figure 18: A cyclic graph[node1,node2,node3] where node1 = (1, [node2,node3])
node2 = (2, [node1])
node3 = (3, [])represents the cyclic graph in Figure 18 as a list of vertices where each vertex is a pairconsisting of a label and an adjacency list. The disadvantage of this approach is thata cyclic graph is operationally indistinguishable from an in nite tree. Kashiwagi
and Wise (1991) use this approach to implement some graph algorithms (strong
components, connected components, acyclicity) by having a stream of `updateable'
values at each node and a problem-speci c method of nding xed points on thosestreams. This produces a graph labelled with results, which, if cyclic, is again
indistinguishable from an in nite tree.
A related approach (Paterson, 1994) is to represent the graph as a function oftype N F.N , where N is the type of node identi ers and F is some functor.
King and Launchbury (1993) implement some graph algorithms (topological sort,connected components, strong components, reachability) by imperatively performing a depth- rst search on the graph, and declaratively manipulating the resulting
depth- rst-search forest.
Burton and Yang (1990) implement graphs in a pure functional language e ectively by implementing an imperative store and threading this through the program.
6.3 Formal Languages and Relations
Moller (Moller, 1993a, 1993b; Moller and Russling, 1993) uses formal languages,
and in particular multiary relations, to model graphs. He derives a number ofgraph algorithms, such as reachability, topological sort and cycle detection.
This approach gives concise speci cations and calculations. However, graphs arestill modelled monolithically|there is no recursive decomposition, and so no direct
help in that way in constructing programs. (Help does come from another direction,
though: from familiar properties of relations and formal languages.)
6.4 Graph Grammars
There is a large body of work in the eld of graph grammars. Courcelle (1990)
gives de nitions in terms of directed hypergraphs, in which edges may have arbitrarily many endpoints; to avoid too much extra notation, we discuss here just the
specialization to edges with exactly two endpoints.
!

An initial-algebra approach to directed acyclic graphs

18

A graph has a source, a sequence consisting of some of the vertices of the graph(perhaps with omissions and duplication). Vertices in the source are `external' andare available for connection to other graphs; other vertices are `internal' and are
hidden.
There are ve constructors:
vertex: a single vertex, which is the sole element of the sourceedge: a single edge, with two vertices that form the source
disjoint union: combines two graphs into a larger graph, concatenating the sources
source fusion: takes a graph and an equivalence relation  on its sources, andidenti es the vertices equivalent under 
source rede nition: rearranges the source of a graph (perhaps omitting some vertices and duplicating others) according to a given mapping
There are eleven laws; these are sucient to transform any term built from theabove constructors into a (non-unique) normal form consisting of the disjoint unionof some vertices and edges, submitted to a single source fusion and then a single
source rede nition.
Graph grammars are appropriate as a basis for describing graph rewriting systems, but they seem less so for more general graph algorithms.
6.5 Skillicorn's De nition
Skillicorn (1994) de nes an algebra of connected undirected vertex-labelled graphs,
using three constructors:
an injection, mapping labels to vertices,a binary operator `connect', connecting two disjoint graphs with a single edge,
anda unary operator `close', adding an edge to a graph, thereby creating a cycle.
In order to indicate which two vertices are connected by the `connect' or `close'
operators, Skillicorn says that the two constructors `are drawn as simple straightlines connecting the two vertices', which seems to imply that his graphs can be
represented faithfully only by two-dimensional pictures, and not by one-dimensionalterms in an algebra.
Moreover, Skillicorn does not state the laws needed to distinguish this algebrafrom an algebra of trees in which each node can have zero, one or two children. He
is therefore forced to decompose a graph in exactly the same way as it was built,
precluding any attempt at load-balancing for parallel execution.
6.6 Free Net Algebras
Molitor (1988) de nes an algebra of `nets', modelling vlsi circuits. The constructorsof this algebra are:a collection of basic `cells',







An initial-algebra approach to directed acyclic graphs

19

some wiring components (straight wires, corners, t-junctions and a `crossover'),andtwo partial binary operators `above' and `beside' which compose circuit diagrams vertically and horizontally, provided that the edges to be matched havethe same number of connections.
He gives a collection of fourteen rather complex laws, and claims that they aresound and complete. (The proof is omitted from Molitor's paper, and the reader
referred to his thesis.)
This work may lead to an algebra of undirected hypergraphs, in which an `edge'
connects arbitrarily many vertices.


7 Conclusions

7.1 Summary
We have presented an initial algebra modelling a particular (and rather unconventional) kind of directed acyclic graph. We have shown that quite a few naturalfunctions on these graphs are catamorphisms on the algebra we have de ned; wehave also seen one natural function (topological sort) that appears not to be acatamorphism. (We believe that this is no fault of the particular algebra presented
here, but is inherent in any initial-algebra model of directed acyclic graphs.) We
have also discussed a number of other approaches to representing graphs.
7.2 Further Work
There are several directions for further work that appear quite promising. A few ofthese are outlined below.
One question that remains to be answered is whether the algebra presented
here is practically useful. Many natural simple problems on damgs turn out
to be damg catamorphisms, but we have not yet seen any more complicatedproblems whose solution was simpli ed by this algebra of damgs.
A problem with the algebra we have de ned here is that it does not model
directed acyclic graphs particularly closely. We have had to introduce `connections' (incoming edges with targets but no sources, and outgoing edges withsources but no targets) for the whole graph, allow multiple edges between apair of vertices, and consider the ordering of the incoming and outgoing edges
of a vertex to be signi cant, all in order to come up with an algebra at all. Is
it possible to adapt this approach to yield an algebra that more closely models
directed acyclic graphs?
The `symmetric strict monoidal category' approach we have used here is basedheavily on the work of Cazanescu and Stefanescu. They use it to obtain
initial-algebra models of sixteen classes of nite relations, corresponding to
all sixteen combinations of totality, surjectivity, univocality (that is, being
single-valued or functional) and injectivity (Cazanescu and Stefanescu, 1991).


An initial-algebra approach to directed acyclic graphs

20

They go on (Cazanescu and Stefanescu, 1990) to present an algebraic theoryof ` ownomials'| owcharts abstracted on both the individual statements andthe interconnection pattern; the algebra of cyclic ownomials consists of thealgebra of acyclic ownomials (similar to our damgs) endowed with `feedback'
operator that cyclically connects the rst few exits to the corresponding number of entries. This may present a way to adapt our approach to model also
possibly cyclic graphs.
Modelling undirected graphs appears to be more dicult, because vertex connections are not partitioned into two groups according to direction, and it istherefore less obvious how to connect subgraphs together.
With all the other initial-algebra de nitions of datatypes that have been explored to date, the concept of an accumulation has proved to be very powerful(Gibbons, 1993). Essentially, an accumulation records all the partial resultsfrom the computation of a catamorphism. One application of `forwards andbackwards accumulations' on directed acyclic graphs might be to compute `earliest and latest possible nishing times' for tasks in a project, in which the tasks
are represented by the vertices of a graph (labelled with task duration) andtheir dependencies by the edges. However, all these other initial algebras havebeen `free', that is, with no laws. It is not immediately obvious how to de ne
accumulations on types with laws, since for these there may be di erent waysof representing the same object, and hence di erent ways of computing thesame catamorphism on that object. These di erent computations necessarily
return the same results, but may well do so with di erent collections of partial
results; which computation should the accumulation record?
7.3 Acknowledgements
The author wishes to thank Bob Paige for pointing out the dislocation law, andother members of ifip wg2.1 and the anonymous referees for many helpful comments. Also, this presentation would have been a lot less elegant without the helpof Virgil Cazanescu and Gheorghe Stefanescu's work on ssmcs.


References

Roland Backhouse, Peter de Bruin, Grant Malcolm, Ed Voermans, and Jaap van derWoude (1991). Relational catamorphisms. In Moller (1991), pages 287{318.
Roland Backhouse (1989). An exploration of the Bird-Meertens formalism. In
International Summer School on Constructive Algorithmics, Hollum, Ameland.
STOP project. Also available as Technical Report CS 8810, Department ofComputer Science, Groningen University, 1988.
R. S. Bird, C. C. Morgan, and J. C. P. Woodcock, editors (1993). LNCS 669:
Mathematics of Program Construction. Springer-Verlag.

An initial-algebra approach to directed acyclic graphs

21

Richard S. Bird (1984). Using circular programs to eliminate multiple traversals of
data. Acta Informatica, 21:239{250.
Richard S. Bird (1987). An introduction to the theory of lists. In M. Broy, editor,
Logic of Programming and Calculi of Discrete Design, pages 3{42. SpringerVerlag. Also available as Technical Monograph PRG-56, from the Programming
Research Group, Oxford University.
Richard S. Bird (1988). Lectures on constructive functional programming. In
Manfred Broy, editor, Constructive Methods in Computer Science. SpringerVerlag. Also available as Technical Monograph PRG-69, from the Programming
Research Group, Oxford University.
Alex Bunkenburg (1993). The Boom hierarchy. In Kevin Hammond and John T.
O'Donnell, editors, 1993 Glasgow Workshop on Functional Programming.
Springer.
F. Warren Burton and Hsi-Kai Yang (1990). Manipulating multilinked data structures in a pure functional language. Software|Practice and Experience,20(11):1167{1185.
Virgil Emil Cazanescu and Gheorghe Stefanescu (1990). Towards a new algebraic
foundation of owchart scheme theory. Fundamenta Informaticae, XIII:171{
210.
Virgil-Emil Cazanescu and Gheorghe Stefanescu (1991). Classes of nite relations
as initial abstract data types I. Discrete Mathematics, 90:233{265.
Bruno Courcelle (1990). Graph rewriting: An algebraic and logic approach. In Jan
van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B,
chapter 5. Elsevier.
Jeremy Gibbons (1991). Algebras for Tree Algorithms. D. Phil. thesis, Programming
Research Group, Oxford University. Available as Technical Monograph PRG94.
Jeremy Gibbons (1993). Upwards and downwards accumulations on trees. In Bird
et al. (1993), pages 122{138. A revised version appears in the Proceedings ofthe Massey Functional Programming Workshop, 1992.
Paul Hoogendijk (1993). Relational programming laws in the Boom hierarchy oftypes. In Bird et al. (1993), pages 163{190.
Johan Jeuring (1989). Deriving algorithms on binary labelled trees. CWI, Amsterdam.
Johan Jeuring (1991). The derivation of hierarchies of algorithms on matrices. In
Moller (1991), pages 9{32.
Yugo Kashiwagi and David S. Wise (1991). Graph algorithms in a lazy functional
programming language. Technical Report 330, Department of Computer Science, Indiana University.

An initial-algebra approach to directed acyclic graphs

22David J. King and John Launchbury (1993). Lazy depth- rst search and linear
graph algorithms in Haskell. Department of Computer Science, University ofGlasgow.
Saunders Mac Lane (1971). Categories for the Working Mathematician. SpringerVerlag.
Lambert Meertens (1986). Algorithmics: Towards programming as a mathematicalactivity. In J. W. de Bakker, M. Hazewinkel, and J. K. Lenstra, editors,
Proc. CWI Symposium on Mathematics and Computer Science, pages 289{
334. North-Holland.
Lambert Meertens (1988). First steps towards the theory of rose trees. CWI,
Amsterdam; IFIP Working Group 2.1 working paper 592 ROM-25.
Paul Molitor (1988). Free net algebras in VLSI-theory. Fundamenta Informaticae,
XI:117{142.
Bernhard Moller and Martin Russling (1993). Shorter paths to graph algorithms.
In Bird et al. (1993), pages 250{268.
B. Moller, editor (1991). IFIP TC2/WG2.1 Working Conference on Constructing
Programs from Speci cations. North-Holland.
Bernard Moller (1993a). Derivation of graph and pointer algorithms. In Bernhard Moller, Helmut Partsch, and Steve Schumann, editors, LNCS 755: IFIP
TC2/WG2.1 State-of-the-Art Report on Formal Program Development, pages
123{160. Springer-Verlag.
Bernhard Moller (1993b). Algebraic calculation of graph and sorting algorithms. In
Dines Bjrner, Manfred Broy, and Igor V. Pottosin, editors, LNCS 735: Formal
Methods in Programming and Their Applications, pages 394{413. SpringerVerlag.
Bob Paige (1994). Comment at IFIP Working Group 2.1 meeting, Renkum.
Ross Paterson (1994). Interpretations of term graphs. Draft. Department of Computing, Imperial College.
David B. Skillicorn (1994). Foundations of Parallel Programming. Cambridge
University Press.
Chris J. Wright (1988). A theory of arrays for program derivation. Transferral
dissertation, Programming Research Group, Oxford University.