Algebra.Graph.Acyclic.AdjacencyMap

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module defines the AdjacencyMap data type and for acyclic graphs, as well as associated operations and algorithms. To avoid name clashes with Algebra.Graph.AdjacencyMap, this module can be imported qualified:

import qualified Algebra.Graph.Acyclic.AdjacencyMap as Acyclic

Data structure

data AdjacencyMap a

The AdjacencyMap data type represents an acyclic graph by a map of vertices to their adjacency sets. Although the internal representation allows for cycles, the methods provided by this module cannot be used to construct a graph with cycles.

The Show instance is defined using basic graph construction primitives where possible, falling back to toAcyclic and Algebra.Graph.AdjacencyMap otherwise:

show empty                == "empty"
show (shrink 1)           == "vertex 1"
show (shrink $ 1 + 2)     == "vertices [1,2]"
show (shrink $ 1 * 2)     == "(fromJust . toAcyclic) (edge 1 2)"
show (shrink $ 1 * 2 * 3) == "(fromJust . toAcyclic) (edges [(1,2),(1,3),(2,3)])"
show (shrink $ 1 * 2 + 3) == "(fromJust . toAcyclic) (overlay (vertex 3) (edge 1 2))"

The total order on graphs is defined using size-lexicographic comparison:

• Compare the number of vertices. In case of a tie, continue.
• Compare the sets of vertices. In case of a tie, continue.
• Compare the number of edges. In case of a tie, continue.
• Compare the sets of edges.

Note that the resulting order refines the isSubgraphOf relation:

isSubgraphOf x y ==> x <= y

Instances

Eq a => Eq (AdjacencyMap a)

Defined in Algebra.Graph.Acyclic.AdjacencyMap

Methods

(==) :: AdjacencyMap a -> AdjacencyMap a -> Bool

(/=) :: AdjacencyMap a -> AdjacencyMap a -> Bool

Ord a => Ord (AdjacencyMap a)

Defined in Algebra.Graph.Acyclic.AdjacencyMap

Methods

compare :: AdjacencyMap a -> AdjacencyMap a -> Ordering

(<) :: AdjacencyMap a -> AdjacencyMap a -> Bool

(<=) :: AdjacencyMap a -> AdjacencyMap a -> Bool

(>) :: AdjacencyMap a -> AdjacencyMap a -> Bool

(>=) :: AdjacencyMap a -> AdjacencyMap a -> Bool

max :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

min :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

(Ord a, Show a) => Show (AdjacencyMap a)

Defined in Algebra.Graph.Acyclic.AdjacencyMap

Methods

showsPrec :: Int -> AdjacencyMap a -> ShowS

show :: AdjacencyMap a -> String

showList :: [AdjacencyMap a] -> ShowS

fromAcyclic :: AdjacencyMap a -> AdjacencyMap a

Extract the underlying acyclic Algebra.Graph.AdjacencyMap. Complexity: O(1) time and memory.

fromAcyclic empty                == empty
fromAcyclic . vertex             == vertex
fromAcyclic (shrink $ 1 * 3 + 2) == 1 * 3 + 2
vertexCount . fromAcyclic        == vertexCount
edgeCount   . fromAcyclic        == edgeCount
isAcyclic   . fromAcyclic        == const True

Basic graph construction primitives

empty :: AdjacencyMap a

Construct the empty graph.

isEmpty     empty == True
hasVertex x empty == False
vertexCount empty == 0
edgeCount   empty == 0

vertex :: a -> AdjacencyMap a

Construct the graph comprising a single isolated vertex.

isEmpty     (vertex x) == False
hasVertex x (vertex y) == (x == y)
vertexCount (vertex x) == 1
edgeCount   (vertex x) == 0

vertices :: Ord a => [a] -> AdjacencyMap a

Construct the graph comprising a given list of isolated vertices. Complexity: O(L * log(L)) time and O(L) memory, where L is the length of the given list.

vertices []            == empty
vertices [x]           == vertex x
hasVertex x . vertices == elem x
vertexCount . vertices == length . nub
vertexSet   . vertices == Set.fromList

union :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (Either a b)

Construct the disjoint union of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

vertexSet (union x y) == Set.unions [ Set.map Left  (vertexSet x)
                                    , Set.map Right (vertexSet y) ]

edgeSet   (union x y) == Set.unions [ Set.map (bimap Left  Left ) (edgeSet x)
                                    , Set.map (bimap Right Right) (edgeSet y) ]

join :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (Either a b)

Construct the join of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

vertexSet (join x y) == Set.unions [ Set.map Left  (vertexSet x)
                                   , Set.map Right (vertexSet y) ]

edgeSet   (join x y) == Set.unions [ Set.map (bimap Left  Left ) (edgeSet x)
                                   , Set.map (bimap Right Right) (edgeSet y)
                                   , Set.map (bimap Left  Right) (Set.cartesianProduct (vertexSet x) (vertexSet y)) ]

Relations on graphs

isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool

The isSubgraphOf function takes two graphs and returns True if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.

