algebraic-graphs-0.5: A library for algebraic graph construction and transformation

Copyright(c) Andrey Mokhov 2016-2019
LicenseMIT (see the file LICENSE)
Maintainerandrey.mokhov@gmail.com
Stabilityexperimental
Safe HaskellNone
LanguageHaskell2010

Algebra.Graph.Acyclic.AdjacencyMap

Contents

Description

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
Synopsis

Data structure

data AdjacencyMap a Source #

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

fromAcyclic :: AdjacencyMap a -> AdjacencyMap a Source #

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 Source #

Construct the empty graph. Complexity: O(1) time and memory.

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

vertex :: a -> AdjacencyMap a Source #

Construct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.

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

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

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) Source #

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) Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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] Source #

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)] Source #

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])] Source #

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

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

vertexSet :: AdjacencyMap a -> Set a Source #

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) Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 O(1) to be evaluated.

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 Source #

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) Source #

Compute the Cartesian product of graphs. Complexity: O(n * m * log(n)^2) time.

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 an 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 the 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 Source #

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] Source #

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) Source #

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) Source #

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 Source #

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 Source #

Construct an acyclic graph from a given adjacency map using scc. If the graph is acyclic in nature, the same graph is returned as an acyclic graph. If the graph is cyclic, then a representative for every strongly connected component in its condensation graph is chosen an 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 Source #

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