Algebra.Graph.Labelled.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 for edge-labelled graphs, as well as associated operations and algorithms. AdjacencyMap is an instance of the Graph type class, which can be used for polymorphic graph construction and manipulation.

Data structure

data AdjacencyMap e a

Edge-labelled graphs, where the type variable e stands for edge labels. For example, AdjacencyMap Bool a is isomorphic to unlabelled graphs defined in the top-level module Algebra.Graph.AdjacencyMap, where False and True denote the lack of and the existence of an unlabelled edge, respectively.

Instances

(Eq a, Eq e) => Eq (AdjacencyMap e a)

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

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

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

(Eq e, Dioid e, Num a, Ord a) => Num (AdjacencyMap e a)

Note: this does not satisfy the usual ring laws; see AdjacencyMap for more details.

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

(+) :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

(-) :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

(*) :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

negate :: AdjacencyMap e a -> AdjacencyMap e a

abs :: AdjacencyMap e a -> AdjacencyMap e a

signum :: AdjacencyMap e a -> AdjacencyMap e a

fromInteger :: Integer -> AdjacencyMap e a

(Ord e, Monoid e, Ord a) => Ord (AdjacencyMap e a)

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

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

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

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

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

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

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

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

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

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

showsPrec :: Int -> AdjacencyMap e a -> ShowS

show :: AdjacencyMap e a -> String

showList :: [AdjacencyMap e a] -> ShowS

IsString a => IsString (AdjacencyMap e a)

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

fromString :: String -> AdjacencyMap e a

Generic (AdjacencyMap e a)

Defined in Algebra.Graph.Labelled.AdjacencyMap

Associated Types

type Rep (AdjacencyMap e a) :: Type -> Type

Methods

from :: AdjacencyMap e a -> Rep (AdjacencyMap e a) x

to :: Rep (AdjacencyMap e a) x -> AdjacencyMap e a

(Ord a, Eq e, Monoid e) => Semigroup (AdjacencyMap e a)

Defined via overlay.

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

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

sconcat :: NonEmpty (AdjacencyMap e a) -> AdjacencyMap e a

stimes :: Integral b => b -> AdjacencyMap e a -> AdjacencyMap e a

(Ord a, Eq e, Monoid e) => Monoid (AdjacencyMap e a)

Defined via overlay and empty.

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

mempty :: AdjacencyMap e a

mappend :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

mconcat :: [AdjacencyMap e a] -> AdjacencyMap e a

(NFData a, NFData e) => NFData (AdjacencyMap e a)

Defined in Algebra.Graph.Labelled.AdjacencyMap

Methods

rnf :: AdjacencyMap e a -> ()

(Eq e, Monoid e, Ord a) => ToGraph (AdjacencyMap e a)

See Algebra.Graph.Labelled.AdjacencyMap.

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (AdjacencyMap e a)

Methods

toGraph :: AdjacencyMap e a -> Graph (ToVertex (AdjacencyMap e a))

foldg :: r -> (ToVertex (AdjacencyMap e a) -> r) -> (r -> r -> r) -> (r -> r -> r) -> AdjacencyMap e a -> r

isEmpty :: AdjacencyMap e a -> Bool

hasVertex :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Bool

hasEdge :: ToVertex (AdjacencyMap e a) -> ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Bool

vertexCount :: AdjacencyMap e a -> Int

edgeCount :: AdjacencyMap e a -> Int

vertexList :: AdjacencyMap e a -> [ToVertex (AdjacencyMap e a)]

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

vertexSet :: AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a))

vertexIntSet :: AdjacencyMap e a -> IntSet

edgeSet :: AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a), ToVertex (AdjacencyMap e a))

preSet :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a))

preIntSet :: Int -> AdjacencyMap e a -> IntSet

postSet :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> Set (ToVertex (AdjacencyMap e a))

postIntSet :: Int -> AdjacencyMap e a -> IntSet

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

dfsForest :: AdjacencyMap e a -> Forest (ToVertex (AdjacencyMap e a))

dfsForestFrom :: [ToVertex (AdjacencyMap e a)] -> AdjacencyMap e a -> Forest (ToVertex (AdjacencyMap e a))

dfs :: [ToVertex (AdjacencyMap e a)] -> AdjacencyMap e a -> [ToVertex (AdjacencyMap e a)]

reachable :: ToVertex (AdjacencyMap e a) -> AdjacencyMap e a -> [ToVertex (AdjacencyMap e a)]

topSort :: AdjacencyMap e a -> Either (Cycle (ToVertex (AdjacencyMap e a))) [ToVertex (AdjacencyMap e a)]

isAcyclic :: AdjacencyMap e a -> Bool

