Acyclic graphs

This page is for discussing and tracking the ongoing development of support for acyclic graphs.

Motivation

Acyclic graphs are both common and heavily used in dependency management. Improvements in this area would therefore directly benefit downstream packages like build, plutus or aura, as well as a few commercial users of the library.

In particular, the result should be a type-safe abstraction, that makes it easier to work with algorithms like scc or topSort as has been remarked in some issues.

There will be question in the document, with the actual question prepended by Question:. The questions are discussion topics and anybody is welcome to answer (ideally by opening an issue to continue the discussion).

Requirements

An abstract data type for acyclic graphs should first be provided in the module Algebra.Graph.Acyclic.AdjacencyMap designed to be imported qualified as Acyclic. We will therefore refer to the data type as Acyclic.AdjacencyMap in this page.

General adjacency maps will be referred to as AdjacencyMap and non-empty adjacency maps as NonEmpty.AdjacencyMap.

Construct an acyclic graph via the SCC algorithm

The SCC algorithm guarantees the absence of cycles in the component graph, so it is a natural choice for an acyclic graph construction primitive.

scc :: Ord a => AdjacencyMap a -> Acyclic.AdjacencyMap (NonEmpty.AdjacencyMap a)

TODO: Add small example.

Construct an acyclic graph via the "acyclic monad"

The basic idea in this method is to incrementally build the graph The safety comes from the fact that one can only define edges only when the vertex is being defined. The directed edges can only be towards vertices which have been defined previously. One can notice an implicit ordering on vertices in this case. The structure of the graph is the main property in consideration here. Any kind of generic implementation will be treated as vertex labels.

For eg,

graph = do
  x1 <- vertex "x1"
  x2 <- vertex "x1"
  return ()

In the example above x1 and x2 are not the same vertices. They are 2 different vertices with the same label.

See: https://gist.github.com/adithyaov/f87b5b496fd88ef91cfe438dfaf3a955

Question: Is this kind of an implementation acceptable?

Question: There no type checking here and we only care about the structure of the graph. What is the point of having a generic implementation?

data AcyclicMonad a
instance Monad AcyclicMonad

runAcyclicMonad :: Ord a => AcyclicMonad a -> Acyclic.AdjacencyMap a

TODO: Add example.

Construct from an algebraic graph

TODO: Add a description of the idea.

type PartialOrder a = a -> a -> Bool

fromGraph :: Ord a => PartialOrder a -> Graph a -> Acyclic.AdjacencyMap a

Example:

Here is a simple example where we do have a partial order in advance:

• Every object file depends only on C source files: file.c < file.o.
• Every executable depends only on object files: file.o < file.exe.

Here we could just use < from the derived Ord instance for the extension data type:

data Extension = C | O | Exe deriving (Eq, Ord)

type File = (FilePath, Extension)

partialOrder :: PartialOrder File
partialOrder (_, x) (_, y) = x < y

I find this a convincing example, where we can have a type-safe construction of an acyclic graph thanks to some domain knowledge.

Deconstruct obtaining a topological sort

Since the graph is acyclic, we are guaranteed that it can be topologically sorted:

topSort :: Ord a => Acyclic.AdjacencyMap a -> [a]

Status

A first prototype available here: https://github.com/snowleopard/alga/pull/199.