isSubgraphOf empty        x                     ==  True
isSubgraphOf (vertex x)   empty                 ==  False
isSubgraphOf (induce p x) x                     ==  True
isSubgraphOf x            (transitiveClosure x) ==  True
isSubgraphOf x y                                ==> x <= y

Graph properties

isEmpty :: AdjacencyMap a -> Bool

Check if a graph is empty. Complexity: O(1) time.

isEmpty empty                             == True
isEmpty (vertex x)                        == False
isEmpty (removeVertex x $ vertex x)       == True
isEmpty (removeEdge 1 2 $ shrink $ 1 * 2) == False

hasVertex :: Ord a => a -> AdjacencyMap a -> Bool

Check if a graph contains a given vertex. Complexity: O(log(n)) time.

hasVertex x empty            == False
hasVertex x (vertex y)       == (x == y)
hasVertex x . removeVertex x == const False

hasEdge :: Ord a => a -> a -> AdjacencyMap a -> Bool

Check if a graph contains a given edge. Complexity: O(log(n)) time.

hasEdge x y empty            == False
hasEdge x y (vertex z)       == False
hasEdge 1 2 (shrink $ 1 * 2) == True
hasEdge x y . removeEdge x y == const False
hasEdge x y                  == elem (x,y) . edgeList

vertexCount :: AdjacencyMap a -> Int

The number of vertices in a graph. Complexity: O(1) time.

vertexCount empty             ==  0
vertexCount (vertex x)        ==  1
vertexCount                   ==  length . vertexList
vertexCount x < vertexCount y ==> x < y

edgeCount :: AdjacencyMap a -> Int

The number of edges in a graph. Complexity: O(n) time.

edgeCount empty            == 0
edgeCount (vertex x)       == 0
edgeCount (shrink $ 1 * 2) == 1
edgeCount                  == length . edgeList

vertexList :: AdjacencyMap a -> [a]

The sorted list of vertices of a given graph. Complexity: O(n) time and memory.

vertexList empty      == []
vertexList (vertex x) == [x]
vertexList . vertices == nub . sort

edgeList :: AdjacencyMap a -> [(a, a)]

The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.

edgeList empty            == []
edgeList (vertex x)       == []
edgeList (shrink $ 2 * 1) == [(2,1)]
edgeList . transpose      == sort . map swap . edgeList

adjacencyList :: AdjacencyMap a -> [(a, [a])]

The sorted adjacency list of a graph. Complexity: O(n + m) time and memory.

adjacencyList empty            == []
adjacencyList (vertex x)       == [(x, [])]
adjacencyList (shrink $ 1 * 2) == [(1, [2]), (2, [])]

vertexSet :: AdjacencyMap a -> Set a

The set of vertices of a given graph. Complexity: O(n) time and memory.

vertexSet empty      == Set.empty
vertexSet . vertex   == Set.singleton
vertexSet . vertices == Set.fromList

edgeSet :: Eq a => AdjacencyMap a -> Set (a, a)

The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory.

edgeSet empty            == Set.empty
edgeSet (vertex x)       == Set.empty
edgeSet (shrink $ 1 * 2) == Set.singleton (1,2)

preSet :: Ord a => a -> AdjacencyMap a -> Set a

The preset of an element x is the set of its direct predecessors. Complexity: O(n * log(n)) time and O(n) memory.

preSet x empty            == Set.empty
preSet x (vertex x)       == Set.empty
preSet 1 (shrink $ 1 * 2) == Set.empty
preSet 2 (shrink $ 1 * 2) == Set.fromList [1]
Set.member x . preSet x   == const False

postSet :: Ord a => a -> AdjacencyMap a -> Set a

The postset of a vertex is the set of its direct successors. Complexity: O(log(n)) time and O(1) memory.

postSet x empty            == Set.empty
postSet x (vertex x)       == Set.empty
postSet 1 (shrink $ 1 * 2) == Set.fromList [2]
postSet 2 (shrink $ 1 * 2) == Set.empty
Set.member x . postSet x   == const False

Graph transformation

removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a

Remove a vertex from a given acyclic graph. Complexity: O(n*log(n)) time.

removeVertex x (vertex x)       == empty
removeVertex 1 (vertex 2)       == vertex 2
removeVertex 1 (shrink $ 1 * 2) == vertex 2
removeVertex x . removeVertex x == removeVertex x

removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a

Remove an edge from a given acyclic graph. Complexity: O(log(n)) time.

removeEdge 1 2 (shrink $ 1 * 2)     == vertices [1,2]
removeEdge x y . removeEdge x y     == removeEdge x y
removeEdge x y . removeVertex x     == removeVertex x
removeEdge 1 2 (shrink $ 1 * 2 * 3) == shrink ((1 + 2) * 3)

transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a

Transpose a given acyclic graph. Complexity: O(m * log(n)) time, O(n + m) memory.

transpose empty       == empty
transpose (vertex x)  == vertex x
transpose . transpose == id
edgeList . transpose  == sort . map swap . edgeList

