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.

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.

Here is a proposed definition for Acyclic.AdjacencyMap:

module Algebra.Graph.Acyclic.AdjacencyMap where

import qualified Algebra.Graph.AdjacencyMap as AM
import qualified Algebra.Graph.AdjacencyMap.Algorithm as AMA

newtype AdjacencyMap a = AAM { 
  fromAcyclic :: AM.AdjacencyMap a
  } deriving (Eq, Ord)

consistent :: Ord a => AdjacencyMap a -> Bool
consistent (AM m) = AM.consistent m && AM.isAcyclic m

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)

Example,

import qualified Algebra.Graph.AdjacencyMap as AM

scc (3 * 1 * 4 * 1 * 5) == fromMaybe empty . toAcyclic $ AM.edges
                             [ (NonEmpty.vertex 3,NonEmpty.vertex 5)
                             , (NonEmpty.vertex 3,NonEmpty.clique1 [1,4,1])
                             , (NonEmpty.clique1 [1,4,1],NonEmpty.vertex 5) ]

Construct from an algebraic graph and a partial order (high priority)

The basic idea of this kind of construction is that if the edges are restricted on the basis of ordering of the elements then it is impossible to construct a back edge and hence it is impossible to construct an acyclic graph. This order can be visualized as somewhat similar to the topological sorting itself.

import Algebra.Graph

type PartialOrder a = a -> a -> Bool

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

Note that the user of this function must provide a valid strict partial order, which satisfies the axioms of irreflexivity and transitivity. If the user violates this, the function may return a cyclic graph.

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.

Construct via Cartesian product (medium priority)

The Cartesian product of two acyclic graphs is acyclic, so let's add box to the API.

Basic graph construction primitives (medium priority)

We could easily support the following graph construction primitives:

empty :: Acyclic.AdjacencyMap a
vertex :: a -> Acyclic.AdjacencyMap a
vertices :: [a] -> Acyclic.AdjacencyMap a
-- D stands for "disjoint"
overlayD :: Acyclic.AdjacencyMap a -> Acyclic.AdjacencyMap b -> Acyclic.AdjacencyMap (Either a b)
connectD :: Acyclic.AdjacencyMap a -> Acyclic.AdjacencyMap b -> Acyclic.AdjacencyMap (Either a b)

I'm not entirely sure how useful these will be in practice, but they are cheap to add, so why not.

Construct via transitive closure (medium priority)

A transitive closure of an acyclic graph is acyclic, so we can support transitiveClousre:

transitiveClosure :: Ord a => Acyclic.AdjacencyMap a -> Acyclic.AdjacencyMap a

Construct an acyclic graph via the "acyclic monad" (low priority)

The priority of this requirement is low, because it seems to work only for graphs that are fixed at compile time. (Andrey: Is this really true?)

(Adithya: I cannot answer the question yet, but seems to be the case.)

Consider that the graph is built by a few monadic computations.

1. Define a singleton vertex. singleton
2. Define an edge. vertexFrom

We have a State monad that tracks the definition sequence of vertices. This definition sequence is used as a PartialOrder while defining the graph. This ordering states that edges are only possible from newer vertices to the older vertices.

For example,

graph = do
  a <- singleton 1           -- order: [1]
  b <- 2 `vertexFrom` [a]    -- order: [1, 2]
  c <- 1 `vertexFrom` [a, b] -- order: [1, 2] -- (c == singleton 1)
  d <- 4 `vertexForm` [c]    -- order: [1, 2]
  return ()

data AcyclicMonad a
instance Monad AcyclicMonad

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

TODO: Add example.

Deconstruct obtaining a topological sort (high priority)

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

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

Using scc for quick and safe construction of acyclic graphs

We could do the following:

shrink :: AdjacencyMap a -> Acyclic.AdjacencyMap a
shrink am = AAM (Map.map (NonEmpty.head . NonEmpty.vertexList1) aam)
  where
    AAM aam = scc am 

This is 1) safe, 2) convenient, 3) complete, i.e. any acyclic graph can be constructed in this way.

However, if the given graph does have a cycle, the result will contain only one vertex from each strongly-connected component, which may cause errors at the user side.

Status

Track the current development at: https://github.com/snowleopard/alga/pull/203.