Copyright | (c) Andrey Mokhov 2016-2022 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
Algebra.Graph.Undirected
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 an undirected version of algebraic graphs. Undirected
graphs satisfy all laws of the
Undirected
type class,
including the commutativity of
connect
.
To avoid name clashes with Algebra.Graph , this module can be imported qualified:
import qualified Algebra.Graph.Undirected as Undirected
Synopsis
- data Graph a
- fromUndirected :: Ord a => Graph a -> Graph a
- toUndirected :: Graph a -> Graph a
- empty :: Graph a
- vertex :: a -> Graph a
- edge :: a -> a -> Graph a
- overlay :: Graph a -> Graph a -> Graph a
- connect :: Graph a -> Graph a -> Graph a
- vertices :: [a] -> Graph a
- edges :: [(a, a)] -> Graph a
- overlays :: [ Graph a] -> Graph a
- connects :: [ Graph a] -> Graph a
- foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
- isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool
- toRelation :: Ord a => Graph a -> Relation a
- isEmpty :: Graph a -> Bool
- size :: Graph a -> Int
- hasVertex :: Eq a => a -> Graph a -> Bool
- hasEdge :: Eq a => a -> a -> Graph a -> Bool
- vertexCount :: Ord a => Graph a -> Int
- edgeCount :: Ord a => Graph a -> Int
- vertexList :: Ord a => Graph a -> [a]
- edgeList :: Ord a => Graph a -> [(a, a)]
- vertexSet :: Ord a => Graph a -> Set a
- edgeSet :: Ord a => Graph a -> Set (a, a)
- adjacencyList :: Ord a => Graph a -> [(a, [a])]
- neighbours :: Ord a => a -> Graph a -> Set a
- path :: [a] -> Graph a
- circuit :: [a] -> Graph a
- clique :: [a] -> Graph a
- biclique :: [a] -> [a] -> Graph a
- star :: a -> [a] -> Graph a
- stars :: [(a, [a])] -> Graph a
- tree :: Tree a -> Graph a
- forest :: Forest a -> Graph a
- removeVertex :: Eq a => a -> Graph a -> Graph a
- removeEdge :: Eq a => a -> a -> Graph a -> Graph a
- replaceVertex :: Eq a => a -> a -> Graph a -> Graph a
- mergeVertices :: (a -> Bool ) -> a -> Graph a -> Graph a
- induce :: (a -> Bool ) -> Graph a -> Graph a
- induceJust :: Graph ( Maybe a) -> Graph a
- complement :: Ord a => Graph a -> Graph a
Algebraic data type for graphs
The
Graph
data type provides the four algebraic graph construction
primitives
empty
,
vertex
,
overlay
and
connect
, as well as various
derived functions. The only difference compared to the
Graph
data type defined in
Algebra.Graph
is that the
connect
operation is
commutative
. We define a
Num
instance as a convenient notation for working
with undirected graphs:
0 ==vertex
0 1 + 2 ==overlay
(vertex
1) (vertex
2) 1 * 2 ==connect
(vertex
1) (vertex
2) 1 + 2 * 3 ==overlay
(vertex
1) (connect
(vertex
2) (vertex
3)) 1 * (2 + 3) ==connect
(vertex
1) (overlay
(vertex
2) (vertex
3))
Note:
the
Num
instance does not satisfy several "customary laws" of
Num
,
which dictate that
fromInteger
0
and
fromInteger
1
should act as
additive and multiplicative identities, and
negate
as additive inverse.
Nevertheless, overloading
fromInteger
,
+
and
*
is very convenient when
working with algebraic graphs; we hope that in future Haskell's Prelude will
provide a more fine-grained class hierarchy for algebraic structures, which we
would be able to utilise without violating any laws.
The
Eq
instance is currently implemented using the
Relation
as the
canonical graph representation
and satisfies all axioms of algebraic graphs:
-
overlay
is commutative and associative:x + y == y + x x + (y + z) == (x + y) + z
-
connect
is associative, commutative and hasempty
as the identity:x * empty == x empty * x == x x * y == y * x x * (y * z) == (x * y) * z
-
connect
distributes overoverlay
:x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z
-
connect
can be decomposed:x * y * z == x * y + x * z + y * z
The following useful theorems can be proved from the above set of axioms.
-
overlay
hasempty
as the identity and is idempotent:x + empty == x empty + x == x x + x == x
-
Absorption and saturation of
connect
:x * y + x + y == x * y x * x * x == x * x
When specifying the time and memory complexity of graph algorithms,
n
will
denote the number of vertices in the graph,
m
will denote the number of edges
in the graph, and
s
will denote the
size
of the corresponding
Graph
expression. For example, if
g
is a
Graph
then
n
,
m
and
s
can be
computed as follows:
n ==vertexCount
g m ==edgeCount
g s ==size
g
Note that
size
counts all leaves of the expression:
vertexCount
empty
== 0size
empty
== 1vertexCount
(vertex
x) == 1size
(vertex
x) == 1vertexCount
(empty
+empty
) == 0size
(empty
+empty
) == 2
Converting an undirected
Graph
to the corresponding
Relation
takes
O(s + m * log(m))
time and
O(s + m)
memory. This is also the complexity of
the graph equality test, because it is currently implemented by converting graph
expressions to canonical representations based on adjacency maps.
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.
Here are a few examples:
vertex
1 <vertex
2vertex
3 <edge
1 2vertex
1 <edge
1 1edge
1 1 <edge
1 2edge
1 2 <edge
1 1 +edge
2 2edge
1 2 <edge
1 3edge
1 2 ==edge
2 1
Note that the resulting order refines the
isSubgraphOf
relation and is
compatible with
overlay
and
connect
operations:
isSubgraphOf
x y ==> x <= y
empty
<= x
x <= x + y
x + y <= x * y
Instances
Monad Graph Source # | |
Functor Graph Source # | |
Applicative Graph Source # | |
Alternative Graph Source # | |
MonadPlus Graph Source # | |
Ord a => Eq ( Graph a) Source # | |
Num a => Num ( Graph a) Source # |
Note:
this does not satisfy the usual ring laws; see
|
Defined in Algebra.Graph.Undirected |
|
Ord a => Ord ( Graph a) Source # | |
Defined in Algebra.Graph.Undirected |
|
( Show a, Ord a) => Show ( Graph a) Source # | |
IsString a => IsString ( Graph a) Source # | |
Defined in Algebra.Graph.Undirected Methods fromString :: String -> Graph a Source # |
|
Generic ( Graph a) Source # | |
Semigroup ( Graph a) Source # |
Defined via
|
Monoid ( Graph a) Source # | |
NFData a => NFData ( Graph a) Source # | |
Defined in Algebra.Graph.Undirected |
|
Undirected ( Graph a) Source # | |
Defined in Algebra.Graph.Class |
|
Graph ( Graph a) Source # | |
type Rep ( Graph a) Source # | |
Defined in Algebra.Graph.Undirected |
|
type Vertex ( Graph a) Source # | |
Defined in Algebra.Graph.Class |
fromUndirected :: Ord a => Graph a -> Graph a Source #
Extract the underlying Algebra.Graph . Complexity: O(n + m) time.
fromUndirected (edge
1 2) ==edges
[(1,2),(2,1)]toUndirected
.fromUndirected
== idvertexCount
. fromUndirected ==vertexCount
edgeCount
. fromUndirected <= (*2) .edgeCount
toUndirected :: Graph a -> Graph a Source #
Construct an undirected graph from a given Algebra.Graph . Complexity: O(1) time.
toUndirected (edge
1 2) ==edge
1 2 toUndirected .fromUndirected
== idvertexCount
. toUndirected ==vertexCount
(*2) .edgeCount
. toUndirected >=edgeCount
Basic graph construction primitives
Construct the empty graph .
isEmpty
empty == TruehasVertex
x empty == FalsevertexCount
empty == 0edgeCount
empty == 0size
empty == 1
vertex :: a -> Graph a Source #
Construct the graph comprising a single isolated vertex .
isEmpty
(vertex x) == FalsehasVertex
x (vertex y) == (x == y)vertexCount
(vertex x) == 1edgeCount
(vertex x) == 0size
(vertex x) == 1
edge :: a -> a -> Graph a Source #
Construct the graph comprising a single edge .
edge x y ==connect
(vertex
x) (vertex
y) edge x y ==edge
y x edge x y ==edges
[(x,y), (y,x)]hasEdge
x y (edge x y) == TrueedgeCount
(edge x y) == 1vertexCount
(edge 1 1) == 1vertexCount
(edge 1 2) == 2
overlay :: Graph a -> Graph a -> Graph a Source #
Overlay
two graphs. This is a commutative, associative and idempotent
operation with the identity
empty
.
Complexity:
O(1)
time and memory,
O(s1 + s2)
size.
isEmpty
(overlay x y) ==isEmpty
x &&isEmpty
yhasVertex
z (overlay x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(overlay x y) >=vertexCount
xvertexCount
(overlay x y) <=vertexCount
x +vertexCount
yedgeCount
(overlay x y) >=edgeCount
xedgeCount
(overlay x y) <=edgeCount
x +edgeCount
ysize
(overlay x y) ==size
x +size
yvertexCount
(overlay 1 2) == 2edgeCount
(overlay 1 2) == 0
connect :: Graph a -> Graph a -> Graph a Source #
Connect
two graphs. This is a commutative and associative operation with
the identity
empty
, which distributes over
overlay
and obeys the
decomposition axiom.
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)
.
connect
x y ==connect
y xisEmpty
(connect x y) ==isEmpty
x &&isEmpty
yhasVertex
z (connect x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(connect x y) >=vertexCount
xvertexCount
(connect x y) <=vertexCount
x +vertexCount
yedgeCount
(connect x y) >=edgeCount
xedgeCount
(connect x y) >=edgeCount
yedgeCount
(connect x y) >=vertexCount
x *vertexCount
yedgeCount
(connect x y) >=vertexCount
x *vertexCount
ydiv
2size
(connect x y) ==size
x +size
yvertexCount
(connect 1 2) == 2edgeCount
(connect 1 2) == 1
vertices :: [a] -> Graph 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 vertices ==overlays
. mapvertex
hasVertex
x . vertices ==elem
xvertexCount
. vertices ==length
.nub
vertexSet
. vertices == Set .fromList
overlays :: [ Graph a] -> Graph 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
connects :: [ Graph a] -> Graph a Source #
Connect 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.
connects [] ==empty
connects [x] == x connects [x,y] ==connect
x y connects ==foldr
connect
empty
isEmpty
. connects ==all
isEmpty
connects == connects .reverse
Graph folding
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph 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, overlay and connect.
Complexity:
O(s)
applications of the given functions. As an example, the
complexity of
size
is
O(s)
, since
const
and
+
have constant costs.
foldgempty
vertex
overlay
connect
== id foldgempty
vertex
overlay
(flip
connect
) == id foldg 1 (const
1) (+) (+) ==size
foldg True (const
False) (&&) (&&) ==isEmpty
foldg False (== x) (||) (||) ==hasVertex
x
Relations on graphs
isSubgraphOf :: Ord a => Graph a -> Graph 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
.
isSubgraphOfempty
x == True isSubgraphOf (vertex
x)empty
== False isSubgraphOf x (overlay
x y) == True isSubgraphOf (overlay
x y) (connect
x y) == True isSubgraphOf (path
xs) (circuit
xs) == True isSubgraphOf (edge
x y) (edge
y x) == True isSubgraphOf x y ==> x <= y
toRelation :: Ord a => Graph a -> Relation a Source #
Convert an undirected graph to a symmetric
Relation
.
Graph properties
isEmpty :: Graph a -> Bool Source #
Check if a graph is empty. Complexity: O(s) time.
isEmptyempty
== True isEmpty (overlay
empty
empty
) == True isEmpty (vertex
x) == False isEmpty (removeVertex
x $vertex
x) == True isEmpty (removeEdge
x y $edge
x y) == False
hasVertex :: Eq a => a -> Graph a -> Bool Source #
Check if a graph contains a given vertex. Complexity: O(s) time.
hasVertex xempty
== False hasVertex x (vertex
y) == (x == y) hasVertex x .removeVertex
x ==const
False
vertexCount :: Ord a => Graph a -> Int Source #
The number of vertices in a graph. Complexity: O(s * log(n)) time.
vertexCountempty
== 0 vertexCount (vertex
x) == 1 vertexCount ==length
.vertexList
vertexCount x < vertexCount y ==> x < y
vertexList :: Ord a => Graph a -> [a] Source #
edgeList :: Ord a => Graph a -> [(a, a)] Source #
The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m) memory. Note that the number of edges m of a graph can be quadratic with respect to the expression size s .
edgeListempty
== [] edgeList (vertex
x) == [] edgeList (edge
x y) == [(min x y, max y x)] edgeList (star
2 [3,1]) == [(1,2), (2,3)]
adjacencyList :: Ord a => Graph a -> [(a, [a])] Source #
Standard families of graphs
clique :: [a] -> Graph a Source #
The clique on a list of vertices. Complexity: O(L) time, memory and size, where L is the length of the given list.
clique [] ==empty
clique [x] ==vertex
x clique [x,y] ==edge
x y clique [x,y,z] ==edges
[(x,y), (x,z), (y,z)] clique (xs ++ ys) ==connect
(clique xs) (clique ys) clique .reverse
== clique
biclique :: [a] -> [a] -> Graph a Source #
The biclique on two lists of vertices. Complexity: O(L1 + L2) time, memory and size, where L1 and L2 are the lengths of the given lists.
biclique [] [] ==empty
biclique [x] [] ==vertex
x biclique [] [y] ==vertex
y biclique [x1,x2] [y1,y2] ==edges
[(x1,y1), (x1,y2), (x2,x2), (x2,y2)] biclique xs ys ==connect
(vertices
xs) (vertices
ys)
stars :: [(a, [a])] -> Graph a Source #
The
stars
formed by overlaying a list of
star
s. An inverse of
adjacencyList
.
Complexity:
O(L)
time, memory and size, where
L
is the total size of the
input.
stars [] ==empty
stars [(x, [])] ==vertex
x stars [(x, [y])] ==edge
x y stars [(x, ys)] ==star
x ys stars ==overlays
.map
(uncurry
star
) stars .adjacencyList
== idoverlay
(stars xs) (stars ys) == stars (xs ++ ys)
tree :: Tree a -> Graph a Source #
The
tree graph
constructed from a given
Tree
data structure.
Complexity:
O(T)
time, memory and size, where
T
is the size of the
given tree (i.e. the number of vertices in the tree).
tree (Node x []) ==vertex
x tree (Node x [Node y [Node z []]]) ==path
[x,y,z] tree (Node x [Node y [], Node z []]) ==star
x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==edges
[(1,2), (1,3), (3,4), (3,5)]
forest :: Forest a -> Graph a Source #
The
forest graph
constructed from a given
Forest
data structure.
Complexity:
O(F)
time, memory and size, where
F
is the size of the
given forest (i.e. the number of vertices in the forest).
forest [] ==empty
forest [x] ==tree
x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==edges
[(1,2), (1,3), (4,5)] forest ==overlays
.map
tree
Graph transformation
removeEdge :: Eq a => a -> a -> Graph a -> Graph a Source #
Remove an edge from a given graph. Complexity: O(s) time, memory and size.
removeEdge x y (edge
x y) ==vertices
[x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y == removeEdge y x 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 a -> Graph a Source #
The function
replaces vertex
replaceVertex
x y
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 ==mergeVertices
(== x) y
mergeVertices :: (a -> Bool ) -> a -> Graph a -> Graph a Source #
Merge vertices satisfying a given predicate into a given vertex. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time.
mergeVertices (const
False) x == id mergeVertices (== x) y ==replaceVertex
x y mergeVerticeseven
1 (0 * 2) == 1 * 1 mergeVerticesodd
1 (3 + 4 * 5) == 4 * 1
induce :: (a -> Bool ) -> Graph a -> Graph 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 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 :: Graph ( Maybe a) -> Graph 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 thenJust
x elseNothing
) ==induce
p
complement :: Ord a => Graph a -> Graph a Source #
The edge complement of a graph. Note that, as can be seen from the examples below, this operation ignores self-loops. Complexity: O(n^2 * log n) time, O(n^2) memory.
complementempty
==empty
complement (vertex
x) == (vertex
x) complement (edge
1 2) == (vertices
[1, 2]) complement (edge
0 0) == (edge
0 0) complement (star
1 [2, 3]) == (overlay
(vertex
1) (edge
2 3)) complement . complement == id