-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A library for algebraic graph construction and transformation
--
-- 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.
--
-- The top-level module Algebra.Graph defines the core data type
-- Graph, which is a deep embedding of four graph construction
-- primitives empty, vertex, overlay and
-- connect. To represent non-empty graphs, see
-- Algebra.Graph.NonEmpty. More conventional graph representations
-- can be found in Algebra.Graph.AdjacencyMap and
-- Algebra.Graph.Relation.
--
-- The type classes defined in Algebra.Graph.Class and
-- Algebra.Graph.HigherKinded.Class can be used for polymorphic
-- graph construction and manipulation. Also see
-- Algebra.Graph.Fold that defines the Boehm-Berarducci encoding
-- of algebraic graphs and provides additional flexibility for
-- polymorphic graph manipulation.
--
-- This is an experimental library and the API is expected to remain
-- unstable until version 1.0.0. Please consider contributing to the
-- on-going discussions on the library API.
@package algebraic-graphs
@version 0.2
-- | This module exposes the implementation of adjacency maps. The API is
-- unstable and unsafe, and is exposed only for documentation. You should
-- use the non-internal module Algebra.Graph.AdjacencyIntMap
-- instead.
module Algebra.Graph.AdjacencyIntMap.Internal
-- | The AdjacencyIntMap 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))
--
--
-- The Show instance is defined using basic graph construction
-- primitives:
--
--
-- show (empty :: AdjacencyIntMap Int) == "empty"
-- show (1 :: AdjacencyIntMap Int) == "vertex 1"
-- show (1 + 2 :: AdjacencyIntMap Int) == "vertices [1,2]"
-- show (1 * 2 :: AdjacencyIntMap Int) == "edge 1 2"
-- show (1 * 2 * 3 :: AdjacencyIntMap Int) == "edges [(1,2),(1,3),(2,3)]"
-- show (1 * 2 + 3 :: AdjacencyIntMap Int) == "overlay (vertex 3) (edge 1 2)"
--
--
-- The Eq instance satisfies all axioms of algebraic graphs:
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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.
newtype AdjacencyIntMap
AM :: IntMap IntSet -> AdjacencyIntMap
-- | The adjacency map of the graph: each vertex is associated with
-- a set of its direct successors. Complexity: O(1) time and
-- memory.
--
--
-- adjacencyIntMap empty == IntMap.empty
-- adjacencyIntMap (vertex x) == IntMap.singleton x IntSet.empty
-- adjacencyIntMap (edge 1 1) == IntMap.singleton 1 (IntSet.singleton 1)
-- adjacencyIntMap (edge 1 2) == IntMap.fromList [(1,IntSet.singleton 2), (2,IntSet.empty)]
--
[adjacencyIntMap] :: AdjacencyIntMap -> IntMap IntSet
-- | Construct the empty graph. Complexity: O(1) time and
-- memory.
--
--
-- isEmpty empty == True
-- hasVertex x empty == False
-- vertexCount empty == 0
-- edgeCount empty == 0
--
empty :: AdjacencyIntMap
-- | Construct the graph comprising a single isolated vertex.
-- Complexity: O(1) time and memory.
--
--
-- isEmpty (vertex x) == False
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
--
vertex :: Int -> AdjacencyIntMap
-- | 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
--
overlay :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
-- | Connect two graphs. 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 x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
-- | Construct a graph from a list of adjacency sets. Complexity: O((n +
-- m) * log(n)) time and O(n + m) memory.
--
--
-- fromAdjacencyIntSets [] == empty
-- fromAdjacencyIntSets [(x, IntSet.empty)] == vertex x
-- fromAdjacencyIntSets [(x, IntSet.singleton y)] == edge x y
-- fromAdjacencyIntSets . map (fmap IntSet.fromList) . adjacencyList == id
-- overlay (fromAdjacencyIntSets xs) (fromAdjacencyIntSets ys) == fromAdjacencyIntSets (xs ++ ys)
--
fromAdjacencyIntSets :: [(Int, IntSet)] -> AdjacencyIntMap
-- | Check if the internal graph representation is consistent, i.e. that
-- all edges refer to existing vertices. 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 empty == True
-- 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
--
consistent :: AdjacencyIntMap -> Bool
instance GHC.Classes.Eq Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap
instance GHC.Show.Show Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap
instance GHC.Num.Num Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap
instance Control.DeepSeq.NFData Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap
-- | This module exposes the implementation of adjacency maps. The API is
-- unstable and unsafe, and is exposed only for documentation. You should
-- use the non-internal module Algebra.Graph.AdjacencyMap instead.
module Algebra.Graph.AdjacencyMap.Internal
-- | 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))
--
--
-- The Show instance is defined using basic graph construction
-- primitives:
--
--
-- show (empty :: AdjacencyMap Int) == "empty"
-- show (1 :: AdjacencyMap Int) == "vertex 1"
-- show (1 + 2 :: AdjacencyMap Int) == "vertices [1,2]"
-- show (1 * 2 :: AdjacencyMap Int) == "edge 1 2"
-- show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
-- show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"
--
--
-- The Eq instance satisfies all axioms of algebraic graphs:
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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.
newtype AdjacencyMap a
AM :: Map a (Set a) -> AdjacencyMap a
-- | The adjacency map of the graph: each vertex is associated with
-- a set of its direct successors. Complexity: O(1) time and
-- memory.
--
--
-- adjacencyMap empty == Map.empty
-- adjacencyMap (vertex x) == Map.singleton x Set.empty
-- adjacencyMap (edge 1 1) == Map.singleton 1 (Set.singleton 1)
-- adjacencyMap (edge 1 2) == Map.fromList [(1,Set.singleton 2), (2,Set.empty)]
--
[adjacencyMap] :: AdjacencyMap a -> Map a (Set a)
-- | Construct the empty graph. Complexity: O(1) time and
-- memory.
--
--
-- isEmpty empty == True
-- hasVertex x empty == False
-- vertexCount empty == 0
-- edgeCount empty == 0
--
empty :: AdjacencyMap a
-- | Construct the graph comprising a single isolated vertex.
-- Complexity: O(1) time and memory.
--
--
-- isEmpty (vertex x) == False
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
--
vertex :: a -> AdjacencyMap 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
--
overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
-- | Connect two graphs. 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 x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
-- | Construct a graph from a list of adjacency sets. Complexity: O((n +
-- m) * log(n)) time and O(n + m) memory.
--
--
-- fromAdjacencySets [] == empty
-- fromAdjacencySets [(x, Set.empty)] == vertex x
-- fromAdjacencySets [(x, Set.singleton y)] == edge x y
-- fromAdjacencySets . map (fmap Set.fromList) . adjacencyList == id
-- overlay (fromAdjacencySets xs) (fromAdjacencySets ys) == fromAdjacencySets (xs ++ ys)
--
fromAdjacencySets :: Ord a => [(a, Set a)] -> AdjacencyMap a
-- | Check if the internal graph representation is consistent, i.e. that
-- all edges refer to existing vertices. 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 empty == True
-- 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
--
consistent :: Ord a => AdjacencyMap a -> Bool
instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a)
-- | 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 various internal utilities and data structures
-- used throughout the library, such as lists with fast concatenation.
-- The API is unstable and unsafe, and is exposed only for documentation.
module Algebra.Graph.Internal
-- | An abstract list data type with O(1) time concatenation (the
-- current implementation uses difference lists). Here a is the
-- type of list elements. List a is a Monoid:
-- mempty corresponds to the empty list and two lists can be
-- concatenated with mappend (or operator <>).
-- Singleton lists can be constructed using the function pure from
-- the Applicative instance. List a is also an
-- instance of IsList, therefore you can use list literals, e.g.
-- [1,4] :: List Int is the same as
-- pure 1 <> pure 4; note
-- that this requires the OverloadedLists GHC extension. To
-- extract plain Haskell lists you can use the toList function
-- from the Foldable instance.
newtype List a
List :: (Endo [a]) -> List a
-- | The focus of a graph expression is a flattened represenentation
-- of the subgraph under focus, its context, as well as the list of all
-- encountered vertices. See removeEdge for a use-case example.
data Focus a
-- | All vertices (leaves) of the graph expression.
Focus :: Bool -> List a -> List a -> List a -> Focus a
-- | True if focus on the specified subgraph is obtained.
[ok] :: Focus a -> Bool
-- | Inputs into the focused subgraph.
[is] :: Focus a -> List a
-- | Outputs out of the focused subgraph.
[os] :: Focus a -> List a
[vs] :: Focus a -> List a
-- | Focus on the empty graph.
emptyFocus :: Focus a
-- | Focus on the graph with a single vertex, given a predicate indicating
-- whether the vertex is of interest.
vertexFocus :: (a -> Bool) -> a -> Focus a
-- | Overlay two foci.
overlayFoci :: Focus a -> Focus a -> Focus a
-- | Connect two foci.
connectFoci :: Focus a -> Focus a -> Focus a
-- | An auxiliary data type for hasEdge: when searching for an
-- edge, we can hit its Tail, i.e. the source vertex, the whole
-- Edge, or Miss it entirely.
data Hit
Miss :: Hit
Tail :: Hit
Edge :: Hit
-- | A safe version of foldr1
foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a
instance GHC.Classes.Ord Algebra.Graph.Internal.Hit
instance GHC.Classes.Eq Algebra.Graph.Internal.Hit
instance GHC.Base.Semigroup (Algebra.Graph.Internal.List a)
instance GHC.Base.Monoid (Algebra.Graph.Internal.List a)
instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Internal.List a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Internal.List a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Internal.List a)
instance GHC.Exts.IsList (Algebra.Graph.Internal.List a)
instance Data.Foldable.Foldable Algebra.Graph.Internal.List
instance GHC.Base.Functor Algebra.Graph.Internal.List
instance GHC.Base.Applicative Algebra.Graph.Internal.List
instance GHC.Base.Monad Algebra.Graph.Internal.List
-- | 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 basic data types and type classes for
-- representing edge labels in edge-labelled graphs, e.g. see
-- Algebra.Graph.Labelled.
module Algebra.Graph.Label
-- | A bounded join semilattice, satisfying the following laws:
--
--
class Semilattice a
zero :: Semilattice a => a
(\/) :: Semilattice a => a -> a -> a
-- | A dioid is an idempotent semiring, i.e. it satisfies the
-- following laws:
--
--
-- - Associativity:
x /\ (y /\ z) == (x /\ y) /\ z
-- - Identity:
x /\ one == x one /\ x == x
-- - Annihilating zero:
x /\ zero == zero zero /\ x ==
-- zero
-- - Distributivity:
x /\ (y \/ z) == x /\ y \/ x /\ z (x \/ y) /\
-- z == x /\ z \/ y /\ z
--
class Semilattice a => Dioid a
one :: Dioid a => a
(/\) :: Dioid a => a -> a -> a
-- | A distance is a non-negative value that can be Finite or
-- Infinite.
data Distance a
Finite :: a -> Distance a
Infinite :: Distance a
instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Label.Distance a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.Distance a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.Distance a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Label.Distance a)
instance GHC.Classes.Ord a => Algebra.Graph.Label.Semilattice (Algebra.Graph.Label.Distance a)
instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.Dioid (Algebra.Graph.Label.Distance a)
instance Algebra.Graph.Label.Dioid GHC.Types.Bool
instance Algebra.Graph.Label.Semilattice GHC.Types.Bool
instance GHC.Classes.Ord a => Algebra.Graph.Label.Semilattice (Data.Set.Internal.Set a)
-- | This module exposes the implementation of the Relation data
-- type. The API is unstable and unsafe, and is exposed only for
-- documentation. You should use the non-internal module
-- Algebra.Graph.Relation instead.
module Algebra.Graph.Relation.Internal
-- | The Relation data type represents a graph as a binary
-- relation. 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))
--
--
-- The Show instance is defined using basic graph construction
-- primitives:
--
--
-- show (empty :: Relation Int) == "empty"
-- show (1 :: Relation Int) == "vertex 1"
-- show (1 + 2 :: Relation Int) == "vertices [1,2]"
-- show (1 * 2 :: Relation Int) == "edge 1 2"
-- show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]"
-- show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"
--
--
-- The Eq instance satisfies all axioms of algebraic graphs:
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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.
data Relation a
Relation :: Set a -> Set (a, a) -> Relation a
-- | The domain of the relation.
[domain] :: Relation a -> Set a
-- | The set of pairs of elements that are related. It is guaranteed
-- that each element belongs to the domain.
[relation] :: Relation a -> Set (a, a)
-- | Construct the empty graph. Complexity: O(1) time and
-- memory.
--
--
-- isEmpty empty == True
-- hasVertex x empty == False
-- vertexCount empty == 0
-- edgeCount empty == 0
--
empty :: Relation a
-- | Construct the graph comprising a single isolated vertex.
-- Complexity: O(1) time and memory.
--
--
-- isEmpty (vertex x) == False
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
--
vertex :: a -> Relation 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 && 'iAlgebra.Graph.Relation.sEmpty' 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
--
overlay :: Ord a => Relation a -> Relation a -> Relation a
-- | Connect two graphs. 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 x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: Ord a => Relation a -> Relation a -> Relation a
-- | Compute the Cartesian product of two sets. Note: this function is
-- for internal use only.
setProduct :: Set a -> Set b -> Set (a, b)
-- | Check if the internal representation of a relation is consistent, i.e.
-- if all pairs of elements in the relation refer to existing
-- elements in the domain. It should be impossible to create an
-- inconsistent Relation, and we use this function in testing.
-- Note: this function is for internal use only.
--
--
-- consistent empty == True
-- 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
--
consistent :: Ord a => Relation a -> Bool
-- | The set of elements that appear in a given set of pairs. Note: this
-- function is for internal use only.
referredToVertexSet :: Ord a => Set (a, a) -> Set a
instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Relation.Internal.Relation a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.Internal.Relation a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.Internal.Relation a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.Internal.Relation a)
-- | 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 Relation data type, as well as
-- associated operations and algorithms. Relation is an instance
-- of the Graph type class, which can be used for polymorphic
-- graph construction and manipulation.
module Algebra.Graph.Relation
-- | The Relation data type represents a graph as a binary
-- relation. 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))
--
--
-- The Show instance is defined using basic graph construction
-- primitives:
--
--
-- show (empty :: Relation Int) == "empty"
-- show (1 :: Relation Int) == "vertex 1"
-- show (1 + 2 :: Relation Int) == "vertices [1,2]"
-- show (1 * 2 :: Relation Int) == "edge 1 2"
-- show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]"
-- show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"
--
--
-- The Eq instance satisfies all axioms of algebraic graphs:
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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.
data Relation a
-- | The domain of the relation.
domain :: Relation a -> Set a
-- | The set of pairs of elements that are related. It is guaranteed
-- that each element belongs to the domain.
relation :: Relation a -> Set (a, a)
-- | Construct the empty graph. Complexity: O(1) time and
-- memory.
--
--
-- isEmpty empty == True
-- hasVertex x empty == False
-- vertexCount empty == 0
-- edgeCount empty == 0
--
empty :: Relation a
-- | Construct the graph comprising a single isolated vertex.
-- Complexity: O(1) time and memory.
--
--
-- isEmpty (vertex x) == False
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
--
vertex :: a -> Relation a
-- | Construct the graph comprising a single edge. Complexity:
-- O(1) time, memory and size.
--
--
-- edge x y == connect (vertex x) (vertex y)
-- hasEdge x y (edge x y) == True
-- edgeCount (edge x y) == 1
-- vertexCount (edge 1 1) == 1
-- vertexCount (edge 1 2) == 2
--
edge :: Ord a => a -> a -> Relation 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 && 'iAlgebra.Graph.Relation.sEmpty' 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
--
overlay :: Ord a => Relation a -> Relation a -> Relation a
-- | Connect two graphs. 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 x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: Ord a => Relation a -> Relation a -> Relation 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
-- hasVertex x . vertices == elem x
-- vertexCount . vertices == length . nub
-- vertexSet . vertices == Set.fromList
--
vertices :: Ord a => [a] -> Relation a
-- | Construct the graph from a list of edges. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- edges [] == empty
-- edges [(x,y)] == edge x y
-- edgeCount . edges == length . nub
--
edges :: Ord a => [(a, a)] -> Relation 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
--
overlays :: Ord a => [Relation a] -> Relation a
-- | Connect a given list of graphs. Complexity: O((n + m) * log(n))
-- time and O(n + m) memory.
--
--
-- connects [] == empty
-- connects [x] == x
-- connects [x,y] == connect x y
-- connects == foldr connect empty
-- isEmpty . connects == all isEmpty
--
connects :: Ord a => [Relation a] -> Relation a
-- | 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.
--
--
-- isSubgraphOf empty 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 :: Ord a => Relation a -> Relation a -> Bool
-- | Check if a relation 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 x y) == False
--
isEmpty :: Relation a -> Bool
-- | Check if a graph contains a given vertex. Complexity: O(log(n))
-- time.
--
--
-- hasVertex x empty == False
-- hasVertex x (vertex x) == True
-- hasVertex 1 (vertex 2) == False
-- hasVertex x . removeVertex x == const False
--
hasVertex :: Ord a => a -> Relation 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 x y) == True
-- hasEdge x y . removeEdge x y == const False
-- hasEdge x y == elem (x,y) . edgeList
--
hasEdge :: Ord a => a -> a -> Relation a -> Bool
-- | The number of vertices in a graph. Complexity: O(1) time.
--
--
-- vertexCount empty == 0
-- vertexCount (vertex x) == 1
-- vertexCount == length . vertexList
--
vertexCount :: Relation a -> Int
-- | The number of edges in a graph. Complexity: O(1) time.
--
--
-- edgeCount empty == 0
-- edgeCount (vertex x) == 0
-- edgeCount (edge x y) == 1
-- edgeCount == length . edgeList
--
edgeCount :: Relation a -> Int
-- | 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
--
vertexList :: Relation a -> [a]
-- | The sorted list of edges of a graph. Complexity: O(n + m) time
-- and O(m) memory.
--
--
-- edgeList empty == []
-- edgeList (vertex x) == []
-- edgeList (edge x y) == [(x,y)]
-- edgeList (star 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . edges == nub . sort
-- edgeList . transpose == sort . map swap . edgeList
--
edgeList :: Relation a -> [(a, a)]
-- | The sorted adjacency list of a graph. Complexity: O(n +
-- m) time and O(m) memory.
--
--
-- adjacencyList empty == []
-- adjacencyList (vertex x) == [(x, [])]
-- adjacencyList (edge 1 2) == [(1, [2]), (2, [])]
-- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]
-- stars . adjacencyList == id
--
adjacencyList :: Eq a => Relation a -> [(a, [a])]
-- | The set of vertices of a given graph. Complexity: O(1) time.
--
--
-- vertexSet empty == Set.empty
-- vertexSet . vertex == Set.singleton
-- vertexSet . vertices == Set.fromList
-- vertexSet . clique == Set.fromList
--
vertexSet :: Relation a -> Set a
-- | The set of vertices of a given graph. Like vertexSet but
-- specialised for graphs with vertices of type Int. Complexity:
-- O(n) time.
--
--
-- vertexIntSet empty == IntSet.empty
-- vertexIntSet . vertex == IntSet.singleton
-- vertexIntSet . vertices == IntSet.fromList
-- vertexIntSet . clique == IntSet.fromList
--
vertexIntSet :: Relation Int -> IntSet
-- | The set of edges of a given graph. Complexity: O(1) time.
--
--
-- edgeSet empty == Set.empty
-- edgeSet (vertex x) == Set.empty
-- edgeSet (edge x y) == Set.singleton (x,y)
-- edgeSet . edges == Set.fromList
--
edgeSet :: Relation a -> Set (a, a)
-- | The preset of an element x is the set of elements that
-- are related to it on the left, i.e. preSet x == { a | aRx
-- }. In the context of directed graphs, this corresponds to the set
-- of direct predecessors of vertex x. Complexity: O(n
-- + m) time and O(n) memory.
--
--
-- preSet x empty == Set.empty
-- preSet x (vertex x) == Set.empty
-- preSet 1 (edge 1 2) == Set.empty
-- preSet y (edge x y) == Set.fromList [x]
--
preSet :: Ord a => a -> Relation a -> Set a
-- | The postset of an element x is the set of elements
-- that are related to it on the right, i.e. postSet x == { a
-- | xRa }. In the context of directed graphs, this corresponds to
-- the set of direct successors of vertex x. Complexity:
-- O(n + m) time and O(n) memory.
--
--
-- postSet x empty == Set.empty
-- postSet x (vertex x) == Set.empty
-- postSet x (edge x y) == Set.fromList [y]
-- postSet 2 (edge 1 2) == Set.empty
--
postSet :: Ord a => a -> Relation a -> Set a
-- | The path on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- path [] == empty
-- path [x] == vertex x
-- path [x,y] == edge x y
-- path . reverse == transpose . path
--
path :: Ord a => [a] -> Relation a
-- | The circuit on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- circuit [] == empty
-- circuit [x] == edge x x
-- circuit [x,y] == edges [(x,y), (y,x)]
-- circuit . reverse == transpose . circuit
--
circuit :: Ord a => [a] -> Relation a
-- | The clique on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- 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 == transpose . clique
--
clique :: Ord a => [a] -> Relation a
-- | The biclique on two lists of vertices. Complexity: O(n *
-- log(n) + m) time and O(n + m) memory.
--
--
-- biclique [] [] == empty
-- biclique [x] [] == vertex x
-- biclique [] [y] == vertex y
-- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
-- biclique xs ys == connect (vertices xs) (vertices ys)
--
biclique :: Ord a => [a] -> [a] -> Relation a
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges [(x,y), (x,z)]
-- star x ys == connect (vertex x) (vertices ys)
--
star :: Ord a => a -> [a] -> Relation a
-- | The stars formed by overlaying a list of stars. An
-- inverse of adjacencyList. Complexity: O(L * log(n))
-- 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 == id
-- overlay (stars xs) (stars ys) == stars (xs ++ ys)
--
stars :: Ord a => [(a, [a])] -> Relation a
-- | The tree graph constructed from a given Tree data
-- structure. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- 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)]
--
tree :: Ord a => Tree a -> Relation a
-- | The forest graph constructed from a given Forest data
-- structure. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- 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
--
forest :: Ord a => Forest a -> Relation a
-- | Remove a vertex from a given graph. Complexity: O(n + m) time.
--
--
-- removeVertex x (vertex x) == empty
-- removeVertex 1 (vertex 2) == vertex 2
-- removeVertex x (edge x x) == empty
-- removeVertex 1 (edge 1 2) == vertex 2
-- removeVertex x . removeVertex x == removeVertex x
--
removeVertex :: Ord a => a -> Relation a -> Relation a
-- | Remove an edge from a given graph. Complexity: O(log(m)) time.
--
--
-- removeEdge x y (edge 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
--
removeEdge :: Ord a => a -> a -> Relation a -> Relation 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 == mergeVertices (== x) y
--
replaceVertex :: Ord a => a -> a -> Relation a -> Relation a
-- | Merge vertices satisfying a given predicate into a given vertex.
-- Complexity: O((n + m) * log(n)) time, assuming that the
-- predicate takes O(1) to be evaluated.
--
--
-- mergeVertices (const False) x == id
-- mergeVertices (== x) y == replaceVertex x y
-- mergeVertices even 1 (0 * 2) == 1 * 1
-- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1
--
mergeVertices :: Ord a => (a -> Bool) -> a -> Relation a -> Relation a
-- | Transpose a given graph. Complexity: O(m * log(m)) time.
--
--
-- transpose empty == empty
-- transpose (vertex x) == vertex x
-- transpose (edge x y) == edge y x
-- transpose . transpose == id
-- edgeList . transpose == sort . map swap . edgeList
--
transpose :: Ord a => Relation a -> Relation a
-- | 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 Relation. Complexity: O((n + m) *
-- log(n)) time.
--
--
-- gmap f empty == empty
-- gmap f (vertex x) == vertex (f x)
-- gmap f (edge x y) == edge (f x) (f y)
-- gmap id == id
-- gmap f . gmap g == gmap (f . g)
--
gmap :: Ord b => (a -> b) -> Relation a -> Relation b
-- | Construct the induced subgraph of a given graph by removing the
-- vertices that do not satisfy a given predicate. Complexity:
-- O(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
--
induce :: (a -> Bool) -> Relation a -> Relation a
-- | Compose two relations: R = compose Q P. Two
-- elements x and y are related in the resulting
-- relation, i.e. xRy, if there exists an element z,
-- such that xPz and zQy. This is an associative
-- operation which has empty as the annihilating zero.
-- Complexity: O(n * m * log(m)) time and O(n + m) memory.
--
--
-- compose empty x == empty
-- compose x empty == empty
-- compose x (compose y z) == compose (compose x y) z
-- compose (edge y z) (edge x y) == edge x z
-- compose (path [1..5]) (path [1..5]) == edges [(1,3),(2,4),(3,5)]
-- compose (circuit [1..5]) (circuit [1..5]) == circuit [1,3,5,2,4]
--
compose :: Ord a => Relation a -> Relation a -> Relation a
-- | Compute the reflexive closure of a Relation. Complexity:
-- O(n * log(m)) time.
--
--
-- reflexiveClosure empty == empty
-- reflexiveClosure (vertex x) == edge x x
--
reflexiveClosure :: Ord a => Relation a -> Relation a
-- | Compute the symmetric closure of a Relation. Complexity:
-- O(m * log(m)) time.
--
--
-- symmetricClosure empty == empty
-- symmetricClosure (vertex x) == vertex x
-- symmetricClosure (edge x y) == edges [(x, y), (y, x)]
--
symmetricClosure :: Ord a => Relation a -> Relation a
-- | Compute the transitive closure of a Relation.
-- Complexity: O(n * m * log(n) * log(m)) time.
--
--
-- transitiveClosure empty == empty
-- transitiveClosure (vertex x) == vertex x
-- transitiveClosure (path $ nub xs) == clique (nub xs)
--
transitiveClosure :: Ord a => Relation a -> Relation a
-- | Compute the preorder closure of a Relation. Complexity:
-- O(n * m * log(m)) time.
--
--
-- preorderClosure empty == empty
-- preorderClosure (vertex x) == edge x x
-- preorderClosure (path $ nub xs) == reflexiveClosure (clique $ nub xs)
--
preorderClosure :: Ord a => Relation a -> Relation a
-- | 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 primitives for interoperability between this
-- library and the Data.Graph module of the containers library. It
-- is for internal use only and may be removed without notice at any
-- point.
module Data.Graph.Typed
-- | GraphKL encapsulates King-Launchbury graphs, which are
-- implemented in the Data.Graph module of the containers
-- library.
data GraphKL a
GraphKL :: Graph -> Vertex -> a -> a -> Maybe Vertex -> GraphKL a
-- | Array-based graph representation (King and Launchbury, 1995).
[toGraphKL] :: GraphKL a -> Graph
-- | A mapping of Data.Graph.Vertex to vertices of type a.
-- This is partial and may fail if the vertex is out of bounds.
[fromVertexKL] :: GraphKL a -> Vertex -> a
-- | A mapping from vertices of type a to
-- Data.Graph.Vertex. Returns Nothing if the argument is
-- not in the graph.
[toVertexKL] :: GraphKL a -> a -> Maybe Vertex
-- | Build GraphKL from an AdjacencyMap. If
-- fromAdjacencyMap g == h then the following holds:
--
--
-- map (fromVertexKL h) (vertices $ toGraphKL h) == vertexList g
-- map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g
-- toGraphKL (fromAdjacencyMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])]
-- toGraphKL (fromAdjacencyMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])]
--
fromAdjacencyMap :: Ord a => AdjacencyMap a -> GraphKL a
-- | Build GraphKL from an AdjacencyIntMap. If
-- fromAdjacencyIntMap g == h then the following holds:
--
--
-- map (fromVertexKL h) (vertices $ toGraphKL h) == toAscList (vertexIntSet g)
-- map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g
-- toGraphKL (fromAdjacencyIntMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])]
-- toGraphKL (fromAdjacencyIntMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])]
--
fromAdjacencyIntMap :: AdjacencyIntMap -> GraphKL Int
-- | Compute the depth-first search forest of a graph.
--
-- In the following we will use the helper function:
--
--
-- (%) :: (GraphKL Int -> a) -> AM.AdjacencyMap Int -> a
-- a % g = a $ fromAdjacencyMap g
--
--
-- for greater clarity. (One could use an AdjacencyIntMap just as well)
--
--
-- forest (dfsForest % edge 1 1) == vertex 1
-- forest (dfsForest % edge 1 2) == edge 1 2
-- forest (dfsForest % edge 2 1) == vertices [1, 2]
-- isSubgraphOf (forest $ dfsForest % x) x == True
-- dfsForest % forest (dfsForest % x) == dfsForest % x
-- dfsForest % vertices vs == map (\v -> Node v []) (nub $ sort vs)
-- dfsForestFrom (vertexList x) % x == dfsForest % x
-- dfsForest % (3 * (1 + 4) * (1 + 5)) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }]}
-- , Node { rootLabel = 3
-- , subForest = [ Node { rootLabel = 4
-- , subForest = [] }]}]
--
dfsForest :: GraphKL a -> Forest a
-- | Compute the depth-first search forest of a graph, searching
-- from each of the given vertices in order. Note that the resulting
-- forest does not necessarily span the whole graph, as some vertices may
-- be unreachable.
--
--
-- forest (dfsForestFrom [1] % edge 1 1) == vertex 1
-- forest (dfsForestFrom [1] % edge 1 2) == edge 1 2
-- forest (dfsForestFrom [2] % edge 1 2) == vertex 2
-- forest (dfsForestFrom [3] % edge 1 2) == empty
-- forest (dfsForestFrom [2, 1] % edge 1 2) == vertices [1, 2]
-- isSubgraphOf (forest $ dfsForestFrom vs % x) x == True
-- dfsForestFrom (vertexList x) % x == dfsForest % x
-- dfsForestFrom vs % vertices vs == map (\v -> Node v []) (nub vs)
-- dfsForestFrom [] % x == []
-- dfsForestFrom [1, 4] % (3 * (1 + 4) * (1 + 5)) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }
-- , Node { rootLabel = 4
-- , subForest = [] }]
--
dfsForestFrom :: [a] -> GraphKL a -> Forest a
-- | Compute the list of vertices visited by the depth-first search
-- in a graph, when searching from each of the given vertices in order.
--
--
-- dfs [1] % edge 1 1 == [1]
-- dfs [1] % edge 1 2 == [1,2]
-- dfs [2] % edge 1 2 == [2]
-- dfs [3] % edge 1 2 == []
-- dfs [1,2] % edge 1 2 == [1,2]
-- dfs [2,1] % edge 1 2 == [2,1]
-- dfs [] % x == []
-- dfs [1,4] % (3 * (1 + 4) * (1 + 5)) == [1, 5, 4]
-- isSubgraphOf (vertices $ dfs vs x) x == True
--
dfs :: [a] -> GraphKL a -> [a]
-- | Compute the topological sort of a graph. Unlike the
-- (Int)AdjacencyMap algorithm this returns a result even if the graph is
-- cyclic.
--
--
-- topSort % (1 * 2 + 3 * 1) == [3,1,2]
-- topSort % (1 * 2 + 2 * 1) == [1,2]
--
topSort :: GraphKL a -> [a]
-- | 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, as well as
-- associated operations and algorithms. AdjacencyMap is an
-- instance of the Graph type class, which can be used for
-- polymorphic graph construction and manipulation.
-- Algebra.Graph.AdjacencyIntMap defines adjacency maps
-- specialised to graphs with Int vertices.
module Algebra.Graph.AdjacencyMap
-- | 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))
--
--
-- The Show instance is defined using basic graph construction
-- primitives:
--
--
-- show (empty :: AdjacencyMap Int) == "empty"
-- show (1 :: AdjacencyMap Int) == "vertex 1"
-- show (1 + 2 :: AdjacencyMap Int) == "vertices [1,2]"
-- show (1 * 2 :: AdjacencyMap Int) == "edge 1 2"
-- show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
-- show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"
--
--
-- The Eq instance satisfies all axioms of algebraic graphs:
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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.
data AdjacencyMap a
-- | The adjacency map of the graph: each vertex is associated with
-- a set of its direct successors. Complexity: O(1) time and
-- memory.
--
--
-- adjacencyMap empty == Map.empty
-- adjacencyMap (vertex x) == Map.singleton x Set.empty
-- adjacencyMap (edge 1 1) == Map.singleton 1 (Set.singleton 1)
-- adjacencyMap (edge 1 2) == Map.fromList [(1,Set.singleton 2), (2,Set.empty)]
--
adjacencyMap :: AdjacencyMap a -> Map a (Set a)
-- | Construct the empty graph. Complexity: O(1) time and
-- memory.
--
--
-- isEmpty empty == True
-- hasVertex x empty == False
-- vertexCount empty == 0
-- edgeCount empty == 0
--
empty :: AdjacencyMap a
-- | Construct the graph comprising a single isolated vertex.
-- Complexity: O(1) time and memory.
--
--
-- isEmpty (vertex x) == False
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
--
vertex :: a -> AdjacencyMap a
-- | Construct the graph comprising a single edge. Complexity:
-- O(1) time, memory.
--
--
-- edge x y == connect (vertex x) (vertex y)
-- hasEdge x y (edge x y) == True
-- edgeCount (edge x y) == 1
-- vertexCount (edge 1 1) == 1
-- vertexCount (edge 1 2) == 2
--
edge :: Ord a => a -> a -> AdjacencyMap 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
--
overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
-- | Connect two graphs. 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 x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap 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
-- hasVertex x . vertices == elem x
-- vertexCount . vertices == length . nub
-- vertexSet . vertices == Set.fromList
--
vertices :: Ord a => [a] -> AdjacencyMap a
-- | Construct the graph from a list of edges. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- edges [] == empty
-- edges [(x,y)] == edge x y
-- edgeCount . edges == length . nub
-- edgeList . edges == nub . sort
--
edges :: Ord a => [(a, a)] -> AdjacencyMap 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
--
overlays :: Ord a => [AdjacencyMap a] -> AdjacencyMap a
-- | Connect a given list of graphs. Complexity: O((n + m) * log(n))
-- time and O(n + m) memory.
--
--
-- connects [] == empty
-- connects [x] == x
-- connects [x,y] == connect x y
-- connects == foldr connect empty
-- isEmpty . connects == all isEmpty
--
connects :: Ord a => [AdjacencyMap a] -> AdjacencyMap a
-- | 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.
--
--
-- isSubgraphOf empty 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 :: Ord a => AdjacencyMap a -> AdjacencyMap 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 x y) == False
--
isEmpty :: AdjacencyMap a -> Bool
-- | Check if a graph contains a given vertex. Complexity: O(log(n))
-- time.
--
--
-- hasVertex x empty == False
-- hasVertex x (vertex x) == True
-- hasVertex 1 (vertex 2) == False
-- hasVertex x . removeVertex x == const False
--
hasVertex :: Ord a => a -> AdjacencyMap 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 x y) == True
-- hasEdge x y . removeEdge x y == const False
-- hasEdge x y == elem (x,y) . edgeList
--
hasEdge :: Ord a => a -> a -> AdjacencyMap a -> Bool
-- | The number of vertices in a graph. Complexity: O(1) time.
--
--
-- vertexCount empty == 0
-- vertexCount (vertex x) == 1
-- vertexCount == length . vertexList
--
vertexCount :: AdjacencyMap a -> Int
-- | The number of edges in a graph. Complexity: O(n) time.
--
--
-- edgeCount empty == 0
-- edgeCount (vertex x) == 0
-- edgeCount (edge x y) == 1
-- edgeCount == length . edgeList
--
edgeCount :: AdjacencyMap a -> Int
-- | 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
--
vertexList :: AdjacencyMap a -> [a]
-- | The sorted list of edges of a graph. Complexity: O(n + m) time
-- and O(m) memory.
--
--
-- edgeList empty == []
-- edgeList (vertex x) == []
-- edgeList (edge x y) == [(x,y)]
-- edgeList (star 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . edges == nub . sort
-- edgeList . transpose == sort . map swap . edgeList
--
edgeList :: AdjacencyMap a -> [(a, a)]
-- | The sorted adjacency list of a graph. Complexity: O(n +
-- m) time and O(m) memory.
--
--
-- adjacencyList empty == []
-- adjacencyList (vertex x) == [(x, [])]
-- adjacencyList (edge 1 2) == [(1, [2]), (2, [])]
-- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]
-- stars . adjacencyList == id
--
adjacencyList :: AdjacencyMap a -> [(a, [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
-- vertexSet . clique == Set.fromList
--
vertexSet :: AdjacencyMap a -> Set a
-- | The set of vertices of a given graph. Like vertexSet but
-- specialised for graphs with vertices of type Int. Complexity:
-- O(n) time and memory.
--
--
-- vertexIntSet empty == IntSet.empty
-- vertexIntSet . vertex == IntSet.singleton
-- vertexIntSet . vertices == IntSet.fromList
-- vertexIntSet . clique == IntSet.fromList
--
vertexIntSet :: AdjacencyMap Int -> IntSet
-- | The set of edges of a given graph. Complexity: O((n + m) *
-- log(m)) time and O(m) memory.
--
--
-- edgeSet empty == Set.empty
-- edgeSet (vertex x) == Set.empty
-- edgeSet (edge x y) == Set.singleton (x,y)
-- edgeSet . edges == Set.fromList
--
edgeSet :: Ord a => AdjacencyMap a -> Set (a, 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 1 2) == Set.empty
-- preSet y (edge x y) == Set.fromList [x]
--
preSet :: Ord a => a -> AdjacencyMap 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 x y) == Set.fromList [y]
-- postSet 2 (edge 1 2) == Set.empty
--
postSet :: Ord a => a -> AdjacencyMap a -> Set a
-- | The path on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- path [] == empty
-- path [x] == vertex x
-- path [x,y] == edge x y
-- path . reverse == transpose . path
--
path :: Ord a => [a] -> AdjacencyMap a
-- | The circuit on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- circuit [] == empty
-- circuit [x] == edge x x
-- circuit [x,y] == edges [(x,y), (y,x)]
-- circuit . reverse == transpose . circuit
--
circuit :: Ord a => [a] -> AdjacencyMap a
-- | The clique on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- 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 == transpose . clique
--
clique :: Ord a => [a] -> AdjacencyMap a
-- | The biclique on two lists of vertices. Complexity: O(n *
-- log(n) + m) time and O(n + m) memory.
--
--
-- biclique [] [] == empty
-- biclique [x] [] == vertex x
-- biclique [] [y] == vertex y
-- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
-- biclique xs ys == connect (vertices xs) (vertices ys)
--
biclique :: Ord a => [a] -> [a] -> AdjacencyMap a
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges [(x,y), (x,z)]
-- star x ys == connect (vertex x) (vertices ys)
--
star :: Ord a => a -> [a] -> AdjacencyMap a
-- | The stars formed by overlaying a list of stars. An
-- inverse of adjacencyList. Complexity: O(L * log(n))
-- 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 == id
-- overlay (stars xs) (stars ys) == stars (xs ++ ys)
--
stars :: Ord a => [(a, [a])] -> AdjacencyMap a
-- | The tree graph constructed from a given Tree data
-- structure. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- 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)]
--
tree :: Ord a => Tree a -> AdjacencyMap a
-- | The forest graph constructed from a given Forest data
-- structure. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- 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
--
forest :: Ord a => Forest a -> AdjacencyMap 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 x x) == empty
-- removeVertex 1 (edge 1 2) == vertex 2
-- removeVertex x . removeVertex x == removeVertex x
--
removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a
-- | Remove an edge from a given graph. Complexity: O(log(n)) time.
--
--
-- removeEdge x y (edge 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
--
removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap 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 == mergeVertices (== x) y
--
replaceVertex :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a
-- | Merge vertices satisfying a given predicate into a given vertex.
-- Complexity: O((n + m) * log(n)) time, assuming that the
-- predicate takes O(1) to be evaluated.
--
--
-- mergeVertices (const False) x == id
-- mergeVertices (== x) y == replaceVertex x y
-- mergeVertices even 1 (0 * 2) == 1 * 1
-- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1
--
mergeVertices :: Ord a => (a -> Bool) -> a -> AdjacencyMap a -> AdjacencyMap 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 x y) == edge y x
-- transpose . transpose == id
-- edgeList . transpose == sort . map swap . edgeList
--
transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a
-- | 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 x y) == edge (f x) (f y)
-- gmap id == id
-- gmap f . gmap g == gmap (f . g)
--
gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b
-- | Construct the induced subgraph of a given graph by removing the
-- vertices that do not satisfy a given predicate. Complexity:
-- O(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
--
induce :: (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a
-- | Compute the depth-first search forest of a graph that
-- corresponds to searching from each of the graph vertices in the
-- Ord a order.
--
--
-- dfsForest empty == []
-- forest (dfsForest $ edge 1 1) == vertex 1
-- forest (dfsForest $ edge 1 2) == edge 1 2
-- forest (dfsForest $ edge 2 1) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForest x) x == True
-- isDfsForestOf (dfsForest x) x == True
-- dfsForest . forest . dfsForest == dfsForest
-- dfsForest (vertices vs) == map (\v -> Node v []) (nub $ sort vs)
-- dfsForestFrom (vertexList x) x == dfsForest x
-- dfsForest $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }]}
-- , Node { rootLabel = 3
-- , subForest = [ Node { rootLabel = 4
-- , subForest = [] }]}]
--
dfsForest :: Ord a => AdjacencyMap a -> Forest a
-- | Compute the depth-first search forest of a graph, searching
-- from each of the given vertices in order. Note that the resulting
-- forest does not necessarily span the whole graph, as some vertices may
-- be unreachable.
--
--
-- dfsForestFrom vs empty == []
-- forest (dfsForestFrom [1] $ edge 1 1) == vertex 1
-- forest (dfsForestFrom [1] $ edge 1 2) == edge 1 2
-- forest (dfsForestFrom [2] $ edge 1 2) == vertex 2
-- forest (dfsForestFrom [3] $ edge 1 2) == empty
-- forest (dfsForestFrom [2,1] $ edge 1 2) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForestFrom vs x) x == True
-- isDfsForestOf (dfsForestFrom (vertexList x) x) x == True
-- dfsForestFrom (vertexList x) x == dfsForest x
-- dfsForestFrom vs (vertices vs) == map (\v -> Node v []) (nub vs)
-- dfsForestFrom [] x == []
-- dfsForestFrom [1,4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }
-- , Node { rootLabel = 4
-- , subForest = [] }]
--
dfsForestFrom :: Ord a => [a] -> AdjacencyMap a -> Forest a
-- | Compute the list of vertices visited by the depth-first search
-- in a graph, when searching from each of the given vertices in order.
--
--
-- dfs vs $ empty == []
-- dfs [1] $ edge 1 1 == [1]
-- dfs [1] $ edge 1 2 == [1,2]
-- dfs [2] $ edge 1 2 == [2]
-- dfs [3] $ edge 1 2 == []
-- dfs [1,2] $ edge 1 2 == [1,2]
-- dfs [2,1] $ edge 1 2 == [2,1]
-- dfs [] $ x == []
-- dfs [1,4] $ 3 * (1 + 4) * (1 + 5) == [1,5,4]
-- isSubgraphOf (vertices $ dfs vs x) x == True
--
dfs :: Ord a => [a] -> AdjacencyMap a -> [a]
-- | Compute the list of vertices that are reachable from a given
-- source vertex in a graph. The vertices in the resulting list appear in
-- the depth-first order.
--
--
-- reachable x $ empty == []
-- reachable 1 $ vertex 1 == [1]
-- reachable 1 $ vertex 2 == []
-- reachable 1 $ edge 1 1 == [1]
-- reachable 1 $ edge 1 2 == [1,2]
-- reachable 4 $ path [1..8] == [4..8]
-- reachable 4 $ circuit [1..8] == [4..8] ++ [1..3]
-- reachable 8 $ clique [8,7..1] == [8] ++ [1..7]
-- isSubgraphOf (vertices $ reachable x y) y == True
--
reachable :: Ord a => a -> AdjacencyMap a -> [a]
-- | Compute the topological sort of a graph or return
-- Nothing if the graph is cyclic.
--
--
-- topSort (1 * 2 + 3 * 1) == Just [3,1,2]
-- topSort (1 * 2 + 2 * 1) == Nothing
-- fmap (flip isTopSortOf x) (topSort x) /= Just False
-- isJust . topSort == isAcyclic
--
topSort :: Ord a => AdjacencyMap a -> Maybe [a]
-- | Check if a given graph is acyclic.
--
--
-- isAcyclic (1 * 2 + 3 * 1) == True
-- isAcyclic (1 * 2 + 2 * 1) == False
-- isAcyclic . circuit == null
-- isAcyclic == isJust . topSort
--
isAcyclic :: Ord a => AdjacencyMap a -> Bool
-- | Compute the condensation of a graph, where each vertex
-- corresponds to a strongly-connected component of the original
-- graph.
--
--
-- scc empty == empty
-- scc (vertex x) == vertex (Set.singleton x)
-- scc (edge x y) == edge (Set.singleton x) (Set.singleton y)
-- scc (circuit (1:xs)) == edge (Set.fromList (1:xs)) (Set.fromList (1:xs))
-- scc (3 * 1 * 4 * 1 * 5) == edges [ (Set.fromList [1,4], Set.fromList [1,4])
-- , (Set.fromList [1,4], Set.fromList [5] )
-- , (Set.fromList [3] , Set.fromList [1,4])
-- , (Set.fromList [3] , Set.fromList [5] )]
--
scc :: Ord a => AdjacencyMap a -> AdjacencyMap (Set a)
-- | Check if a given forest is a correct depth-first search forest
-- of a graph. The implementation is based on the paper "Depth-First
-- Search and Strong Connectivity in Coq" by François Pottier.
--
--
-- isDfsForestOf [] empty == True
-- isDfsForestOf [] (vertex 1) == False
-- isDfsForestOf [Node 1 []] (vertex 1) == True
-- isDfsForestOf [Node 1 []] (vertex 2) == False
-- isDfsForestOf [Node 1 [], Node 1 []] (vertex 1) == False
-- isDfsForestOf [Node 1 []] (edge 1 1) == True
-- isDfsForestOf [Node 1 []] (edge 1 2) == False
-- isDfsForestOf [Node 1 [], Node 2 []] (edge 1 2) == False
-- isDfsForestOf [Node 2 [], Node 1 []] (edge 1 2) == True
-- isDfsForestOf [Node 1 [Node 2 []]] (edge 1 2) == True
-- isDfsForestOf [Node 1 [], Node 2 []] (vertices [1,2]) == True
-- isDfsForestOf [Node 2 [], Node 1 []] (vertices [1,2]) == True
-- isDfsForestOf [Node 1 [Node 2 []]] (vertices [1,2]) == False
-- isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (path [1,2,3]) == True
-- isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (path [1,2,3]) == False
-- isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (path [1,2,3]) == True
-- isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (path [1,2,3]) == True
-- isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] (path [1,2,3]) == False
--
isDfsForestOf :: Ord a => Forest a -> AdjacencyMap a -> Bool
-- | Check if a given list of vertices is a correct topological sort
-- of a graph.
--
--
-- isTopSortOf [3,1,2] (1 * 2 + 3 * 1) == True
-- isTopSortOf [1,2,3] (1 * 2 + 3 * 1) == False
-- isTopSortOf [] (1 * 2 + 3 * 1) == False
-- isTopSortOf [] empty == True
-- isTopSortOf [x] (vertex x) == True
-- isTopSortOf [x] (edge x x) == False
--
isTopSortOf :: Ord a => [a] -> AdjacencyMap a -> Bool
-- | 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 AdjacencyIntMap data type, as well as
-- associated operations and algorithms. AdjacencyIntMap is an
-- instance of the Graph type class, which can be used for
-- polymorphic graph construction and manipulation. See
-- Algebra.Graph.AdjacencyMap for graphs with non-Int
-- vertices.
module Algebra.Graph.AdjacencyIntMap
-- | The AdjacencyIntMap 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))
--
--
-- The Show instance is defined using basic graph construction
-- primitives:
--
--
-- show (empty :: AdjacencyIntMap Int) == "empty"
-- show (1 :: AdjacencyIntMap Int) == "vertex 1"
-- show (1 + 2 :: AdjacencyIntMap Int) == "vertices [1,2]"
-- show (1 * 2 :: AdjacencyIntMap Int) == "edge 1 2"
-- show (1 * 2 * 3 :: AdjacencyIntMap Int) == "edges [(1,2),(1,3),(2,3)]"
-- show (1 * 2 + 3 :: AdjacencyIntMap Int) == "overlay (vertex 3) (edge 1 2)"
--
--
-- The Eq instance satisfies all axioms of algebraic graphs:
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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.
data AdjacencyIntMap
-- | The adjacency map of the graph: each vertex is associated with
-- a set of its direct successors. Complexity: O(1) time and
-- memory.
--
--
-- adjacencyIntMap empty == IntMap.empty
-- adjacencyIntMap (vertex x) == IntMap.singleton x IntSet.empty
-- adjacencyIntMap (edge 1 1) == IntMap.singleton 1 (IntSet.singleton 1)
-- adjacencyIntMap (edge 1 2) == IntMap.fromList [(1,IntSet.singleton 2), (2,IntSet.empty)]
--
adjacencyIntMap :: AdjacencyIntMap -> IntMap IntSet
-- | Construct the empty graph. Complexity: O(1) time and
-- memory.
--
--
-- isEmpty empty == True
-- hasVertex x empty == False
-- vertexCount empty == 0
-- edgeCount empty == 0
--
empty :: AdjacencyIntMap
-- | Construct the graph comprising a single isolated vertex.
-- Complexity: O(1) time and memory.
--
--
-- isEmpty (vertex x) == False
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
--
vertex :: Int -> AdjacencyIntMap
-- | Construct the graph comprising a single edge. Complexity:
-- O(1) time, memory.
--
--
-- edge x y == connect (vertex x) (vertex y)
-- hasEdge x y (edge x y) == True
-- edgeCount (edge x y) == 1
-- vertexCount (edge 1 1) == 1
-- vertexCount (edge 1 2) == 2
--
edge :: Int -> Int -> AdjacencyIntMap
-- | 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
--
overlay :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
-- | Connect two graphs. 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 x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
-- | 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
-- hasVertex x . vertices == elem x
-- vertexCount . vertices == length . nub
-- vertexIntSet . vertices == IntSet.fromList
--
vertices :: [Int] -> AdjacencyIntMap
-- | Construct the graph from a list of edges. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- edges [] == empty
-- edges [(x,y)] == edge x y
-- edgeCount . edges == length . nub
-- edgeList . edges == nub . sort
--
edges :: [(Int, Int)] -> AdjacencyIntMap
-- | 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
--
overlays :: [AdjacencyIntMap] -> AdjacencyIntMap
-- | Connect a given list of graphs. Complexity: O((n + m) * log(n))
-- time and O(n + m) memory.
--
--
-- connects [] == empty
-- connects [x] == x
-- connects [x,y] == connect x y
-- connects == foldr connect empty
-- isEmpty . connects == all isEmpty
--
connects :: [AdjacencyIntMap] -> AdjacencyIntMap
-- | 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.
--
--
-- isSubgraphOf empty 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 :: AdjacencyIntMap -> AdjacencyIntMap -> 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 x y) == False
--
isEmpty :: AdjacencyIntMap -> Bool
-- | Check if a graph contains a given vertex. Complexity: O(log(n))
-- time.
--
--
-- hasVertex x empty == False
-- hasVertex x (vertex x) == True
-- hasVertex 1 (vertex 2) == False
-- hasVertex x . removeVertex x == const False
--
hasVertex :: Int -> AdjacencyIntMap -> 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 x y) == True
-- hasEdge x y . removeEdge x y == const False
-- hasEdge x y == elem (x,y) . edgeList
--
hasEdge :: Int -> Int -> AdjacencyIntMap -> Bool
-- | The number of vertices in a graph. Complexity: O(1) time.
--
--
-- vertexCount empty == 0
-- vertexCount (vertex x) == 1
-- vertexCount == length . vertexList
--
vertexCount :: AdjacencyIntMap -> Int
-- | The number of edges in a graph. Complexity: O(n) time.
--
--
-- edgeCount empty == 0
-- edgeCount (vertex x) == 0
-- edgeCount (edge x y) == 1
-- edgeCount == length . edgeList
--
edgeCount :: AdjacencyIntMap -> Int
-- | 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
--
vertexList :: AdjacencyIntMap -> [Int]
-- | The sorted list of edges of a graph. Complexity: O(n + m) time
-- and O(m) memory.
--
--
-- edgeList empty == []
-- edgeList (vertex x) == []
-- edgeList (edge x y) == [(x,y)]
-- edgeList (star 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . edges == nub . sort
-- edgeList . transpose == sort . map swap . edgeList
--
edgeList :: AdjacencyIntMap -> [(Int, Int)]
-- | The sorted adjacency list of a graph. Complexity: O(n +
-- m) time and O(m) memory.
--
--
-- adjacencyList empty == []
-- adjacencyList (vertex x) == [(x, [])]
-- adjacencyList (edge 1 2) == [(1, [2]), (2, [])]
-- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]
-- stars . adjacencyList == id
--
adjacencyList :: AdjacencyIntMap -> [(Int, [Int])]
-- | The set of vertices of a given graph. Complexity: O(n) time and
-- memory.
--
--
-- vertexIntSet empty == IntSet.empty
-- vertexIntSet . vertex == IntSet.singleton
-- vertexIntSet . vertices == IntSet.fromList
-- vertexIntSet . clique == IntSet.fromList
--
vertexIntSet :: AdjacencyIntMap -> IntSet
-- | The set of edges of a given graph. Complexity: O((n + m) *
-- log(m)) time and O(m) memory.
--
--
-- edgeSet empty == Set.empty
-- edgeSet (vertex x) == Set.empty
-- edgeSet (edge x y) == Set.singleton (x,y)
-- edgeSet . edges == Set.fromList
--
edgeSet :: AdjacencyIntMap -> Set (Int, Int)
-- | The preset (here preIntSet) of an element x
-- is the set of its direct predecessors. Complexity: O(n *
-- log(n)) time and O(n) memory.
--
--
-- preIntSet x empty == Set.empty
-- preIntSet x (vertex x) == Set.empty
-- preIntSet 1 (edge 1 2) == Set.empty
-- preIntSet y (edge x y) == Set.fromList [x]
--
preIntSet :: Int -> AdjacencyIntMap -> IntSet
-- | The postset (here postIntSet) of a vertex is the set
-- of its direct successors.
--
--
-- postIntSet x empty == IntSet.empty
-- postIntSet x (vertex x) == IntSet.empty
-- postIntSet x (edge x y) == IntSet.fromList [y]
-- postIntSet 2 (edge 1 2) == IntSet.empty
--
postIntSet :: Int -> AdjacencyIntMap -> IntSet
-- | The path on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- path [] == empty
-- path [x] == vertex x
-- path [x,y] == edge x y
-- path . reverse == transpose . path
--
path :: [Int] -> AdjacencyIntMap
-- | The circuit on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- circuit [] == empty
-- circuit [x] == edge x x
-- circuit [x,y] == edges [(x,y), (y,x)]
-- circuit . reverse == transpose . circuit
--
circuit :: [Int] -> AdjacencyIntMap
-- | The clique on a list of vertices. Complexity: O((n + m) *
-- log(n)) time and O(n + m) memory.
--
--
-- 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 == transpose . clique
--
clique :: [Int] -> AdjacencyIntMap
-- | The biclique on two lists of vertices. Complexity: O(n *
-- log(n) + m) time and O(n + m) memory.
--
--
-- biclique [] [] == empty
-- biclique [x] [] == vertex x
-- biclique [] [y] == vertex y
-- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
-- biclique xs ys == connect (vertices xs) (vertices ys)
--
biclique :: [Int] -> [Int] -> AdjacencyIntMap
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges [(x,y), (x,z)]
-- star x ys == connect (vertex x) (vertices ys)
--
star :: Int -> [Int] -> AdjacencyIntMap
-- | The stars formed by overlaying a list of stars. An
-- inverse of adjacencyList. Complexity: O(L * log(n))
-- 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 == id
-- overlay (stars xs) (stars ys) == stars (xs ++ ys)
--
stars :: [(Int, [Int])] -> AdjacencyIntMap
-- | The tree graph constructed from a given Tree data
-- structure. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- 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)]
--
tree :: Tree Int -> AdjacencyIntMap
-- | The forest graph constructed from a given Forest data
-- structure. Complexity: O((n + m) * log(n)) time and O(n +
-- m) memory.
--
--
-- 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
--
forest :: Forest Int -> AdjacencyIntMap
-- | 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 x x) == empty
-- removeVertex 1 (edge 1 2) == vertex 2
-- removeVertex x . removeVertex x == removeVertex x
--
removeVertex :: Int -> AdjacencyIntMap -> AdjacencyIntMap
-- | Remove an edge from a given graph. Complexity: O(log(n)) time.
--
--
-- removeEdge x y (edge 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
--
removeEdge :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap
-- | The function replaceVertex x y replaces vertex
-- x with vertex y in a given AdjacencyIntMap.
-- 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 == mergeVertices (== x) y
--
replaceVertex :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap
-- | Merge vertices satisfying a given predicate into a given vertex.
-- Complexity: O((n + m) * log(n)) time, assuming that the
-- predicate takes O(1) to be evaluated.
--
--
-- mergeVertices (const False) x == id
-- mergeVertices (== x) y == replaceVertex x y
-- mergeVertices even 1 (0 * 2) == 1 * 1
-- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1
--
mergeVertices :: (Int -> Bool) -> Int -> AdjacencyIntMap -> AdjacencyIntMap
-- | Transpose a given graph. Complexity: O(m * log(n)) time, O(n
-- + m) memory.
--
--
-- transpose empty == empty
-- transpose (vertex x) == vertex x
-- transpose (edge x y) == edge y x
-- transpose . transpose == id
-- edgeList . transpose == sort . map swap . edgeList
--
transpose :: AdjacencyIntMap -> AdjacencyIntMap
-- | 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 AdjacencyIntMap. Complexity: O((n + m)
-- * log(n)) time.
--
--
-- gmap f empty == empty
-- gmap f (vertex x) == vertex (f x)
-- gmap f (edge x y) == edge (f x) (f y)
-- gmap id == id
-- gmap f . gmap g == gmap (f . g)
--
gmap :: (Int -> Int) -> AdjacencyIntMap -> AdjacencyIntMap
-- | Construct the induced subgraph of a given graph by removing the
-- vertices that do not satisfy a given predicate. Complexity:
-- O(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
--
induce :: (Int -> Bool) -> AdjacencyIntMap -> AdjacencyIntMap
-- | Compute the depth-first search forest of a graph that
-- corresponds to searching from each of the graph vertices in the
-- Ord a order.
--
--
-- dfsForest empty == []
-- forest (dfsForest $ edge 1 1) == vertex 1
-- forest (dfsForest $ edge 1 2) == edge 1 2
-- forest (dfsForest $ edge 2 1) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForest x) x == True
-- isDfsForestOf (dfsForest x) x == True
-- dfsForest . forest . dfsForest == dfsForest
-- dfsForest (vertices vs) == map (\v -> Node v []) (nub $ sort vs)
-- dfsForestFrom (vertexList x) x == dfsForest x
-- dfsForest $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }]}
-- , Node { rootLabel = 3
-- , subForest = [ Node { rootLabel = 4
-- , subForest = [] }]}]
--
dfsForest :: AdjacencyIntMap -> Forest Int
-- | Compute the depth-first search forest of a graph, searching
-- from each of the given vertices in order. Note that the resulting
-- forest does not necessarily span the whole graph, as some vertices may
-- be unreachable.
--
--
-- dfsForestFrom vs empty == []
-- forest (dfsForestFrom [1] $ edge 1 1) == vertex 1
-- forest (dfsForestFrom [1] $ edge 1 2) == edge 1 2
-- forest (dfsForestFrom [2] $ edge 1 2) == vertex 2
-- forest (dfsForestFrom [3] $ edge 1 2) == empty
-- forest (dfsForestFrom [2,1] $ edge 1 2) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForestFrom vs x) x == True
-- isDfsForestOf (dfsForestFrom (vertexList x) x) x == True
-- dfsForestFrom (vertexList x) x == dfsForest x
-- dfsForestFrom vs (vertices vs) == map (\v -> Node v []) (nub vs)
-- dfsForestFrom [] x == []
-- dfsForestFrom [1,4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }
-- , Node { rootLabel = 4
-- , subForest = [] }]
--
dfsForestFrom :: [Int] -> AdjacencyIntMap -> Forest Int
-- | Compute the list of vertices visited by the depth-first search
-- in a graph, when searching from each of the given vertices in order.
--
--
-- dfs vs $ empty == []
-- dfs [1] $ edge 1 1 == [1]
-- dfs [1] $ edge 1 2 == [1,2]
-- dfs [2] $ edge 1 2 == [2]
-- dfs [3] $ edge 1 2 == []
-- dfs [1,2] $ edge 1 2 == [1,2]
-- dfs [2,1] $ edge 1 2 == [2,1]
-- dfs [] $ x == []
-- dfs [1,4] $ 3 * (1 + 4) * (1 + 5) == [1,5,4]
-- isSubgraphOf (vertices $ dfs vs x) x == True
--
dfs :: [Int] -> AdjacencyIntMap -> [Int]
-- | Compute the list of vertices that are reachable from a given
-- source vertex in a graph. The vertices in the resulting list appear in
-- the depth-first order.
--
--
-- reachable x $ empty == []
-- reachable 1 $ vertex 1 == [1]
-- reachable 1 $ vertex 2 == []
-- reachable 1 $ edge 1 1 == [1]
-- reachable 1 $ edge 1 2 == [1,2]
-- reachable 4 $ path [1..8] == [4..8]
-- reachable 4 $ circuit [1..8] == [4..8] ++ [1..3]
-- reachable 8 $ clique [8,7..1] == [8] ++ [1..7]
-- isSubgraphOf (vertices $ reachable x y) y == True
--
reachable :: Int -> AdjacencyIntMap -> [Int]
-- | Compute the topological sort of a graph or return
-- Nothing if the graph is cyclic.
--
--
-- topSort (1 * 2 + 3 * 1) == Just [3,1,2]
-- topSort (1 * 2 + 2 * 1) == Nothing
-- fmap (flip isTopSortOf x) (topSort x) /= Just False
-- isJust . topSort == isAcyclic
--
topSort :: AdjacencyIntMap -> Maybe [Int]
-- | Check if a given graph is acyclic.
--
--
-- isAcyclic (1 * 2 + 3 * 1) == True
-- isAcyclic (1 * 2 + 2 * 1) == False
-- isAcyclic . circuit == null
-- isAcyclic == isJust . topSort
--
isAcyclic :: AdjacencyIntMap -> Bool
-- | Check if a given forest is a correct depth-first search forest
-- of a graph. The implementation is based on the paper "Depth-First
-- Search and Strong Connectivity in Coq" by François Pottier.
--
--
-- isDfsForestOf [] empty == True
-- isDfsForestOf [] (vertex 1) == False
-- isDfsForestOf [Node 1 []] (vertex 1) == True
-- isDfsForestOf [Node 1 []] (vertex 2) == False
-- isDfsForestOf [Node 1 [], Node 1 []] (vertex 1) == False
-- isDfsForestOf [Node 1 []] (edge 1 1) == True
-- isDfsForestOf [Node 1 []] (edge 1 2) == False
-- isDfsForestOf [Node 1 [], Node 2 []] (edge 1 2) == False
-- isDfsForestOf [Node 2 [], Node 1 []] (edge 1 2) == True
-- isDfsForestOf [Node 1 [Node 2 []]] (edge 1 2) == True
-- isDfsForestOf [Node 1 [], Node 2 []] (vertices [1,2]) == True
-- isDfsForestOf [Node 2 [], Node 1 []] (vertices [1,2]) == True
-- isDfsForestOf [Node 1 [Node 2 []]] (vertices [1,2]) == False
-- isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (path [1,2,3]) == True
-- isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (path [1,2,3]) == False
-- isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (path [1,2,3]) == True
-- isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (path [1,2,3]) == True
-- isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] (path [1,2,3]) == False
--
isDfsForestOf :: Forest Int -> AdjacencyIntMap -> Bool
-- | Check if a given list of vertices is a correct topological sort
-- of a graph.
--
--
-- isTopSortOf [3,1,2] (1 * 2 + 3 * 1) == True
-- isTopSortOf [1,2,3] (1 * 2 + 3 * 1) == False
-- isTopSortOf [] (1 * 2 + 3 * 1) == False
-- isTopSortOf [] empty == True
-- isTopSortOf [x] (vertex x) == True
-- isTopSortOf [x] (edge x x) == False
--
isTopSortOf :: [Int] -> AdjacencyIntMap -> Bool
-- | 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 core data type Graph and associated
-- algorithms. For graphs that are known to be non-empty at
-- compile time, see Algebra.Graph.NonEmpty. Graph is an
-- instance of type classes defined in modules Algebra.Graph.Class
-- and Algebra.Graph.HigherKinded.Class, which can be used for
-- polymorphic graph construction and manipulation.
module Algebra.Graph
-- | The Graph data type is a deep embedding of the core graph
-- construction primitives empty, vertex, overlay
-- and connect. 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))
--
--
-- The Eq instance is currently implemented using the
-- AdjacencyMap 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 and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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 is slightly different from the length
-- method of the Foldable type class, as the latter does not count
-- empty leaves of the expression:
--
--
-- length empty == 0
-- size empty == 1
-- length (vertex x) == 1
-- size (vertex x) == 1
-- length (empty + empty) == 0
-- size (empty + empty) == 2
--
--
-- The size of any graph is positive, and the difference
-- (size g - length g) corresponds to the number
-- of occurrences of empty in an expression g.
--
-- Converting a Graph to the corresponding AdjacencyMap
-- 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.
data Graph a
Empty :: Graph a
Vertex :: a -> Graph a
Overlay :: (Graph a) -> (Graph a) -> Graph a
Connect :: (Graph a) -> (Graph a) -> Graph a
-- | 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
-- size empty == 1
--
empty :: Graph a
-- | 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 x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
-- size (vertex x) == 1
--
vertex :: a -> Graph a
-- | Construct the graph comprising a single edge. Complexity:
-- O(1) time, memory and size.
--
--
-- edge x y == connect (vertex x) (vertex y)
-- hasEdge x y (edge x y) == True
-- edgeCount (edge x y) == 1
-- vertexCount (edge 1 1) == 1
-- vertexCount (edge 1 2) == 2
--
edge :: a -> a -> Graph a
-- | Overlay two graphs. An alias for the constructor
-- Overlay. 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 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
-- size (overlay x y) == size x + size y
-- vertexCount (overlay 1 2) == 2
-- edgeCount (overlay 1 2) == 0
--
overlay :: Graph a -> Graph a -> Graph a
-- | Connect two graphs. An alias for the constructor
-- Connect. This is an 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).
--
--
-- isEmpty (connect x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- size (connect x y) == size x + size y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: Graph a -> Graph a -> Graph a
-- | 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
--
vertices :: [a] -> Graph a
-- | Construct the graph from a list of edges. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- edges [] == empty
-- edges [(x,y)] == edge x y
-- edgeCount . edges == length . nub
--
edges :: [(a, a)] -> Graph a
-- | 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
--
overlays :: [Graph a] -> Graph a
-- | 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 :: [Graph a] -> Graph a
-- | 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 given functions. As
-- an example, the complexity of size is O(s), since all
-- functions have cost O(1).
--
--
-- foldg empty vertex overlay connect == id
-- foldg empty vertex overlay (flip connect) == transpose
-- foldg [] return (++) (++) == toList
-- foldg 0 (const 1) (+) (+) == length
-- foldg 1 (const 1) (+) (+) == size
-- foldg True (const False) (&&) (&&) == isEmpty
--
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
-- | 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 (path xs) (circuit xs) == True
--
isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool
-- | Structural equality on graph expressions. Complexity: O(s)
-- time.
--
--
-- x === x == True
-- x === x + empty == False
-- x + y === x + y == True
-- 1 + 2 === 2 + 1 == False
-- x + y === x * y == False
--
(===) :: Eq a => Graph a -> Graph a -> Bool
infix 4 ===
-- | Check if a graph is empty. A convenient alias for null.
-- 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 x y) == False
--
isEmpty :: Graph a -> Bool
-- | 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
--
size :: Graph a -> Int
-- | Check if a graph contains a given vertex. A convenient alias for
-- elem. Complexity: O(s) time.
--
--
-- hasVertex x empty == False
-- hasVertex x (vertex x) == True
-- hasVertex 1 (vertex 2) == False
-- hasVertex x . removeVertex x == const False
--
hasVertex :: Eq a => a -> Graph a -> Bool
-- | 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 x y) == True
-- hasEdge x y . removeEdge x y == const False
-- hasEdge x y == elem (x,y) . edgeList
--
hasEdge :: Eq a => a -> a -> Graph a -> Bool
-- | The number of vertices in a graph. Complexity: O(s * log(n))
-- time.
--
--
-- vertexCount empty == 0
-- vertexCount (vertex x) == 1
-- vertexCount == length . vertexList
--
vertexCount :: Ord a => Graph a -> Int
-- | The number of edges in a graph. 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.
--
--
-- edgeCount empty == 0
-- edgeCount (vertex x) == 0
-- edgeCount (edge x y) == 1
-- edgeCount == length . edgeList
--
edgeCount :: Ord a => Graph a -> Int
-- | 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
--
vertexList :: Ord a => Graph a -> [a]
-- | 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.
--
--
-- edgeList empty == []
-- edgeList (vertex x) == []
-- edgeList (edge x y) == [(x,y)]
-- edgeList (star 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . edges == nub . sort
-- edgeList . transpose == sort . map swap . edgeList
--
edgeList :: Ord a => Graph a -> [(a, a)]
-- | 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
-- vertexSet . clique == Set.fromList
--
vertexSet :: Ord a => Graph a -> Set a
-- | The set of vertices of a given graph. Like vertexSet but
-- specialised for graphs with vertices of type Int. Complexity:
-- O(s * log(n)) time and O(n) memory.
--
--
-- vertexIntSet empty == IntSet.empty
-- vertexIntSet . vertex == IntSet.singleton
-- vertexIntSet . vertices == IntSet.fromList
-- vertexIntSet . clique == IntSet.fromList
--
vertexIntSet :: Graph Int -> IntSet
-- | The set of edges of a given graph. Complexity: O(s * log(m))
-- time and O(m) memory.
--
--
-- edgeSet empty == Set.empty
-- edgeSet (vertex x) == Set.empty
-- edgeSet (edge x y) == Set.singleton (x,y)
-- edgeSet . edges == Set.fromList
--
edgeSet :: Ord a => Graph a -> Set (a, a)
-- | The sorted adjacency list of a graph. Complexity: O(n +
-- m) time and O(m) memory.
--
--
-- adjacencyList empty == []
-- adjacencyList (vertex x) == [(x, [])]
-- adjacencyList (edge 1 2) == [(1, [2]), (2, [])]
-- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]
-- stars . adjacencyList == id
--
adjacencyList :: Ord a => Graph a -> [(a, [a])]
-- | The adjacency map of a graph: each vertex is associated with a
-- set of its direct successors. 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.
adjacencyMap :: Ord a => Graph a -> Map a (Set a)
-- | Like adjacencyMap but specialised for graphs with vertices of
-- type Int.
adjacencyIntMap :: Graph Int -> IntMap IntSet
-- | The path on a list of vertices. Complexity: O(L) time,
-- memory and size, where L is the length of the given list.
--
--
-- path [] == empty
-- path [x] == vertex x
-- path [x,y] == edge x y
-- path . reverse == transpose . path
--
path :: [a] -> Graph a
-- | The circuit on a list of vertices. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- circuit [] == empty
-- circuit [x] == edge x x
-- circuit [x,y] == edges [(x,y), (y,x)]
-- circuit . reverse == transpose . circuit
--
circuit :: [a] -> Graph a
-- | 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 == transpose . clique
--
clique :: [a] -> Graph a
-- | 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,y1), (x2,y2)]
-- biclique xs ys == connect (vertices xs) (vertices ys)
--
biclique :: [a] -> [a] -> Graph a
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O(L) time, memory and size, where L
-- is the length of the given list.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges [(x,y), (x,z)]
-- star x ys == connect (vertex x) (vertices ys)
--
star :: a -> [a] -> Graph a
-- | The stars formed by overlaying a list of stars. 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 == id
-- overlay (stars xs) (stars ys) == stars (xs ++ ys)
--
stars :: [(a, [a])] -> Graph a
-- | 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)]
--
tree :: Tree a -> Graph a
-- | 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
--
forest :: Forest a -> Graph a
-- | Construct a mesh graph from two lists of vertices. Complexity:
-- O(L1 * L2) time, memory and size, where L1 and L2
-- are the lengths of the given lists.
--
--
-- mesh xs [] == empty
-- mesh [] ys == empty
-- mesh [x] [y] == vertex (x, y)
-- mesh xs ys == box (path xs) (path ys)
-- mesh [1..3] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b'))
-- , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ]
--
mesh :: [a] -> [b] -> Graph (a, b)
-- | Construct a torus graph from two lists of vertices. Complexity:
-- O(L1 * L2) time, memory and size, where L1 and L2
-- are the lengths of the given lists.
--
--
-- torus xs [] == empty
-- torus [] ys == empty
-- torus [x] [y] == edge (x,y) (x,y)
-- torus xs ys == box (circuit xs) (circuit ys)
-- torus [1,2] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b'))
-- , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ]
--
torus :: [a] -> [b] -> Graph (a, b)
-- | Construct a De Bruijn graph of a given non-negative dimension
-- using symbols from a given alphabet. Complexity: O(A^(D + 1))
-- time, memory and size, where A is the size of the alphabet and
-- D is the dimension of the graph.
--
--
-- deBruijn 0 xs == edge [] []
-- n > 0 ==> deBruijn n [] == empty
-- deBruijn 1 [0,1] == edges [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
-- deBruijn 2 "0" == edge "00" "00"
-- deBruijn 2 "01" == edges [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
-- , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
-- transpose (deBruijn n xs) == fmap reverse $ deBruijn n xs
-- vertexCount (deBruijn n xs) == (length $ nub xs)^n
-- n > 0 ==> edgeCount (deBruijn n xs) == (length $ nub xs)^(n + 1)
--
deBruijn :: Int -> [a] -> Graph [a]
-- | 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 x x) == empty
-- removeVertex 1 (edge 1 2) == vertex 2
-- removeVertex x . removeVertex x == removeVertex x
--
removeVertex :: Eq a => a -> Graph a -> Graph a
-- | 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 . 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
-- size (removeEdge x y z) <= 3 * size z
--
removeEdge :: Eq a => a -> a -> Graph a -> Graph a
-- | 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 == mergeVertices (== x) y
--
replaceVertex :: Eq a => a -> a -> Graph a -> Graph a
-- | Merge vertices satisfying a given predicate into a given vertex.
-- Complexity: O(s) time, memory and size, assuming that the
-- predicate takes O(1) to be evaluated.
--
--
-- mergeVertices (const False) x == id
-- mergeVertices (== x) y == replaceVertex x y
-- mergeVertices even 1 (0 * 2) == 1 * 1
-- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1
--
mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a
-- | Split a vertex into a list of vertices with the same connectivity.
-- Complexity: O(s + k * L) time, memory and size, where k
-- is the number of occurrences of the vertex in the expression and
-- L is the length of the given list.
--
--
-- splitVertex x [] == removeVertex x
-- splitVertex x [x] == id
-- splitVertex x [y] == replaceVertex x y
-- splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
--
splitVertex :: Eq a => a -> [a] -> Graph a -> Graph a
-- | Transpose a given graph. Complexity: O(s) time, memory and
-- size.
--
--
-- transpose empty == empty
-- transpose (vertex x) == vertex x
-- transpose (edge x y) == edge y x
-- transpose . transpose == id
-- transpose (box x y) == box (transpose x) (transpose y)
-- edgeList . transpose == sort . map swap . edgeList
--
transpose :: Graph a -> Graph a
-- | 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
--
induce :: (a -> Bool) -> Graph a -> Graph a
-- | Simplify a graph expression. Semantically, this is the identity
-- function, but it simplifies a given expression according to the laws
-- of the algebra. The function does not compute the simplest possible
-- expression, but uses heuristics to obtain useful simplifications in
-- reasonable time. Complexity: the function performs O(s) graph
-- comparisons. It is guaranteed that the size of the result does not
-- exceed the size of the given expression.
--
--
-- simplify == id
-- size (simplify x) <= size x
-- simplify empty === empty
-- simplify 1 === 1
-- simplify (1 + 1) === 1
-- simplify (1 + 2 + 1) === 1 + 2
-- simplify (1 * 1 * 1) === 1 * 1
--
simplify :: Ord a => Graph a -> Graph a
-- | Sparsify a graph by adding intermediate Left
-- Int vertices between the original vertices (wrapping the
-- latter in Right) such that the resulting graph is
-- sparse, i.e. contains only O(s) edges, but preserves the
-- reachability relation between the original vertices. Sparsification is
-- useful when working with dense graphs, as it can reduce the number of
-- edges from O(n^2) down to O(n) by replacing cliques, bicliques and
-- similar densely connected structures by sparse subgraphs built out of
-- intermediate vertices. Complexity: O(s) time, memory and size.
--
--
-- sort . reachable x == sort . rights . reachable (Right x) . sparsify
-- vertexCount (sparsify x) <= vertexCount x + size x + 1
-- edgeCount (sparsify x) <= 3 * size x
-- size (sparsify x) <= 3 * size x
--
sparsify :: Graph a -> Graph (Either Int a)
-- | Compute the Cartesian product of graphs. Complexity: O(s1 *
-- s2) time, memory and size, where s1 and s2 are the
-- sizes of the given graphs.
--
--
-- box (path [0,1]) (path "ab") == edges [ ((0,'a'), (0,'b'))
-- , ((0,'a'), (1,'a'))
-- , ((0,'b'), (1,'b'))
-- , ((1,'a'), (1,'b')) ]
--
--
-- Up to an isomorphism between the resulting vertex types, this
-- operation is commutative, associative,
-- distributes over overlay, 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 (overlay y z) == overlay (box x y) (box x z)
-- box x (vertex ()) ~~ x
-- box x empty ~~ empty
-- transpose (box x y) == box (transpose x) (transpose y)
-- vertexCount (box x y) == vertexCount x * vertexCount y
-- edgeCount (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y
--
box :: Graph a -> Graph b -> Graph (a, b)
-- | The context of a subgraph comprises the input and output vertices
-- outside the subgraph that are connected to the vertices inside the
-- subgraph.
data Context a
Context :: [a] -> [a] -> Context a
[inputs] :: Context a -> [a]
[outputs] :: Context a -> [a]
-- | Extract the context from a graph Focus. Returns
-- Nothing if the focus could not be obtained.
context :: (a -> Bool) -> Graph a -> Maybe (Context a)
instance Data.Traversable.Traversable Algebra.Graph.Graph
instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Graph a)
instance GHC.Base.Functor Algebra.Graph.Graph
instance Data.Foldable.Foldable Algebra.Graph.Graph
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Graph a)
instance GHC.Num.Num a => GHC.Num.Num (Algebra.Graph.Graph a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Graph a)
instance GHC.Base.Applicative Algebra.Graph.Graph
instance GHC.Base.Monad Algebra.Graph.Graph
instance GHC.Base.Alternative Algebra.Graph.Graph
instance GHC.Base.MonadPlus Algebra.Graph.Graph
-- | 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 type class ToGraph for capturing data
-- types that can be converted to algebraic graphs. To make an instance
-- of this class you need to define just a single method (toGraph
-- or foldg), which gives you access to many other useful methods
-- for free. This type class is similar to the standard
-- Data.Foldable defined for lists.
module Algebra.Graph.ToGraph
-- | The ToGraph type class captures data types that can be
-- converted to algebraic graphs.
class ToGraph t where {
type family ToVertex t;
}
-- | Convert a value to the corresponding algebraic graph, see
-- Algebra.Graph.
--
--
-- toGraph == foldg Empty Vertex Overlay Connect
--
toGraph :: ToGraph t => t -> Graph (ToVertex t)
-- | The method foldg is used for generalised graph folding. It
-- collapses a given value by applying the provided graph construction
-- primitives. The order of arguments is: empty, vertex, overlay and
-- connect, and it is assumed that the arguments satisfy the axioms of
-- the graph algebra.
--
--
-- foldg == Algebra.Graph.foldg . toGraph
--
foldg :: ToGraph t => r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
-- | Check if a graph is empty.
--
--
-- isEmpty == foldg True (const False) (&&) (&&)
--
isEmpty :: ToGraph t => t -> Bool
-- | The size of a graph, i.e. the number of leaves of the
-- expression including empty leaves.
--
--
-- size == foldg 1 (const 1) (+) (+)
--
size :: ToGraph t => t -> Int
-- | Check if a graph contains a given vertex.
--
--
-- hasVertex x == foldg False (==x) (||) (||)
--
hasVertex :: (ToGraph t, Eq (ToVertex t)) => ToVertex t -> t -> Bool
-- | Check if a graph contains a given edge.
--
--
-- hasEdge x y == Algebra.Graph.hasEdge x y . toGraph
--
hasEdge :: (ToGraph t, Eq (ToVertex t)) => ToVertex t -> ToVertex t -> t -> Bool
-- | The number of vertices in a graph.
--
--
-- vertexCount == Set.size . vertexSet
--
vertexCount :: (ToGraph t, Ord (ToVertex t)) => t -> Int
-- | The number of edges in a graph.
--
--
-- edgeCount == Set.size . edgeSet
--
edgeCount :: (ToGraph t, Ord (ToVertex t)) => t -> Int
-- | The sorted list of vertices of a given graph.
--
--
-- vertexList == Set.toAscList . vertexSet
--
vertexList :: (ToGraph t, Ord (ToVertex t)) => t -> [ToVertex t]
-- | The sorted list of edges of a graph.
--
--
-- edgeList == Set.toAscList . edgeSet
--
edgeList :: (ToGraph t, Ord (ToVertex t)) => t -> [(ToVertex t, ToVertex t)]
-- | The set of vertices of a graph.
--
--
-- vertexSet == foldg Set.empty Set.singleton Set.union Set.union
--
vertexSet :: (ToGraph t, Ord (ToVertex t)) => t -> Set (ToVertex t)
-- | The set of vertices of a graph. Like vertexSet but specialised
-- for graphs with vertices of type Int.
--
--
-- vertexIntSet == foldg IntSet.empty IntSet.singleton IntSet.union IntSet.union
--
vertexIntSet :: (ToGraph t, ToVertex t ~ Int) => t -> IntSet
-- | The set of edges of a graph.
--
--
-- edgeSet == Algebra.Graph.AdjacencyMap.edgeSet . toAdjacencyMap
--
edgeSet :: (ToGraph t, Ord (ToVertex t)) => t -> Set (ToVertex t, ToVertex t)
-- | The preset of a vertex is the set of its direct
-- predecessors.
--
--
-- preSet x == Algebra.Graph.AdjacencyMap.preSet x . toAdjacencyMap
--
preSet :: (ToGraph t, Ord (ToVertex t)) => ToVertex t -> t -> Set (ToVertex t)
-- | The preset (here preIntSet) of a vertex is the set of
-- its direct predecessors. Like preSet but specialised for
-- graphs with vertices of type Int.
--
--
-- preIntSet x == Algebra.Graph.AdjacencyIntMap.preIntSet x . toAdjacencyIntMap
--
preIntSet :: (ToGraph t, ToVertex t ~ Int) => Int -> t -> IntSet
-- | The postset of a vertex is the set of its direct
-- successors.
--
--
-- postSet x == Algebra.Graph.AdjacencyMap.postSet x . toAdjacencyMap
--
postSet :: (ToGraph t, Ord (ToVertex t)) => ToVertex t -> t -> Set (ToVertex t)
-- | The postset (here postIntSet) of a vertex is the set
-- of its direct successors. Like postSet but specialised
-- for graphs with vertices of type Int.
--
--
-- postIntSet x == Algebra.Graph.AdjacencyIntMap.postIntSet x . toAdjacencyIntMap
--
postIntSet :: (ToGraph t, ToVertex t ~ Int) => Int -> t -> IntSet
-- | The sorted adjacency list of a graph.
--
--
-- adjacencyList == Algebra.Graph.AdjacencyMap.adjacencyList . toAdjacencyMap
--
adjacencyList :: (ToGraph t, Ord (ToVertex t)) => t -> [(ToVertex t, [ToVertex t])]
-- | The adjacency map of a graph: each vertex is associated with a
-- set of its direct successors.
--
--
-- adjacencyMap == Algebra.Graph.AdjacencyMap.adjacencyMap . toAdjacencyMap
--
adjacencyMap :: (ToGraph t, Ord (ToVertex t)) => t -> Map (ToVertex t) (Set (ToVertex t))
-- | The adjacency map of a graph: each vertex is associated with a
-- set of its direct successors. Like adjacencyMap but
-- specialised for graphs with vertices of type Int.
--
--
-- adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMap
--
adjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet
-- | The transposed adjacency map of a graph: each vertex is
-- associated with a set of its direct predecessors.
--
--
-- adjacencyMapTranspose == Algebra.Graph.AdjacencyMap.adjacencyMap . toAdjacencyMapTranspose
--
adjacencyMapTranspose :: (ToGraph t, Ord (ToVertex t)) => t -> Map (ToVertex t) (Set (ToVertex t))
-- | The transposed adjacency map of a graph: each vertex is
-- associated with a set of its direct predecessors. Like
-- adjacencyMapTranspose but specialised for graphs with vertices
-- of type Int.
--
--
-- adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMapTranspose
--
adjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet
-- | Compute the depth-first search forest of a graph that
-- corresponds to searching from each of the graph vertices in the
-- Ord a order.
--
--
-- dfsForest == Algebra.Graph.AdjacencyMap.dfsForest . toAdjacencyMap
--
dfsForest :: (ToGraph t, Ord (ToVertex t)) => t -> Forest (ToVertex t)
-- | Compute the depth-first search forest of a graph, searching
-- from each of the given vertices in order. Note that the resulting
-- forest does not necessarily span the whole graph, as some vertices may
-- be unreachable.
--
--
-- dfsForestFrom vs == Algebra.Graph.AdjacencyMap.dfsForestFrom vs . toAdjacencyMap
--
dfsForestFrom :: (ToGraph t, Ord (ToVertex t)) => [ToVertex t] -> t -> Forest (ToVertex t)
-- | Compute the list of vertices visited by the depth-first search
-- in a graph, when searching from each of the given vertices in order.
--
--
-- dfs vs == Algebra.Graph.AdjacencyMap.dfs vs . toAdjacencyMap
--
dfs :: (ToGraph t, Ord (ToVertex t)) => [ToVertex t] -> t -> [ToVertex t]
-- | Compute the list of vertices that are reachable from a given
-- source vertex in a graph. The vertices in the resulting list appear in
-- the depth-first order.
--
--
-- reachable x == Algebra.Graph.AdjacencyMap.reachable x . toAdjacencyMap
--
reachable :: (ToGraph t, Ord (ToVertex t)) => ToVertex t -> t -> [ToVertex t]
-- | Compute the topological sort of a graph or return
-- Nothing if the graph is cyclic.
--
--
-- topSort == Algebra.Graph.AdjacencyMap.topSort . toAdjacencyMap
--
topSort :: (ToGraph t, Ord (ToVertex t)) => t -> Maybe [ToVertex t]
-- | Check if a given graph is acyclic.
--
--
-- isAcyclic == Algebra.Graph.AdjacencyMap.isAcyclic . toAdjacencyMap
--
isAcyclic :: (ToGraph t, Ord (ToVertex t)) => t -> Bool
-- | Convert a value to the corresponding AdjacencyMap.
--
--
-- toAdjacencyMap == foldg empty vertex overlay connect
--
toAdjacencyMap :: (ToGraph t, Ord (ToVertex t)) => t -> AdjacencyMap (ToVertex t)
-- | Convert a value to the corresponding AdjacencyMap and transpose
-- the result.
--
--
-- toAdjacencyMapTranspose == foldg empty vertex overlay (flip connect)
--
toAdjacencyMapTranspose :: (ToGraph t, Ord (ToVertex t)) => t -> AdjacencyMap (ToVertex t)
-- | Convert a value to the corresponding AdjacencyIntMap.
--
--
-- toAdjacencyIntMap == foldg empty vertex overlay connect
--
toAdjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
-- | Convert a value to the corresponding AdjacencyIntMap and
-- transpose the result.
--
--
-- toAdjacencyIntMapTranspose == foldg empty vertex overlay (flip connect)
--
toAdjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap
-- | Check if a given forest is a valid depth-first search forest of
-- a graph.
--
--
-- isDfsForestOf f == Algebra.Graph.AdjacencyMap.isDfsForestOf f . toAdjacencyMap
--
isDfsForestOf :: (ToGraph t, Ord (ToVertex t)) => Forest (ToVertex t) -> t -> Bool
-- | Check if a given list of vertices is a valid topological sort
-- of a graph.
--
--
-- isTopSortOf vs == Algebra.Graph.AdjacencyMap.isTopSortOf vs . toAdjacencyMap
--
isTopSortOf :: (ToGraph t, Ord (ToVertex t)) => [ToVertex t] -> t -> Bool
instance GHC.Classes.Ord a => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Graph a)
instance GHC.Classes.Ord a => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a)
instance Algebra.Graph.ToGraph.ToGraph Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap
instance GHC.Classes.Ord a => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Relation.Internal.Relation a)
-- | 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 basic functionality for exporting graphs in
-- textual and binary formats. Algebra.Graph.Export.Dot provides
-- DOT-specific functions.
module Algebra.Graph.Export
-- | An abstract document data type with O(1) time concatenation
-- (the current implementation uses difference lists). Here s is
-- the type of abstract symbols or strings (text or binary). Doc
-- s is a Monoid, therefore mempty corresponds to
-- the empty document and two documents can be concatenated with
-- mappend (or operator <>). Documents comprising a
-- single symbol or string can be constructed using the function
-- literal. Alternatively, you can construct documents as string
-- literals, e.g. simply as "alga", by using the
-- OverloadedStrings GHC extension. To extract the document
-- contents use the function render. See some examples below.
data Doc s
-- | Construct a document comprising a single symbol or string. If
-- s is an instance of class IsString, then documents of
-- type Doc s can be constructed directly from string
-- literals (see the second example below).
--
--
-- literal "Hello, " <> literal "World!" == literal "Hello, World!"
-- literal "I am just a string literal" == "I am just a string literal"
-- literal mempty == mempty
-- render . literal == id
-- literal . render == id
--
literal :: s -> Doc s
-- | Render the document as a single string. An inverse of the function
-- literal.
--
--
-- render (literal "al" <> literal "ga") :: (IsString s, Monoid s) => s
-- render (literal "al" <> literal "ga") == "alga"
-- render mempty == mempty
-- render . literal == id
-- literal . render == id
--
render :: Monoid s => Doc s -> s
-- | Concatenate two documents, separated by a single space, unless one of
-- the documents is empty. The operator <+> is associative with
-- identity mempty.
--
--
-- x <+> mempty == x
-- mempty <+> x == x
-- x <+> (y <+> z) == (x <+> y) <+> z
-- "name" <+> "surname" == "name surname"
--
(<+>) :: (Eq s, IsString s, Monoid s) => Doc s -> Doc s -> Doc s
infixl 7 <+>
-- | Wrap a document in square brackets.
--
--
-- brackets "i" == "[i]"
-- brackets mempty == "[]"
--
brackets :: IsString s => Doc s -> Doc s
-- | Wrap a document into double quotes.
--
--
-- doubleQuotes "/path/with spaces" == "\"/path/with spaces\""
-- doubleQuotes (doubleQuotes mempty) == "\"\"\"\""
--
doubleQuotes :: IsString s => Doc s -> Doc s
-- | Prepend a given number of spaces to a document.
--
--
-- indent 0 == id
-- indent 1 mempty == " "
--
indent :: IsString s => Int -> Doc s -> Doc s
-- | Concatenate documents after appending a terminating newline symbol to
-- each.
--
--
-- unlines [] == mempty
-- unlines [mempty] == "\n"
-- unlines ["title", "subtitle"] == "title\nsubtitle\n"
--
unlines :: IsString s => [Doc s] -> Doc s
-- | Export a graph into a document given two functions that construct
-- documents for individual vertices and edges. The order of export is:
-- vertices, sorted by Ord a, and then edges, sorted by
-- Ord (a, a).
--
-- For example:
--
--
-- vDoc x = literal (show x) <> "\n"
-- eDoc x y = literal (show x) <> " -> " <> literal (show y) <> "\n"
-- > putStrLn $ render $ export vDoc eDoc (1 + 2 * (3 + 4) :: Graph Int)
--
-- 1
-- 2
-- 3
-- 4
-- 2 -> 3
-- 2 -> 4
--
export :: (Ord a, ToGraph g, ToVertex g ~ a) => (a -> Doc s) -> (a -> a -> Doc s) -> g -> Doc s
instance GHC.Base.Semigroup (Algebra.Graph.Export.Doc s)
instance GHC.Base.Monoid (Algebra.Graph.Export.Doc s)
instance (GHC.Base.Monoid s, GHC.Show.Show s) => GHC.Show.Show (Algebra.Graph.Export.Doc s)
instance (GHC.Base.Monoid s, GHC.Classes.Eq s) => GHC.Classes.Eq (Algebra.Graph.Export.Doc s)
instance (GHC.Base.Monoid s, GHC.Classes.Ord s) => GHC.Classes.Ord (Algebra.Graph.Export.Doc s)
instance Data.String.IsString s => Data.String.IsString (Algebra.Graph.Export.Doc s)
-- | 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 functions for exporting graphs in the DOT file
-- format.
module Algebra.Graph.Export.Dot
-- | An attribute is just a key-value pair, for example "shape" :=
-- "box". Attributes are used to specify the style of graph elements
-- during export.
data Attribute s
(:=) :: s -> s -> Attribute s
-- | The record Style a s specifies the style to
-- use when exporting a graph in the DOT format. Here a is the
-- type of the graph vertices, and s is the type of string to
-- represent the resulting DOT document (e.g. String, Text, etc.). Most
-- fields can be empty. The only field that has no obvious default value
-- is vertexName, which holds a function of type a ->
-- s to compute vertex names. See the example for the function
-- export.
data Style a s
Style :: s -> s -> [Attribute s] -> [Attribute s] -> [Attribute s] -> a -> s -> a -> [Attribute s] -> a -> a -> [Attribute s] -> Style a s
-- | Name of the graph.
[graphName] :: Style a s -> s
-- | Preamble is added at the beginning of the DOT file body.
[preamble] :: Style a s -> s
-- | Graph style, e.g. ["bgcolor" := "azure"].
[graphAttributes] :: Style a s -> [Attribute s]
-- | Default vertex style, e.g. ["shape" := "diamond"].
[defaultVertexAttributes] :: Style a s -> [Attribute s]
-- | Default edge style, e.g. ["style" := "dashed"].
[defaultEdgeAttributes] :: Style a s -> [Attribute s]
-- | Compute a vertex name.
[vertexName] :: Style a s -> a -> s
-- | Attributes of a specific vertex.
[vertexAttributes] :: Style a s -> a -> [Attribute s]
-- | Attributes of a specific edge.
[edgeAttributes] :: Style a s -> a -> a -> [Attribute s]
-- | Default style for exporting graphs. All style settings are empty
-- except for vertexName, which is provided as the only argument.
defaultStyle :: Monoid s => (a -> s) -> Style a s
-- | Default style for exporting graphs whose vertices are
-- Show-able. All style settings are empty except for
-- vertexName, which is computed from show.
--
--
-- defaultStyleViaShow = defaultStyle (fromString . show)
--
defaultStyleViaShow :: (Show a, IsString s, Monoid s) => Style a s
-- | Export a graph with a given style.
--
-- For example:
--
--
-- style :: Style Int String
-- style = Style
-- { graphName = "Example"
-- , preamble = " // This is an example\n"
-- , graphAttributes = ["label" := "Example", "labelloc" := "top"]
-- , defaultVertexAttributes = ["shape" := "circle"]
-- , defaultEdgeAttributes = mempty
-- , vertexName = \x -> "v" ++ show x
-- , vertexAttributes = \x -> ["color" := "blue" | odd x ]
-- , edgeAttributes = \x y -> ["style" := "dashed" | odd (x * y)] }
--
-- > putStrLn $ export style (1 * 2 + 3 * 4 * 5 :: Graph Int)
--
-- digraph Example
-- {
-- // This is an example
--
-- graph [label="Example" labelloc="top"]
-- node [shape="circle"]
-- "v1" [color="blue"]
-- "v2"
-- "v3" [color="blue"]
-- "v4"
-- "v5" [color="blue"]
-- "v1" -> "v2"
-- "v3" -> "v4"
-- "v3" -> "v5" [style="dashed"]
-- "v4" -> "v5"
-- }
--
export :: (IsString s, Monoid s, Eq s, Ord a, ToGraph g, ToVertex g ~ a) => Style a s -> g -> s
-- | Export a graph whose vertices are represented simply by their names.
--
-- For example:
--
--
-- > Text.putStrLn $ exportAsIs (circuit ["a", "b", "c"] :: AdjacencyMap Text)
--
-- digraph
-- {
-- "a"
-- "b"
-- "c"
-- "a" -> "b"
-- "b" -> "c"
-- "c" -> "a"
-- }
--
exportAsIs :: (IsString s, Monoid s, Ord s, ToGraph g, ToVertex g ~ s) => g -> s
-- | Export a graph using the defaultStyleViaShow.
--
-- For example:
--
--
-- > putStrLn $ exportViaShow (1 + 2 * (3 + 4) :: Graph Int)
--
-- digraph
-- {
-- "1"
-- "2"
-- "3"
-- "4"
-- "2" -> "3"
-- "2" -> "4"
-- }
--
exportViaShow :: (IsString s, Monoid s, Eq s, ToGraph g, Ord (ToVertex g), Show (ToVertex g)) => g -> s
-- | 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 data type NonEmptyGraph for graphs that
-- are known to be non-empty at compile time. The naming convention
-- generally follows that of Data.List.NonEmpty: we use suffix
-- 1 to indicate the functions whose interface must be changed
-- compared to Algebra.Graph, e.g. vertices1.
module Algebra.Graph.NonEmpty
-- | The NonEmptyGraph data type is a deep embedding of the core
-- graph construction primitives vertex, overlay and
-- connect. As one can guess from the name, the empty graph cannot
-- be represented using this data type. See module Algebra.Graph
-- for a graph data type that allows for the construction of the empty
-- graph.
--
-- 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 that the signum method of the Num type class cannot
-- be implemented.
--
-- The Eq instance is currently implemented using the
-- AdjacencyMap as the canonical graph representation and
-- 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 over overlay:
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 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 NonEmptyGraph expression,
-- defined as the number of vertex leaves. For example, if g is
-- a NonEmptyGraph then n, m and s can be
-- computed as follows:
--
--
-- n == vertexCount g
-- m == edgeCount g
-- s == size g
--
--
-- The size of any graph is positive and coincides with the result
-- of length method of the Foldable type class. We define
-- size only for the consistency with the API of other graph
-- representations, such as Algebra.Graph.
--
-- Converting a NonEmptyGraph to the corresponding
-- AdjacencyMap 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.
data NonEmptyGraph a
Vertex :: a -> NonEmptyGraph a
Overlay :: (NonEmptyGraph a) -> (NonEmptyGraph a) -> NonEmptyGraph a
Connect :: (NonEmptyGraph a) -> (NonEmptyGraph a) -> NonEmptyGraph a
-- | Convert a Graph into NonEmptyGraph. Returns
-- Nothing if the argument is empty. Complexity:
-- O(s) time, memory and size.
--
--
-- toNonEmptyGraph empty == Nothing
-- toNonEmptyGraph (toGraph x) == Just (x :: NonEmptyGraph a)
--
toNonEmptyGraph :: Graph a -> Maybe (NonEmptyGraph a)
-- | Construct the graph comprising a single isolated vertex. An
-- alias for the constructor Vertex. Complexity: O(1) time,
-- memory and size.
--
--
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
-- size (vertex x) == 1
--
vertex :: a -> NonEmptyGraph a
-- | Construct the graph comprising a single edge. Complexity:
-- O(1) time, memory and size.
--
--
-- edge x y == connect (vertex x) (vertex y)
-- hasEdge x y (edge x y) == True
-- edgeCount (edge x y) == 1
-- vertexCount (edge 1 1) == 1
-- vertexCount (edge 1 2) == 2
--
edge :: a -> a -> NonEmptyGraph a
-- | Overlay two graphs. An alias for the constructor
-- Overlay. This is a commutative, associative and idempotent
-- operation. Complexity: O(1) time and memory, O(s1 + s2)
-- size.
--
--
-- 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
-- size (overlay x y) == size x + size y
-- vertexCount (overlay 1 2) == 2
-- edgeCount (overlay 1 2) == 0
--
overlay :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a
-- | Overlay a possibly empty graph with a non-empty graph. If the first
-- argument is empty, the function returns the second argument;
-- otherwise it is semantically the same as overlay. Complexity:
-- O(s1) time and memory, and O(s1 + s2) size.
--
--
-- overlay1 empty x == x
-- x /= empty ==> overlay1 x y == overlay (fromJust $ toNonEmptyGraph x) y
--
overlay1 :: Graph a -> NonEmptyGraph a -> NonEmptyGraph a
-- | Connect two graphs. An alias for the constructor
-- Connect. This is an associative operation, 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).
--
--
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- size (connect x y) == size x + size y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a
-- | 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.
--
--
-- vertices1 (x :| []) == vertex x
-- hasVertex x . vertices1 == elem x
-- vertexCount . vertices1 == length . nub
-- vertexSet . vertices1 == Set.fromList . toList
--
vertices1 :: NonEmpty a -> NonEmptyGraph a
-- | Construct the graph from a list of edges. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- edges1 ((x,y) :| []) == edge x y
-- edgeCount . edges1 == length . nub
--
edges1 :: NonEmpty (a, a) -> NonEmptyGraph a
-- | 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.
--
--
-- overlays1 (x :| [] ) == x
-- overlays1 (x :| [y]) == overlay x y
--
overlays1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a
-- | 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.
--
--
-- connects1 (x :| [] ) == x
-- connects1 (x :| [y]) == connect x y
--
connects1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a
-- | Generalised graph folding: recursively collapse a NonEmptyGraph
-- by applying the provided functions to the leaves and internal nodes of
-- the expression. The order of arguments is: vertex, overlay 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).
--
--
-- foldg1 (const 1) (+) (+) == size
-- foldg1 (==x) (||) (||) == hasVertex x
--
foldg1 :: (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> NonEmptyGraph a -> b
-- | 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 x (overlay x y) == True
-- isSubgraphOf (overlay x y) (connect x y) == True
-- isSubgraphOf (path1 xs) (circuit1 xs) == True
--
isSubgraphOf :: Ord a => NonEmptyGraph a -> NonEmptyGraph a -> Bool
-- | Structural equality on graph expressions. Complexity: O(s)
-- time.
--
--
-- x === x == True
-- x + y === x + y == True
-- 1 + 2 === 2 + 1 == False
-- x + y === x * y == False
--
(===) :: Eq a => NonEmptyGraph a -> NonEmptyGraph a -> Bool
infix 4 ===
-- | The size of a graph, i.e. the number of leaves of the
-- expression. Complexity: O(s) time.
--
--
-- 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
--
size :: NonEmptyGraph a -> Int
-- | Check if a graph contains a given vertex. A convenient alias for
-- elem. Complexity: O(s) time.
--
--
-- hasVertex x (vertex x) == True
-- hasVertex 1 (vertex 2) == False
--
hasVertex :: Eq a => a -> NonEmptyGraph a -> Bool
-- | Check if a graph contains a given edge. Complexity: O(s) time.
--
--
-- hasEdge x y (vertex z) == False
-- hasEdge x y (edge x y) == True
-- hasEdge x y . removeEdge x y == const False
-- hasEdge x y == elem (x,y) . edgeList
--
hasEdge :: Eq a => a -> a -> NonEmptyGraph a -> Bool
-- | The number of vertices in a graph. Complexity: O(s * log(n))
-- time.
--
--
-- vertexCount (vertex x) == 1
-- vertexCount x >= 1
-- vertexCount == length . vertexList1
--
vertexCount :: Ord a => NonEmptyGraph a -> Int
-- | The number of edges in a graph. 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.
--
--
-- edgeCount (vertex x) == 0
-- edgeCount (edge x y) == 1
-- edgeCount == length . edgeList
--
edgeCount :: Ord a => NonEmptyGraph a -> Int
-- | The sorted list of vertices of a given graph. Complexity: O(s *
-- log(n)) time and O(n) memory.
--
--
-- vertexList1 (vertex x) == x :| []
-- vertexList1 . vertices1 == nub . sort
--
vertexList1 :: Ord a => NonEmptyGraph a -> NonEmpty a
-- | 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.
--
--
-- edgeList (vertex x) == []
-- edgeList (edge x y) == [(x,y)]
-- edgeList (star 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . edges1 == nub . sort . toList
-- edgeList . transpose == sort . map swap . edgeList
--
edgeList :: Ord a => NonEmptyGraph a -> [(a, a)]
-- | The set of vertices of a given graph. Complexity: O(s * log(n))
-- time and O(n) memory.
--
--
-- vertexSet . vertex == Set.singleton
-- vertexSet . vertices1 == Set.fromList . toList
-- vertexSet . clique1 == Set.fromList . toList
--
vertexSet :: Ord a => NonEmptyGraph a -> Set a
-- | The set of vertices of a given graph. Like vertexSet but
-- specialised for graphs with vertices of type Int. Complexity:
-- O(s * log(n)) time and O(n) memory.
--
--
-- vertexIntSet . vertex == IntSet.singleton
-- vertexIntSet . vertices1 == IntSet.fromList . toList
-- vertexIntSet . clique1 == IntSet.fromList . toList
--
vertexIntSet :: NonEmptyGraph Int -> IntSet
-- | The set of edges of a given graph. Complexity: O(s * log(m))
-- time and O(m) memory.
--
--
-- edgeSet (vertex x) == Set.empty
-- edgeSet (edge x y) == Set.singleton (x,y)
-- edgeSet . edges1 == Set.fromList . toList
--
edgeSet :: Ord a => NonEmptyGraph a -> Set (a, a)
-- | The path on a list of vertices. Complexity: O(L) time,
-- memory and size, where L is the length of the given list.
--
--
-- path1 (x :| [] ) == vertex x
-- path1 (x :| [y]) == edge x y
-- path1 . reverse == transpose . path1
--
path1 :: NonEmpty a -> NonEmptyGraph a
-- | The circuit on a list of vertices. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- circuit1 (x :| [] ) == edge x x
-- circuit1 (x :| [y]) == edges1 ((x,y) :| [(y,x)])
-- circuit1 . reverse == transpose . circuit1
--
circuit1 :: NonEmpty a -> NonEmptyGraph a
-- | The clique on a list of vertices. Complexity: O(L) time,
-- memory and size, where L is the length of the given list.
--
--
-- clique1 (x :| [] ) == vertex x
-- clique1 (x :| [y] ) == edge x y
-- clique1 (x :| [y,z]) == edges1 ((x,y) :| [(x,z), (y,z)])
-- clique1 (xs <> ys) == connect (clique1 xs) (clique1 ys)
-- clique1 . reverse == transpose . clique1
--
clique1 :: NonEmpty a -> NonEmptyGraph a
-- | 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.
--
--
-- biclique1 (x1 :| [x2]) (y1 :| [y2]) == edges1 ((x1,y1) :| [(x1,y2), (x2,y1), (x2,y2)])
-- biclique1 xs ys == connect (vertices1 xs) (vertices1 ys)
--
biclique1 :: NonEmpty a -> NonEmpty a -> NonEmptyGraph a
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O(L) time, memory and size, where L
-- is the length of the given list.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges1 ((x,y) :| [(x,z)])
--
star :: a -> [a] -> NonEmptyGraph a
-- | The stars formed by overlaying a non-empty list of
-- stars. Complexity: O(L) time, memory and size, where
-- L is the total size of the input.
--
--
-- stars1 ((x, []) :| []) == vertex x
-- stars1 ((x, [y]) :| []) == edge x y
-- stars1 ((x, ys) :| []) == star x ys
-- stars1 == overlays1 . fmap (uncurry star)
-- overlay (stars1 xs) (stars1 ys) == stars1 (xs <> ys)
--
stars1 :: NonEmpty (a, [a]) -> NonEmptyGraph a
-- | 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 []]]) == path1 (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 []]]) == edges1 ((1,2) :| [(1,3), (3,4), (3,5)])
--
tree :: Tree a -> NonEmptyGraph a
-- | Construct a mesh graph from two lists of vertices. Complexity:
-- O(L1 * L2) time, memory and size, where L1 and L2
-- are the lengths of the given lists.
--
--
-- mesh1 (x :| []) (y :| []) == vertex (x, y)
-- mesh1 xs ys == box (path1 xs) (path1 ys)
-- mesh1 (1 :| [2,3]) ('a' :| "b") == edges1 (fromList [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a'))
-- , ((1,'b'),(2,'b')), ((2,'a'),(2,'b'))
-- , ((2,'a'),(3,'a')), ((2,'b'),(3,'b'))
-- , ((3,'a'),(3,'b')) ])
--
mesh1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (a, b)
-- | Construct a torus graph from two lists of vertices. Complexity:
-- O(L1 * L2) time, memory and size, where L1 and L2
-- are the lengths of the given lists.
--
--
-- torus1 (x :| []) (y :| []) == edge (x,y) (x,y)
-- torus1 xs ys == box (circuit1 xs) (circuit1 ys)
-- torus1 (1 :| [2]) ('a' :| "b") == edges1 (fromList [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a'))
-- , ((1,'b'),(1,'a')), ((1,'b'),(2,'b'))
-- , ((2,'a'),(1,'a')), ((2,'a'),(2,'b'))
-- , ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ])
--
torus1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (a, b)
-- | Remove a vertex from a given graph. Returns Nothing if the
-- resulting graph is empty. Complexity: O(s) time, memory and
-- size.
--
--
-- removeVertex1 x (vertex x) == Nothing
-- removeVertex1 1 (vertex 2) == Just (vertex 2)
-- removeVertex1 x (edge x x) == Nothing
-- removeVertex1 1 (edge 1 2) == Just (vertex 2)
-- removeVertex1 x >=> removeVertex1 x == removeVertex1 x
--
removeVertex1 :: Eq a => a -> NonEmptyGraph a -> Maybe (NonEmptyGraph a)
-- | Remove an edge from a given graph. Complexity: O(s) time,
-- memory and size.
--
--
-- removeEdge x y (edge x y) == vertices1 (x :| [y])
-- removeEdge x y . removeEdge x y == removeEdge x y
-- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2
-- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2
-- size (removeEdge x y z) <= 3 * size z
--
removeEdge :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a
-- | The function replaceVertex x y replaces vertex
-- x with vertex y in a given NonEmptyGraph. 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
--
replaceVertex :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a
-- | Merge vertices satisfying a given predicate into a given vertex.
-- Complexity: O(s) time, memory and size, assuming that the
-- predicate takes O(1) to be evaluated.
--
--
-- mergeVertices (const False) x == id
-- mergeVertices (== x) y == replaceVertex x y
-- mergeVertices even 1 (0 * 2) == 1 * 1
-- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1
--
mergeVertices :: (a -> Bool) -> a -> NonEmptyGraph a -> NonEmptyGraph a
-- | Split a vertex into a list of vertices with the same connectivity.
-- Complexity: O(s + k * L) time, memory and size, where k
-- is the number of occurrences of the vertex in the expression and
-- L is the length of the given list.
--
--
-- splitVertex1 x (x :| [] ) == id
-- splitVertex1 x (y :| [] ) == replaceVertex x y
-- splitVertex1 1 (0 :| [1]) $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
--
splitVertex1 :: Eq a => a -> NonEmpty a -> NonEmptyGraph a -> NonEmptyGraph a
-- | Transpose a given graph. Complexity: O(s) time, memory and
-- size.
--
--
-- transpose (vertex x) == vertex x
-- transpose (edge x y) == edge y x
-- transpose . transpose == id
-- transpose (box x y) == box (transpose x) (transpose y)
-- edgeList . transpose == sort . map swap . edgeList
--
transpose :: NonEmptyGraph a -> NonEmptyGraph a
-- | Construct the induced subgraph of a given graph by removing the
-- vertices that do not satisfy a given predicate. Returns
-- Nothing if the resulting graph is empty. Complexity:
-- O(s) time, memory and size, assuming that the predicate takes
-- O(1) to be evaluated.
--
--
-- induce1 (const True ) x == Just x
-- induce1 (const False) x == Nothing
-- induce1 (/= x) == removeVertex1 x
-- induce1 p >=> induce1 q == induce1 (\x -> p x && q x)
--
induce1 :: (a -> Bool) -> NonEmptyGraph a -> Maybe (NonEmptyGraph a)
-- | Simplify a graph expression. Semantically, this is the identity
-- function, but it simplifies a given expression according to the laws
-- of the algebra. The function does not compute the simplest possible
-- expression, but uses heuristics to obtain useful simplifications in
-- reasonable time. Complexity: the function performs O(s) graph
-- comparisons. It is guaranteed that the size of the result does not
-- exceed the size of the given expression.
--
--
-- simplify == id
-- size (simplify x) <= size x
-- simplify 1 === 1
-- simplify (1 + 1) === 1
-- simplify (1 + 2 + 1) === 1 + 2
-- simplify (1 * 1 * 1) === 1 * 1
--
simplify :: Ord a => NonEmptyGraph a -> NonEmptyGraph a
-- | Sparsify a graph by adding intermediate Left
-- Int vertices between the original vertices (wrapping the
-- latter in Right) such that the resulting graph is
-- sparse, i.e. contains only O(s) edges, but preserves the
-- reachability relation between the original vertices. Sparsification is
-- useful when working with dense graphs, as it can reduce the number of
-- edges from O(n^2) down to O(n) by replacing cliques, bicliques and
-- similar densely connected structures by sparse subgraphs built out of
-- intermediate vertices. Complexity: O(s) time, memory and size.
--
--
-- sort . reachable x == sort . rights . reachable (Right x) . sparsify
-- vertexCount (sparsify x) <= vertexCount x + size x + 1
-- edgeCount (sparsify x) <= 3 * size x
-- size (sparsify x) <= 3 * size x
--
sparsify :: NonEmptyGraph a -> NonEmptyGraph (Either Int a)
-- | Compute the Cartesian product of graphs. Complexity: O(s1 *
-- s2) time, memory and size, where s1 and s2 are the
-- sizes of the given graphs.
--
--
-- box (path1 $ fromList [0,1]) (path1 $ fromList "ab") == edges1 (fromList [ ((0,'a'), (0,'b'))
-- , ((0,'a'), (1,'a'))
-- , ((0,'b'), (1,'b'))
-- , ((1,'a'), (1,'b')) ])
--
--
-- Up to an isomorphism between the resulting vertex types, this
-- operation is commutative, associative,
-- distributes over overlay, and has singleton graphs as
-- identities. 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 (overlay y z) == overlay (box x y) (box x z)
-- box x (vertex ()) ~~ x
-- transpose (box x y) == box (transpose x) (transpose y)
-- vertexCount (box x y) == vertexCount x * vertexCount y
-- edgeCount (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y
--
box :: NonEmptyGraph a -> NonEmptyGraph b -> NonEmptyGraph (a, b)
instance Data.Traversable.Traversable Algebra.Graph.NonEmpty.NonEmptyGraph
instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.NonEmpty.NonEmptyGraph a)
instance GHC.Base.Functor Algebra.Graph.NonEmpty.NonEmptyGraph
instance Data.Foldable.Foldable Algebra.Graph.NonEmpty.NonEmptyGraph
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.NonEmpty.NonEmptyGraph a)
instance Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.NonEmpty.NonEmptyGraph a)
instance GHC.Num.Num a => GHC.Num.Num (Algebra.Graph.NonEmpty.NonEmptyGraph a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.NonEmpty.NonEmptyGraph a)
instance GHC.Base.Applicative Algebra.Graph.NonEmpty.NonEmptyGraph
instance GHC.Base.Monad Algebra.Graph.NonEmpty.NonEmptyGraph
-- | 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 Fold data type -- the Boehm-Berarducci
-- encoding of algebraic graphs, which is used for generalised graph
-- folding and for the implementation of polymorphic graph construction
-- and transformation algorithms. Fold is an instance of type
-- classes defined in modules Algebra.Graph.Class and
-- Algebra.Graph.HigherKinded.Class, which can be used for
-- polymorphic graph construction and manipulation.
module Algebra.Graph.Fold
-- | The Fold data type is the Boehm-Berarducci encoding of the core
-- graph construction primitives empty, vertex,
-- overlay and connect. 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))
--
--
-- The Show instance is defined using basic graph construction
-- primitives:
--
--
-- show (empty :: Fold Int) == "empty"
-- show (1 :: Fold Int) == "vertex 1"
-- show (1 + 2 :: Fold Int) == "vertices [1,2]"
-- show (1 * 2 :: Fold Int) == "edge 1 2"
-- show (1 * 2 * 3 :: Fold Int) == "edges [(1,2),(1,3),(2,3)]"
-- show (1 * 2 + 3 :: Fold Int) == "overlay (vertex 3) (edge 1 2)"
--
--
-- The Eq instance is currently implemented using the
-- AdjacencyMap 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 and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- 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 Fold then n, m and s can be
-- computed as follows:
--
--
-- n == vertexCount g
-- m == edgeCount g
-- s == size g
--
--
-- Note that size is slightly different from the length
-- method of the Foldable type class, as the latter does not count
-- empty leaves of the expression:
--
--
-- length empty == 0
-- size empty == 1
-- length (vertex x) == 1
-- size (vertex x) == 1
-- length (empty + empty) == 0
-- size (empty + empty) == 2
--
--
-- The size of any graph is positive, and the difference
-- (size g - length g) corresponds to the number
-- of occurrences of empty in an expression g.
--
-- Converting a Fold to the corresponding AdjacencyMap
-- 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.
data Fold a
-- | Construct the empty graph. Complexity: O(1) time, memory
-- and size.
--
--
-- isEmpty empty == True
-- hasVertex x empty == False
-- vertexCount empty == 0
-- edgeCount empty == 0
-- size empty == 1
--
empty :: Fold a
-- | Construct the graph comprising a single isolated vertex.
-- Complexity: O(1) time, memory and size.
--
--
-- isEmpty (vertex x) == False
-- hasVertex x (vertex x) == True
-- vertexCount (vertex x) == 1
-- edgeCount (vertex x) == 0
-- size (vertex x) == 1
--
vertex :: a -> Fold a
-- | Construct the graph comprising a single edge. Complexity:
-- O(1) time, memory and size.
--
--
-- edge x y == connect (vertex x) (vertex y)
-- hasEdge x y (edge x y) == True
-- edgeCount (edge x y) == 1
-- vertexCount (edge 1 1) == 1
-- vertexCount (edge 1 2) == 2
--
edge :: a -> a -> Fold a
-- | 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 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
-- size (overlay x y) == size x + size y
-- vertexCount (overlay 1 2) == 2
-- edgeCount (overlay 1 2) == 0
--
overlay :: Fold a -> Fold a -> Fold a
-- | Connect two graphs. This is an 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).
--
--
-- isEmpty (connect x y) == isEmpty x && isEmpty y
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y
-- vertexCount (connect x y) >= vertexCount x
-- vertexCount (connect x y) <= vertexCount x + vertexCount y
-- edgeCount (connect x y) >= edgeCount x
-- edgeCount (connect x y) >= edgeCount y
-- edgeCount (connect x y) >= vertexCount x * vertexCount y
-- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
-- size (connect x y) == size x + size y
-- vertexCount (connect 1 2) == 2
-- edgeCount (connect 1 2) == 1
--
connect :: Fold a -> Fold a -> Fold a
-- | 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
--
vertices :: [a] -> Fold a
-- | Construct the graph from a list of edges. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- edges [] == empty
-- edges [(x,y)] == edge x y
-- edgeCount . edges == length . nub
--
edges :: [(a, a)] -> Fold a
-- | 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
--
overlays :: [Fold a] -> Fold a
-- | 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 :: [Fold a] -> Fold a
-- | 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
-- given functions. As an example, the complexity of size is
-- O(s), since all functions have cost O(1).
--
--
-- foldg empty vertex overlay connect == id
-- foldg empty vertex overlay (flip connect) == transpose
-- foldg [] return (++) (++) == toList
-- foldg 0 (const 1) (+) (+) == length
-- foldg 1 (const 1) (+) (+) == size
-- foldg True (const False) (&&) (&&) == isEmpty
--
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold a -> b
-- | 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 (path xs) (circuit xs) == True
--
isSubgraphOf :: Ord a => Fold a -> Fold a -> Bool
-- | Check if a graph is empty. A convenient alias for null.
-- 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 x y) == False
--
isEmpty :: Fold a -> Bool
-- | 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
--
size :: Fold a -> Int
-- | Check if a graph contains a given vertex. A convenient alias for
-- elem. Complexity: O(s) time.
--
--
-- hasVertex x empty == False
-- hasVertex x (vertex x) == True
-- hasVertex 1 (vertex 2) == False
-- hasVertex x . removeVertex x == const False
--
hasVertex :: Eq a => a -> Fold a -> Bool
-- | 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 x y) == True
-- hasEdge x y . removeEdge x y == const False
-- hasEdge x y == elem (x,y) . edgeList
--
hasEdge :: Eq a => a -> a -> Fold a -> Bool
-- | The number of vertices in a graph. Complexity: O(s * log(n))
-- time.
--
--
-- vertexCount empty == 0
-- vertexCount (vertex x) == 1
-- vertexCount == length . vertexList
--
vertexCount :: Ord a => Fold a -> Int
-- | The number of edges in a graph. 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.
--
--
-- edgeCount empty == 0
-- edgeCount (vertex x) == 0
-- edgeCount (edge x y) == 1
-- edgeCount == length . edgeList
--
edgeCount :: Ord a => Fold a -> Int
-- | 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
--
vertexList :: Ord a => Fold a -> [a]
-- | 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.
--
--
-- edgeList empty == []
-- edgeList (vertex x) == []
-- edgeList (edge x y) == [(x,y)]
-- edgeList (star 2 [3,1]) == [(2,1), (2,3)]
-- edgeList . edges == nub . sort
-- edgeList . transpose == sort . map swap . edgeList
--
edgeList :: Ord a => Fold a -> [(a, a)]
-- | 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
-- vertexSet . clique == Set.fromList
--
vertexSet :: Ord a => Fold a -> Set a
-- | The set of vertices of a given graph. Like vertexSet but
-- specialised for graphs with vertices of type Int. Complexity:
-- O(s * log(n)) time and O(n) memory.
--
--
-- vertexIntSet empty == IntSet.empty
-- vertexIntSet . vertex == IntSet.singleton
-- vertexIntSet . vertices == IntSet.fromList
-- vertexIntSet . clique == IntSet.fromList
--
vertexIntSet :: Fold Int -> IntSet
-- | The set of edges of a given graph. Complexity: O(s * log(m))
-- time and O(m) memory.
--
--
-- edgeSet empty == Set.empty
-- edgeSet (vertex x) == Set.empty
-- edgeSet (edge x y) == Set.singleton (x,y)
-- edgeSet . edges == Set.fromList
--
edgeSet :: Ord a => Fold a -> Set (a, a)
-- | The sorted adjacency list of a graph. 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.
--
--
-- adjacencyList empty == []
-- adjacencyList (vertex x) == [(x, [])]
-- adjacencyList (edge 1 2) == [(1, [2]), (2, [])]
-- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]
-- stars . adjacencyList == id
--
adjacencyList :: Ord a => Fold a -> [(a, [a])]
-- | The path on a list of vertices. Complexity: O(L) time,
-- memory and size, where L is the length of the given list.
--
--
-- path [] == empty
-- path [x] == vertex x
-- path [x,y] == edge x y
-- path . reverse == transpose . path
--
path :: [a] -> Fold a
-- | The circuit on a list of vertices. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- circuit [] == empty
-- circuit [x] == edge x x
-- circuit [x,y] == edges [(x,y), (y,x)]
-- circuit . reverse == transpose . circuit
--
circuit :: [a] -> Fold a
-- | 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 == transpose . clique
--
clique :: [a] -> Fold a
-- | 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,y1), (x2,y2)]
-- biclique xs ys == connect (vertices xs) (vertices ys)
--
biclique :: [a] -> [a] -> Fold a
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O(L) time, memory and size, where L
-- is the length of the given list.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges [(x,y), (x,z)]
-- star x ys == connect (vertex x) (vertices ys)
--
star :: a -> [a] -> Fold a
-- | The stars formed by overlaying a list of stars. 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 == id
-- overlay (stars xs) (stars ys) == stars (xs ++ ys)
--
stars :: [(a, [a])] -> Fold a
-- | 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 x x) == empty
-- removeVertex 1 (edge 1 2) == vertex 2
-- removeVertex x . removeVertex x == removeVertex x
--
removeVertex :: Eq a => a -> Fold a -> Fold a
-- | 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 . 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
-- size (removeEdge x y z) <= 3 * size z
--
removeEdge :: Eq a => a -> a -> Fold a -> Fold a
-- | Transpose a given graph. Complexity: O(s) time, memory and
-- size.
--
--
-- transpose empty == empty
-- transpose (vertex x) == vertex x
-- transpose (edge x y) == edge y x
-- transpose . transpose == id
-- transpose (box x y) == box (transpose x) (transpose y)
-- edgeList . transpose == sort . map swap . edgeList
--
transpose :: Fold a -> Fold a
-- | 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
--
induce :: (a -> Bool) -> Fold a -> Fold a
-- | Simplify a graph expression. Semantically, this is the identity
-- function, but it simplifies a given polymorphic graph expression
-- according to the laws of the algebra. The function does not compute
-- the simplest possible expression, but uses heuristics to obtain useful
-- simplifications in reasonable time. Complexity: the function performs
-- O(s) graph comparisons. It is guaranteed that the size of the
-- result does not exceed the size of the given expression. Below the
-- operator ~> denotes the is simplified to relation.
--
--
-- simplify == id
-- size (simplify x) <= size x
-- simplify empty ~> empty
-- simplify 1 ~> 1
-- simplify (1 + 1) ~> 1
-- simplify (1 + 2 + 1) ~> 1 + 2
-- simplify (1 * 1 * 1) ~> 1 * 1
--
simplify :: Ord a => Fold a -> Fold a
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Fold.Fold a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Fold.Fold a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Fold.Fold a)
instance GHC.Num.Num a => GHC.Num.Num (Algebra.Graph.Fold.Fold a)
instance GHC.Base.Functor Algebra.Graph.Fold.Fold
instance GHC.Base.Applicative Algebra.Graph.Fold.Fold
instance GHC.Base.Alternative Algebra.Graph.Fold.Fold
instance GHC.Base.MonadPlus Algebra.Graph.Fold.Fold
instance GHC.Base.Monad Algebra.Graph.Fold.Fold
instance Data.Foldable.Foldable Algebra.Graph.Fold.Fold
instance Data.Traversable.Traversable Algebra.Graph.Fold.Fold
instance Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Fold.Fold a)
-- | 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 core type class Graph, a few graph
-- subclasses, and basic polymorphic graph construction primitives.
-- Functions that cannot be implemented fully polymorphically and require
-- the use of an intermediate data type are not included. For example, to
-- compute the size of a Graph expression you will need to use a
-- concrete data type, such as Algebra.Graph.
--
-- See Algebra.Graph.Class for alternative definitions where the
-- core type class is not higher-kinded and permits more instances.
module Algebra.Graph.HigherKinded.Class
-- | The core type class for constructing algebraic graphs is defined by
-- introducing the connect method to the standard MonadPlus
-- class and reusing the following existing methods:
--
--
-- - The empty method comes from the Alternative class
-- and corresponds to the empty graph. This module simply
-- re-exports it.
-- - The vertex graph construction primitive is an alias for
-- pure of the Applicative type class.
-- - Graph overlay is an alias for mplus of the
-- MonadPlus type class.
--
--
-- The Graph type class is characterised by the following minimal
-- set of axioms. In equations we use + and * as
-- convenient shortcuts for overlay and connect,
-- respectively.
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- The core type class Graph corresponds to unlabelled directed
-- graphs. Undirected, Reflexive, Transitive and
-- Preorder graphs can be obtained by extending the minimal set of
-- axioms.
--
-- 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.
class (Traversable g, MonadPlus g) => Graph g
-- | Connect two graphs.
connect :: Graph g => g a -> g a -> g a
-- | The identity of <|>
empty :: Alternative f => f a
-- | Construct the graph comprising a single isolated vertex. An alias for
-- pure.
vertex :: Graph g => a -> g a
-- | Overlay two graphs. An alias for <|>.
overlay :: Graph g => g a -> g a -> g a
-- | The class of undirected graphs that satisfy the following
-- additional axiom.
--
--
-- - connect is commutative:
x * y == y * x
--
class Graph g => Undirected g
-- | The class of reflexive graphs that satisfy the following
-- additional axiom.
--
--
--
-- Or, alternatively, if we remember that vertex is an alias for
-- pure:
--
--
-- pure x == pure x * pure x
--
--
-- Note that by applying the axiom in the reverse direction, one can
-- always remove all self-loops resulting in an irreflexive graph.
-- This type class can therefore be also used in the context of
-- irreflexive graphs.
class Graph g => Reflexive g
-- | The class of transitive graphs that satisfy the following
-- additional axiom.
--
--
--
-- By repeated application of the axiom one can turn any graph into its
-- transitive closure or transitive reduction.
class Graph g => Transitive g
-- | The class of preorder graphs that are both reflexive and
-- transitive.
class (Reflexive g, Transitive g) => Preorder g
-- | Construct the graph comprising a single edge. Complexity: O(1)
-- time, memory and size.
--
--
-- edge x y == connect (vertex x) (vertex y)
-- vertexCount (edge 1 1) == 1
-- vertexCount (edge 1 2) == 2
--
edge :: Graph g => a -> a -> g a
-- | 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
--
vertices :: Graph g => [a] -> g a
-- | Construct the graph from a list of edges. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- edges [] == empty
-- edges [(x,y)] == edge x y
--
edges :: Graph g => [(a, a)] -> g a
-- | 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
--
overlays :: Graph g => [g a] -> g a
-- | 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 :: Graph g => [g a] -> g a
-- | The isSubgraphOf function takes two graphs and returns
-- True if the first graph is a subgraph of the second.
-- Here is the current implementation:
--
--
-- isSubgraphOf x y = overlay x y == y
--
--
-- The complexity therefore depends on the complexity of equality testing
-- of the specific graph instance.
--
--
-- isSubgraphOf empty 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 :: (Graph g, Eq (g a)) => g a -> g a -> Bool
-- | Check if a graph is empty. A convenient alias for null.
-- Complexity: O(s) time.
--
--
-- isEmpty empty == True
-- isEmpty (overlay empty empty) == True
-- isEmpty (vertex x) == False
-- isEmpty (removeVertex x $ vertex x) == True
--
isEmpty :: Graph g => g a -> Bool
-- | Check if a graph contains a given vertex. A convenient alias for
-- elem. Complexity: O(s) time.
--
--
-- hasVertex x empty == False
-- hasVertex x (vertex x) == True
-- hasVertex 1 (vertex 2) == False
-- hasVertex x . removeVertex x == const False
--
hasVertex :: (Eq a, Graph g) => a -> g a -> Bool
-- | 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 x y) == True
-- hasEdge x y == elem (x,y) . edgeList
--
hasEdge :: (Eq (g a), Graph g, Ord a) => a -> a -> g a -> Bool
-- | The number of vertices in a graph. Complexity: O(s * log(n))
-- time.
--
--
-- vertexCount empty == 0
-- vertexCount (vertex x) == 1
-- vertexCount == length . vertexList
--
vertexCount :: (Ord a, Graph g) => g a -> Int
-- | 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
--
vertexList :: (Ord a, Graph g) => g a -> [a]
-- | 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
-- vertexSet . clique == Set.fromList
--
vertexSet :: (Ord a, Graph g) => g a -> Set a
-- | The set of vertices of a given graph. Like vertexSet but
-- specialised for graphs with vertices of type Int. Complexity:
-- O(s * log(n)) time and O(n) memory.
--
--
-- vertexIntSet empty == IntSet.empty
-- vertexIntSet . vertex == IntSet.singleton
-- vertexIntSet . vertices == IntSet.fromList
-- vertexIntSet . clique == IntSet.fromList
--
vertexIntSet :: Graph g => g Int -> IntSet
-- | The path on a list of vertices. Complexity: O(L) time,
-- memory and size, where L is the length of the given list.
--
--
-- path [] == empty
-- path [x] == vertex x
-- path [x,y] == edge x y
--
path :: Graph g => [a] -> g a
-- | The circuit on a list of vertices. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- circuit [] == empty
-- circuit [x] == edge x x
-- circuit [x,y] == edges [(x,y), (y,x)]
--
circuit :: Graph g => [a] -> g a
-- | 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 :: Graph g => [a] -> g a
-- | 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,y1), (x2,y2)]
-- biclique xs ys == connect (vertices xs) (vertices ys)
--
biclique :: Graph g => [a] -> [a] -> g a
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O(L) time, memory and size, where L
-- is the length of the given list.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges [(x,y), (x,z)]
-- star x ys == connect (vertex x) (vertices ys)
--
star :: Graph g => a -> [a] -> g a
-- | The star transpose formed by a list of leaves connected to a
-- centre vertex. Complexity: O(L) time, memory and size, where
-- L is the length of the given list.
--
--
-- starTranspose x [] == vertex x
-- starTranspose x [y] == edge y x
-- starTranspose x [y,z] == edges [(y,x), (z,x)]
-- starTranspose x ys == connect (vertices ys) (vertex x)
-- starTranspose x ys == transpose (star x ys)
--
starTranspose :: Graph g => a -> [a] -> g a
-- | 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)]
--
tree :: Graph g => Tree a -> g a
-- | 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
--
forest :: Graph g => Forest a -> g a
-- | Construct a mesh graph from two lists of vertices. Complexity:
-- O(L1 * L2) time, memory and size, where L1 and L2
-- are the lengths of the given lists.
--
--
-- mesh xs [] == empty
-- mesh [] ys == empty
-- mesh [x] [y] == vertex (x, y)
-- mesh xs ys == box (path xs) (path ys)
-- mesh [1..3] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b'))
-- , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ]
--
mesh :: Graph g => [a] -> [b] -> g (a, b)
-- | Construct a torus graph from two lists of vertices. Complexity:
-- O(L1 * L2) time, memory and size, where L1 and L2
-- are the lengths of the given lists.
--
--
-- torus xs [] == empty
-- torus [] ys == empty
-- torus [x] [y] == edge (x,y) (x,y)
-- torus xs ys == box (circuit xs) (circuit ys)
-- torus [1,2] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b'))
-- , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ]
--
torus :: Graph g => [a] -> [b] -> g (a, b)
-- | Construct a De Bruijn graph of a given non-negative dimension
-- using symbols from a given alphabet. Complexity: O(A^(D + 1))
-- time, memory and size, where A is the size of the alphabet and
-- D is the dimension of the graph.
--
--
-- deBruijn 0 xs == edge [] []
-- n > 0 ==> deBruijn n [] == empty
-- deBruijn 1 [0,1] == edges [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
-- deBruijn 2 "0" == edge "00" "00"
-- deBruijn 2 "01" == edges [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
-- , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
-- transpose (deBruijn n xs) == fmap reverse $ deBruijn n xs
-- vertexCount (deBruijn n xs) == (length $ nub xs)^n
-- n > 0 ==> edgeCount (deBruijn n xs) == (length $ nub xs)^(n + 1)
--
deBruijn :: Graph g => Int -> [a] -> g [a]
-- | 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 x x) == empty
-- removeVertex 1 (edge 1 2) == vertex 2
-- removeVertex x . removeVertex x == removeVertex x
--
removeVertex :: (Eq a, Graph g) => a -> g a -> g a
-- | 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 == mergeVertices (== x) y
--
replaceVertex :: (Eq a, Graph g) => a -> a -> g a -> g a
-- | Merge vertices satisfying a given predicate into a given vertex.
-- Complexity: O(s) time, memory and size, assuming that the
-- predicate takes O(1) to be evaluated.
--
--
-- mergeVertices (const False) x == id
-- mergeVertices (== x) y == replaceVertex x y
-- mergeVertices even 1 (0 * 2) == 1 * 1
-- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1
--
mergeVertices :: Graph g => (a -> Bool) -> a -> g a -> g a
-- | Split a vertex into a list of vertices with the same connectivity.
-- Complexity: O(s + k * L) time, memory and size, where k
-- is the number of occurrences of the vertex in the expression and
-- L is the length of the given list.
--
--
-- splitVertex x [] == removeVertex x
-- splitVertex x [x] == id
-- splitVertex x [y] == replaceVertex x y
-- splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
--
splitVertex :: (Eq a, Graph g) => a -> [a] -> g a -> g a
-- | 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
--
induce :: Graph g => (a -> Bool) -> g a -> g a
-- | Compute the Cartesian product of graphs. Complexity: O(s1 *
-- s2) time, memory and size, where s1 and s2 are the
-- sizes of the given graphs.
--
--
-- box (path [0,1]) (path "ab") == edges [ ((0,'a'), (0,'b'))
-- , ((0,'a'), (1,'a'))
-- , ((0,'b'), (1,'b'))
-- , ((1,'a'), (1,'b')) ]
--
--
-- Up to an isomorphism between the resulting vertex types, this
-- operation is commutative, associative,
-- distributes over overlay, 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 (overlay y z) == overlay (box x y) (box x z)
-- box x (vertex ()) ~~ x
-- box x empty ~~ empty
-- vertexCount (box x y) == vertexCount x * vertexCount y
-- edgeCount (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y
--
box :: Graph g => g a -> g b -> g (a, b)
instance Algebra.Graph.HigherKinded.Class.Graph Algebra.Graph.Graph
instance Algebra.Graph.HigherKinded.Class.Graph Algebra.Graph.Fold.Fold
-- | 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 core type class Graph, a few graph
-- subclasses, and basic polymorphic graph construction primitives.
-- Functions that cannot be implemented fully polymorphically and require
-- the use of an intermediate data type are not included. For example, to
-- compute the number of vertices in a Graph expression you will
-- need to use a concrete data type, such as Algebra.Graph.Fold.
-- Other useful Graph instances are defined in
-- Algebra.Graph, Algebra.Graph.AdjacencyMap and
-- Algebra.Graph.Relation.
--
-- See Algebra.Graph.HigherKinded.Class for the higher-kinded
-- version of the core graph type class.
module Algebra.Graph.Class
-- | The core type class for constructing algebraic graphs, characterised
-- by the following minimal set of axioms. In equations we use +
-- and * as convenient shortcuts for overlay and
-- connect, respectively.
--
--
-- - overlay is commutative and associative:
x + y == y + x
-- x + (y + z) == (x + y) + z
-- - connect is associative and has empty as the
-- identity:
x * empty == x empty * x == x x * (y * z) == (x * y) *
-- z
-- - connect distributes over overlay:
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.
--
--
--
-- The core type class Graph corresponds to unlabelled directed
-- graphs. Undirected, Reflexive, Transitive and
-- Preorder graphs can be obtained by extending the minimal set of
-- axioms.
--
-- 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.
class Graph g where {
type family Vertex g;
}
-- | Construct the empty graph.
empty :: Graph g => g
-- | Construct the graph with a single vertex.
vertex :: Graph g => Vertex g -> g
-- | Overlay two graphs.
overlay :: Graph g => g -> g -> g
-- | Connect two graphs.
connect :: Graph g => g -> g -> g
-- | The class of undirected graphs that satisfy the following
-- additional axiom.
--
--
-- - connect is commutative:
x * y == y * x
--
class Graph g => Undirected g
-- | The class of reflexive graphs that satisfy the following
-- additional axiom.
--
--
--
-- Note that by applying the axiom in the reverse direction, one can
-- always remove all self-loops resulting in an irreflexive graph.
-- This type class can therefore be also used in the context of
-- irreflexive graphs.
class Graph g => Reflexive g
-- | The class of transitive graphs that satisfy the following
-- additional axiom.
--
--
--
-- By repeated application of the axiom one can turn any graph into its
-- transitive closure or transitive reduction.
class Graph g => Transitive g
-- | The class of preorder graphs that are both reflexive and
-- transitive.
class (Reflexive g, Transitive g) => Preorder g
-- | Construct the graph comprising a single edge. Complexity: O(1)
-- time, memory and size.
--
--
-- edge x y == connect (vertex x) (vertex y)
--
edge :: Graph g => Vertex g -> Vertex g -> g
-- | 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 :: Graph g => [Vertex g] -> g
-- | 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
--
overlays :: Graph g => [g] -> g
-- | 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
--
connects :: Graph g => [g] -> g
-- | Construct the graph from a list of edges. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- edges [] == empty
-- edges [(x,y)] == edge x y
--
edges :: Graph g => [(Vertex g, Vertex g)] -> g
-- | The isSubgraphOf function takes two graphs and returns
-- True if the first graph is a subgraph of the second.
-- Here is the current implementation:
--
--
-- isSubgraphOf x y = overlay x y == y
--
--
-- The complexity therefore depends on the complexity of equality testing
-- of the specific graph instance.
--
--
-- isSubgraphOf empty 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 :: (Graph g, Eq g) => g -> g -> Bool
-- | The path on a list of vertices. Complexity: O(L) time,
-- memory and size, where L is the length of the given list.
--
--
-- path [] == empty
-- path [x] == vertex x
-- path [x,y] == edge x y
--
path :: Graph g => [Vertex g] -> g
-- | The circuit on a list of vertices. Complexity: O(L)
-- time, memory and size, where L is the length of the given list.
--
--
-- circuit [] == empty
-- circuit [x] == edge x x
-- circuit [x,y] == edges [(x,y), (y,x)]
--
circuit :: Graph g => [Vertex g] -> g
-- | 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 :: Graph g => [Vertex g] -> g
-- | 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,y1), (x2,y2)]
-- biclique xs ys == connect (vertices xs) (vertices ys)
--
biclique :: Graph g => [Vertex g] -> [Vertex g] -> g
-- | The star formed by a centre vertex connected to a list of
-- leaves. Complexity: O(L) time, memory and size, where L
-- is the length of the given list.
--
--
-- star x [] == vertex x
-- star x [y] == edge x y
-- star x [y,z] == edges [(x,y), (x,z)]
-- star x ys == connect (vertex x) (vertices ys)
--
star :: Graph g => Vertex g -> [Vertex g] -> g
-- | The star transpose formed by a list of leaves connected to a
-- centre vertex. Complexity: O(L) time, memory and size, where
-- L is the length of the given list.
--
--
-- starTranspose x [] == vertex x
-- starTranspose x [y] == edge y x
-- starTranspose x [y,z] == edges [(y,x), (z,x)]
-- starTranspose x ys == connect (vertices ys) (vertex x)
-- starTranspose x ys == transpose (star x ys)
--
starTranspose :: Graph g => Vertex g -> [Vertex g] -> g
-- | 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)]
--
tree :: Graph g => Tree (Vertex g) -> g
-- | 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
--
forest :: Graph g => Forest (Vertex g) -> g
instance Algebra.Graph.Class.Preorder ()
instance Algebra.Graph.Class.Preorder g => Algebra.Graph.Class.Preorder (GHC.Base.Maybe g)
instance Algebra.Graph.Class.Preorder g => Algebra.Graph.Class.Preorder (a -> g)
instance (Algebra.Graph.Class.Preorder g, Algebra.Graph.Class.Preorder h) => Algebra.Graph.Class.Preorder (g, h)
instance (Algebra.Graph.Class.Preorder g, Algebra.Graph.Class.Preorder h, Algebra.Graph.Class.Preorder i) => Algebra.Graph.Class.Preorder (g, h, i)
instance Algebra.Graph.Class.Transitive ()
instance Algebra.Graph.Class.Transitive g => Algebra.Graph.Class.Transitive (GHC.Base.Maybe g)
instance Algebra.Graph.Class.Transitive g => Algebra.Graph.Class.Transitive (a -> g)
instance (Algebra.Graph.Class.Transitive g, Algebra.Graph.Class.Transitive h) => Algebra.Graph.Class.Transitive (g, h)
instance (Algebra.Graph.Class.Transitive g, Algebra.Graph.Class.Transitive h, Algebra.Graph.Class.Transitive i) => Algebra.Graph.Class.Transitive (g, h, i)
instance Algebra.Graph.Class.Reflexive ()
instance Algebra.Graph.Class.Reflexive g => Algebra.Graph.Class.Reflexive (GHC.Base.Maybe g)
instance Algebra.Graph.Class.Reflexive g => Algebra.Graph.Class.Reflexive (a -> g)
instance (Algebra.Graph.Class.Reflexive g, Algebra.Graph.Class.Reflexive h) => Algebra.Graph.Class.Reflexive (g, h)
instance (Algebra.Graph.Class.Reflexive g, Algebra.Graph.Class.Reflexive h, Algebra.Graph.Class.Reflexive i) => Algebra.Graph.Class.Reflexive (g, h, i)
instance Algebra.Graph.Class.Undirected ()
instance Algebra.Graph.Class.Undirected g => Algebra.Graph.Class.Undirected (GHC.Base.Maybe g)
instance Algebra.Graph.Class.Undirected g => Algebra.Graph.Class.Undirected (a -> g)
instance (Algebra.Graph.Class.Undirected g, Algebra.Graph.Class.Undirected h) => Algebra.Graph.Class.Undirected (g, h)
instance (Algebra.Graph.Class.Undirected g, Algebra.Graph.Class.Undirected h, Algebra.Graph.Class.Undirected i) => Algebra.Graph.Class.Undirected (g, h, i)
instance Algebra.Graph.Class.Graph (Algebra.Graph.Graph a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a)
instance Algebra.Graph.Class.Graph (Algebra.Graph.Fold.Fold a)
instance Algebra.Graph.Class.Graph Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap
instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.Internal.Relation a)
instance Algebra.Graph.Class.Graph ()
instance Algebra.Graph.Class.Graph g => Algebra.Graph.Class.Graph (GHC.Base.Maybe g)
instance Algebra.Graph.Class.Graph g => Algebra.Graph.Class.Graph (a -> g)
instance (Algebra.Graph.Class.Graph g, Algebra.Graph.Class.Graph h) => Algebra.Graph.Class.Graph (g, h)
instance (Algebra.Graph.Class.Graph g, Algebra.Graph.Class.Graph h, Algebra.Graph.Class.Graph i) => Algebra.Graph.Class.Graph (g, h, i)
-- | This module exposes the implementation of derived binary relation data
-- types. The API is unstable and unsafe, and is exposed only for
-- documentation. You should use the non-internal modules
-- Algebra.Graph.Relation.Reflexive,
-- Algebra.Graph.Relation.Symmetric,
-- Algebra.Graph.Relation.Transitive and
-- Algebra.Graph.Relation.Preorder instead.
module Algebra.Graph.Relation.InternalDerived
-- | The ReflexiveRelation data type represents a reflexive
-- binary relation over a set of elements. Reflexive relations
-- satisfy all laws of the Reflexive type class and, in
-- particular, the self-loop axiom:
--
--
-- vertex x == vertex x * vertex x
--
--
-- The Show instance produces reflexively closed expressions:
--
--
-- show (1 :: ReflexiveRelation Int) == "edge 1 1"
-- show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"
--
newtype ReflexiveRelation a
ReflexiveRelation :: Relation a -> ReflexiveRelation a
[fromReflexive] :: ReflexiveRelation a -> Relation a
-- | The SymmetricRelation data type represents a symmetric
-- binary relation over a set of elements. Symmetric relations
-- satisfy all laws of the Undirected type class and, in
-- particular, the commutativity of connect:
--
--
-- connect x y == connect y x
--
--
-- The Show instance produces symmetrically closed expressions:
--
--
-- show (1 :: SymmetricRelation Int) == "vertex 1"
-- show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"
--
newtype SymmetricRelation a
SymmetricRelation :: Relation a -> SymmetricRelation a
[fromSymmetric] :: SymmetricRelation a -> Relation a
-- | The TransitiveRelation data type represents a transitive
-- binary relation over a set of elements. Transitive relations
-- satisfy all laws of the Transitive type class and, in
-- particular, the closure axiom:
--
--
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z
--
--
-- For example, the following holds:
--
--
-- path xs == (clique xs :: TransitiveRelation Int)
--
--
-- The Show instance produces transitively closed expressions:
--
--
-- show (1 * 2 :: TransitiveRelation Int) == "edge 1 2"
-- show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"
--
newtype TransitiveRelation a
TransitiveRelation :: Relation a -> TransitiveRelation a
[fromTransitive] :: TransitiveRelation a -> Relation a
-- | The PreorderRelation data type represents a binary relation
-- that is both reflexive and transitive. Preorders satisfy all laws
-- of the Preorder type class and, in particular, the
-- self-loop axiom:
--
--
-- vertex x == vertex x * vertex x
--
--
-- and the closure axiom:
--
--
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z
--
--
-- For example, the following holds:
--
--
-- path xs == (clique xs :: PreorderRelation Int)
--
--
-- The Show instance produces reflexively and transitively closed
-- expressions:
--
--
-- show (1 :: PreorderRelation Int) == "edge 1 1"
-- show (1 * 2 :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]"
-- show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"
--
newtype PreorderRelation a
PreorderRelation :: Relation a -> PreorderRelation a
[fromPreorder] :: PreorderRelation a -> Relation a
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Reflexive (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Transitive (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Preorder (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Transitive (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Undirected (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a)
instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a)
instance GHC.Classes.Ord a => Algebra.Graph.Class.Reflexive (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a)
-- | An abstract implementation of transitive binary relations. Use
-- Algebra.Graph.Class for polymorphic construction and
-- manipulation.
module Algebra.Graph.Relation.Transitive
-- | The TransitiveRelation data type represents a transitive
-- binary relation over a set of elements. Transitive relations
-- satisfy all laws of the Transitive type class and, in
-- particular, the closure axiom:
--
--
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z
--
--
-- For example, the following holds:
--
--
-- path xs == (clique xs :: TransitiveRelation Int)
--
--
-- The Show instance produces transitively closed expressions:
--
--
-- show (1 * 2 :: TransitiveRelation Int) == "edge 1 2"
-- show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"
--
data TransitiveRelation a
-- | Construct a transitive relation from a Relation. Complexity:
-- O(1) time.
fromRelation :: Relation a -> TransitiveRelation a
-- | Extract the underlying relation. Complexity: O(n * m * log(m))
-- time.
toRelation :: Ord a => TransitiveRelation a -> Relation a
-- | An abstract implementation of symmetric binary relations. Use
-- Algebra.Graph.Class for polymorphic construction and
-- manipulation.
module Algebra.Graph.Relation.Symmetric
-- | The SymmetricRelation data type represents a symmetric
-- binary relation over a set of elements. Symmetric relations
-- satisfy all laws of the Undirected type class and, in
-- particular, the commutativity of connect:
--
--
-- connect x y == connect y x
--
--
-- The Show instance produces symmetrically closed expressions:
--
--
-- show (1 :: SymmetricRelation Int) == "vertex 1"
-- show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"
--
data SymmetricRelation a
-- | Construct a symmetric relation from a Relation. Complexity:
-- O(1) time.
fromRelation :: Relation a -> SymmetricRelation a
-- | Extract the underlying relation. Complexity: O(m*log(m)) time.
toRelation :: Ord a => SymmetricRelation a -> Relation a
-- | The set of neighbours of an element x is the set of
-- elements that are related to it, i.e. neighbours x == { a | aRx
-- }. In the context of undirected graphs, this corresponds to the
-- set of adjacent vertices of vertex x.
--
--
-- neighbours x empty == Set.empty
-- neighbours x (vertex x) == Set.empty
-- neighbours x (edge x y) == Set.fromList [y]
-- neighbours y (edge x y) == Set.fromList [x]
--
neighbours :: Ord a => a -> SymmetricRelation a -> Set a
-- | An abstract implementation of reflexive binary relations. Use
-- Algebra.Graph.Class for polymorphic construction and
-- manipulation.
module Algebra.Graph.Relation.Reflexive
-- | The ReflexiveRelation data type represents a reflexive
-- binary relation over a set of elements. Reflexive relations
-- satisfy all laws of the Reflexive type class and, in
-- particular, the self-loop axiom:
--
--
-- vertex x == vertex x * vertex x
--
--
-- The Show instance produces reflexively closed expressions:
--
--
-- show (1 :: ReflexiveRelation Int) == "edge 1 1"
-- show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"
--
data ReflexiveRelation a
-- | Construct a reflexive relation from a Relation. Complexity:
-- O(1) time.
fromRelation :: Relation a -> ReflexiveRelation a
-- | Extract the underlying relation. Complexity: O(n*log(m)) time.
toRelation :: Ord a => ReflexiveRelation a -> Relation a
-- | An abstract implementation of preorder relations. Use
-- Algebra.Graph.Class for polymorphic construction and
-- manipulation.
module Algebra.Graph.Relation.Preorder
-- | The PreorderRelation data type represents a binary relation
-- that is both reflexive and transitive. Preorders satisfy all laws
-- of the Preorder type class and, in particular, the
-- self-loop axiom:
--
--
-- vertex x == vertex x * vertex x
--
--
-- and the closure axiom:
--
--
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z
--
--
-- For example, the following holds:
--
--
-- path xs == (clique xs :: PreorderRelation Int)
--
--
-- The Show instance produces reflexively and transitively closed
-- expressions:
--
--
-- show (1 :: PreorderRelation Int) == "edge 1 1"
-- show (1 * 2 :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]"
-- show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"
--
data PreorderRelation a
-- | Construct a preorder relation from a Relation. Complexity:
-- O(1) time.
fromRelation :: Relation a -> PreorderRelation a
-- | Extract the underlying relation. Complexity: O(n * m * log(m))
-- time.
toRelation :: Ord a => PreorderRelation a -> Relation a
-- | 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.
module Algebra.Graph.Labelled
-- | 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.
data Graph e a
Empty :: Graph e a
Vertex :: a -> Graph e a
Connect :: e -> (Graph e a) -> (Graph e a) -> Graph e a
-- | A type synonym for unlabelled graphs.
type UnlabelledGraph a = Graph Bool a
-- | Construct the empty graph. An alias for the constructor
-- Empty. Complexity: O(1) time, memory and size.
empty :: Graph e a
-- | Construct the graph comprising a single isolated vertex. An
-- alias for the constructor Vertex. Complexity: O(1) time,
-- memory and size.
vertex :: a -> Graph e a
-- | Construct the graph comprising a single edge with the label
-- one. Complexity: O(1) time, memory and size.
edge :: Dioid e => a -> a -> Graph e a
-- | Overlay two graphs. An alias for Connect zero.
-- This is a commutative, associative and idempotent operation with the
-- identity empty. Complexity: O(1) time and memory,
-- O(s1 + s2) size.
overlay :: Semilattice e => Graph e a -> Graph e a -> Graph e a
-- | Connect two graphs. An alias for Connect one.
-- This is an associative operation with the identity empty, which
-- distributes over overlay and obeys the decomposition axiom. See
-- the full list of laws in Algebra.Graph. 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 :: Dioid e => Graph e a -> Graph e a -> Graph e a
-- | 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).
connectBy :: e -> Graph e a -> Graph e a -> Graph e a
-- | The left-hand part of a convenient ternary-ish operator x
-- -<e>- y for connecting graphs with labelled edges. For
-- example:
--
--
-- x = vertex "x"
-- y = vertex "y"
-- z = x -<2>- y
--
(-<) :: Graph e a -> e -> (Graph e a, e)
infixl 5 -<
-- | The right-hand part of a convenient ternary-ish operator x
-- -<e>- y for connecting graphs with labelled edges. For
-- example:
--
--
-- x = vertex "x"
-- y = vertex "y"
-- z = x -<2>- y
--
(>-) :: (Graph e a, e) -> Graph e a -> Graph e a
infixl 5 >-
-- | Extract the label of a specified edge from a graph.
edgeLabel :: (Eq a, Semilattice e) => a -> a -> Graph e a -> e
instance Data.Traversable.Traversable (Algebra.Graph.Labelled.Graph e)
instance (GHC.Show.Show a, GHC.Show.Show e) => GHC.Show.Show (Algebra.Graph.Labelled.Graph e a)
instance GHC.Base.Functor (Algebra.Graph.Labelled.Graph e)
instance Data.Foldable.Foldable (Algebra.Graph.Labelled.Graph e)
instance Algebra.Graph.Label.Dioid e => Algebra.Graph.Class.Graph (Algebra.Graph.Labelled.Graph e a)