induce :: (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a

Construct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(n + m) time, assuming that the predicate takes constant time.

induce (const True ) x      == x
induce (const False) x      == empty
induce (/= x)               == removeVertex x
induce p . induce q         == induce (x -> p x && q x)
isSubgraphOf (induce p x) x == True

induceJust :: Ord a => AdjacencyMap (Maybe a) -> AdjacencyMap a

Construct the induced subgraph of a given graph by removing the vertices that are Nothing. Complexity: O(n + m) time.

induceJust (vertex Nothing) == empty
induceJust . vertex . Just  == vertex

Graph composition

box :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (a, b)

Compute the Cartesian product of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

edgeList (box (shrink $ 1 * 2) (shrink $ 10 * 20)) == [ ((1,10), (1,20))
                                                      , ((1,10), (2,10))
                                                      , ((1,20), (2,20))
                                                      , ((2,10), (2,20)) ]

Up to isomorphism between the resulting vertex types, this operation is commutative and associative, has singleton graphs as identities and empty as the annihilating zero. Below ~~ stands for equality up to an isomorphism, e.g. (x, ()) ~~ x.

box x y               ~~ box y x
box x (box y z)       ~~ box (box x y) z
box x (vertex ())     ~~ x
box x empty           ~~ empty
transpose   (box x y) == box (transpose x) (transpose y)
vertexCount (box x y) == vertexCount x * vertexCount y
edgeCount   (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y

Relational operations

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

Compute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time.

transitiveClosure empty                    == empty
transitiveClosure (vertex x)               == vertex x
transitiveClosure (shrink $ 1 * 2 + 2 * 3) == shrink (1 * 2 + 1 * 3 + 2 * 3)
transitiveClosure . transitiveClosure      == transitiveClosure

Algorithms

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

Compute a topological sort of an acyclic graph.

topSort empty                          == []
topSort (vertex x)                     == [x]
topSort (shrink $ 1 * (2 + 4) + 3 * 4) == [1, 2, 3, 4]
topSort (join x y)                     == fmap Left (topSort x) ++ fmap Right (topSort y)
Right . topSort                        == topSort . fromAcyclic

scc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a)

Compute the acyclic condensation of a graph, where each vertex corresponds to a strongly-connected component of the original graph. Note that component graphs are non-empty, and are therefore of type Algebra.Graph.NonEmpty.AdjacencyMap.

           scc empty               == empty
           scc (vertex x)          == vertex (NonEmpty.vertex x)
           scc (edge 1 1)          == vertex (NonEmpty.edge 1 1)
edgeList $ scc (edge 1 2)          == [ (NonEmpty.vertex 1       , NonEmpty.vertex 2       ) ]
edgeList $ scc (3 * 1 * 4 * 1 * 5) == [ (NonEmpty.vertex 3       , NonEmpty.vertex 5       )
                                      , (NonEmpty.vertex 3       , NonEmpty.clique1 [1,4,1])
                                      , (NonEmpty.clique1 [1,4,1], NonEmpty.vertex 5       ) ]

Conversion to acyclic graphs

toAcyclic :: Ord a => AdjacencyMap a -> Maybe (AdjacencyMap a)

Construct an acyclic graph from a given adjacency map, or return Nothing if the input contains cycles.

toAcyclic (path    [1,2,3]) == Just (shrink $ 1 * 2 + 2 * 3)
toAcyclic (clique  [3,2,1]) == Just (transpose (shrink $ 1 * 2 * 3))
toAcyclic (circuit [1,2,3]) == Nothing
toAcyclic . fromAcyclic     == Just

toAcyclicOrd :: Ord a => AdjacencyMap a -> AdjacencyMap a

Construct an acyclic graph from a given adjacency map, keeping only edges (x,y) where x < y according to the supplied Ord a instance.

toAcyclicOrd empty       == empty
toAcyclicOrd . vertex    == vertex
toAcyclicOrd (1 + 2)     == shrink (1 + 2)
toAcyclicOrd (1 * 2)     == shrink (1 * 2)
toAcyclicOrd (2 * 1)     == shrink (1 + 2)
toAcyclicOrd (1 * 2 * 1) == shrink (1 * 2)
toAcyclicOrd (1 * 2 * 3) == shrink (1 * 2 * 3)

shrink :: Ord a => AdjacencyMap a -> AdjacencyMap a

Construct an acyclic graph from a given adjacency map using scc. If the graph is acyclic, it is returned as is. If the graph is cyclic, then a representative for every strongly connected component in its condensation graph is chosen and these representatives are used to build an acyclic graph.

shrink . vertex      == vertex
shrink . vertices    == vertices
shrink . fromAcyclic == id

Miscellaneous

consistent :: Ord a => AdjacencyMap a -> Bool

Check if the internal representation of an acyclic graph is consistent, i.e. that all edges refer to existing vertices and the graph is acyclic. It should be impossible to create an inconsistent AdjacencyMap.

consistent empty                 == True
consistent (vertex x)            == True
consistent (vertices xs)         == True
consistent (union x y)           == True
consistent (join x y)            == True
consistent (transpose x)         == True
consistent (box x y)             == True
consistent (transitiveClosure x) == True
consistent (scc x)               == True
fmap consistent (toAcyclic x)    /= False
consistent (toAcyclicOrd x)      == True