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

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 provides a minimal and experimental implementation of algebraic graphs with edge labels. The API will be expanded in the next release.

Synopsis

Algebraic data type for edge-labelled graphs

data Graph e a Source #

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

Constructors

Empty 
Vertex a 
Connect e (Graph e a) (Graph e a) 
Instances
Bifunctor Graph Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

bimap :: (a -> b) -> (c -> d) -> Graph a c -> Graph b d #

first :: (a -> b) -> Graph a c -> Graph b c #

second :: (b -> c) -> Graph a b -> Graph a c #

Functor (Graph e) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

fmap :: (a -> b) -> Graph e a -> Graph e b #

(<$) :: a -> Graph e b -> Graph e a #

(Eq e, Monoid e, Ord a) => Eq (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

(==) :: Graph e a -> Graph e a -> Bool #

(/=) :: Graph e a -> Graph e a -> Bool #

(Ord a, Num a, Dioid e) => Num (Graph e a) Source #

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

Instance details

Defined in Algebra.Graph.Labelled

Methods

(+) :: Graph e a -> Graph e a -> Graph e a #

(-) :: Graph e a -> Graph e a -> Graph e a #

(*) :: Graph e a -> Graph e a -> Graph e a #

negate :: Graph e a -> Graph e a #

abs :: Graph e a -> Graph e a #

signum :: Graph e a -> Graph e a #

fromInteger :: Integer -> Graph e a #

(Eq e, Monoid e, Ord a, Ord e) => Ord (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

compare :: Graph e a -> Graph e a -> Ordering #

(<) :: Graph e a -> Graph e a -> Bool #

(<=) :: Graph e a -> Graph e a -> Bool #

(>) :: Graph e a -> Graph e a -> Bool #

(>=) :: Graph e a -> Graph e a -> Bool #

max :: Graph e a -> Graph e a -> Graph e a #

min :: Graph e a -> Graph e a -> Graph e a #

(Show a, Show e) => Show (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

showsPrec :: Int -> Graph e a -> ShowS #

show :: Graph e a -> String #

showList :: [Graph e a] -> ShowS #

Generic (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Associated Types

type Rep (Graph e a) :: Type -> Type #

Methods

from :: Graph e a -> Rep (Graph e a) x #

to :: Rep (Graph e a) x -> Graph e a #

(NFData e, NFData a) => NFData (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

rnf :: Graph e a -> () #

(Eq e, Monoid e, Ord a) => ToGraph (Graph e a) Source #

See Algebra.Graph.Labelled.

Instance details

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (Graph e a) :: Type Source #

Methods

toGraph :: Graph e a -> Graph0 (ToVertex (Graph e a)) Source #

foldg :: r -> (ToVertex (Graph e a) -> r) -> (r -> r -> r) -> (r -> r -> r) -> Graph e a -> r Source #

isEmpty :: Graph e a -> Bool Source #

hasVertex :: ToVertex (Graph e a) -> Graph e a -> Bool Source #

hasEdge :: ToVertex (Graph e a) -> ToVertex (Graph e a) -> Graph e a -> Bool Source #

vertexCount :: Graph e a -> Int Source #

edgeCount :: Graph e a -> Int Source #

vertexList :: Graph e a -> [ToVertex (Graph e a)] Source #

edgeList :: Graph e a -> [(ToVertex (Graph e a), ToVertex (Graph e a))] Source #

vertexSet :: Graph e a -> Set (ToVertex (Graph e a)) Source #

vertexIntSet :: Graph e a -> IntSet Source #

edgeSet :: Graph e a -> Set (ToVertex (Graph e a), ToVertex (Graph e a)) Source #

preSet :: ToVertex (Graph e a) -> Graph e a -> Set (ToVertex (Graph e a)) Source #

preIntSet :: Int -> Graph e a -> IntSet Source #

postSet :: ToVertex (Graph e a) -> Graph e a -> Set (ToVertex (Graph e a)) Source #

postIntSet :: Int -> Graph e a -> IntSet Source #

adjacencyList :: Graph e a -> [(ToVertex (Graph e a), [ToVertex (Graph e a)])] Source #

dfsForest :: Graph e a -> Forest (ToVertex (Graph e a)) Source #

dfsForestFrom :: [ToVertex (Graph e a)] -> Graph e a -> Forest (ToVertex (Graph e a)) Source #

dfs :: [ToVertex (Graph e a)] -> Graph e a -> [ToVertex (Graph e a)] Source #

reachable :: ToVertex (Graph e a) -> Graph e a -> [ToVertex (Graph e a)] Source #

topSort :: Graph e a -> Either (Cycle (ToVertex (Graph e a))) [ToVertex (Graph e a)] Source #

isAcyclic :: Graph e a -> Bool Source #

toAdjacencyMap :: Graph e a -> AdjacencyMap (ToVertex (Graph e a)) Source #

toAdjacencyMapTranspose :: Graph e a -> AdjacencyMap (ToVertex (Graph e a)) Source #

toAdjacencyIntMap :: Graph e a -> AdjacencyIntMap Source #

toAdjacencyIntMapTranspose :: Graph e a -> AdjacencyIntMap Source #

isDfsForestOf :: Forest (ToVertex (Graph e a)) -> Graph e a -> Bool Source #

isTopSortOf :: [ToVertex (Graph e a)] -> Graph e a -> Bool Source #

Dioid e => Graph (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Class

Associated Types

type Vertex (Graph e a) :: Type Source #

Methods

empty :: Graph e a Source #

vertex :: Vertex (Graph e a) -> Graph e a Source #

overlay :: Graph e a -> Graph e a -> Graph e a Source #

connect :: Graph e a -> Graph e a -> Graph e a Source #

type Rep (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

type ToVertex (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.ToGraph

type ToVertex (Graph e a) = a
type Vertex (Graph e a) Source # 
Instance details

Defined in Algebra.Graph.Class

type Vertex (Graph e a) = a

empty :: Graph e a Source #

Construct the empty graph. An alias for the constructor Empty. Complexity: O(1) time, memory and size.

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

vertex :: a -> Graph e a Source #

Construct the graph comprising a single isolated vertex. An alias for the constructor Vertex. Complexity: O(1) time, memory and size.

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

edge :: e -> a -> a -> Graph e a Source #

Construct the graph comprising a single labelled edge. Complexity: O(1) time, memory and size.

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

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

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

(>-) :: (a, e) -> a -> Graph e a infixl 5 Source #

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 :: Monoid e => Graph e a -> Graph e a -> Graph e a Source #

Overlay two graphs. An alias for Connect zero. Complexity: O(1) time and memory, O(s1 + s2) size.

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 :: e -> Graph e a -> Graph e a -> Graph e a Source #

Connect two graphs with edges labelled by a given label. An alias for Connect. Complexity: O(1) time and memory, O(s1 + s2) size. 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 :: Monoid e => [a] -> Graph e a Source #

Construct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, 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

edges :: Monoid e => [(e, a, a)] -> Graph e a Source #

Construct the graph from a list of labelled edges. Complexity: O(L) time, memory and size, where L is the length of the given list.

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

overlays :: Monoid e => [Graph e a] -> Graph e a Source #

Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L is the length of the given list, and S is the sum of sizes of the graphs in the list.

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

Graph folding

foldg :: b -> (a -> b) -> (e -> b -> b -> b) -> Graph e a -> b Source #

Generalised Graph folding: recursively collapse a Graph by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: empty, vertex and connect. Complexity: O(s) applications of given functions. As an example, the complexity of size is O(s), since all functions have cost O(1).

foldg empty     vertex        connect             == id
foldg empty     vertex        (fmap flip connect) == transpose
foldg 1         (const 1)     (const (+))         == size
foldg True      (const False) (const (&&))        == isEmpty
foldg False     (== x)        (const (||))        == hasVertex x
foldg Set.empty Set.singleton (const Set.union)   == vertexSet

Relations on graphs

isSubgraphOf :: (Eq e, Monoid e, Ord a) => Graph e a -> Graph e a -> Bool Source #

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             (overlay x y) ==  True
isSubgraphOf (overlay x y) (connect x y) ==  True
isSubgraphOf x y                         ==> x <= y

Graph properties

isEmpty :: Graph e a -> Bool Source #

Check if a graph is empty. Complexity: O(s) 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

size :: Graph e a -> Int Source #

The size of a graph, i.e. the number of leaves of the expression including empty leaves. Complexity: O(s) time.

size empty         == 1
size (vertex x)    == 1
size (overlay x y) == size x + size y
size (connect x y) == size x + size y
size x             >= 1
size x             >= vertexCount x

hasVertex :: Eq a => a -> Graph e a -> Bool Source #

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

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

hasEdge :: (Eq e, Monoid e, Ord a) => a -> a -> Graph e a -> Bool Source #

Check if a graph contains a given edge. Complexity: O(s) 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 :: (Eq a, Monoid e) => a -> a -> Graph e a -> e Source #

Extract the label of a specified edge from a graph.

vertexList :: Ord a => Graph e a -> [a] Source #

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

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

edgeList :: (Eq e, Monoid e, Ord a) => Graph e a -> [(e, a, a)] Source #

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 :: Ord a => Graph e a -> Set a Source #

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

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

edgeSet :: (Eq e, Monoid e, Ord a) => Graph e a -> Set (e, a, a) Source #

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)

Graph transformation

removeVertex :: Eq a => a -> Graph e a -> Graph e a Source #

Remove a vertex from a given graph. Complexity: O(s) time, memory and size.

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 :: (Eq a, Eq e, Monoid e) => a -> a -> Graph e a -> Graph e a Source #

Remove an edge from a given graph. Complexity: O(s) time, memory and size.

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 a => a -> a -> Graph e a -> Graph e a Source #

The function replaceVertex x y replaces vertex x with vertex y in a given Graph. If y already exists, x and y will be merged. Complexity: O(s) time, memory and size.

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

replaceEdge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> Graph e a -> Graph e a Source #

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 :: Graph e a -> Graph e a Source #

Transpose a given graph. Complexity: O(s) time, memory and size.

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

emap :: (e -> f) -> Graph e a -> Graph f a Source #

Transform a graph by applying a function to each of its edge labels. Complexity: O(s) time, memory and size.

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) -> Graph e a -> Graph e a Source #

Construct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s) time, memory and size, 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 :: Graph e (Maybe a) -> Graph e a Source #

Construct the induced subgraph of a given graph by removing the vertices that are Nothing. Complexity: O(s) time, memory and size.

induceJust (vertex Nothing)                               == empty
induceJust (edge (Just x) Nothing)                        == vertex x
induceJust . fmap Just                                    == id
induceJust . fmap (\x -> if p x then Just x else Nothing) == induce p

Relational operations

closure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a Source #

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) => Graph e a -> Graph e a Source #

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 :: Monoid e => Graph e a -> Graph e a Source #

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) => Graph e a -> Graph e a Source #

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

Types of edge-labelled graphs

type UnlabelledGraph a = Graph Any a Source #

A type synonym for unlabelled graphs.

type Automaton a s = Graph (RegularExpression a) s Source #

A type synonym for automata or labelled transition systems.

type Network e a = Graph (Distance e) a Source #

A network is a graph whose edges are labelled with distances.

Context

data Context e a Source #

The Context of a subgraph comprises its inputs and outputs, i.e. all the vertices that are connected to the subgraph's vertices (along with the corresponding edge labels). Note that inputs and outputs can belong to the subgraph itself. In general, there are no guarantees on the order of vertices in inputs and outputs; furthermore, there may be repetitions.

Constructors

Context 

Fields

Instances
(Eq e, Eq a) => Eq (Context e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

(==) :: Context e a -> Context e a -> Bool #

(/=) :: Context e a -> Context e a -> Bool #

(Show e, Show a) => Show (Context e a) Source # 
Instance details

Defined in Algebra.Graph.Labelled

Methods

showsPrec :: Int -> Context e a -> ShowS #

show :: Context e a -> String #

showList :: [Context e a] -> ShowS #

context :: (Eq e, Monoid e) => (a -> Bool) -> Graph e a -> Maybe (Context e a) Source #

Extract the Context of a subgraph specified by a given predicate. Returns Nothing if the specified subgraph is empty.

context (const False) x                   == Nothing
context (== 1)        (edge e 1 2)        == if e == zero then Just (Context [] []) else Just (Context [     ] [(e,2)])
context (== 2)        (edge e 1 2)        == if e == zero then Just (Context [] []) else Just (Context [(e,1)] [     ])
context (const True ) (edge e 1 2)        == if e == zero then Just (Context [] []) else Just (Context [(e,1)] [(e,2)])
context (== 4)        (3 * 1 * 4 * 1 * 5) == Just (Context [(one,3), (one,1)] [(one,1), (one,5)])