Copyright | (c) Andrey Mokhov 2016-2018 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
This module exposes the implementation of non-empty adjacency maps. The API is unstable and unsafe, and is exposed only for documentation. You should use the non-internal module Algebra.Graph.NonEmpty.AdjacencyMap instead.
Synopsis
- newtype AdjacencyMap a = NAM {
- am :: AdjacencyMap a
- consistent :: Ord a => AdjacencyMap a -> Bool
Adjacency map implementation
newtype AdjacencyMap a Source #
The AdjacencyMap
data type represents a graph by a map of vertices to
their adjacency sets. We define a Num
instance as a convenient notation for
working with 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 signum
method of the type class Num
cannot be implemented and
will throw an error. Furthermore, 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 Show
instance is defined using basic graph construction primitives:
show (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices1 [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges1 [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"
The Eq
instance satisfies the following laws of algebraic graphs:
overlay
is commutative, associative and idempotent:x + y == y + x x + (y + z) == (x + y) + z x + x == x
connect
is associative: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
connect
satisfies absorption and saturation:x * y + x + y == x * y x * x * x == x * x
When specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges in the graph, respectively.
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 3
Note that the resulting order refines the
isSubgraphOf
relation and is compatible
with overlay
and
connect
operations:
isSubgraphOf
x y ==> x <= y
x <= x + y x + y <= x * y
NAM | |
|
Instances
consistent :: Ord a => AdjacencyMap a -> Bool Source #
Check if the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and the graph is non-empty. It should be impossible to create an inconsistent adjacency map, and we use this function in testing. Note: this function is for internal use only.
consistent (vertex
x) == True consistent (overlay
x y) == True consistent (connect
x y) == True consistent (edge
x y) == True consistent (edges
xs) == True consistent (stars
xs) == True