Copyright | (c) Andrey Mokhov 2016-2019 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
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 and for acyclic graphs, as
well as associated operations and algorithms. To avoid name clashes with
Algebra.Graph.AdjacencyMap, this module can be imported qualified:
import qualified Algebra.Graph.Acyclic.AdjacencyMap as Acyclic
Synopsis
- data AdjacencyMap a
- fromAcyclic :: AdjacencyMap a -> AdjacencyMap a
- empty :: AdjacencyMap a
- vertex :: a -> AdjacencyMap a
- vertices :: Ord a => [a] -> AdjacencyMap a
- union :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (Either a b)
- join :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (Either a b)
- isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool
- isEmpty :: AdjacencyMap a -> Bool
- hasVertex :: Ord a => a -> AdjacencyMap a -> Bool
- hasEdge :: Ord a => a -> a -> AdjacencyMap a -> Bool
- vertexCount :: AdjacencyMap a -> Int
- edgeCount :: AdjacencyMap a -> Int
- vertexList :: AdjacencyMap a -> [a]
- edgeList :: AdjacencyMap a -> [(a, a)]
- adjacencyList :: AdjacencyMap a -> [(a, [a])]
- vertexSet :: AdjacencyMap a -> Set a
- edgeSet :: Eq a => AdjacencyMap a -> Set (a, a)
- preSet :: Ord a => a -> AdjacencyMap a -> Set a
- postSet :: Ord a => a -> AdjacencyMap a -> Set a
- removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a
- removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a
- transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a
- induce :: (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a
- induceJust :: Ord a => AdjacencyMap (Maybe a) -> AdjacencyMap a
- box :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (a, b)
- transitiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a
- topSort :: Ord a => AdjacencyMap a -> [a]
- scc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a)
- toAcyclic :: Ord a => AdjacencyMap a -> Maybe (AdjacencyMap a)
- toAcyclicOrd :: Ord a => AdjacencyMap a -> AdjacencyMap a
- shrink :: Ord a => AdjacencyMap a -> AdjacencyMap a
- consistent :: Ord a => AdjacencyMap a -> Bool
Data structure
data AdjacencyMap a Source #
The AdjacencyMap
data type represents an acyclic graph by a map of
vertices to their adjacency sets. Although the internal representation allows
for cycles, the methods provided by this module cannot be used to construct a
graph with cycles.
The Show
instance is defined using basic graph construction primitives where
possible, falling back to toAcyclic
and Algebra.Graph.AdjacencyMap
otherwise:
show empty == "empty" show (shrink 1) == "vertex 1" show (shrink $ 1 + 2) == "vertices [1,2]" show (shrink $ 1 * 2) == "(fromJust . toAcyclic) (edge 1 2)" show (shrink $ 1 * 2 * 3) == "(fromJust . toAcyclic) (edges [(1,2),(1,3),(2,3)])" show (shrink $ 1 * 2 + 3) == "(fromJust . toAcyclic) (overlay (vertex 3) (edge 1 2))"
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.
Note that the resulting order refines the isSubgraphOf
relation:
isSubgraphOf
x y ==> x <= y
Instances
Eq a => Eq (AdjacencyMap a) Source # | |
Defined in Algebra.Graph.Acyclic.AdjacencyMap (==) :: AdjacencyMap a -> AdjacencyMap a -> Bool # (/=) :: AdjacencyMap a -> AdjacencyMap a -> Bool # | |
Ord a => Ord (AdjacencyMap a) Source # | |
Defined in Algebra.Graph.Acyclic.AdjacencyMap compare :: AdjacencyMap a -> AdjacencyMap a -> Ordering # (<) :: AdjacencyMap a -> AdjacencyMap a -> Bool # (<=) :: AdjacencyMap a -> AdjacencyMap a -> Bool # (>) :: AdjacencyMap a -> AdjacencyMap a -> Bool # (>=) :: AdjacencyMap a -> AdjacencyMap a -> Bool # max :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a # min :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a # | |
(Ord a, Show a) => Show (AdjacencyMap a) Source # | |
Defined in Algebra.Graph.Acyclic.AdjacencyMap showsPrec :: Int -> AdjacencyMap a -> ShowS # show :: AdjacencyMap a -> String # showList :: [AdjacencyMap a] -> ShowS # |
fromAcyclic :: AdjacencyMap a -> AdjacencyMap a Source #
Extract the underlying acyclic Algebra.Graph.AdjacencyMap. Complexity: O(1) time and memory.
fromAcyclicempty
==empty
fromAcyclic .vertex
==vertex
fromAcyclic (shrink $ 1 * 3 + 2) == 1 * 3 + 2vertexCount
. fromAcyclic ==vertexCount
edgeCount
. fromAcyclic ==edgeCount
isAcyclic
. fromAcyclic ==const
True
Basic graph construction primitives
empty :: AdjacencyMap a Source #
Construct the empty graph. Complexity: O(1) time and memory.
isEmpty
empty == TruehasVertex
x empty == FalsevertexCount
empty == 0edgeCount
empty == 0
vertex :: a -> AdjacencyMap a Source #
Construct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.
isEmpty
(vertex x) == FalsehasVertex
x (vertex y) == (x == y)vertexCount
(vertex x) == 1edgeCount
(vertex x) == 0
vertices :: Ord a => [a] -> AdjacencyMap a Source #
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
xhasVertex
x . vertices ==elem
xvertexCount
. vertices ==length
.nub
vertexSet
. vertices == Set.fromList
union :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (Either a b) Source #
Construct the disjoint union of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.
vertexSet
(union x y) == Set.unions
[ Set.map
Left
(vertexSet
x) , Set.map
Right
(vertexSet
y) ]edgeSet
(union x y) == Set.unions
[ Set.map
(bimap
Left
Left
) (edgeSet
x) , Set.map
(bimap
Right
Right
) (edgeSet
y) ]
join :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (Either a b) Source #
Construct the join of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.
vertexSet
(join x y) == Set.unions
[ Set.map
Left
(vertexSet
x) , Set.map
Right
(vertexSet
y) ]edgeSet
(join x y) == Set.unions
[ Set.map
(bimap
Left
Left
) (edgeSet
x) , Set.map
(bimap
Right
Right
) (edgeSet
y) , Set.map
(bimap
Left
Right
) (Set.cartesianProduct
(vertexSet
x) (vertexSet
y)) ]
Relations on graphs
isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool Source #
The isSubgraphOf
function takes two graphs and returns True
if the
first graph is a subgraph of the second.
Complexity: O((n + m) * log(n)) time.
isSubgraphOfempty
x == True isSubgraphOf (vertex
x)empty
== False isSubgraphOf (induce
p x) x == True isSubgraphOf x (transitiveClosure
x) == True isSubgraphOf x y ==> x <= y
Graph properties
isEmpty :: AdjacencyMap a -> Bool Source #
Check if a graph is empty. Complexity: O(1) time.
isEmptyempty
== True isEmpty (vertex
x) == False isEmpty (removeVertex
x $vertex
x) == True isEmpty (removeEdge
1 2 $ shrink $ 1 * 2) == False
hasVertex :: Ord a => a -> AdjacencyMap a -> Bool Source #
Check if a graph contains a given vertex. Complexity: O(log(n)) time.
hasVertex xempty
== False hasVertex x (vertex
y) == (x == y) hasVertex x .removeVertex
x ==const
False
vertexCount :: AdjacencyMap a -> Int Source #
The number of vertices in a graph. Complexity: O(1) time.
vertexCountempty
== 0 vertexCount (vertex
x) == 1 vertexCount ==length
.vertexList
vertexCount x < vertexCount y ==> x < y
edgeCount :: AdjacencyMap a -> Int Source #
vertexList :: AdjacencyMap a -> [a] Source #
edgeList :: AdjacencyMap a -> [(a, a)] Source #
adjacencyList :: AdjacencyMap a -> [(a, [a])] Source #
vertexSet :: AdjacencyMap a -> Set a Source #
Graph transformation
removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a Source #
removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a Source #
Remove an edge from a given acyclic graph. Complexity: O(log(n)) time.
removeEdge 1 2 (shrink $ 1 * 2) ==vertices
[1,2] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .removeVertex
x ==removeVertex
x removeEdge 1 2 (shrink $ 1 * 2 * 3) == shrink ((1 + 2) * 3)
transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a Source #
induce :: (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a Source #
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 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 :: Ord a => AdjacencyMap (Maybe a) -> AdjacencyMap a Source #
Graph composition
box :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (a, b) Source #
Compute the Cartesian product of graphs. Complexity: O(n * m * log(n)^2) time.
edgeList
(box (shrink $ 1 * 2) (shrink $ 10 * 20)) == [ ((1,10), (1,20))
, ((1,10), (2,10))
, ((1,20), (2,20))
, ((2,10), (2,20)) ]
Up to an isomorphism between the resulting vertex types, this operation
is commutative and associative, has singleton graphs as identities and
empty
as the annihilating zero. Below ~~
stands for the equality up to
an isomorphism, e.g. (x, ()) ~~ x
.
box x y ~~ box y x box x (box y z) ~~ box (box x y) z box x (vertex
()) ~~ x box xempty
~~empty
transpose
(box x y) == box (transpose
x) (transpose
y)vertexCount
(box x y) ==vertexCount
x *vertexCount
yedgeCount
(box x y) <=vertexCount
x *edgeCount
y +edgeCount
x *vertexCount
y
Relational operations
transitiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a Source #
Algorithms
topSort :: Ord a => AdjacencyMap a -> [a] Source #
scc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a) Source #
Compute the acyclic condensation of a graph, where each vertex corresponds to a strongly-connected component of the original graph. Note that component graphs are non-empty, and are therefore of type Algebra.Graph.NonEmpty.AdjacencyMap.
sccempty
==empty
scc (vertex
x) ==vertex
(NonEmpty.vertex
x) scc (edge
1 1) ==vertex
(NonEmpty.edge
1 1)edgeList
$ scc (edge
1 2) == [ (NonEmpty.vertex
1 , NonEmpty.vertex
2 ) ]edgeList
$ scc (3 * 1 * 4 * 1 * 5) == [ (NonEmpty.vertex
3 , NonEmpty.vertex
5 ) , (NonEmpty.vertex
3 , NonEmpty.clique1
[1,4,1]) , (NonEmpty.clique1
[1,4,1], NonEmpty.vertex
5 ) ]
Conversion to acyclic graphs
toAcyclic :: Ord a => AdjacencyMap a -> Maybe (AdjacencyMap a) Source #
toAcyclicOrd :: Ord a => AdjacencyMap a -> AdjacencyMap a Source #
Construct an acyclic graph from a given adjacency map, keeping only edges
(x,y)
where x < y
according to the supplied Ord
a
instance.
toAcyclicOrdempty
==empty
toAcyclicOrd .vertex
==vertex
toAcyclicOrd (1 + 2) == shrink (1 + 2) toAcyclicOrd (1 * 2) == shrink (1 * 2) toAcyclicOrd (2 * 1) == shrink (1 + 2) toAcyclicOrd (1 * 2 * 1) == shrink (1 * 2) toAcyclicOrd (1 * 2 * 3) == shrink (1 * 2 * 3)
shrink :: Ord a => AdjacencyMap a -> AdjacencyMap a Source #
Construct an acyclic graph from a given adjacency map using scc
.
If the graph is acyclic in nature, the same graph is returned as an acyclic graph.
If the graph is cyclic, then a representative for every strongly connected
component in its condensation graph is chosen an these representatives are
used to build an acyclic graph.
shrink .vertex
==vertex
shrink .vertices
==vertices
shrink .fromAcyclic
==id
Miscellaneous
consistent :: Ord a => AdjacencyMap a -> Bool Source #
Check if the internal representation of an acyclic graph is consistent,
i.e. that all edges refer to existing vertices and the graph is acyclic. It
should be impossible to create an inconsistent AdjacencyMap
.
consistentempty
== True consistent (vertex
x) == True consistent (vertices
xs) == True consistent (union
x y) == True consistent (join
x y) == True consistent (transpose
x) == True consistent (box
x y) == True consistent (transitiveClosure
x) == True consistent (scc
x) == Truefmap
consistent (toAcyclic
x) /= False consistent (toAcyclicOrd
x) == True