toAdjacencyMap :: AdjacencyMap e a -> AdjacencyMap0 (ToVertex (AdjacencyMap e a))

toAdjacencyMapTranspose :: AdjacencyMap e a -> AdjacencyMap0 (ToVertex (AdjacencyMap e a))

toAdjacencyIntMap :: AdjacencyMap e a -> AdjacencyIntMap

toAdjacencyIntMapTranspose :: AdjacencyMap e a -> AdjacencyIntMap

isDfsForestOf :: Forest (ToVertex (AdjacencyMap e a)) -> AdjacencyMap e a -> Bool

isTopSortOf :: [ToVertex (AdjacencyMap e a)] -> AdjacencyMap e a -> Bool

(Dioid e, Eq e, Ord a) => Graph (AdjacencyMap e a)

Defined in Algebra.Graph.Class

Associated Types

type Vertex (AdjacencyMap e a)

Methods

empty :: AdjacencyMap e a

vertex :: Vertex (AdjacencyMap e a) -> AdjacencyMap e a

overlay :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

connect :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

type Rep (AdjacencyMap e a)

Defined in Algebra.Graph.Labelled.AdjacencyMap

type Rep (AdjacencyMap e a) = D1 ('MetaData "AdjacencyMap" "Algebra.Graph.Labelled.AdjacencyMap" "algebraic-graphs-0.6.1-1GHbchCaOhb8Cb1GtyPsoY" 'True) (C1 ('MetaCons "AM" 'PrefixI 'True) (S1 ('MetaSel ('Just "adjacencyMap") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map a (Map a e)))))

type ToVertex (AdjacencyMap e a)

Defined in Algebra.Graph.ToGraph

type ToVertex (AdjacencyMap e a) = a

type Vertex (AdjacencyMap e a)

Defined in Algebra.Graph.Class

type Vertex (AdjacencyMap e a) = a

adjacencyMap :: AdjacencyMap e a -> Map a (Map a e)

The adjacency map of an edge-labelled graph: each vertex is associated with a map from its direct successors to the corresponding edge labels.

Basic graph construction primitives

empty :: AdjacencyMap e a

Construct the empty graph.

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

vertex :: a -> AdjacencyMap e 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

edge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> AdjacencyMap e a

Construct the graph comprising a single edge.

edge e    x y              == connect e (vertex x) (vertex y)
edge zero x y              == vertices [x,y]
hasEdge   x y (edge e x y) == (e /= zero)
edgeLabel x y (edge e x y) == e
edgeCount     (edge e x y) == if e == zero then 0 else 1
vertexCount   (edge e 1 1) == 1
vertexCount   (edge e 1 2) == 2

(-<) :: a -> e -> (a, e) infixl 5

The left-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges.

x -<e>- y == edge e x y

(>-) :: (Eq e, Monoid e, Ord a) => (a, e) -> a -> AdjacencyMap e a infixl 5

The right-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges.

x -<e>- y == edge e x y

overlay :: (Eq e, Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

Overlay two graphs. This is a commutative, associative and idempotent operation with the identity empty. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

isEmpty     (overlay x y) == isEmpty   x   && isEmpty   y
hasVertex z (overlay x y) == hasVertex z x || hasVertex z y
vertexCount (overlay x y) >= vertexCount x
vertexCount (overlay x y) <= vertexCount x + vertexCount y
edgeCount   (overlay x y) >= edgeCount x
edgeCount   (overlay x y) <= edgeCount x   + edgeCount y
vertexCount (overlay 1 2) == 2
edgeCount   (overlay 1 2) == 0

Note: overlay composes edges in parallel using the operator <+> with zero acting as the identity:

edgeLabel x y $ overlay (edge e x y) (edge zero x y) == e
edgeLabel x y $ overlay (edge e x y) (edge f    x y) == e <+> f

Furthermore, when applied to transitive graphs, overlay composes edges in sequence using the operator <.> with one acting as the identity:

edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge one y z)) == e
edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge f   y z)) == e <.> f

connect :: (Eq e, Monoid e, Ord a) => e -> AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a

Connect two graphs with edges labelled by a given label. When applied to the same labels, this is an associative operation with the identity empty, which distributes over overlay and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).

