Modulealgebraic-graphs-0.8Haskell2010

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 C.Graph type class, which can be used for polymorphic graph construction and manipulation.

1 type
40 values

Packagealgebraic-graphs-0.8
Exports41
LanguageHaskell2010
LicenceMIT
SourceAdjacencyMap.hs

Data structure

2 declarations

newtypenewtype 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.

Instances14Eq, Num, Ord, Show, IsString, Generic, …

(Eq a, Eq e) => Eq (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
(Eq e, Dioid e, Num a, Ord a) => Num (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
Note: this does not satisfy the usual ring laws; see AdjacencyMap for more details.
(Ord e, Monoid e, Ord a) => Ord (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
(Ord a, Show a, Ord e, Show e) => Show (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
IsString a => IsString (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
Generic (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
(Ord a, Eq e, Monoid e) => Semigroup (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
Defined via overlay.
(Ord a, Eq e, Monoid e) => Monoid (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
Defined via overlay and empty.
(NFData a, NFData e) => NFData (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
(Dioid e, Eq e, Ord a) => Graph (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Class
(Eq e, Monoid e, Ord a) => ToGraph (AdjacencyMap e a)Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
Defined via skeleton and the ToGraph instance of AdjacencyMap.
type Rep (AdjacencyMap e a) = D1 ('MetaData "AdjacencyMap" "Algebra.Graph.Labelled.AdjacencyMap" "algebraic-graphs-0.8-8JX2W3BiNP382gnPBc0Np8" 'True) (C1 ('MetaCons "AM" 'PrefixI 'True) (S1 ('MetaSel ('Just "adjacencyMap") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map a (Map a e)))))Defined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap
type Vertex (AdjacencyMap e a) = aDefined in algebraic-graphs-0.8 · Algebra.Graph.Class
type ToVertex (AdjacencyMap e a) = aDefined in algebraic-graphs-0.8 · Algebra.Graph.Labelled.AdjacencyMap

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

11 declarations

valueempty :: AdjacencyMap e a

Construct the empty graph.

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

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

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

value(-<) :: a -> e -> (a, e)

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

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

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

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

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

valueoverlay

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

valueconnect

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

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

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

valueoverlays

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

valuefromAdjacencyMaps

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

1 declaration

valueisSubgraphOf

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

13 declarations

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

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

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

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

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

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

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

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

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

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

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

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

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

9 declarations

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

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

valuereplaceVertex

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

valuereplaceEdge

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

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

valuegmap

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

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

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

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

4 declarations

valueclosure

:: (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 y x)

valuereflexiveClosure

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

valuesymmetricClosure

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

valuetransitiveClosure

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

1 declaration

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