Compositional Graphs
August 2002

Introduction

In many applications, graphs are a natural representation for the structure of a problem domain. Since functional languages supports only (tree-structured) algebraic datatypes, there are various ways to represent graphs in declarative languages. This page describes a representation of graphs in the functional logic language Curry. The proposed representation is compositional as lists or tree structures are. This property makes the representation useful for many application domains, like graphical user interfaces or web programming.

Application

Simple graphs are represented by an algebraic type as follows: 

    data Graph = Graph [Node] [Edge]
    data Node = Node Int
    data Edge = Edge Int Int
Edges consist (at a minimum) of a source and a target node which can be uniquely identified by, e.g., integers.

Graph instances so defined cannot be composed. If g is a graph and joinGraphs is a function that composes two graphs by joining their nodes and edges, respectively, the expression (joinGraphs g1 g1) produces a non-intended graph containing supposedly different nodes with identical numbers. The proposed solution makes use of logical variables which enable the composition of graphs similar to other data structures.

Design

The definition of the type Graph is unchanged. In an instance, the nodes are coded as logical variables, e.g.: 

    g = Graph [Node n1, Node n2, Node n3]
              [Edge n1 n2, Edge n3 n2, Edge n1 n3, Edge n3 n3]
       where n1,n2,n3 free
Since n1, n2 and n3 are local variables, g becomes compositional as a list or a tree would be. For example, (joinGraphs g g) is a graph with six different nodes.

Implementation

Graph.curry (library)
examples.curry (examples of use of the library)
thompson.curry (NFA construction for accepting regular expressions)

References

The following paper, in PDF format, describes in detail the technique addressed by this page.


Work supported in part by the NSF
grants INT-9981317 and CCR-0110496 		Contact antoy@cs.pdx.edu
Last updated: Mon Aug 19 16:23:40 PDT 2002