isEmpty     (connect e x y) == isEmpty   x   && isEmpty   y
hasVertex z (connect e x y) == hasVertex z x || hasVertex z y
vertexCount (connect e x y) >= vertexCount x
vertexCount (connect e x y) <= vertexCount x + vertexCount y
edgeCount   (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
vertexCount (connect e 1 2) == 2
edgeCount   (connect e 1 2) == if e == zero then 0 else 1

vertices :: Ord a => [a] -> AdjacencyMap e 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
vertices               == overlays . map vertex
hasVertex x . vertices == elem x
vertexCount . vertices == length . nub
vertexSet   . vertices == Set.fromList

edges :: (Eq e, Monoid e, Ord a) => [(e, a, a)] -> AdjacencyMap e a

Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

edges []        == empty
edges [(e,x,y)] == edge e x y
edges           == overlays . map (\(e, x, y) -> edge e x y)

overlays :: (Eq e, Monoid e, Ord a) => [AdjacencyMap e a] -> AdjacencyMap e a

Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

overlays []        == empty
overlays [x]       == x
overlays [x,y]     == overlay x y
overlays           == foldr overlay empty
isEmpty . overlays == all isEmpty

fromAdjacencyMaps :: (Eq e, Monoid e, Ord a) => [(a, Map a e)] -> AdjacencyMap e a

Construct a graph from a list of adjacency sets. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

fromAdjacencyMaps []                                  == empty
fromAdjacencyMaps [(x, Map.empty)]                    == vertex x
fromAdjacencyMaps [(x, Map.singleton y e)]            == if e == zero then vertices [x,y] else edge e x y
overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs ++ ys)

Relations on graphs

isSubgraphOf :: (Eq e, Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a -> Bool

The isSubgraphOf function takes two graphs and returns True if the first graph is a subgraph of the second. Complexity: O(s + m * log(m)) time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.

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

Graph properties

isEmpty :: AdjacencyMap e a -> Bool

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

isEmpty empty                         == True
isEmpty (overlay empty empty)         == True
isEmpty (vertex x)                    == False
isEmpty (removeVertex x $ vertex x)   == True
isEmpty (removeEdge x y $ edge e x y) == False

hasVertex :: Ord a => a -> AdjacencyMap e 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 e 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 x y (edge e x y)     == (e /= zero)
hasEdge x y . removeEdge x y == const False
hasEdge x y                  == not . null . filter (\(_,ex,ey) -> ex == x && ey == y) . edgeList

edgeLabel :: (Monoid e, Ord a) => a -> a -> AdjacencyMap e a -> e

Extract the label of a specified edge in a graph. Complexity: O(log(n)) time.

edgeLabel x y empty         == zero
edgeLabel x y (vertex z)    == zero
edgeLabel x y (edge e x y)  == e
edgeLabel s t (overlay x y) == edgeLabel s t x + edgeLabel s t y

vertexCount :: AdjacencyMap e 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 e a -> Int

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

edgeCount empty        == 0
edgeCount (vertex x)   == 0
edgeCount (edge e x y) == if e == zero then 0 else 1
edgeCount              == length . edgeList

vertexList :: AdjacencyMap e 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 e a -> [(e, a, a)]

The list of edges of a graph, sorted lexicographically with respect to pairs of connected vertices (i.e. edge-labels are ignored when sorting). Complexity: O(n + m) time and O(m) memory.

edgeList empty        == []
edgeList (vertex x)   == []
edgeList (edge e x y) == if e == zero then [] else [(e,x,y)]

vertexSet :: AdjacencyMap e 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, Eq e) => AdjacencyMap e a -> Set (e, a, a)

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

edgeSet empty        == Set.empty
edgeSet (vertex x)   == Set.empty
edgeSet (edge e x y) == if e == zero then Set.empty else Set.singleton (e,x,y)

preSet :: Ord a => a -> AdjacencyMap e 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 (edge e 1 2) == Set.empty
preSet y (edge e x y) == if e == zero then Set.empty else Set.fromList [x]

postSet :: Ord a => a -> AdjacencyMap e 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 x (edge e x y) == if e == zero then Set.empty else Set.fromList [y]
postSet 2 (edge e 1 2) == Set.empty

skeleton :: Ord a => AdjacencyMap e a -> AdjacencyMap a

Convert a graph to the corresponding unlabelled AdjacencyMap by forgetting labels on all non-zero edges. Complexity: O((n + m) * log(n)) time and memory.

hasEdge x y == hasEdge x y . skeleton

Graph transformation

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

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

removeVertex x (vertex x)       == empty
removeVertex 1 (vertex 2)       == vertex 2
removeVertex x (edge e x x)     == empty
removeVertex 1 (edge e 1 2)     == vertex 2
removeVertex x . removeVertex x == removeVertex x

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

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

removeEdge x y (edge e x y)     == vertices [x,y]
removeEdge x y . removeEdge x y == removeEdge x y
removeEdge x y . removeVertex x == removeVertex x
removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2

replaceVertex :: (Eq e, Monoid e, Ord a) => a -> a -> AdjacencyMap e a -> AdjacencyMap e a

The function replaceVertex x y replaces vertex x with vertex y in a given AdjacencyMap. If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time.

