Modulealgebraic-graphs-0.8Haskell2010

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

1 type
32 values

Packagealgebraic-graphs-0.8
Exports33
LanguageHaskell2010
LicenceMIT
SourceAdjacencyMap.hs

Data structure

2 declarations

newtypenewtype 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

Instances3Eq, Ord, Show

Eq a => Eq (AdjacencyMap a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Acyclic.AdjacencyMap
Ord a => Ord (AdjacencyMap a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Acyclic.AdjacencyMap
(Ord a, Show a) => Show (AdjacencyMap a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Acyclic.AdjacencyMap

valuefromAcyclic :: 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

5 declarations

valueempty :: AdjacencyMap a

Construct the empty graph.

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

valuevertex :: 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

valuevertices :: 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

valueunion

:: (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) ]

valuejoin

:: (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

1 declaration

valueisSubgraphOf :: 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

12 declarations

valueisEmpty :: 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

valuehasVertex :: 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

valuehasEdge :: 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

valuevertexCount :: 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

valueedgeCount :: 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

valuevertexList :: 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

valueedgeList :: 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

valueadjacencyList :: 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, [])]

valuevertexSet :: 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

valueedgeSet :: 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)

valuepreSet :: 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

valuepostSet :: 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

5 declarations

valueremoveVertex :: 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

valueremoveEdge :: 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)

valuetranspose :: 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

valueinduce :: (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

valueinduceJust :: 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

1 declaration

valuebox

:: (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

1 declaration

valuetransitiveClosure :: 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

2 declarations

valuetopSort :: 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

valuescc :: 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.NonEmpty.clique1 [1,4,1])
                                      , (NonEmpty.NonEmpty.clique1 [1,4,1], NonEmpty.vertex 5       ) ]

Conversion to acyclic graphs

3 declarations

valuetoAcyclic :: 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

valuetoAcyclicOrd :: 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)

valueshrink :: 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

1 declaration

valueconsistent :: 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