replaceVertex x x            == id
replaceVertex x y (vertex x) == vertex y
replaceVertex x y            == gmap (\v -> if v == x then y else v)

replaceEdge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> AdjacencyMap e a -> AdjacencyMap e a

Replace an edge from a given graph. If it doesn't exist, it will be created. Complexity: O(log(n)) time.

replaceEdge e x y z                 == overlay (removeEdge x y z) (edge e x y)
replaceEdge e x y (edge f x y)      == edge e x y
edgeLabel x y (replaceEdge e x y z) == e

transpose :: (Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a

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

transpose empty        == empty
transpose (vertex x)   == vertex x
transpose (edge e x y) == edge e y x
transpose . transpose  == id

gmap :: (Eq e, Monoid e, Ord a, Ord b) => (a -> b) -> AdjacencyMap e a -> AdjacencyMap e b

Transform a graph by applying a function to each of its vertices. This is similar to Functor's fmap but can be used with non-fully-parametric AdjacencyMap. Complexity: O((n + m) * log(n)) time.

gmap f empty        == empty
gmap f (vertex x)   == vertex (f x)
gmap f (edge e x y) == edge e (f x) (f y)
gmap id             == id
gmap f . gmap g     == gmap (f . g)

emap :: (Eq f, Monoid f) => (e -> f) -> AdjacencyMap e a -> AdjacencyMap f a

Transform a graph by applying a function h to each of its edge labels. Complexity: O((n + m) * log(n)) time.

The function h is required to be a homomorphism on the underlying type of labels e. At the very least it must preserve zero and <+>:

h zero      == zero
h x <+> h y == h (x <+> y)

If e is also a semiring, then h must also preserve the multiplicative structure:

h one       == one
h x <.> h y == h (x <.> y)

If the above requirements hold, then the implementation provides the following guarantees.

emap h empty           == empty
emap h (vertex x)      == vertex x
emap h (edge e x y)    == edge (h e) x y
emap h (overlay x y)   == overlay (emap h x) (emap h y)
emap h (connect e x y) == connect (h e) (emap h x) (emap h y)
emap id                == id
emap g . emap h        == emap (g . h)

induce :: (a -> Bool) -> AdjacencyMap e a -> AdjacencyMap e 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 e (Maybe a) -> AdjacencyMap e 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 (edge (Just x) Nothing)                        == vertex x
induceJust . gmap Just                                    == id
induceJust . gmap (\x -> if p x then Just x else Nothing) == induce p

Relational operations

closure :: (Eq e, Ord a, StarSemiring e) => AdjacencyMap e a -> AdjacencyMap e a

Compute the reflexive and transitive closure of a graph over the underlying star semiring using the Warshall-Floyd-Kleene algorithm.

closure empty         == empty
closure (vertex x)    == edge one x x
closure (edge e x x)  == edge one x x
closure (edge e x y)  == edges [(one,x,x), (e,x,y), (one,y,y)]
closure               == reflexiveClosure . transitiveClosure
closure               == transitiveClosure . reflexiveClosure
closure . closure     == closure
postSet x (closure y) == Set.fromList (reachable x y)

reflexiveClosure :: (Ord a, Semiring e) => AdjacencyMap e a -> AdjacencyMap e a

Compute the reflexive closure of a graph over the underlying semiring by adding a self-loop of weight one to every vertex. Complexity: O(n * log(n)) time.

reflexiveClosure empty              == empty
reflexiveClosure (vertex x)         == edge one x x
reflexiveClosure (edge e x x)       == edge one x x
reflexiveClosure (edge e x y)       == edges [(one,x,x), (e,x,y), (one,y,y)]
reflexiveClosure . reflexiveClosure == reflexiveClosure

symmetricClosure :: (Eq e, Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a

Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.

symmetricClosure empty              == empty
symmetricClosure (vertex x)         == vertex x
symmetricClosure (edge e x y)       == edges [(e,x,y), (e,y,x)]
symmetricClosure x                  == overlay x (transpose x)
symmetricClosure . symmetricClosure == symmetricClosure

transitiveClosure :: (Eq e, Ord a, StarSemiring e) => AdjacencyMap e a -> AdjacencyMap e a

Compute the transitive closure of a graph over the underlying star semiring using a modified version of the Warshall-Floyd-Kleene algorithm, which omits the reflexivity step.

transitiveClosure empty               == empty
transitiveClosure (vertex x)          == vertex x
transitiveClosure (edge e x y)        == edge e x y
transitiveClosure . transitiveClosure == transitiveClosure

Miscellaneous

consistent :: (Ord a, Eq e, Monoid e) => AdjacencyMap e a -> Bool

Check that the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and there are no zero-labelled edges. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.