-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A library for algebraic graph construction and transformation
--   
--   <a>Alga</a> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory and implementation details.
--   
--   The top-level module <a>Algebra.Graph</a> defines the core data type
--   <a>Graph</a>, which is a deep embedding of four graph construction
--   primitives <i>empty</i>, <i>vertex</i>, <i>overlay</i> and
--   <i>connect</i>. To represent non-empty graphs, see
--   <a>Algebra.Graph.NonEmpty</a>. More conventional graph representations
--   can be found in <a>Algebra.Graph.AdjacencyMap</a> and
--   <a>Algebra.Graph.Relation</a>.
--   
--   The type classes defined in <a>Algebra.Graph.Class</a> and
--   <a>Algebra.Graph.HigherKinded.Class</a> can be used for polymorphic
--   graph construction and manipulation. Also see
--   <a>Algebra.Graph.Fold</a> 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 <a>discussions on the library API</a>.
@package algebraic-graphs
@version 0.1.1.1


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the core type class <a>Graph</a>, 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 <a>Graph</a> expression you will
--   need to use a concrete data type, such as <a>Algebra.Graph.Fold</a>.
--   Other useful <a>Graph</a> instances are defined in
--   <a>Algebra.Graph</a>, <a>Algebra.Graph.AdjacencyMap</a> and
--   <a>Algebra.Graph.Relation</a>.
--   
--   See <a>Algebra.Graph.HigherKinded.Class</a> 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 <tt>+</tt>
--   and <tt>*</tt> as convenient shortcuts for <a>overlay</a> and
--   <a>connect</a>, respectively.
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   The core type class <a>Graph</a> corresponds to unlabelled directed
--   graphs. <a>Undirected</a>, <a>Reflexive</a>, <a>Transitive</a> and
--   <a>Preorder</a> graphs can be obtained by extending the minimal set of
--   axioms.
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> will denote the number of vertices in the graph, <i>m</i>
--   will denote the number of edges in the graph, and <i>s</i> will denote
--   the <i>size</i> of the corresponding <a>Graph</a> 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 <i>undirected graphs</i> that satisfy the following
--   additional axiom.
--   
--   <ul>
--   <li><a>connect</a> is commutative:<pre>x * y == y * x</pre></li>
--   </ul>
class Graph g => Undirected g

-- | The class of <i>reflexive graphs</i> that satisfy the following
--   additional axiom.
--   
--   <ul>
--   <li>Each vertex has a <i>self-loop</i>:<pre>vertex x == vertex x *
--   vertex x</pre></li>
--   </ul>
--   
--   Note that by applying the axiom in the reverse direction, one can
--   always remove all self-loops resulting in an <i>irreflexive graph</i>.
--   This type class can therefore be also used in the context of
--   irreflexive graphs.
class Graph g => Reflexive g

-- | The class of <i>transitive graphs</i> that satisfy the following
--   additional axiom.
--   
--   <ul>
--   <li>The <i>closure</i> axiom: graphs with equal transitive closures
--   are equal.<pre>y /= empty ==&gt; x * y + x * z + y * z == x * y + y *
--   z</pre></li>
--   </ul>
--   
--   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 <i>preorder graphs</i> that are both reflexive and
--   transitive.
class (Reflexive g, Transitive g) => Preorder g

-- | Construct the graph comprising a single edge. Complexity: <i>O(1)</i>
--   time, memory and size.
--   
--   <pre>
--   edge x y == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   </pre>
edge :: Graph g => Vertex g -> Vertex g -> g

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L)</i> time, memory and size, where <i>L</i> is the
--   length of the given list.
--   
--   <pre>
--   vertices []  == <a>empty</a>
--   vertices [x] == <a>vertex</a> x
--   </pre>
vertices :: Graph g => [Vertex g] -> g

-- | Overlay a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   overlays []    == <a>empty</a>
--   overlays [x]   == x
--   overlays [x,y] == <a>overlay</a> x y
--   overlays       == <a>foldr</a> <a>overlay</a> <a>empty</a>
--   </pre>
overlays :: Graph g => [g] -> g

-- | Connect a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   connects []    == <a>empty</a>
--   connects [x]   == x
--   connects [x,y] == <a>connect</a> x y
--   connects       == <a>foldr</a> <a>connect</a> <a>empty</a>
--   </pre>
connects :: Graph g => [g] -> g

-- | Construct the graph from a list of edges. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   edges []      == <a>empty</a>
--   edges [(x,y)] == <a>edge</a> x y
--   </pre>
edges :: Graph g => [(Vertex g, Vertex g)] -> g

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Here is the current implementation:
--   
--   <pre>
--   isSubgraphOf x y = <a>overlay</a> x y == y
--   </pre>
--   
--   The complexity therefore depends on the complexity of equality testing
--   of the specific graph instance.
--   
--   <pre>
--   isSubgraphOf <a>empty</a>         x             == True
--   isSubgraphOf (<a>vertex</a> x)    <a>empty</a>         == False
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path</a> xs)     (<a>circuit</a> xs)  == True
--   </pre>
isSubgraphOf :: (Graph g, Eq g) => g -> g -> Bool

-- | The <i>path</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   path []    == <a>empty</a>
--   path [x]   == <a>vertex</a> x
--   path [x,y] == <a>edge</a> x y
--   </pre>
path :: Graph g => [Vertex g] -> g

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   circuit []    == <a>empty</a>
--   circuit [x]   == <a>edge</a> x x
--   circuit [x,y] == <a>edges</a> [(x,y), (y,x)]
--   </pre>
circuit :: Graph g => [Vertex g] -> g

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   clique []         == <a>empty</a>
--   clique [x]        == <a>vertex</a> x
--   clique [x,y]      == <a>edge</a> x y
--   clique [x,y,z]    == <a>edges</a> [(x,y), (x,z), (y,z)]
--   clique (xs ++ ys) == <a>connect</a> (clique xs) (clique ys)
--   </pre>
clique :: Graph g => [Vertex g] -> g

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(L1 +
--   L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i> are the
--   lengths of the given lists.
--   
--   <pre>
--   biclique []      []      == <a>empty</a>
--   biclique [x]     []      == <a>vertex</a> x
--   biclique []      [y]     == <a>vertex</a> y
--   biclique [x1,x2] [y1,y2] == <a>edges</a> [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
--   biclique xs      ys      == <a>connect</a> (<a>vertices</a> xs) (<a>vertices</a> ys)
--   </pre>
biclique :: Graph g => [Vertex g] -> [Vertex g] -> g

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O(L)</i> time, memory and size, where <i>L</i>
--   is the length of the given list.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges</a> [(x,y), (x,z)]
--   star x ys    == <a>connect</a> (<a>vertex</a> x) (<a>vertices</a> ys)
--   </pre>
star :: Graph g => Vertex g -> [Vertex g] -> g

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges</a> [(y,x), (z,x)]
--   starTranspose x ys    == <a>connect</a> (<a>vertices</a> ys) (<a>vertex</a> x)
--   starTranspose x ys    == transpose (<a>star</a> x ys)
--   </pre>
starTranspose :: Graph g => Vertex g -> [Vertex g] -> g

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O(T)</i> time, memory and size, where
--   <i>T</i> is the size of the given tree (i.e. the number of vertices in
--   the tree).
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path</a> [x,y,z]
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges</a> [(1,2), (1,3), (3,4), (3,5)]
--   </pre>
tree :: Graph g => Tree (Vertex g) -> g

-- | The <i>forest graph</i> constructed from a given <a>Forest</a> data
--   structure. Complexity: <i>O(F)</i> time, memory and size, where
--   <i>F</i> is the size of the given forest (i.e. the number of vertices
--   in the forest).
--   
--   <pre>
--   forest []                                                  == <a>empty</a>
--   forest [x]                                                 == <a>tree</a> x
--   forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == <a>edges</a> [(1,2), (1,3), (4,5)]
--   forest                                                     == <a>overlays</a> . map <a>tree</a>
--   </pre>
forest :: Graph g => Forest (Vertex g) -> g

-- | The <a>ToGraph</a> type class captures data types that can be
--   converted to polymorphic graph expressions. The conversion method
--   <a>toGraph</a> semantically acts as the identity on graph data
--   structures, but allows to convert graphs between different data
--   representations.
--   
--   <pre>
--         toGraph (g     :: <a>Graph</a> a  ) :: <a>Graph</a> a       == g
--   <a>show</a> (toGraph (1 * 2 :: <a>Graph</a> Int) :: <a>Relation</a> Int) == "edge 1 2"
--   </pre>
--   
--   The second method <a>foldg</a> is used for generalised graph folding.
--   It recursively collapses a given data type by applying the provided
--   graph construction primitives. The order of arguments is: empty,
--   vertex, overlay and connect, and it is assumed that the functions
--   satisfy the axioms of the algebra. The following law establishes the
--   relation between <a>toGraph</a> and <a>foldg</a>:
--   
--   <pre>
--   toGraph == foldg <a>empty</a> <a>vertex</a> <a>overlay</a> <a>connect</a>
--   </pre>
class ToGraph t where {
    type family ToVertex t;
}
toGraph :: (ToGraph t, Graph g, Vertex g ~ ToVertex t) => t -> g
foldg :: ToGraph t => r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r
instance Algebra.Graph.Class.Graph (Algebra.Graph.Class.G a)
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 ()
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 adjacency maps. The API is
--   unstable and unsafe, and is exposed only for documentation. You should
--   use the non-internal module <a>Algebra.Graph.AdjacencyMap</a> instead.
module Algebra.Graph.AdjacencyMap.Internal

-- | The <a>AdjacencyMap</a> data type represents a graph by a map of
--   vertices to their adjacency sets. We define a <a>Num</a> instance as a
--   convenient notation for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Show</a> instance is defined using basic graph construction
--   primitives:
--   
--   <pre>
--   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)"
--   </pre>
--   
--   The <a>Eq</a> instance satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> and <i>m</i> will denote the number of vertices and edges in
--   the graph, respectively.
data AdjacencyMap a
AM :: !(Map a (Set a)) -> GraphKL a -> AdjacencyMap a

-- | The <i>adjacency map</i> of the graph: each vertex is associated with
--   a set of its direct successors.
[adjacencyMap] :: AdjacencyMap a -> !(Map a (Set a))

-- | Cached King-Launchbury representation. <i>Note: this field is for
--   internal use only</i>.
[graphKL] :: AdjacencyMap a -> GraphKL a

-- | Construct an <a>AdjacencyMap</a> from a map of successor sets and
--   (lazily) compute the corresponding King-Launchbury representation.
--   <i>Note: this function is for internal use only</i>.
mkAM :: Ord a => Map 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. <i>Note: this function is for internal use only</i>.
--   
--   <pre>
--   consistent <a>empty</a>                  == True
--   consistent (<a>vertex</a> x)             == True
--   consistent (<a>overlay</a> x y)          == True
--   consistent (<a>connect</a> x y)          == True
--   consistent (<a>edge</a> x y)             == True
--   consistent (<a>edges</a> xs)             == True
--   consistent (<a>graph</a> xs ys)          == True
--   consistent (<a>fromAdjacencyList</a> xs) == True
--   </pre>
consistent :: Ord a => AdjacencyMap a -> Bool

-- | <a>GraphKL</a> encapsulates King-Launchbury graphs, which are
--   implemented in the <a>Data.Graph</a> module of the <tt>containers</tt>
--   library. <i>Note: this data structure is for internal use only</i>.
--   
--   If <tt>mkGraphKL (adjacencyMap g) == h</tt> then the following holds:
--   
--   <pre>
--   map (<a>fromVertexKL</a> h) (<a>vertices</a> $ <a>toGraphKL</a> h)                               == <a>vertexList</a> g
--   map (\(x, y) -&gt; (<a>fromVertexKL</a> h x, <a>fromVertexKL</a> h y)) (<a>edges</a> $ <a>toGraphKL</a> h) == <a>edgeList</a> g
--   </pre>
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 <a>Data.Graph.Vertex</a> to vertices of type <tt>a</tt>.
[fromVertexKL] :: GraphKL a -> Vertex -> a

-- | A mapping from vertices of type <tt>a</tt> to
--   <a>Data.Graph.Vertex</a>. Returns <a>Nothing</a> if the argument is
--   not in the graph.
[toVertexKL] :: GraphKL a -> a -> Maybe Vertex

-- | Build <a>GraphKL</a> from a map of successor sets. <i>Note: this
--   function is for internal use only</i>.
mkGraphKL :: Ord a => Map a (Set a) -> GraphKL a
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 => Algebra.Graph.Class.Graph (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 Algebra.Graph.Class.ToGraph (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a)


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the <a>AdjacencyMap</a> data type, as well as
--   associated operations and algorithms. <a>AdjacencyMap</a> is an
--   instance of the <a>Graph</a> type class, which can be used for
--   polymorphic graph construction and manipulation.
--   <a>Algebra.Graph.IntAdjacencyMap</a> defines adjacency maps
--   specialised to graphs with <tt>Int</tt> vertices.
module Algebra.Graph.AdjacencyMap

-- | The <a>AdjacencyMap</a> data type represents a graph by a map of
--   vertices to their adjacency sets. We define a <a>Num</a> instance as a
--   convenient notation for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Show</a> instance is defined using basic graph construction
--   primitives:
--   
--   <pre>
--   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)"
--   </pre>
--   
--   The <a>Eq</a> instance satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> and <i>m</i> will denote the number of vertices and edges in
--   the graph, respectively.
data AdjacencyMap a

-- | The <i>adjacency map</i> of the graph: each vertex is associated with
--   a set of its direct successors.
adjacencyMap :: AdjacencyMap a -> (Map a (Set a))

-- | Construct the <i>empty graph</i>. Complexity: <i>O(1)</i> time and
--   memory.
--   
--   <pre>
--   <a>isEmpty</a>     empty == True
--   <a>hasVertex</a> x empty == False
--   <a>vertexCount</a> empty == 0
--   <a>edgeCount</a>   empty == 0
--   </pre>
empty :: Ord a => AdjacencyMap a

-- | Construct the graph comprising <i>a single isolated vertex</i>.
--   Complexity: <i>O(1)</i> time and memory.
--   
--   <pre>
--   <a>isEmpty</a>     (vertex x) == False
--   <a>hasVertex</a> x (vertex x) == True
--   <a>vertexCount</a> (vertex x) == 1
--   <a>edgeCount</a>   (vertex x) == 0
--   </pre>
vertex :: Ord a => a -> AdjacencyMap a

-- | Construct the graph comprising <i>a single edge</i>. Complexity:
--   <i>O(1)</i> time, memory.
--   
--   <pre>
--   edge x y               == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   <a>hasEdge</a> x y (edge x y) == True
--   <a>edgeCount</a>   (edge x y) == 1
--   <a>vertexCount</a> (edge 1 1) == 1
--   <a>vertexCount</a> (edge 1 2) == 2
--   </pre>
edge :: Ord a => a -> a -> AdjacencyMap a

-- | <i>Overlay</i> two graphs. This is a commutative, associative and
--   idempotent operation with the identity <a>empty</a>. Complexity:
--   <i>O((n + m) * log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   <a>isEmpty</a>     (overlay x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (overlay x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (overlay x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (overlay x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (overlay x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (overlay x y) &lt;= <a>edgeCount</a> x   + <a>edgeCount</a> y
--   <a>vertexCount</a> (overlay 1 2) == 2
--   <a>edgeCount</a>   (overlay 1 2) == 0
--   </pre>
overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

-- | <i>Connect</i> two graphs. This is an associative operation with the
--   identity <a>empty</a>, which distributes over <a>overlay</a> and obeys
--   the decomposition axiom. Complexity: <i>O((n + m) * log(n))</i> time
--   and <i>O(n + m)</i> memory. Note that the number of edges in the
--   resulting graph is quadratic with respect to the number of vertices of
--   the arguments: <i>m = O(m1 + m2 + n1 * n2)</i>.
--   
--   <pre>
--   <a>isEmpty</a>     (connect x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (connect x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (connect x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (connect x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &lt;= <a>vertexCount</a> x * <a>vertexCount</a> y + <a>edgeCount</a> x + <a>edgeCount</a> y
--   <a>vertexCount</a> (connect 1 2) == 2
--   <a>edgeCount</a>   (connect 1 2) == 1
--   </pre>
connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L * log(L))</i> time and <i>O(L)</i> memory, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   vertices []            == <a>empty</a>
--   vertices [x]           == <a>vertex</a> x
--   <a>hasVertex</a> x . vertices == <a>elem</a> x
--   <a>vertexCount</a> . vertices == <a>length</a> . <a>nub</a>
--   <a>vertexSet</a>   . vertices == Set.<a>fromList</a>
--   </pre>
vertices :: Ord a => [a] -> AdjacencyMap a

-- | Construct the graph from a list of edges. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   edges []          == <a>empty</a>
--   edges [(x, y)]    == <a>edge</a> x y
--   <a>edgeCount</a> . edges == <a>length</a> . <a>nub</a>
--   <a>edgeList</a> . edges  == <a>nub</a> . <a>sort</a>
--   </pre>
edges :: Ord a => [(a, a)] -> AdjacencyMap a

-- | Overlay a given list of graphs. Complexity: <i>O((n + m) * log(n))</i>
--   time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   overlays []        == <a>empty</a>
--   overlays [x]       == x
--   overlays [x,y]     == <a>overlay</a> x y
--   overlays           == <a>foldr</a> <a>overlay</a> <a>empty</a>
--   <a>isEmpty</a> . overlays == <a>all</a> <a>isEmpty</a>
--   </pre>
overlays :: Ord a => [AdjacencyMap a] -> AdjacencyMap a

-- | Connect a given list of graphs. Complexity: <i>O((n + m) * log(n))</i>
--   time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   connects []        == <a>empty</a>
--   connects [x]       == x
--   connects [x,y]     == <a>connect</a> x y
--   connects           == <a>foldr</a> <a>connect</a> <a>empty</a>
--   <a>isEmpty</a> . connects == <a>all</a> <a>isEmpty</a>
--   </pre>
connects :: Ord a => [AdjacencyMap a] -> AdjacencyMap a

-- | Construct a graph from an adjacency list. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   fromAdjacencyList []                                  == <a>empty</a>
--   fromAdjacencyList [(x, [])]                           == <a>vertex</a> x
--   fromAdjacencyList [(x, [y])]                          == <a>edge</a> x y
--   fromAdjacencyList . <a>adjacencyList</a>                     == id
--   <a>overlay</a> (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys)
--   </pre>
fromAdjacencyList :: Ord a => [(a, [a])] -> AdjacencyMap a

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Complexity: <i>O((n + m) * log(n))</i> time.
--   
--   <pre>
--   isSubgraphOf <a>empty</a>         x             == True
--   isSubgraphOf (<a>vertex</a> x)    <a>empty</a>         == False
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path</a> xs)     (<a>circuit</a> xs)  == True
--   </pre>
isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool

-- | Check if a graph is empty. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   isEmpty <a>empty</a>                       == True
--   isEmpty (<a>overlay</a> <a>empty</a> <a>empty</a>)       == True
--   isEmpty (<a>vertex</a> x)                  == False
--   isEmpty (<a>removeVertex</a> x $ <a>vertex</a> x) == True
--   isEmpty (<a>removeEdge</a> x y $ <a>edge</a> x y) == False
--   </pre>
isEmpty :: AdjacencyMap a -> Bool

-- | Check if a graph contains a given vertex. Complexity: <i>O(log(n))</i>
--   time.
--   
--   <pre>
--   hasVertex x <a>empty</a>            == False
--   hasVertex x (<a>vertex</a> x)       == True
--   hasVertex 1 (<a>vertex</a> 2)       == False
--   hasVertex x . <a>removeVertex</a> x == const False
--   </pre>
hasVertex :: Ord a => a -> AdjacencyMap a -> Bool

-- | Check if a graph contains a given edge. Complexity: <i>O(log(n))</i>
--   time.
--   
--   <pre>
--   hasEdge x y <a>empty</a>            == False
--   hasEdge x y (<a>vertex</a> z)       == False
--   hasEdge x y (<a>edge</a> x y)       == True
--   hasEdge x y . <a>removeEdge</a> x y == const False
--   hasEdge x y                  == <a>elem</a> (x,y) . <a>edgeList</a>
--   </pre>
hasEdge :: Ord a => a -> a -> AdjacencyMap a -> Bool

-- | The number of vertices in a graph. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   vertexCount <a>empty</a>      == 0
--   vertexCount (<a>vertex</a> x) == 1
--   vertexCount            == <a>length</a> . <a>vertexList</a>
--   </pre>
vertexCount :: AdjacencyMap a -> Int

-- | The number of edges in a graph. Complexity: <i>O(n)</i> time.
--   
--   <pre>
--   edgeCount <a>empty</a>      == 0
--   edgeCount (<a>vertex</a> x) == 0
--   edgeCount (<a>edge</a> x y) == 1
--   edgeCount            == <a>length</a> . <a>edgeList</a>
--   </pre>
edgeCount :: AdjacencyMap a -> Int

-- | The sorted list of vertices of a given graph. Complexity: <i>O(n)</i>
--   time and memory.
--   
--   <pre>
--   vertexList <a>empty</a>      == []
--   vertexList (<a>vertex</a> x) == [x]
--   vertexList . <a>vertices</a> == <a>nub</a> . <a>sort</a>
--   </pre>
vertexList :: AdjacencyMap a -> [a]

-- | The sorted list of edges of a graph. Complexity: <i>O(n + m)</i> time
--   and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeList <a>empty</a>          == []
--   edgeList (<a>vertex</a> x)     == []
--   edgeList (<a>edge</a> x y)     == [(x,y)]
--   edgeList (<a>star</a> 2 [3,1]) == [(2,1), (2,3)]
--   edgeList . <a>edges</a>        == <a>nub</a> . <a>sort</a>
--   edgeList . <a>transpose</a>    == <a>sort</a> . map <a>swap</a> . edgeList
--   </pre>
edgeList :: AdjacencyMap a -> [(a, a)]

-- | The sorted <i>adjacency list</i> of a graph. Complexity: <i>O(n +
--   m)</i> time and <i>O(m)</i> memory.
--   
--   <pre>
--   adjacencyList <a>empty</a>               == []
--   adjacencyList (<a>vertex</a> x)          == [(x, [])]
--   adjacencyList (<a>edge</a> 1 2)          == [(1, [2]), (2, [])]
--   adjacencyList (<a>star</a> 2 [3,1])      == [(1, []), (2, [1,3]), (3, [])]
--   <a>fromAdjacencyList</a> . adjacencyList == id
--   </pre>
adjacencyList :: AdjacencyMap a -> [(a, [a])]

-- | The set of vertices of a given graph. Complexity: <i>O(n)</i> time and
--   memory.
--   
--   <pre>
--   vertexSet <a>empty</a>      == Set.<a>empty</a>
--   vertexSet . <a>vertex</a>   == Set.<a>singleton</a>
--   vertexSet . <a>vertices</a> == Set.<a>fromList</a>
--   vertexSet . <a>clique</a>   == Set.<a>fromList</a>
--   </pre>
vertexSet :: AdjacencyMap a -> Set a

-- | The set of edges of a given graph. Complexity: <i>O((n + m) *
--   log(m))</i> time and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeSet <a>empty</a>      == Set.<a>empty</a>
--   edgeSet (<a>vertex</a> x) == Set.<a>empty</a>
--   edgeSet (<a>edge</a> x y) == Set.<a>singleton</a> (x,y)
--   edgeSet . <a>edges</a>    == Set.<a>fromList</a>
--   </pre>
edgeSet :: Ord a => AdjacencyMap a -> Set (a, a)

-- | The <i>postset</i> (here <a>postSet</a>) of a vertex is the set of its
--   <i>direct successors</i>.
--   
--   <pre>
--   postSet x <a>empty</a>      == Set.<a>empty</a>
--   postSet x (<a>vertex</a> x) == Set.<a>empty</a>
--   postSet x (<a>edge</a> x y) == Set.<a>fromList</a> [y]
--   postSet 2 (<a>edge</a> 1 2) == Set.<a>empty</a>
--   </pre>
postSet :: Ord a => a -> AdjacencyMap a -> Set a

-- | The <i>path</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   path []        == <a>empty</a>
--   path [x]       == <a>vertex</a> x
--   path [x,y]     == <a>edge</a> x y
--   path . <a>reverse</a> == <a>transpose</a> . path
--   </pre>
path :: Ord a => [a] -> AdjacencyMap a

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   circuit []        == <a>empty</a>
--   circuit [x]       == <a>edge</a> x x
--   circuit [x,y]     == <a>edges</a> [(x,y), (y,x)]
--   circuit . <a>reverse</a> == <a>transpose</a> . circuit
--   </pre>
circuit :: Ord a => [a] -> AdjacencyMap a

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   clique []         == <a>empty</a>
--   clique [x]        == <a>vertex</a> x
--   clique [x,y]      == <a>edge</a> x y
--   clique [x,y,z]    == <a>edges</a> [(x,y), (x,z), (y,z)]
--   clique (xs ++ ys) == <a>connect</a> (clique xs) (clique ys)
--   clique . <a>reverse</a>  == <a>transpose</a> . clique
--   </pre>
clique :: Ord a => [a] -> AdjacencyMap a

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(n *
--   log(n) + m)</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   biclique []      []      == <a>empty</a>
--   biclique [x]     []      == <a>vertex</a> x
--   biclique []      [y]     == <a>vertex</a> y
--   biclique [x1,x2] [y1,y2] == <a>edges</a> [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
--   biclique xs      ys      == <a>connect</a> (<a>vertices</a> xs) (<a>vertices</a> ys)
--   </pre>
biclique :: Ord a => [a] -> [a] -> AdjacencyMap a

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges</a> [(x,y), (x,z)]
--   star x ys    == <a>connect</a> (<a>vertex</a> x) (<a>vertices</a> ys)
--   </pre>
star :: Ord a => a -> [a] -> AdjacencyMap a

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges</a> [(y,x), (z,x)]
--   starTranspose x ys    == <a>connect</a> (<a>vertices</a> ys) (<a>vertex</a> x)
--   starTranspose x ys    == <a>transpose</a> (<a>star</a> x ys)
--   </pre>
starTranspose :: Ord a => a -> [a] -> AdjacencyMap a

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path</a> [x,y,z]
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges</a> [(1,2), (1,3), (3,4), (3,5)]
--   </pre>
tree :: Ord a => Tree a -> AdjacencyMap a

-- | The <i>forest graph</i> constructed from a given <a>Forest</a> data
--   structure. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   forest []                                                  == <a>empty</a>
--   forest [x]                                                 == <a>tree</a> x
--   forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == <a>edges</a> [(1,2), (1,3), (4,5)]
--   forest                                                     == <a>overlays</a> . map <a>tree</a>
--   </pre>
forest :: Ord a => Forest a -> AdjacencyMap a

-- | Remove a vertex from a given graph. Complexity: <i>O(n*log(n))</i>
--   time.
--   
--   <pre>
--   removeVertex x (<a>vertex</a> x)       == <a>empty</a>
--   removeVertex 1 (<a>vertex</a> 2)       == <a>vertex</a> 2
--   removeVertex x (<a>edge</a> x x)       == <a>empty</a>
--   removeVertex 1 (<a>edge</a> 1 2)       == <a>vertex</a> 2
--   removeVertex x . removeVertex x == removeVertex x
--   </pre>
removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a

-- | Remove an edge from a given graph. Complexity: <i>O(log(n))</i> time.
--   
--   <pre>
--   removeEdge x y (<a>edge</a> x y)       == <a>vertices</a> [x, y]
--   removeEdge x y . removeEdge x y == removeEdge x y
--   removeEdge x y . <a>removeVertex</a> x == <a>removeVertex</a> x
--   removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
--   removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2
--   </pre>
removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a

-- | The function <tt><a>replaceVertex</a> x y</tt> replaces vertex
--   <tt>x</tt> with vertex <tt>y</tt> in a given <a>AdjacencyMap</a>. If
--   <tt>y</tt> already exists, <tt>x</tt> and <tt>y</tt> will be merged.
--   Complexity: <i>O((n + m) * log(n))</i> time.
--   
--   <pre>
--   replaceVertex x x            == id
--   replaceVertex x y (<a>vertex</a> x) == <a>vertex</a> y
--   replaceVertex x y            == <a>mergeVertices</a> (== x) y
--   </pre>
replaceVertex :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a

-- | Merge vertices satisfying a given predicate into a given vertex.
--   Complexity: <i>O((n + m) * log(n))</i> time, assuming that the
--   predicate takes <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   mergeVertices (const False) x    == id
--   mergeVertices (== x) y           == <a>replaceVertex</a> x y
--   mergeVertices even 1 (0 * 2)     == 1 * 1
--   mergeVertices odd  1 (3 + 4 * 5) == 4 * 1
--   </pre>
mergeVertices :: Ord a => (a -> Bool) -> a -> AdjacencyMap a -> AdjacencyMap a

-- | Transpose a given graph. Complexity: <i>O(m * log(n))</i> time, <i>O(n
--   + m)</i> memory.
--   
--   <pre>
--   transpose <a>empty</a>       == <a>empty</a>
--   transpose (<a>vertex</a> x)  == <a>vertex</a> x
--   transpose (<a>edge</a> x y)  == <a>edge</a> y x
--   transpose . transpose == id
--   <a>edgeList</a> . transpose  == <a>sort</a> . map <a>swap</a> . <a>edgeList</a>
--   </pre>
transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a

-- | Transform a graph by applying a function to each of its vertices. This
--   is similar to <tt>Functor</tt>'s <a>fmap</a> but can be used with
--   non-fully-parametric <a>AdjacencyMap</a>. Complexity: <i>O((n + m) *
--   log(n))</i> time.
--   
--   <pre>
--   gmap f <a>empty</a>      == <a>empty</a>
--   gmap f (<a>vertex</a> x) == <a>vertex</a> (f x)
--   gmap f (<a>edge</a> x y) == <a>edge</a> (f x) (f y)
--   gmap id           == id
--   gmap f . gmap g   == gmap (f . g)
--   </pre>
gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b

-- | Construct the <i>induced subgraph</i> of a given graph by removing the
--   vertices that do not satisfy a given predicate. Complexity:
--   <i>O(m)</i> time, assuming that the predicate takes <i>O(1)</i> to be
--   evaluated.
--   
--   <pre>
--   induce (const True ) x      == x
--   induce (const False) x      == <a>empty</a>
--   induce (/= x)               == <a>removeVertex</a> x
--   induce p . induce q         == induce (\x -&gt; p x &amp;&amp; q x)
--   <a>isSubgraphOf</a> (induce p x) x == True
--   </pre>
induce :: Ord a => (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a

-- | Compute the <i>depth-first search</i> forest of a graph.
--   
--   <pre>
--   <a>forest</a> (dfsForest $ <a>edge</a> 1 1)         == <a>vertex</a> 1
--   <a>forest</a> (dfsForest $ <a>edge</a> 1 2)         == <a>edge</a> 1 2
--   <a>forest</a> (dfsForest $ <a>edge</a> 2 1)         == <a>vertices</a> [1, 2]
--   <a>isSubgraphOf</a> (<a>forest</a> $ dfsForest x) x == True
--   dfsForest . <a>forest</a> . dfsForest        == dfsForest
--   dfsForest (<a>vertices</a> vs)               == map (\v -&gt; Node v []) (<a>nub</a> $ <a>sort</a> vs)
--   <a>dfsForestFrom</a> (<a>vertexList</a> 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 = [] }]}]
--   </pre>
dfsForest :: AdjacencyMap a -> Forest a

-- | Compute the <i>depth-first search</i> 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.
--   
--   <pre>
--   <a>forest</a> (dfsForestFrom [1]    $ <a>edge</a> 1 1)     == <a>vertex</a> 1
--   <a>forest</a> (dfsForestFrom [1]    $ <a>edge</a> 1 2)     == <a>edge</a> 1 2
--   <a>forest</a> (dfsForestFrom [2]    $ <a>edge</a> 1 2)     == <a>vertex</a> 2
--   <a>forest</a> (dfsForestFrom [3]    $ <a>edge</a> 1 2)     == <a>empty</a>
--   <a>forest</a> (dfsForestFrom [2, 1] $ <a>edge</a> 1 2)     == <a>vertices</a> [1, 2]
--   <a>isSubgraphOf</a> (<a>forest</a> $ dfsForestFrom vs x) x == True
--   dfsForestFrom (<a>vertexList</a> x) x               == <a>dfsForest</a> x
--   dfsForestFrom vs             (<a>vertices</a> vs)   == map (\v -&gt; Node v []) (<a>nub</a> vs)
--   dfsForestFrom []             x               == []
--   dfsForestFrom [1, 4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
--                                                          , subForest = [ Node { rootLabel = 5
--                                                                               , subForest = [] }
--                                                   , Node { rootLabel = 4
--                                                          , subForest = [] }]
--   </pre>
dfsForestFrom :: [a] -> AdjacencyMap a -> Forest a

-- | Compute the list of vertices visited by the <i>depth-first search</i>
--   in a graph, when searching from each of the given vertices in order.
--   
--   <pre>
--   dfs [1]    $ <a>edge</a> 1 1                == [1]
--   dfs [1]    $ <a>edge</a> 1 2                == [1, 2]
--   dfs [2]    $ <a>edge</a> 1 2                == [2]
--   dfs [3]    $ <a>edge</a> 1 2                == []
--   dfs [1, 2] $ <a>edge</a> 1 2                == [1, 2]
--   dfs [2, 1] $ <a>edge</a> 1 2                == [2, 1]
--   dfs []     $ x                       == []
--   dfs [1, 4] $ 3 * (1 + 4) * (1 + 5)   == [1, 5, 4]
--   <a>isSubgraphOf</a> (<a>vertices</a> $ dfs vs x) x == True
--   </pre>
dfs :: [a] -> AdjacencyMap a -> [a]

-- | Compute the <i>topological sort</i> of a graph or return
--   <tt>Nothing</tt> if the graph is cyclic.
--   
--   <pre>
--   topSort (1 * 2 + 3 * 1)             == Just [3,1,2]
--   topSort (1 * 2 + 2 * 1)             == Nothing
--   fmap (flip <a>isTopSort</a> x) (topSort x) /= Just False
--   </pre>
topSort :: Ord a => AdjacencyMap a -> Maybe [a]

-- | Check if a given list of vertices is a valid <i>topological sort</i>
--   of a graph.
--   
--   <pre>
--   isTopSort [3, 1, 2] (1 * 2 + 3 * 1) == True
--   isTopSort [1, 2, 3] (1 * 2 + 3 * 1) == False
--   isTopSort []        (1 * 2 + 3 * 1) == False
--   isTopSort []        <a>empty</a>           == True
--   isTopSort [x]       (<a>vertex</a> x)      == True
--   isTopSort [x]       (<a>edge</a> x x)      == False
--   </pre>
isTopSort :: Ord a => [a] -> AdjacencyMap a -> Bool

-- | Compute the <i>condensation</i> of a graph, where each vertex
--   corresponds to a <i>strongly-connected component</i> of the original
--   graph.
--   
--   <pre>
--   scc <a>empty</a>               == <a>empty</a>
--   scc (<a>vertex</a> x)          == <a>vertex</a> (Set.<a>singleton</a> x)
--   scc (<a>edge</a> x y)          == <a>edge</a> (Set.<a>singleton</a> x) (Set.<a>singleton</a> y)
--   scc (<a>circuit</a> (1:xs))    == <a>edge</a> (Set.<a>fromList</a> (1:xs)) (Set.<a>fromList</a> (1:xs))
--   scc (3 * 1 * 4 * 1 * 5) == <a>edges</a> [ (Set.<a>fromList</a> [1,4], Set.<a>fromList</a> [1,4])
--                                    , (Set.<a>fromList</a> [1,4], Set.<a>fromList</a> [5]  )
--                                    , (Set.<a>fromList</a> [3]  , Set.<a>fromList</a> [1,4])
--                                    , (Set.<a>fromList</a> [3]  , Set.<a>fromList</a> [5]  )]
--   </pre>
scc :: Ord a => AdjacencyMap a -> AdjacencyMap (Set a)


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the core type class <a>Graph</a>, 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 <a>Graph</a> expression you will need to use a
--   concrete data type, such as <a>Algebra.Graph</a>.
--   
--   See <a>Algebra.Graph.Class</a> 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 <a>connect</a> method to the standard <a>MonadPlus</a>
--   class and reusing the following existing methods:
--   
--   <ul>
--   <li>The <a>empty</a> method comes from the <a>Alternative</a> class
--   and corresponds to the <i>empty graph</i>. This module simply
--   re-exports it.</li>
--   <li>The <a>vertex</a> graph construction primitive is an alias for
--   <a>pure</a> of the <a>Applicative</a> type class.</li>
--   <li>Graph <a>overlay</a> is an alias for <tt>mplus</tt> of the
--   <a>MonadPlus</a> type class.</li>
--   </ul>
--   
--   The <a>Graph</a> type class is characterised by the following minimal
--   set of axioms. In equations we use <tt>+</tt> and <tt>*</tt> as
--   convenient shortcuts for <a>overlay</a> and <a>connect</a>,
--   respectively.
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   The core type class <a>Graph</a> corresponds to unlabelled directed
--   graphs. <a>Undirected</a>, <a>Reflexive</a>, <a>Transitive</a> and
--   <a>Preorder</a> graphs can be obtained by extending the minimal set of
--   axioms.
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> will denote the number of vertices in the graph, <i>m</i>
--   will denote the number of edges in the graph, and <i>s</i> will denote
--   the <i>size</i> of the corresponding <a>Graph</a> expression.
class (Traversable g, MonadPlus g) => Graph g

-- | Connect two graphs.
connect :: Graph g => g a -> g a -> g a

-- | The identity of <a>&lt;|&gt;</a>
empty :: Alternative f => forall a. () => f a

-- | Construct the graph comprising a single isolated vertex. An alias for
--   <a>pure</a>.
vertex :: Graph g => a -> g a

-- | Overlay two graphs. An alias for <a>&lt;|&gt;</a>.
overlay :: Graph g => g a -> g a -> g a

-- | The class of <i>undirected graphs</i> that satisfy the following
--   additional axiom.
--   
--   <ul>
--   <li><a>connect</a> is commutative:<pre>x * y == y * x</pre></li>
--   </ul>
class Graph g => Undirected g

-- | The class of <i>reflexive graphs</i> that satisfy the following
--   additional axiom.
--   
--   <ul>
--   <li>Each vertex has a <i>self-loop</i>:<pre>vertex x == vertex x *
--   vertex x</pre></li>
--   </ul>
--   
--   Or, alternatively, if we remember that <a>vertex</a> is an alias for
--   <a>pure</a>:
--   
--   <pre>
--   pure x == pure x * pure x
--   </pre>
--   
--   Note that by applying the axiom in the reverse direction, one can
--   always remove all self-loops resulting in an <i>irreflexive graph</i>.
--   This type class can therefore be also used in the context of
--   irreflexive graphs.
class Graph g => Reflexive g

-- | The class of <i>transitive graphs</i> that satisfy the following
--   additional axiom.
--   
--   <ul>
--   <li>The <i>closure</i> axiom: graphs with equal transitive closures
--   are equal.<pre>y /= empty ==&gt; x * y + x * z + y * z == x * y + y *
--   z</pre></li>
--   </ul>
--   
--   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 <i>preorder graphs</i> that are both reflexive and
--   transitive.
class (Reflexive g, Transitive g) => Preorder g

-- | Construct the graph comprising a single edge. Complexity: <i>O(1)</i>
--   time, memory and size.
--   
--   <pre>
--   edge x y               == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   <a>vertexCount</a> (edge 1 1) == 1
--   <a>vertexCount</a> (edge 1 2) == 2
--   </pre>
edge :: Graph g => a -> a -> g a

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L)</i> time, memory and size, where <i>L</i> is the
--   length of the given list.
--   
--   <pre>
--   vertices []            == <a>empty</a>
--   vertices [x]           == <a>vertex</a> x
--   <a>hasVertex</a> x . vertices == <a>elem</a> x
--   <a>vertexCount</a> . vertices == <a>length</a> . <a>nub</a>
--   <a>vertexSet</a>   . vertices == Set.<a>fromList</a>
--   </pre>
vertices :: Graph g => [a] -> g a

-- | Construct the graph from a list of edges. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   edges []      == <a>empty</a>
--   edges [(x,y)] == <a>edge</a> x y
--   </pre>
edges :: Graph g => [(a, a)] -> g a

-- | Overlay a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   overlays []        == <a>empty</a>
--   overlays [x]       == x
--   overlays [x,y]     == <a>overlay</a> x y
--   overlays           == <a>foldr</a> <a>overlay</a> <a>empty</a>
--   <a>isEmpty</a> . overlays == <a>all</a> <a>isEmpty</a>
--   </pre>
overlays :: Graph g => [g a] -> g a

-- | Connect a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   connects []        == <a>empty</a>
--   connects [x]       == x
--   connects [x,y]     == <a>connect</a> x y
--   connects           == <a>foldr</a> <a>connect</a> <a>empty</a>
--   <a>isEmpty</a> . connects == <a>all</a> <a>isEmpty</a>
--   </pre>
connects :: Graph g => [g a] -> g a

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Here is the current implementation:
--   
--   <pre>
--   isSubgraphOf x y = <a>overlay</a> x y == y
--   </pre>
--   
--   The complexity therefore depends on the complexity of equality testing
--   of the specific graph instance.
--   
--   <pre>
--   isSubgraphOf <a>empty</a>         x             == True
--   isSubgraphOf (<a>vertex</a> x)    <a>empty</a>         == False
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path</a> xs)     (<a>circuit</a> xs)  == True
--   </pre>
isSubgraphOf :: (Graph g, Eq (g a)) => g a -> g a -> Bool

-- | Check if a graph is empty. A convenient alias for <a>null</a>.
--   Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   isEmpty <a>empty</a>                       == True
--   isEmpty (<a>overlay</a> <a>empty</a> <a>empty</a>)       == True
--   isEmpty (<a>vertex</a> x)                  == False
--   isEmpty (<a>removeVertex</a> x $ <a>vertex</a> x) == True
--   </pre>
isEmpty :: Graph g => g a -> Bool

-- | Check if a graph contains a given vertex. A convenient alias for
--   <a>elem</a>. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasVertex x <a>empty</a>            == False
--   hasVertex x (<a>vertex</a> x)       == True
--   hasVertex 1 (<a>vertex</a> 2)       == False
--   hasVertex x . <a>removeVertex</a> x == const False
--   </pre>
hasVertex :: (Eq a, Graph g) => a -> g a -> Bool

-- | Check if a graph contains a given edge. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasEdge x y <a>empty</a>            == False
--   hasEdge x y (<a>vertex</a> z)       == False
--   hasEdge x y (<a>edge</a> x y)       == True
--   hasEdge x y                  == <a>elem</a> (x,y) . <tt>edgeList</tt>
--   </pre>
hasEdge :: (Eq (g a), Graph g, Ord a) => a -> a -> g a -> Bool

-- | The number of vertices in a graph. Complexity: <i>O(s * log(n))</i>
--   time.
--   
--   <pre>
--   vertexCount <a>empty</a>      == 0
--   vertexCount (<a>vertex</a> x) == 1
--   vertexCount            == <a>length</a> . <a>vertexList</a>
--   </pre>
vertexCount :: (Ord a, Graph g) => g a -> Int

-- | The sorted list of vertices of a given graph. Complexity: <i>O(s *
--   log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexList <a>empty</a>      == []
--   vertexList (<a>vertex</a> x) == [x]
--   vertexList . <a>vertices</a> == <a>nub</a> . <a>sort</a>
--   </pre>
vertexList :: (Ord a, Graph g) => g a -> [a]

-- | The set of vertices of a given graph. Complexity: <i>O(s * log(n))</i>
--   time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexSet <a>empty</a>      == Set.<a>empty</a>
--   vertexSet . <a>vertex</a>   == Set.<a>singleton</a>
--   vertexSet . <a>vertices</a> == Set.<a>fromList</a>
--   vertexSet . <a>clique</a>   == Set.<a>fromList</a>
--   </pre>
vertexSet :: (Ord a, Graph g) => g a -> Set a

-- | The set of vertices of a given graph. Like <a>vertexSet</a> but
--   specialised for graphs with vertices of type <a>Int</a>. Complexity:
--   <i>O(s * log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexIntSet <a>empty</a>      == IntSet.<a>empty</a>
--   vertexIntSet . <a>vertex</a>   == IntSet.<a>singleton</a>
--   vertexIntSet . <a>vertices</a> == IntSet.<a>fromList</a>
--   vertexIntSet . <a>clique</a>   == IntSet.<a>fromList</a>
--   </pre>
vertexIntSet :: Graph g => g Int -> IntSet

-- | The <i>path</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   path []    == <a>empty</a>
--   path [x]   == <a>vertex</a> x
--   path [x,y] == <a>edge</a> x y
--   </pre>
path :: Graph g => [a] -> g a

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   circuit []    == <a>empty</a>
--   circuit [x]   == <a>edge</a> x x
--   circuit [x,y] == <a>edges</a> [(x,y), (y,x)]
--   </pre>
circuit :: Graph g => [a] -> g a

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   clique []         == <a>empty</a>
--   clique [x]        == <a>vertex</a> x
--   clique [x,y]      == <a>edge</a> x y
--   clique [x,y,z]    == <a>edges</a> [(x,y), (x,z), (y,z)]
--   clique (xs ++ ys) == <a>connect</a> (clique xs) (clique ys)
--   </pre>
clique :: Graph g => [a] -> g a

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(L1 +
--   L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i> are the
--   lengths of the given lists.
--   
--   <pre>
--   biclique []      []      == <a>empty</a>
--   biclique [x]     []      == <a>vertex</a> x
--   biclique []      [y]     == <a>vertex</a> y
--   biclique [x1,x2] [y1,y2] == <a>edges</a> [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
--   biclique xs      ys      == <a>connect</a> (<a>vertices</a> xs) (<a>vertices</a> ys)
--   </pre>
biclique :: Graph g => [a] -> [a] -> g a

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O(L)</i> time, memory and size, where <i>L</i>
--   is the length of the given list.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges</a> [(x,y), (x,z)]
--   star x ys    == <a>connect</a> (<a>vertex</a> x) (<a>vertices</a> ys)
--   </pre>
star :: Graph g => a -> [a] -> g a

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges</a> [(y,x), (z,x)]
--   starTranspose x ys    == <a>connect</a> (<a>vertices</a> ys) (<a>vertex</a> x)
--   starTranspose x ys    == transpose (<a>star</a> x ys)
--   </pre>
starTranspose :: Graph g => a -> [a] -> g a

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O(T)</i> time, memory and size, where
--   <i>T</i> is the size of the given tree (i.e. the number of vertices in
--   the tree).
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path</a> [x,y,z]
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges</a> [(1,2), (1,3), (3,4), (3,5)]
--   </pre>
tree :: Graph g => Tree a -> g a

-- | The <i>forest graph</i> constructed from a given <a>Forest</a> data
--   structure. Complexity: <i>O(F)</i> time, memory and size, where
--   <i>F</i> is the size of the given forest (i.e. the number of vertices
--   in the forest).
--   
--   <pre>
--   forest []                                                  == <a>empty</a>
--   forest [x]                                                 == <a>tree</a> x
--   forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == <a>edges</a> [(1,2), (1,3), (4,5)]
--   forest                                                     == <a>overlays</a> . map <a>tree</a>
--   </pre>
forest :: Graph g => Forest a -> g a

-- | Construct a <i>mesh graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   mesh xs     []   == <a>empty</a>
--   mesh []     ys   == <a>empty</a>
--   mesh [x]    [y]  == <a>vertex</a> (x, y)
--   mesh xs     ys   == <a>box</a> (<a>path</a> xs) (<a>path</a> ys)
--   mesh [1..3] "ab" == <a>edges</a> [ ((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')) ]
--   </pre>
mesh :: Graph g => [a] -> [b] -> g (a, b)

-- | Construct a <i>torus graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   torus xs    []   == <a>empty</a>
--   torus []    ys   == <a>empty</a>
--   torus [x]   [y]  == <a>edge</a> (x, y) (x, y)
--   torus xs    ys   == <a>box</a> (<a>circuit</a> xs) (<a>circuit</a> ys)
--   torus [1,2] "ab" == <a>edges</a> [ ((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')) ]
--   </pre>
torus :: Graph g => [a] -> [b] -> g (a, b)

-- | Construct a <i>De Bruijn graph</i> of a given non-negative dimension
--   using symbols from a given alphabet. Complexity: <i>O(A^(D + 1))</i>
--   time, memory and size, where <i>A</i> is the size of the alphabet and
--   <i>D</i> is the dimension of the graph.
--   
--   <pre>
--             deBruijn 0 xs               == <a>edge</a> [] []
--   n &gt; 0 ==&gt; deBruijn n []               == <a>empty</a>
--             deBruijn 1 [0,1]            == <a>edges</a> [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
--             deBruijn 2 "0"              == <a>edge</a> "00" "00"
--             deBruijn 2 "01"             == <a>edges</a> [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
--                                                  , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
--             transpose   (deBruijn n xs) == <a>fmap</a> <a>reverse</a> $ deBruijn n xs
--             <a>vertexCount</a> (deBruijn n xs) == (<a>length</a> $ <a>nub</a> xs)^n
--   n &gt; 0 ==&gt; <tt>edgeCount</tt>   (deBruijn n xs) == (<a>length</a> $ <a>nub</a> xs)^(n + 1)
--   </pre>
deBruijn :: Graph g => Int -> [a] -> g [a]

-- | Remove a vertex from a given graph. Complexity: <i>O(s)</i> time,
--   memory and size.
--   
--   <pre>
--   removeVertex x (<a>vertex</a> x)       == <a>empty</a>
--   removeVertex 1 (<a>vertex</a> 2)       == <a>vertex</a> 2
--   removeVertex x (<a>edge</a> x x)       == <a>empty</a>
--   removeVertex 1 (<a>edge</a> 1 2)       == <a>vertex</a> 2
--   removeVertex x . removeVertex x == removeVertex x
--   </pre>
removeVertex :: (Eq a, Graph g) => a -> g a -> g a

-- | The function <tt><a>replaceVertex</a> x y</tt> replaces vertex
--   <tt>x</tt> with vertex <tt>y</tt> in a given <a>Graph</a>. If
--   <tt>y</tt> already exists, <tt>x</tt> and <tt>y</tt> will be merged.
--   Complexity: <i>O(s)</i> time, memory and size.
--   
--   <pre>
--   replaceVertex x x            == id
--   replaceVertex x y (<a>vertex</a> x) == <a>vertex</a> y
--   replaceVertex x y            == <a>mergeVertices</a> (== x) y
--   </pre>
replaceVertex :: (Eq a, Graph g) => a -> a -> g a -> g a

-- | Merge vertices satisfying a given predicate into a given vertex.
--   Complexity: <i>O(s)</i> time, memory and size, assuming that the
--   predicate takes <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   mergeVertices (const False) x    == id
--   mergeVertices (== x) y           == <a>replaceVertex</a> x y
--   mergeVertices even 1 (0 * 2)     == 1 * 1
--   mergeVertices odd  1 (3 + 4 * 5) == 4 * 1
--   </pre>
mergeVertices :: Graph g => (a -> Bool) -> a -> g a -> g a

-- | Split a vertex into a list of vertices with the same connectivity.
--   Complexity: <i>O(s + k * L)</i> time, memory and size, where <i>k</i>
--   is the number of occurrences of the vertex in the expression and
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   splitVertex x []                  == <a>removeVertex</a> x
--   splitVertex x [x]                 == id
--   splitVertex x [y]                 == <a>replaceVertex</a> x y
--   splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
--   </pre>
splitVertex :: (Eq a, Graph g) => a -> [a] -> g a -> g a

-- | Construct the <i>induced subgraph</i> of a given graph by removing the
--   vertices that do not satisfy a given predicate. Complexity:
--   <i>O(s)</i> time, memory and size, assuming that the predicate takes
--   <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   induce (const True ) x      == x
--   induce (const False) x      == <a>empty</a>
--   induce (/= x)               == <a>removeVertex</a> x
--   induce p . induce q         == induce (\x -&gt; p x &amp;&amp; q x)
--   <a>isSubgraphOf</a> (induce p x) x == True
--   </pre>
induce :: Graph g => (a -> Bool) -> g a -> g a

-- | Compute the <i>Cartesian product</i> of graphs. Complexity: <i>O(s1 *
--   s2)</i> time, memory and size, where <i>s1</i> and <i>s2</i> are the
--   sizes of the given graphs.
--   
--   <pre>
--   box (<a>path</a> [0,1]) (<a>path</a> "ab") == <a>edges</a> [ ((0,'a'), (0,'b'))
--                                         , ((0,'a'), (1,'a'))
--                                         , ((0,'b'), (1,'b'))
--                                         , ((1,'a'), (1,'b')) ]
--   </pre>
--   
--   Up to an isomorphism between the resulting vertex types, this
--   operation is <i>commutative</i>, <i>associative</i>,
--   <i>distributes</i> over <a>overlay</a>, has singleton graphs as
--   <i>identities</i> and <a>empty</a> as the <i>annihilating zero</i>.
--   Below <tt>~~</tt> stands for the equality up to an isomorphism, e.g.
--   <tt>(x, ()) ~~ x</tt>.
--   
--   <pre>
--   box x y               ~~ box y x
--   box x (box y z)       ~~ box (box x y) z
--   box x (<a>overlay</a> y z)   == <a>overlay</a> (box x y) (box x z)
--   box x (<a>vertex</a> ())     ~~ x
--   box x <a>empty</a>           ~~ <a>empty</a>
--   <a>vertexCount</a> (box x y) == <a>vertexCount</a> x * <a>vertexCount</a> y
--   <tt>edgeCount</tt>   (box x y) &lt;= <a>vertexCount</a> x * <tt>edgeCount</tt> y + <tt>edgeCount</tt> x * <a>vertexCount</a> y
--   </pre>
box :: Graph g => g a -> g b -> g (a, b)

-- | The <a>ToGraph</a> type class captures data types that can be
--   converted to polymorphic graph expressions. The conversion method
--   <a>toGraph</a> semantically acts as the identity on graph data
--   structures, but allows to convert graphs between different data
--   representations.
--   
--   <pre>
--         toGraph (g     :: <a>Graph</a> a  ) :: <a>Graph</a> a   == g
--   <a>show</a> (toGraph (1 * 2 :: <a>Graph</a> Int) :: <a>Fold</a> Int) == "edge 1 2"
--   </pre>
class ToGraph t
toGraph :: (ToGraph t, Graph g) => t a -> g a


-- | 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 <a>Algebra.Graph.IntAdjacencyMap</a>
--   instead.
module Algebra.Graph.IntAdjacencyMap.Internal

-- | The <a>IntAdjacencyMap</a> data type represents a graph by a map of
--   vertices to their adjacency sets. We define a <a>Num</a> instance as a
--   convenient notation for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Show</a> instance is defined using basic graph construction
--   primitives:
--   
--   <pre>
--   show (empty     :: IntAdjacencyMap Int) == "empty"
--   show (1         :: IntAdjacencyMap Int) == "vertex 1"
--   show (1 + 2     :: IntAdjacencyMap Int) == "vertices [1,2]"
--   show (1 * 2     :: IntAdjacencyMap Int) == "edge 1 2"
--   show (1 * 2 * 3 :: IntAdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
--   show (1 * 2 + 3 :: IntAdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"
--   </pre>
--   
--   The <a>Eq</a> instance satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> and <i>m</i> will denote the number of vertices and edges in
--   the graph, respectively.
data IntAdjacencyMap
AM :: !(IntMap IntSet) -> GraphKL -> IntAdjacencyMap

-- | The <i>adjacency map</i> of the graph: each vertex is associated with
--   a set of its direct successors.
[adjacencyMap] :: IntAdjacencyMap -> !(IntMap IntSet)

-- | Cached King-Launchbury representation. <i>Note: this field is for
--   internal use only</i>.
[graphKL] :: IntAdjacencyMap -> GraphKL

-- | Construct an <tt>AdjacencyMap</tt> from a map of successor sets and
--   (lazily) compute the corresponding King-Launchbury representation.
--   <i>Note: this function is for internal use only</i>.
mkAM :: IntMap IntSet -> IntAdjacencyMap

-- | 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. <i>Note: this function is for internal use only</i>.
--   
--   <pre>
--   consistent <a>empty</a>                  == True
--   consistent (<a>vertex</a> x)             == True
--   consistent (<a>overlay</a> x y)          == True
--   consistent (<a>connect</a> x y)          == True
--   consistent (<a>edge</a> x y)             == True
--   consistent (<a>edges</a> xs)             == True
--   consistent (<a>graph</a> xs ys)          == True
--   consistent (<a>fromAdjacencyList</a> xs) == True
--   </pre>
consistent :: IntAdjacencyMap -> Bool

-- | <a>GraphKL</a> encapsulates King-Launchbury graphs, which are
--   implemented in the <a>Data.Graph</a> module of the <tt>containers</tt>
--   library. <i>Note: this data structure is for internal use only</i>.
--   
--   If <tt>mkGraphKL (adjacencyMap g) == h</tt> then the following holds:
--   
--   <pre>
--   map (<a>fromVertexKL</a> h) (<a>vertices</a> $ <a>toGraphKL</a> h)                               == <a>vertexList</a> g
--   map (\(x, y) -&gt; (<a>fromVertexKL</a> h x, <a>fromVertexKL</a> h y)) (<a>edges</a> $ <a>toGraphKL</a> h) == <a>edgeList</a> g
--   </pre>
data GraphKL
GraphKL :: Graph -> (Vertex -> Int) -> (Int -> Maybe Vertex) -> GraphKL

-- | Array-based graph representation (King and Launchbury, 1995).
[toGraphKL] :: GraphKL -> Graph

-- | A mapping of <a>Data.Graph.Vertex</a> to vertices of type
--   <tt>Int</tt>.
[fromVertexKL] :: GraphKL -> Vertex -> Int

-- | A mapping from vertices of type <tt>Int</tt> to
--   <a>Data.Graph.Vertex</a>. Returns <a>Nothing</a> if the argument is
--   not in the graph.
[toVertexKL] :: GraphKL -> Int -> Maybe Vertex

-- | Build <a>GraphKL</a> from a map of successor sets. <i>Note: this
--   function is for internal use only</i>.
mkGraphKL :: IntMap IntSet -> GraphKL
instance GHC.Classes.Eq Algebra.Graph.IntAdjacencyMap.Internal.IntAdjacencyMap
instance GHC.Show.Show Algebra.Graph.IntAdjacencyMap.Internal.IntAdjacencyMap
instance Algebra.Graph.Class.Graph Algebra.Graph.IntAdjacencyMap.Internal.IntAdjacencyMap
instance GHC.Num.Num Algebra.Graph.IntAdjacencyMap.Internal.IntAdjacencyMap
instance Algebra.Graph.Class.ToGraph Algebra.Graph.IntAdjacencyMap.Internal.IntAdjacencyMap


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the <a>IntAdjacencyMap</a> data type, as well as
--   associated operations and algorithms. <a>IntAdjacencyMap</a> is an
--   instance of the <a>Graph</a> type class, which can be used for
--   polymorphic graph construction and manipulation. See
--   <a>Algebra.Graph.AdjacencyMap</a> for graphs with non-<tt>Int</tt>
--   vertices.
module Algebra.Graph.IntAdjacencyMap

-- | The <a>IntAdjacencyMap</a> data type represents a graph by a map of
--   vertices to their adjacency sets. We define a <a>Num</a> instance as a
--   convenient notation for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Show</a> instance is defined using basic graph construction
--   primitives:
--   
--   <pre>
--   show (empty     :: IntAdjacencyMap Int) == "empty"
--   show (1         :: IntAdjacencyMap Int) == "vertex 1"
--   show (1 + 2     :: IntAdjacencyMap Int) == "vertices [1,2]"
--   show (1 * 2     :: IntAdjacencyMap Int) == "edge 1 2"
--   show (1 * 2 * 3 :: IntAdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
--   show (1 * 2 + 3 :: IntAdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"
--   </pre>
--   
--   The <a>Eq</a> instance satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> and <i>m</i> will denote the number of vertices and edges in
--   the graph, respectively.
data IntAdjacencyMap

-- | The <i>adjacency map</i> of the graph: each vertex is associated with
--   a set of its direct successors.
adjacencyMap :: IntAdjacencyMap -> (IntMap IntSet)

-- | Construct the <i>empty graph</i>. Complexity: <i>O(1)</i> time and
--   memory.
--   
--   <pre>
--   <a>isEmpty</a>     empty == True
--   <a>hasVertex</a> x empty == False
--   <a>vertexCount</a> empty == 0
--   <a>edgeCount</a>   empty == 0
--   </pre>
empty :: IntAdjacencyMap

-- | Construct the graph comprising <i>a single isolated vertex</i>.
--   Complexity: <i>O(1)</i> time and memory.
--   
--   <pre>
--   <a>isEmpty</a>     (vertex x) == False
--   <a>hasVertex</a> x (vertex x) == True
--   <a>vertexCount</a> (vertex x) == 1
--   <a>edgeCount</a>   (vertex x) == 0
--   </pre>
vertex :: Int -> IntAdjacencyMap

-- | Construct the graph comprising <i>a single edge</i>. Complexity:
--   <i>O(1)</i> time, memory.
--   
--   <pre>
--   edge x y               == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   <a>hasEdge</a> x y (edge x y) == True
--   <a>edgeCount</a>   (edge x y) == 1
--   <a>vertexCount</a> (edge 1 1) == 1
--   <a>vertexCount</a> (edge 1 2) == 2
--   </pre>
edge :: Int -> Int -> IntAdjacencyMap

-- | <i>Overlay</i> two graphs. This is a commutative, associative and
--   idempotent operation with the identity <a>empty</a>. Complexity:
--   <i>O((n + m) * log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   <a>isEmpty</a>     (overlay x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (overlay x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (overlay x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (overlay x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (overlay x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (overlay x y) &lt;= <a>edgeCount</a> x   + <a>edgeCount</a> y
--   <a>vertexCount</a> (overlay 1 2) == 2
--   <a>edgeCount</a>   (overlay 1 2) == 0
--   </pre>
overlay :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap

-- | <i>Connect</i> two graphs. This is an associative operation with the
--   identity <a>empty</a>, which distributes over <a>overlay</a> and obeys
--   the decomposition axiom. Complexity: <i>O((n + m) * log(n))</i> time
--   and <i>O(n + m)</i> memory. Note that the number of edges in the
--   resulting graph is quadratic with respect to the number of vertices of
--   the arguments: <i>m = O(m1 + m2 + n1 * n2)</i>.
--   
--   <pre>
--   <a>isEmpty</a>     (connect x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (connect x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (connect x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (connect x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &lt;= <a>vertexCount</a> x * <a>vertexCount</a> y + <a>edgeCount</a> x + <a>edgeCount</a> y
--   <a>vertexCount</a> (connect 1 2) == 2
--   <a>edgeCount</a>   (connect 1 2) == 1
--   </pre>
connect :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L * log(L))</i> time and <i>O(L)</i> memory, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   vertices []             == <a>empty</a>
--   vertices [x]            == <a>vertex</a> x
--   <a>hasVertex</a> x  . vertices == <a>elem</a> x
--   <a>vertexCount</a>  . vertices == <a>length</a> . <a>nub</a>
--   <a>vertexIntSet</a> . vertices == IntSet.<a>fromList</a>
--   </pre>
vertices :: [Int] -> IntAdjacencyMap

-- | Construct the graph from a list of edges. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   edges []          == <a>empty</a>
--   edges [(x, y)]    == <a>edge</a> x y
--   <a>edgeCount</a> . edges == <a>length</a> . <a>nub</a>
--   <a>edgeList</a> . edges  == <a>nub</a> . <a>sort</a>
--   </pre>
edges :: [(Int, Int)] -> IntAdjacencyMap

-- | Overlay a given list of graphs. Complexity: <i>O((n + m) * log(n))</i>
--   time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   overlays []        == <a>empty</a>
--   overlays [x]       == x
--   overlays [x,y]     == <a>overlay</a> x y
--   overlays           == <a>foldr</a> <a>overlay</a> <a>empty</a>
--   <a>isEmpty</a> . overlays == <a>all</a> <a>isEmpty</a>
--   </pre>
overlays :: [IntAdjacencyMap] -> IntAdjacencyMap

-- | Connect a given list of graphs. Complexity: <i>O((n + m) * log(n))</i>
--   time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   connects []        == <a>empty</a>
--   connects [x]       == x
--   connects [x,y]     == <a>connect</a> x y
--   connects           == <a>foldr</a> <a>connect</a> <a>empty</a>
--   <a>isEmpty</a> . connects == <a>all</a> <a>isEmpty</a>
--   </pre>
connects :: [IntAdjacencyMap] -> IntAdjacencyMap

-- | Construct a graph from an adjacency list. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   fromAdjacencyList []                                  == <a>empty</a>
--   fromAdjacencyList [(x, [])]                           == <a>vertex</a> x
--   fromAdjacencyList [(x, [y])]                          == <a>edge</a> x y
--   fromAdjacencyList . <a>adjacencyList</a>                     == id
--   <a>overlay</a> (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys)
--   </pre>
fromAdjacencyList :: [(Int, [Int])] -> IntAdjacencyMap

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Complexity: <i>O((n + m) * log(n))</i> time.
--   
--   <pre>
--   isSubgraphOf <a>empty</a>         x             == True
--   isSubgraphOf (<a>vertex</a> x)    <a>empty</a>         == False
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path</a> xs)     (<a>circuit</a> xs)  == True
--   </pre>
isSubgraphOf :: IntAdjacencyMap -> IntAdjacencyMap -> Bool

-- | Check if a graph is empty. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   isEmpty <a>empty</a>                       == True
--   isEmpty (<a>overlay</a> <a>empty</a> <a>empty</a>)       == True
--   isEmpty (<a>vertex</a> x)                  == False
--   isEmpty (<a>removeVertex</a> x $ <a>vertex</a> x) == True
--   isEmpty (<a>removeEdge</a> x y $ <a>edge</a> x y) == False
--   </pre>
isEmpty :: IntAdjacencyMap -> Bool

-- | Check if a graph contains a given vertex. Complexity: <i>O(log(n))</i>
--   time.
--   
--   <pre>
--   hasVertex x <a>empty</a>            == False
--   hasVertex x (<a>vertex</a> x)       == True
--   hasVertex 1 (<a>vertex</a> 2)       == False
--   hasVertex x . <a>removeVertex</a> x == const False
--   </pre>
hasVertex :: Int -> IntAdjacencyMap -> Bool

-- | Check if a graph contains a given edge. Complexity: <i>O(log(n))</i>
--   time.
--   
--   <pre>
--   hasEdge x y <a>empty</a>            == False
--   hasEdge x y (<a>vertex</a> z)       == False
--   hasEdge x y (<a>edge</a> x y)       == True
--   hasEdge x y . <a>removeEdge</a> x y == const False
--   hasEdge x y                  == <a>elem</a> (x,y) . <a>edgeList</a>
--   </pre>
hasEdge :: Int -> Int -> IntAdjacencyMap -> Bool

-- | The number of vertices in a graph. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   vertexCount <a>empty</a>      == 0
--   vertexCount (<a>vertex</a> x) == 1
--   vertexCount            == <a>length</a> . <a>vertexList</a>
--   </pre>
vertexCount :: IntAdjacencyMap -> Int

-- | The number of edges in a graph. Complexity: <i>O(n)</i> time.
--   
--   <pre>
--   edgeCount <a>empty</a>      == 0
--   edgeCount (<a>vertex</a> x) == 0
--   edgeCount (<a>edge</a> x y) == 1
--   edgeCount            == <a>length</a> . <a>edgeList</a>
--   </pre>
edgeCount :: IntAdjacencyMap -> Int

-- | The sorted list of vertices of a given graph. Complexity: <i>O(n)</i>
--   time and memory.
--   
--   <pre>
--   vertexList <a>empty</a>      == []
--   vertexList (<a>vertex</a> x) == [x]
--   vertexList . <a>vertices</a> == <a>nub</a> . <a>sort</a>
--   </pre>
vertexList :: IntAdjacencyMap -> [Int]

-- | The sorted list of edges of a graph. Complexity: <i>O(n + m)</i> time
--   and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeList <a>empty</a>          == []
--   edgeList (<a>vertex</a> x)     == []
--   edgeList (<a>edge</a> x y)     == [(x,y)]
--   edgeList (<a>star</a> 2 [3,1]) == [(2,1), (2,3)]
--   edgeList . <a>edges</a>        == <a>nub</a> . <a>sort</a>
--   edgeList . <a>transpose</a>    == <a>sort</a> . map <a>swap</a> . edgeList
--   </pre>
edgeList :: IntAdjacencyMap -> [(Int, Int)]

-- | The sorted <i>adjacency list</i> of a graph. Complexity: <i>O(n +
--   m)</i> time and <i>O(m)</i> memory.
--   
--   <pre>
--   adjacencyList <a>empty</a>               == []
--   adjacencyList (<a>vertex</a> x)          == [(x, [])]
--   adjacencyList (<a>edge</a> 1 2)          == [(1, [2]), (2, [])]
--   adjacencyList (<a>star</a> 2 [3,1])      == [(1, []), (2, [1,3]), (3, [])]
--   <a>fromAdjacencyList</a> . adjacencyList == id
--   </pre>
adjacencyList :: IntAdjacencyMap -> [(Int, [Int])]

-- | The set of vertices of a given graph. Complexity: <i>O(n)</i> time and
--   memory.
--   
--   <pre>
--   vertexIntSet <a>empty</a>      == IntSet.<a>empty</a>
--   vertexIntSet . <a>vertex</a>   == IntSet.<a>singleton</a>
--   vertexIntSet . <a>vertices</a> == IntSet.<a>fromList</a>
--   vertexIntSet . <a>clique</a>   == IntSet.<a>fromList</a>
--   </pre>
vertexIntSet :: IntAdjacencyMap -> IntSet

-- | The set of edges of a given graph. Complexity: <i>O((n + m) *
--   log(m))</i> time and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeSet <a>empty</a>      == Set.<a>empty</a>
--   edgeSet (<a>vertex</a> x) == Set.<a>empty</a>
--   edgeSet (<a>edge</a> x y) == Set.<a>singleton</a> (x,y)
--   edgeSet . <a>edges</a>    == Set.<a>fromList</a>
--   </pre>
edgeSet :: IntAdjacencyMap -> Set (Int, Int)

-- | The <i>postset</i> (here <a>postIntSet</a>) of a vertex is the set of
--   its <i>direct successors</i>.
--   
--   <pre>
--   postIntSet x <a>empty</a>      == IntSet.<a>empty</a>
--   postIntSet x (<a>vertex</a> x) == IntSet.<a>empty</a>
--   postIntSet x (<a>edge</a> x y) == IntSet.<a>fromList</a> [y]
--   postIntSet 2 (<a>edge</a> 1 2) == IntSet.<a>empty</a>
--   </pre>
postIntSet :: Int -> IntAdjacencyMap -> IntSet

-- | The <i>path</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   path []        == <a>empty</a>
--   path [x]       == <a>vertex</a> x
--   path [x,y]     == <a>edge</a> x y
--   path . <a>reverse</a> == <a>transpose</a> . path
--   </pre>
path :: [Int] -> IntAdjacencyMap

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   circuit []        == <a>empty</a>
--   circuit [x]       == <a>edge</a> x x
--   circuit [x,y]     == <a>edges</a> [(x,y), (y,x)]
--   circuit . <a>reverse</a> == <a>transpose</a> . circuit
--   </pre>
circuit :: [Int] -> IntAdjacencyMap

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   clique []         == <a>empty</a>
--   clique [x]        == <a>vertex</a> x
--   clique [x,y]      == <a>edge</a> x y
--   clique [x,y,z]    == <a>edges</a> [(x,y), (x,z), (y,z)]
--   clique (xs ++ ys) == <a>connect</a> (clique xs) (clique ys)
--   clique . <a>reverse</a>  == <a>transpose</a> . clique
--   </pre>
clique :: [Int] -> IntAdjacencyMap

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(n *
--   log(n) + m)</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   biclique []      []      == <a>empty</a>
--   biclique [x]     []      == <a>vertex</a> x
--   biclique []      [y]     == <a>vertex</a> y
--   biclique [x1,x2] [y1,y2] == <a>edges</a> [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
--   biclique xs      ys      == <a>connect</a> (<a>vertices</a> xs) (<a>vertices</a> ys)
--   </pre>
biclique :: [Int] -> [Int] -> IntAdjacencyMap

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges</a> [(x,y), (x,z)]
--   star x ys    == <a>connect</a> (<a>vertex</a> x) (<a>vertices</a> ys)
--   </pre>
star :: Int -> [Int] -> IntAdjacencyMap

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges</a> [(y,x), (z,x)]
--   starTranspose x ys    == <a>connect</a> (<a>vertices</a> ys) (<a>vertex</a> x)
--   starTranspose x ys    == <a>transpose</a> (<a>star</a> x ys)
--   </pre>
starTranspose :: Int -> [Int] -> IntAdjacencyMap

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path</a> [x,y,z]
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges</a> [(1,2), (1,3), (3,4), (3,5)]
--   </pre>
tree :: Tree Int -> IntAdjacencyMap

-- | The <i>forest graph</i> constructed from a given <a>Forest</a> data
--   structure. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   forest []                                                  == <a>empty</a>
--   forest [x]                                                 == <a>tree</a> x
--   forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == <a>edges</a> [(1,2), (1,3), (4,5)]
--   forest                                                     == <a>overlays</a> . map <a>tree</a>
--   </pre>
forest :: Forest Int -> IntAdjacencyMap

-- | Remove a vertex from a given graph. Complexity: <i>O(n*log(n))</i>
--   time.
--   
--   <pre>
--   removeVertex x (<a>vertex</a> x)       == <a>empty</a>
--   removeVertex 1 (<a>vertex</a> 2)       == <a>vertex</a> 2
--   removeVertex x (<a>edge</a> x x)       == <a>empty</a>
--   removeVertex 1 (<a>edge</a> 1 2)       == <a>vertex</a> 2
--   removeVertex x . removeVertex x == removeVertex x
--   </pre>
removeVertex :: Int -> IntAdjacencyMap -> IntAdjacencyMap

-- | Remove an edge from a given graph. Complexity: <i>O(log(n))</i> time.
--   
--   <pre>
--   removeEdge x y (<a>edge</a> x y)       == <a>vertices</a> [x, y]
--   removeEdge x y . removeEdge x y == removeEdge x y
--   removeEdge x y . <a>removeVertex</a> x == <a>removeVertex</a> x
--   removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
--   removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2
--   </pre>
removeEdge :: Int -> Int -> IntAdjacencyMap -> IntAdjacencyMap

-- | The function <tt><a>replaceVertex</a> x y</tt> replaces vertex
--   <tt>x</tt> with vertex <tt>y</tt> in a given <a>IntAdjacencyMap</a>.
--   If <tt>y</tt> already exists, <tt>x</tt> and <tt>y</tt> will be
--   merged. Complexity: <i>O((n + m) * log(n))</i> time.
--   
--   <pre>
--   replaceVertex x x            == id
--   replaceVertex x y (<a>vertex</a> x) == <a>vertex</a> y
--   replaceVertex x y            == <a>mergeVertices</a> (== x) y
--   </pre>
replaceVertex :: Int -> Int -> IntAdjacencyMap -> IntAdjacencyMap

-- | Merge vertices satisfying a given predicate into a given vertex.
--   Complexity: <i>O((n + m) * log(n))</i> time, assuming that the
--   predicate takes <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   mergeVertices (const False) x    == id
--   mergeVertices (== x) y           == <a>replaceVertex</a> x y
--   mergeVertices even 1 (0 * 2)     == 1 * 1
--   mergeVertices odd  1 (3 + 4 * 5) == 4 * 1
--   </pre>
mergeVertices :: (Int -> Bool) -> Int -> IntAdjacencyMap -> IntAdjacencyMap

-- | Transpose a given graph. Complexity: <i>O(m * log(n))</i> time, <i>O(n
--   + m)</i> memory.
--   
--   <pre>
--   transpose <a>empty</a>       == <a>empty</a>
--   transpose (<a>vertex</a> x)  == <a>vertex</a> x
--   transpose (<a>edge</a> x y)  == <a>edge</a> y x
--   transpose . transpose == id
--   <a>edgeList</a> . transpose  == <a>sort</a> . map <a>swap</a> . <a>edgeList</a>
--   </pre>
transpose :: IntAdjacencyMap -> IntAdjacencyMap

-- | Transform a graph by applying a function to each of its vertices. This
--   is similar to <tt>Functor</tt>'s <a>fmap</a> but can be used with
--   non-fully-parametric <a>IntAdjacencyMap</a>. Complexity: <i>O((n + m)
--   * log(n))</i> time.
--   
--   <pre>
--   gmap f <a>empty</a>      == <a>empty</a>
--   gmap f (<a>vertex</a> x) == <a>vertex</a> (f x)
--   gmap f (<a>edge</a> x y) == <a>edge</a> (f x) (f y)
--   gmap id           == id
--   gmap f . gmap g   == gmap (f . g)
--   </pre>
gmap :: (Int -> Int) -> IntAdjacencyMap -> IntAdjacencyMap

-- | Construct the <i>induced subgraph</i> of a given graph by removing the
--   vertices that do not satisfy a given predicate. Complexity:
--   <i>O(m)</i> time, assuming that the predicate takes <i>O(1)</i> to be
--   evaluated.
--   
--   <pre>
--   induce (const True ) x      == x
--   induce (const False) x      == <a>empty</a>
--   induce (/= x)               == <a>removeVertex</a> x
--   induce p . induce q         == induce (\x -&gt; p x &amp;&amp; q x)
--   <a>isSubgraphOf</a> (induce p x) x == True
--   </pre>
induce :: (Int -> Bool) -> IntAdjacencyMap -> IntAdjacencyMap

-- | Compute the <i>depth-first search</i> forest of a graph.
--   
--   <pre>
--   <a>forest</a> (dfsForest $ <a>edge</a> 1 1)         == <a>vertex</a> 1
--   <a>forest</a> (dfsForest $ <a>edge</a> 1 2)         == <a>edge</a> 1 2
--   <a>forest</a> (dfsForest $ <a>edge</a> 2 1)         == <a>vertices</a> [1, 2]
--   <a>isSubgraphOf</a> (<a>forest</a> $ dfsForest x) x == True
--   dfsForest . <a>forest</a> . dfsForest        == dfsForest
--   dfsForest (<a>vertices</a> vs)               == map (\v -&gt; Node v []) (<a>nub</a> $ <a>sort</a> vs)
--   <a>dfsForestFrom</a> (<a>vertexList</a> 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 = [] }]}]
--   </pre>
dfsForest :: IntAdjacencyMap -> Forest Int

-- | Compute the <i>depth-first search</i> 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.
--   
--   <pre>
--   <a>forest</a> (dfsForestFrom [1]    $ <a>edge</a> 1 1)     == <a>vertex</a> 1
--   <a>forest</a> (dfsForestFrom [1]    $ <a>edge</a> 1 2)     == <a>edge</a> 1 2
--   <a>forest</a> (dfsForestFrom [2]    $ <a>edge</a> 1 2)     == <a>vertex</a> 2
--   <a>forest</a> (dfsForestFrom [3]    $ <a>edge</a> 1 2)     == <a>empty</a>
--   <a>forest</a> (dfsForestFrom [2, 1] $ <a>edge</a> 1 2)     == <a>vertices</a> [1, 2]
--   <a>isSubgraphOf</a> (<a>forest</a> $ dfsForestFrom vs x) x == True
--   dfsForestFrom (<a>vertexList</a> x) x               == <a>dfsForest</a> x
--   dfsForestFrom vs             (<a>vertices</a> vs)   == map (\v -&gt; Node v []) (<a>nub</a> vs)
--   dfsForestFrom []             x               == []
--   dfsForestFrom [1, 4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
--                                                          , subForest = [ Node { rootLabel = 5
--                                                                               , subForest = [] }
--                                                   , Node { rootLabel = 4
--                                                          , subForest = [] }]
--   </pre>
dfsForestFrom :: [Int] -> IntAdjacencyMap -> Forest Int

-- | Compute the list of vertices visited by the <i>depth-first search</i>
--   in a graph, when searching from each of the given vertices in order.
--   
--   <pre>
--   dfs [1]    $ <a>edge</a> 1 1                == [1]
--   dfs [1]    $ <a>edge</a> 1 2                == [1, 2]
--   dfs [2]    $ <a>edge</a> 1 2                == [2]
--   dfs [3]    $ <a>edge</a> 1 2                == []
--   dfs [1, 2] $ <a>edge</a> 1 2                == [1, 2]
--   dfs [2, 1] $ <a>edge</a> 1 2                == [2, 1]
--   dfs []     $ x                       == []
--   dfs [1, 4] $ 3 * (1 + 4) * (1 + 5)   == [1, 5, 4]
--   <a>isSubgraphOf</a> (<a>vertices</a> $ dfs vs x) x == True
--   </pre>
dfs :: [Int] -> IntAdjacencyMap -> [Int]

-- | Compute the <i>topological sort</i> of a graph or return
--   <tt>Nothing</tt> if the graph is cyclic.
--   
--   <pre>
--   topSort (1 * 2 + 3 * 1)             == Just [3,1,2]
--   topSort (1 * 2 + 2 * 1)             == Nothing
--   fmap (flip <a>isTopSort</a> x) (topSort x) /= Just False
--   </pre>
topSort :: IntAdjacencyMap -> Maybe [Int]

-- | Check if a given list of vertices is a valid <i>topological sort</i>
--   of a graph.
--   
--   <pre>
--   isTopSort [3, 1, 2] (1 * 2 + 3 * 1) == True
--   isTopSort [1, 2, 3] (1 * 2 + 3 * 1) == False
--   isTopSort []        (1 * 2 + 3 * 1) == False
--   isTopSort []        <a>empty</a>           == True
--   isTopSort [x]       (<a>vertex</a> x)      == True
--   isTopSort [x]       (<a>edge</a> x x)      == False
--   </pre>
isTopSort :: [Int] -> IntAdjacencyMap -> Bool


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> 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 <i>O(1)</i> time concatenation (the
--   current implementation uses difference lists). Here <tt>a</tt> is the
--   type of list elements. <a>List</a> <tt>a</tt> is a <a>Monoid</a>:
--   <a>mempty</a> corresponds to the empty list and two lists can be
--   concatenated with <a>mappend</a> (or operator <a>&lt;&gt;</a>).
--   Singleton lists can be constructed using the function <a>pure</a> from
--   the <a>Applicative</a> instance. <a>List</a> <tt>a</tt> is also an
--   instance of <tt>IsList</tt>, therefore you can use list literals, e.g.
--   <tt>[1,4]</tt> <tt>::</tt> <a>List</a> <tt>Int</tt> is the same as
--   <a>pure</a> <tt>1</tt> <a>&lt;&gt;</a> <a>pure</a> <tt>4</tt>; note
--   that this requires the <tt>OverloadedLists</tt> GHC extension. To
--   extract plain Haskell lists you can use the <a>toList</a> function
--   from the <a>Foldable</a> instance.
newtype List a
List :: (Endo [a]) -> List a

-- | The <i>focus</i> 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 <a>removeEdge</a> for a use-case example.
data Focus a

-- | <a>Focus</a> on a specified subgraph.
focus :: ToGraph g => (ToVertex g -> Bool) -> g -> Focus (ToVertex g)

-- | 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 <a>Focus</a>. Returns
--   <tt>Nothing</tt> if the focus could not be obtained.
context :: ToGraph g => (ToVertex g -> Bool) -> g -> Maybe (Context (ToVertex g))
instance Data.Semigroup.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


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> 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. <a>Algebra.Graph.Export.Dot</a> provides
--   DOT-specific functions.
module Algebra.Graph.Export

-- | An abstract document data type with <i>O(1)</i> time concatenation
--   (the current implementation uses difference lists). Here <tt>s</tt> is
--   the type of abstract symbols or strings (text or binary). <a>Doc</a>
--   <tt>s</tt> is a <a>Monoid</a>, therefore <a>mempty</a> corresponds to
--   the empty document and two documents can be concatenated with
--   <a>mappend</a> (or operator <a>&lt;&gt;</a>). Documents comprising a
--   single symbol or string can be constructed using the function
--   <a>literal</a>. Alternatively, you can construct documents as string
--   literals, e.g. simply as <tt>"alga"</tt>, by using the
--   <tt>OverloadedStrings</tt> GHC extension. To extract the document
--   contents use the function <a>render</a>. See some examples below.
data Doc s

-- | Construct a document comprising a single symbol or string. If
--   <tt>s</tt> is an instance of class <a>IsString</a>, then documents of
--   type <a>Doc</a> <tt>s</tt> can be constructed directly from string
--   literals (see the second example below).
--   
--   <pre>
--   literal "Hello, " <a>&lt;&gt;</a> literal "World!" == literal "Hello, World!"
--   literal "I am just a string literal"  == "I am just a string literal"
--   literal <a>mempty</a>                        == <a>mempty</a>
--   <a>render</a> . literal                      == <a>id</a>
--   literal . <a>render</a>                      == <a>id</a>
--   </pre>
literal :: s -> Doc s

-- | Render the document as a single string. An inverse of the function
--   <a>literal</a>.
--   
--   <pre>
--   render (<a>literal</a> "al" <a>&lt;&gt;</a> <a>literal</a> "ga") :: (<a>IsString</a> s, <a>Monoid</a> s) =&gt; s
--   render (<a>literal</a> "al" <a>&lt;&gt;</a> <a>literal</a> "ga") == "alga"
--   render <a>mempty</a>                         == <a>mempty</a>
--   render . <a>literal</a>                      == <a>id</a>
--   <a>literal</a> . render                      == <a>id</a>
--   </pre>
render :: Monoid s => Doc s -> s

-- | Concatenate two documents, separated by a single space, unless one of
--   the documents is empty. The operator &lt;+&gt; is associative with
--   identity <a>mempty</a>.
--   
--   <pre>
--   x &lt;+&gt; <a>mempty</a>         == x
--   <a>mempty</a> &lt;+&gt; x         == x
--   x &lt;+&gt; (y &lt;+&gt; z)      == (x &lt;+&gt; y) &lt;+&gt; z
--   "name" &lt;+&gt; "surname" == "name surname"
--   </pre>
(<+>) :: (Eq s, IsString s, Monoid s) => Doc s -> Doc s -> Doc s
infixl 7 <+>

-- | Wrap a document in square brackets.
--   
--   <pre>
--   brackets "i"    == "[i]"
--   brackets <a>mempty</a> == "[]"
--   </pre>
brackets :: IsString s => Doc s -> Doc s

-- | Wrap a document into double quotes.
--   
--   <pre>
--   doubleQuotes "/path/with spaces"   == "\"/path/with spaces\""
--   doubleQuotes (doubleQuotes <a>mempty</a>) == "\"\"\"\""
--   </pre>
doubleQuotes :: IsString s => Doc s -> Doc s

-- | Prepend a given number of spaces to a document.
--   
--   <pre>
--   indent 0        == <a>id</a>
--   indent 1 <a>mempty</a> == " "
--   </pre>
indent :: IsString s => Int -> Doc s -> Doc s

-- | Concatenate documents after appending a terminating newline symbol to
--   each.
--   
--   <pre>
--   unlines []                    == <a>mempty</a>
--   unlines [<a>mempty</a>]              == "\n"
--   unlines ["title", "subtitle"] == "title\nsubtitle\n"
--   </pre>
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 <a>Ord</a> <tt>a</tt>, and then edges, sorted by
--   <a>Ord</a> <tt>(a, a)</tt>.
--   
--   For example:
--   
--   <pre>
--   vDoc x   = <a>literal</a> (<a>show</a> x) &lt;&gt; "\n"
--   eDoc x y = <a>literal</a> (<a>show</a> x) &lt;&gt; " -&gt; " &lt;&gt; <a>literal</a> (<a>show</a> y) &lt;&gt; "\n"
--   &gt; putStrLn $ <a>render</a> $ export vDoc eDoc (1 + 2 * (3 + 4) :: <a>Graph</a> Int)
--   
--   1
--   2
--   3
--   4
--   2 -&gt; 3
--   2 -&gt; 4
--   </pre>
export :: (Ord a, ToGraph g, ToVertex g ~ a) => (a -> Doc s) -> (a -> a -> Doc s) -> g -> Doc s
instance Data.Semigroup.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)


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> 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 <tt>"shape" :=
--   "box"</tt>. Attributes are used to specify the style of graph elements
--   during export.
data Attribute s
(:=) :: s -> s -> Attribute s

-- | The record <a>Style</a> <tt>a</tt> <tt>s</tt> specifies the style to
--   use when exporting a graph in the DOT format. Here <tt>a</tt> is the
--   type of the graph vertices, and <tt>s</tt> 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 <a>vertexName</a>, which holds a function of type <tt>a -&gt;
--   s</tt> to compute vertex names. See the example for the function
--   <a>export</a>.
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. <tt>["bgcolor" := "azure"]</tt>.
[graphAttributes] :: Style a s -> [Attribute s]

-- | Default vertex style, e.g. <tt>["shape" := "diamond"]</tt>.
[defaultVertexAttributes] :: Style a s -> [Attribute s]

-- | Default edge style, e.g. <tt>["style" := "dashed"]</tt>.
[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 <a>vertexName</a>, which is provided as the only argument.
defaultStyle :: Monoid s => (a -> s) -> Style a s

-- | Default style for exporting graphs whose vertices are
--   <a>Show</a>-able. All style settings are empty except for
--   <a>vertexName</a>, which is computed from <a>show</a>.
--   
--   <pre>
--   defaultStyleViaShow = <a>defaultStyle</a> (<a>fromString</a> . <a>show</a>)
--   </pre>
defaultStyleViaShow :: (Show a, IsString s, Monoid s) => Style a s

-- | Export a graph with a given style.
--   
--   For example:
--   
--   <pre>
--   style :: <a>Style</a> Int String
--   style = <a>Style</a>
--       { <a>graphName</a>               = "Example"
--       , <a>preamble</a>                = "  // This is an example\n"
--       , <a>graphAttributes</a>         = ["label" := "Example", "labelloc" := "top"]
--       , <a>defaultVertexAttributes</a> = ["shape" := "circle"]
--       , <a>defaultEdgeAttributes</a>   = <a>mempty</a>
--       , <a>vertexName</a>              = \x   -&gt; "v" ++ <a>show</a> x
--       , <a>vertexAttributes</a>        = \x   -&gt; ["color" := "blue"   | <a>odd</a> x      ]
--       , <a>edgeAttributes</a>          = \x y -&gt; ["style" := "dashed" | <a>odd</a> (x * y)] }
--   
--   &gt; putStrLn $ export style (1 * 2 + 3 * 4 * 5 :: <tt>Graph</tt> 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" -&gt; "v2"
--     "v3" -&gt; "v4"
--     "v3" -&gt; "v5" [style="dashed"]
--     "v4" -&gt; "v5"
--   }
--   </pre>
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:
--   
--   <pre>
--   &gt; Text.putStrLn $ exportAsIs (<a>circuit</a> ["a", "b", "c"] :: <a>AdjacencyMap</a> Text)
--   
--   digraph
--   {
--     "a"
--     "b"
--     "c"
--     "a" -&gt; "b"
--     "b" -&gt; "c"
--     "c" -&gt; "a"
--   }
--   </pre>
exportAsIs :: (IsString s, Monoid s, Ord s, ToGraph g, ToVertex g ~ s) => g -> s

-- | Export a graph using the <a>defaultStyleViaShow</a>.
--   
--   For example:
--   
--   <pre>
--   &gt; putStrLn $ exportViaShow (1 + 2 * (3 + 4) :: <a>Graph</a> Int)
--   
--   digraph
--   {
--     "1"
--     "2"
--     "3"
--     "4"
--     "2" -&gt; "3"
--     "2" -&gt; "4"
--   }
--   </pre>
exportViaShow :: (IsString s, Monoid s, Eq s, ToGraph g, Ord (ToVertex g), Show (ToVertex g)) => g -> s


-- | This module exposes the implementation of the <a>Relation</a> data
--   type. The API is unstable and unsafe, and is exposed only for
--   documentation. You should use the non-internal module
--   <a>Algebra.Graph.Relation</a> instead.
module Algebra.Graph.Relation.Internal

-- | The <a>Relation</a> data type represents a graph as a <i>binary
--   relation</i>. We define a <a>Num</a> instance as a convenient notation
--   for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Show</a> instance is defined using basic graph construction
--   primitives:
--   
--   <pre>
--   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)"
--   </pre>
--   
--   The <a>Eq</a> instance satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> and <i>m</i> will denote the number of vertices and edges in
--   the graph, respectively.
data Relation a
Relation :: Set a -> Set (a, a) -> Relation a

-- | The <i>domain</i> of the relation.
[domain] :: Relation a -> Set a

-- | The set of pairs of elements that are <i>related</i>. It is guaranteed
--   that each element belongs to the domain.
[relation] :: Relation a -> Set (a, a)

-- | Check if the internal representation of a relation is consistent, i.e.
--   if all pairs of elements in the <a>relation</a> refer to existing
--   elements in the <a>domain</a>. It should be impossible to create an
--   inconsistent <a>Relation</a>, and we use this function in testing.
--   <i>Note: this function is for internal use only</i>.
--   
--   <pre>
--   consistent <a>empty</a>                  == True
--   consistent (<a>vertex</a> x)             == True
--   consistent (<a>overlay</a> x y)          == True
--   consistent (<a>connect</a> x y)          == True
--   consistent (<a>edge</a> x y)             == True
--   consistent (<a>edges</a> xs)             == True
--   consistent (<a>graph</a> xs ys)          == True
--   consistent (<a>fromAdjacencyList</a> xs) == True
--   </pre>
consistent :: Ord a => Relation a -> Bool

-- | Compute the Cartesian product of two sets. <i>Note: this function is
--   for internal use only</i>.
setProduct :: Set a -> Set b -> Set (a, b)

-- | The set of elements that appear in a given set of pairs. <i>Note: this
--   function is for internal use only</i>.
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 GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.Internal.Relation a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.Internal.Relation a)
instance Algebra.Graph.Class.ToGraph (Algebra.Graph.Relation.Internal.Relation a)


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the <a>Relation</a> data type, as well as
--   associated operations and algorithms. <a>Relation</a> is an instance
--   of the <a>Graph</a> type class, which can be used for polymorphic
--   graph construction and manipulation.
module Algebra.Graph.Relation

-- | The <a>Relation</a> data type represents a graph as a <i>binary
--   relation</i>. We define a <a>Num</a> instance as a convenient notation
--   for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Show</a> instance is defined using basic graph construction
--   primitives:
--   
--   <pre>
--   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)"
--   </pre>
--   
--   The <a>Eq</a> instance satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> and <i>m</i> will denote the number of vertices and edges in
--   the graph, respectively.
data Relation a

-- | The <i>domain</i> of the relation.
domain :: Relation a -> Set a

-- | The set of pairs of elements that are <i>related</i>. It is guaranteed
--   that each element belongs to the domain.
relation :: Relation a -> Set (a, a)

-- | Construct the <i>empty graph</i>. Complexity: <i>O(1)</i> time and
--   memory.
--   
--   <pre>
--   <a>isEmpty</a>     empty == True
--   <a>hasVertex</a> x empty == False
--   <a>vertexCount</a> empty == 0
--   <a>edgeCount</a>   empty == 0
--   </pre>
empty :: Ord a => Relation a

-- | Construct the graph comprising <i>a single isolated vertex</i>.
--   Complexity: <i>O(1)</i> time and memory.
--   
--   <pre>
--   <a>isEmpty</a>     (vertex x) == False
--   <a>hasVertex</a> x (vertex x) == True
--   <a>vertexCount</a> (vertex x) == 1
--   <a>edgeCount</a>   (vertex x) == 0
--   </pre>
vertex :: Ord a => a -> Relation a

-- | Construct the graph comprising <i>a single edge</i>. Complexity:
--   <i>O(1)</i> time, memory and size.
--   
--   <pre>
--   edge x y               == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   <a>hasEdge</a> x y (edge x y) == True
--   <a>edgeCount</a>   (edge x y) == 1
--   <a>vertexCount</a> (edge 1 1) == 1
--   <a>vertexCount</a> (edge 1 2) == 2
--   </pre>
edge :: Ord a => a -> a -> Relation a

-- | <i>Overlay</i> two graphs. This is a commutative, associative and
--   idempotent operation with the identity <a>empty</a>. Complexity:
--   <i>O((n + m) * log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   <a>isEmpty</a>     (overlay x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (overlay x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (overlay x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (overlay x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (overlay x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (overlay x y) &lt;= <a>edgeCount</a> x   + <a>edgeCount</a> y
--   <a>vertexCount</a> (overlay 1 2) == 2
--   <a>edgeCount</a>   (overlay 1 2) == 0
--   </pre>
overlay :: Ord a => Relation a -> Relation a -> Relation a

-- | <i>Connect</i> two graphs. This is an associative operation with the
--   identity <a>empty</a>, which distributes over <a>overlay</a> and obeys
--   the decomposition axiom. Complexity: <i>O((n + m) * log(n))</i> time
--   and <i>O(n + m)</i> memory. Note that the number of edges in the
--   resulting graph is quadratic with respect to the number of vertices of
--   the arguments: <i>m = O(m1 + m2 + n1 * n2)</i>.
--   
--   <pre>
--   <a>isEmpty</a>     (connect x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (connect x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (connect x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (connect x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &lt;= <a>vertexCount</a> x * <a>vertexCount</a> y + <a>edgeCount</a> x + <a>edgeCount</a> y
--   <a>vertexCount</a> (connect 1 2) == 2
--   <a>edgeCount</a>   (connect 1 2) == 1
--   </pre>
connect :: Ord a => Relation a -> Relation a -> Relation a

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L * log(L))</i> time and <i>O(L)</i> memory, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   vertices []            == <a>empty</a>
--   vertices [x]           == <a>vertex</a> x
--   <a>hasVertex</a> x . vertices == <a>elem</a> x
--   <a>vertexCount</a> . vertices == <a>length</a> . <a>nub</a>
--   <a>vertexSet</a>   . vertices == Set.<a>fromList</a>
--   </pre>
vertices :: Ord a => [a] -> Relation a

-- | Construct the graph from a list of edges. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   edges []          == <a>empty</a>
--   edges [(x,y)]     == <a>edge</a> x y
--   <a>edgeCount</a> . edges == <a>length</a> . <a>nub</a>
--   </pre>
edges :: Ord a => [(a, a)] -> Relation a

-- | Overlay a given list of graphs. Complexity: <i>O((n + m) * log(n))</i>
--   time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   overlays []        == <a>empty</a>
--   overlays [x]       == x
--   overlays [x,y]     == <a>overlay</a> x y
--   overlays           == <a>foldr</a> <a>overlay</a> <a>empty</a>
--   <a>isEmpty</a> . overlays == <a>all</a> <a>isEmpty</a>
--   </pre>
overlays :: Ord a => [Relation a] -> Relation a

-- | Connect a given list of graphs. Complexity: <i>O((n + m) * log(n))</i>
--   time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   connects []        == <a>empty</a>
--   connects [x]       == x
--   connects [x,y]     == <a>connect</a> x y
--   connects           == <a>foldr</a> <a>connect</a> <a>empty</a>
--   <a>isEmpty</a> . connects == <a>all</a> <a>isEmpty</a>
--   </pre>
connects :: Ord a => [Relation a] -> Relation a

-- | Construct a graph from an adjacency list. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   fromAdjacencyList []                                  == <a>empty</a>
--   fromAdjacencyList [(x, [])]                           == <a>vertex</a> x
--   fromAdjacencyList [(x, [y])]                          == <a>edge</a> x y
--   <a>overlay</a> (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys)
--   </pre>
fromAdjacencyList :: Ord a => [(a, [a])] -> Relation a

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Complexity: <i>O((n + m) * log(n))</i> time.
--   
--   <pre>
--   isSubgraphOf <a>empty</a>         x             == True
--   isSubgraphOf (<a>vertex</a> x)    <a>empty</a>         == False
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path</a> xs)     (<a>circuit</a> xs)  == True
--   </pre>
isSubgraphOf :: Ord a => Relation a -> Relation a -> Bool

-- | Check if a relation is empty. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   isEmpty <a>empty</a>                       == True
--   isEmpty (<a>overlay</a> <a>empty</a> <a>empty</a>)       == True
--   isEmpty (<a>vertex</a> x)                  == False
--   isEmpty (<a>removeVertex</a> x $ <a>vertex</a> x) == True
--   isEmpty (<a>removeEdge</a> x y $ <a>edge</a> x y) == False
--   </pre>
isEmpty :: Relation a -> Bool

-- | Check if a graph contains a given vertex. Complexity: <i>O(log(n))</i>
--   time.
--   
--   <pre>
--   hasVertex x <a>empty</a>            == False
--   hasVertex x (<a>vertex</a> x)       == True
--   hasVertex 1 (<a>vertex</a> 2)       == False
--   hasVertex x . <a>removeVertex</a> x == const False
--   </pre>
hasVertex :: Ord a => a -> Relation a -> Bool

-- | Check if a graph contains a given edge. Complexity: <i>O(log(n))</i>
--   time.
--   
--   <pre>
--   hasEdge x y <a>empty</a>            == False
--   hasEdge x y (<a>vertex</a> z)       == False
--   hasEdge x y (<a>edge</a> x y)       == True
--   hasEdge x y . <a>removeEdge</a> x y == const False
--   hasEdge x y                  == <a>elem</a> (x,y) . <a>edgeList</a>
--   </pre>
hasEdge :: Ord a => a -> a -> Relation a -> Bool

-- | The number of vertices in a graph. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   vertexCount <a>empty</a>      == 0
--   vertexCount (<a>vertex</a> x) == 1
--   vertexCount            == <a>length</a> . <a>vertexList</a>
--   </pre>
vertexCount :: Relation a -> Int

-- | The number of edges in a graph. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   edgeCount <a>empty</a>      == 0
--   edgeCount (<a>vertex</a> x) == 0
--   edgeCount (<a>edge</a> x y) == 1
--   edgeCount            == <a>length</a> . <a>edgeList</a>
--   </pre>
edgeCount :: Relation a -> Int

-- | The sorted list of vertices of a given graph. Complexity: <i>O(n)</i>
--   time and memory.
--   
--   <pre>
--   vertexList <a>empty</a>      == []
--   vertexList (<a>vertex</a> x) == [x]
--   vertexList . <a>vertices</a> == <a>nub</a> . <a>sort</a>
--   </pre>
vertexList :: Relation a -> [a]

-- | The sorted list of edges of a graph. Complexity: <i>O(n + m)</i> time
--   and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeList <a>empty</a>          == []
--   edgeList (<a>vertex</a> x)     == []
--   edgeList (<a>edge</a> x y)     == [(x,y)]
--   edgeList (<a>star</a> 2 [3,1]) == [(2,1), (2,3)]
--   edgeList . <a>edges</a>        == <a>nub</a> . <a>sort</a>
--   edgeList . <a>transpose</a>    == <a>sort</a> . map <a>swap</a> . edgeList
--   </pre>
edgeList :: Relation a -> [(a, a)]

-- | The set of vertices of a given graph. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   vertexSet <a>empty</a>      == Set.<a>empty</a>
--   vertexSet . <a>vertex</a>   == Set.<a>singleton</a>
--   vertexSet . <a>vertices</a> == Set.<a>fromList</a>
--   vertexSet . <a>clique</a>   == Set.<a>fromList</a>
--   </pre>
vertexSet :: Relation a -> Set a

-- | The set of vertices of a given graph. Like <a>vertexSet</a> but
--   specialised for graphs with vertices of type <a>Int</a>. Complexity:
--   <i>O(n)</i> time.
--   
--   <pre>
--   vertexIntSet <a>empty</a>      == IntSet.<a>empty</a>
--   vertexIntSet . <a>vertex</a>   == IntSet.<a>singleton</a>
--   vertexIntSet . <a>vertices</a> == IntSet.<a>fromList</a>
--   vertexIntSet . <a>clique</a>   == IntSet.<a>fromList</a>
--   </pre>
vertexIntSet :: Relation Int -> IntSet

-- | The set of edges of a given graph. Complexity: <i>O(1)</i> time.
--   
--   <pre>
--   edgeSet <a>empty</a>      == Set.<a>empty</a>
--   edgeSet (<a>vertex</a> x) == Set.<a>empty</a>
--   edgeSet (<a>edge</a> x y) == Set.<a>singleton</a> (x,y)
--   edgeSet . <a>edges</a>    == Set.<a>fromList</a>
--   </pre>
edgeSet :: Relation a -> Set (a, a)

-- | The <i>preset</i> (here <a>preSet</a>) of an element <tt>x</tt> is the
--   set of elements that are related to it on the <i>left</i>, i.e.
--   <tt>preSet x == { a | aRx }</tt>. In the context of directed graphs,
--   this corresponds to the set of <i>direct predecessors</i> of vertex
--   <tt>x</tt>. Complexity: <i>O(n + m)</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   preSet x <a>empty</a>      == Set.<a>empty</a>
--   preSet x (<a>vertex</a> x) == Set.<a>empty</a>
--   preSet 1 (<a>edge</a> 1 2) == Set.<a>empty</a>
--   preSet y (<a>edge</a> x y) == Set.<a>fromList</a> [x]
--   </pre>
preSet :: Ord a => a -> Relation a -> Set a

-- | The <i>postset</i> (here <a>postSet</a>) of an element <tt>x</tt> is
--   the set of elements that are related to it on the <i>right</i>, i.e.
--   <tt>postSet x == { a | xRa }</tt>. In the context of directed graphs,
--   this corresponds to the set of <i>direct successors</i> of vertex
--   <tt>x</tt>. Complexity: <i>O(n + m)</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   postSet x <a>empty</a>      == Set.<a>empty</a>
--   postSet x (<a>vertex</a> x) == Set.<a>empty</a>
--   postSet x (<a>edge</a> x y) == Set.<a>fromList</a> [y]
--   postSet 2 (<a>edge</a> 1 2) == Set.<a>empty</a>
--   </pre>
postSet :: Ord a => a -> Relation a -> Set a

-- | The <i>path</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   path []        == <a>empty</a>
--   path [x]       == <a>vertex</a> x
--   path [x,y]     == <a>edge</a> x y
--   path . <a>reverse</a> == <a>transpose</a> . path
--   </pre>
path :: Ord a => [a] -> Relation a

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   circuit []        == <a>empty</a>
--   circuit [x]       == <a>edge</a> x x
--   circuit [x,y]     == <a>edges</a> [(x,y), (y,x)]
--   circuit . <a>reverse</a> == <a>transpose</a> . circuit
--   </pre>
circuit :: Ord a => [a] -> Relation a

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O((n + m) *
--   log(n))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   clique []         == <a>empty</a>
--   clique [x]        == <a>vertex</a> x
--   clique [x,y]      == <a>edge</a> x y
--   clique [x,y,z]    == <a>edges</a> [(x,y), (x,z), (y,z)]
--   clique (xs ++ ys) == <a>connect</a> (clique xs) (clique ys)
--   clique . <a>reverse</a>  == <a>transpose</a> . clique
--   </pre>
clique :: Ord a => [a] -> Relation a

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(n *
--   log(n) + m)</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   biclique []      []      == <a>empty</a>
--   biclique [x]     []      == <a>vertex</a> x
--   biclique []      [y]     == <a>vertex</a> y
--   biclique [x1,x2] [y1,y2] == <a>edges</a> [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
--   biclique xs      ys      == <a>connect</a> (<a>vertices</a> xs) (<a>vertices</a> ys)
--   </pre>
biclique :: Ord a => [a] -> [a] -> Relation a

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges</a> [(x,y), (x,z)]
--   star x ys    == <a>connect</a> (<a>vertex</a> x) (<a>vertices</a> ys)
--   </pre>
star :: Ord a => a -> [a] -> Relation a

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges</a> [(y,x), (z,x)]
--   starTranspose x ys    == <a>connect</a> (<a>vertices</a> ys) (<a>vertex</a> x)
--   starTranspose x ys    == <a>transpose</a> (<a>star</a> x ys)
--   </pre>
starTranspose :: Ord a => a -> [a] -> Relation a

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path</a> [x,y,z]
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges</a> [(1,2), (1,3), (3,4), (3,5)]
--   </pre>
tree :: Ord a => Tree a -> Relation a

-- | The <i>forest graph</i> constructed from a given <a>Forest</a> data
--   structure. Complexity: <i>O((n + m) * log(n))</i> time and <i>O(n +
--   m)</i> memory.
--   
--   <pre>
--   forest []                                                  == <a>empty</a>
--   forest [x]                                                 == <a>tree</a> x
--   forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == <a>edges</a> [(1,2), (1,3), (4,5)]
--   forest                                                     == <a>overlays</a> . map <a>tree</a>
--   </pre>
forest :: Ord a => Forest a -> Relation a

-- | Remove a vertex from a given graph. Complexity: <i>O(n + m)</i> time.
--   
--   <pre>
--   removeVertex x (<a>vertex</a> x)       == <a>empty</a>
--   removeVertex 1 (<a>vertex</a> 2)       == <a>vertex</a> 2
--   removeVertex x (<a>edge</a> x x)       == <a>empty</a>
--   removeVertex 1 (<a>edge</a> 1 2)       == <a>vertex</a> 2
--   removeVertex x . removeVertex x == removeVertex x
--   </pre>
removeVertex :: Ord a => a -> Relation a -> Relation a

-- | Remove an edge from a given graph. Complexity: <i>O(log(m))</i> time.
--   
--   <pre>
--   removeEdge x y (<a>edge</a> x y)       == <a>vertices</a> [x, y]
--   removeEdge x y . removeEdge x y == removeEdge x y
--   removeEdge x y . <a>removeVertex</a> x == <a>removeVertex</a> x
--   removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
--   removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2
--   </pre>
removeEdge :: Ord a => a -> a -> Relation a -> Relation a

-- | The function <tt><a>replaceVertex</a> x y</tt> replaces vertex
--   <tt>x</tt> with vertex <tt>y</tt> in a given <tt>AdjacencyMap</tt>. If
--   <tt>y</tt> already exists, <tt>x</tt> and <tt>y</tt> will be merged.
--   Complexity: <i>O((n + m) * log(n))</i> time.
--   
--   <pre>
--   replaceVertex x x            == id
--   replaceVertex x y (<a>vertex</a> x) == <a>vertex</a> y
--   replaceVertex x y            == <a>mergeVertices</a> (== x) y
--   </pre>
replaceVertex :: Ord a => a -> a -> Relation a -> Relation a

-- | Merge vertices satisfying a given predicate into a given vertex.
--   Complexity: <i>O((n + m) * log(n))</i> time, assuming that the
--   predicate takes <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   mergeVertices (const False) x    == id
--   mergeVertices (== x) y           == <a>replaceVertex</a> x y
--   mergeVertices even 1 (0 * 2)     == 1 * 1
--   mergeVertices odd  1 (3 + 4 * 5) == 4 * 1
--   </pre>
mergeVertices :: Ord a => (a -> Bool) -> a -> Relation a -> Relation a

-- | Transpose a given graph. Complexity: <i>O(m * log(m))</i> time.
--   
--   <pre>
--   transpose <a>empty</a>       == <a>empty</a>
--   transpose (<a>vertex</a> x)  == <a>vertex</a> x
--   transpose (<a>edge</a> x y)  == <a>edge</a> y x
--   transpose . transpose == id
--   <a>edgeList</a> . transpose  == <a>sort</a> . map <a>swap</a> . <a>edgeList</a>
--   </pre>
transpose :: Ord a => Relation a -> Relation a

-- | Transform a graph by applying a function to each of its vertices. This
--   is similar to <tt>Functor</tt>'s <a>fmap</a> but can be used with
--   non-fully-parametric <a>Relation</a>. Complexity: <i>O((n + m) *
--   log(n))</i> time.
--   
--   <pre>
--   gmap f <a>empty</a>      == <a>empty</a>
--   gmap f (<a>vertex</a> x) == <a>vertex</a> (f x)
--   gmap f (<a>edge</a> x y) == <a>edge</a> (f x) (f y)
--   gmap id           == id
--   gmap f . gmap g   == gmap (f . g)
--   </pre>
gmap :: Ord b => (a -> b) -> Relation a -> Relation b

-- | Construct the <i>induced subgraph</i> of a given graph by removing the
--   vertices that do not satisfy a given predicate. Complexity:
--   <i>O(m)</i> time, assuming that the predicate takes <i>O(1)</i> to be
--   evaluated.
--   
--   <pre>
--   induce (const True ) x      == x
--   induce (const False) x      == <a>empty</a>
--   induce (/= x)               == <a>removeVertex</a> x
--   induce p . induce q         == induce (\x -&gt; p x &amp;&amp; q x)
--   <a>isSubgraphOf</a> (induce p x) x == True
--   </pre>
induce :: (a -> Bool) -> Relation a -> Relation a

-- | <i>Compose</i> two relations: <tt>R = <a>compose</a> Q P</tt>. Two
--   elements <tt>x</tt> and <tt>y</tt> are related in the resulting
--   relation, i.e. <tt>xRy</tt>, if there exists an element <tt>z</tt>,
--   such that <tt>xPz</tt> and <tt>zQy</tt>. This is an associative
--   operation which has <a>empty</a> as the <i>annihilating zero</i>.
--   Complexity: <i>O(n * m * log(m))</i> time and <i>O(n + m)</i> memory.
--   
--   <pre>
--   compose <a>empty</a>            x                == <a>empty</a>
--   compose x                <a>empty</a>            == <a>empty</a>
--   compose x                (compose y z)    == compose (compose x y) z
--   compose (<a>edge</a> y z)       (<a>edge</a> x y)       == <a>edge</a> x z
--   compose (<a>path</a>    [1..5]) (<a>path</a>    [1..5]) == <a>edges</a> [(1,3),(2,4),(3,5)]
--   compose (<a>circuit</a> [1..5]) (<a>circuit</a> [1..5]) == <a>circuit</a> [1,3,5,2,4]
--   </pre>
compose :: Ord a => Relation a -> Relation a -> Relation a

-- | Compute the <i>reflexive closure</i> of a <a>Relation</a>. Complexity:
--   <i>O(n * log(m))</i> time.
--   
--   <pre>
--   reflexiveClosure <a>empty</a>      == <a>empty</a>
--   reflexiveClosure (<a>vertex</a> x) == <a>edge</a> x x
--   </pre>
reflexiveClosure :: Ord a => Relation a -> Relation a

-- | Compute the <i>symmetric closure</i> of a <a>Relation</a>. Complexity:
--   <i>O(m * log(m))</i> time.
--   
--   <pre>
--   symmetricClosure <a>empty</a>      == <a>empty</a>
--   symmetricClosure (<a>vertex</a> x) == <a>vertex</a> x
--   symmetricClosure (<a>edge</a> x y) == <a>edges</a> [(x, y), (y, x)]
--   </pre>
symmetricClosure :: Ord a => Relation a -> Relation a

-- | Compute the <i>transitive closure</i> of a <a>Relation</a>.
--   Complexity: <i>O(n * m * log(n) * log(m))</i> time.
--   
--   <pre>
--   transitiveClosure <a>empty</a>           == <a>empty</a>
--   transitiveClosure (<a>vertex</a> x)      == <a>vertex</a> x
--   transitiveClosure (<a>path</a> $ <a>nub</a> xs) == <a>clique</a> (<a>nub</a> xs)
--   </pre>
transitiveClosure :: Ord a => Relation a -> Relation a

-- | Compute the <i>preorder closure</i> of a <a>Relation</a>. Complexity:
--   <i>O(n * m * log(m))</i> time.
--   
--   <pre>
--   preorderClosure <a>empty</a>           == <a>empty</a>
--   preorderClosure (<a>vertex</a> x)      == <a>edge</a> x x
--   preorderClosure (<a>path</a> $ <a>nub</a> xs) == <a>reflexiveClosure</a> (<a>clique</a> $ <a>nub</a> xs)
--   </pre>
preorderClosure :: Ord a => Relation a -> Relation a


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the <a>Fold</a> 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. <a>Fold</a> is an instance of type
--   classes defined in modules <a>Algebra.Graph.Class</a> and
--   <a>Algebra.Graph.HigherKinded.Class</a>, which can be used for
--   polymorphic graph construction and manipulation.
module Algebra.Graph.Fold

-- | The <a>Fold</a> data type is the Boehm-Berarducci encoding of the core
--   graph construction primitives <a>empty</a>, <a>vertex</a>,
--   <a>overlay</a> and <a>connect</a>. We define a <a>Num</a> instance as
--   a convenient notation for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Show</a> instance is defined using basic graph construction
--   primitives:
--   
--   <pre>
--   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)"
--   </pre>
--   
--   The <a>Eq</a> instance is currently implemented using the
--   <a>AdjacencyMap</a> as the <i>canonical graph representation</i> and
--   satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> will denote the number of vertices in the graph, <i>m</i>
--   will denote the number of edges in the graph, and <i>s</i> will denote
--   the <i>size</i> of the corresponding graph expression. For example, if
--   g is a <a>Fold</a> then <i>n</i>, <i>m</i> and <i>s</i> can be
--   computed as follows:
--   
--   <pre>
--   n == <a>vertexCount</a> g
--   m == <a>edgeCount</a> g
--   s == <a>size</a> g
--   </pre>
--   
--   Note that <a>size</a> is slightly different from the <a>length</a>
--   method of the <a>Foldable</a> type class, as the latter does not count
--   <a>empty</a> leaves of the expression:
--   
--   <pre>
--   <a>length</a> <a>empty</a>           == 0
--   <a>size</a>   <a>empty</a>           == 1
--   <a>length</a> (<a>vertex</a> x)      == 1
--   <a>size</a>   (<a>vertex</a> x)      == 1
--   <a>length</a> (<a>empty</a> + <a>empty</a>) == 0
--   <a>size</a>   (<a>empty</a> + <a>empty</a>) == 2
--   </pre>
--   
--   The <a>size</a> of any graph is positive, and the difference
--   <tt>(<a>size</a> g - <a>length</a> g)</tt> corresponds to the number
--   of occurrences of <a>empty</a> in an expression <tt>g</tt>.
--   
--   Converting a <a>Fold</a> to the corresponding <a>AdjacencyMap</a>
--   takes <i>O(s + m * log(m))</i> time and <i>O(s + m)</i> 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 <i>empty graph</i>. Complexity: <i>O(1)</i> time, memory
--   and size.
--   
--   <pre>
--   <a>isEmpty</a>     empty == True
--   <a>hasVertex</a> x empty == False
--   <a>vertexCount</a> empty == 0
--   <a>edgeCount</a>   empty == 0
--   <a>size</a>        empty == 1
--   </pre>
empty :: Graph g => g

-- | Construct the graph comprising <i>a single isolated vertex</i>.
--   Complexity: <i>O(1)</i> time, memory and size.
--   
--   <pre>
--   <a>isEmpty</a>     (vertex x) == False
--   <a>hasVertex</a> x (vertex x) == True
--   <a>vertexCount</a> (vertex x) == 1
--   <a>edgeCount</a>   (vertex x) == 0
--   <a>size</a>        (vertex x) == 1
--   </pre>
vertex :: Graph g => Vertex g -> g

-- | Construct the graph comprising <i>a single edge</i>. Complexity:
--   <i>O(1)</i> time, memory and size.
--   
--   <pre>
--   edge x y               == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   <a>hasEdge</a> x y (edge x y) == True
--   <a>edgeCount</a>   (edge x y) == 1
--   <a>vertexCount</a> (edge 1 1) == 1
--   <a>vertexCount</a> (edge 1 2) == 2
--   </pre>
edge :: Graph g => Vertex g -> Vertex g -> g

-- | <i>Overlay</i> two graphs. This is a commutative, associative and
--   idempotent operation with the identity <a>empty</a>. Complexity:
--   <i>O(1)</i> time and memory, <i>O(s1 + s2)</i> size.
--   
--   <pre>
--   <a>isEmpty</a>     (overlay x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (overlay x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (overlay x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (overlay x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (overlay x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (overlay x y) &lt;= <a>edgeCount</a> x   + <a>edgeCount</a> y
--   <a>size</a>        (overlay x y) == <a>size</a> x        + <a>size</a> y
--   <a>vertexCount</a> (overlay 1 2) == 2
--   <a>edgeCount</a>   (overlay 1 2) == 0
--   </pre>
overlay :: Graph g => g -> g -> g

-- | <i>Connect</i> two graphs. This is an associative operation with the
--   identity <a>empty</a>, which distributes over <a>overlay</a> and obeys
--   the decomposition axiom. Complexity: <i>O(1)</i> time and memory,
--   <i>O(s1 + s2)</i> size. Note that the number of edges in the resulting
--   graph is quadratic with respect to the number of vertices of the
--   arguments: <i>m = O(m1 + m2 + n1 * n2)</i>.
--   
--   <pre>
--   <a>isEmpty</a>     (connect x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (connect x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (connect x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (connect x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &lt;= <a>vertexCount</a> x * <a>vertexCount</a> y + <a>edgeCount</a> x + <a>edgeCount</a> y
--   <a>size</a>        (connect x y) == <a>size</a> x        + <a>size</a> y
--   <a>vertexCount</a> (connect 1 2) == 2
--   <a>edgeCount</a>   (connect 1 2) == 1
--   </pre>
connect :: Graph g => g -> g -> g

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L)</i> time, memory and size, where <i>L</i> is the
--   length of the given list.
--   
--   <pre>
--   vertices []            == <a>empty</a>
--   vertices [x]           == <a>vertex</a> x
--   <a>hasVertex</a> x . vertices == <a>elem</a> x
--   <a>vertexCount</a> . vertices == <a>length</a> . <a>nub</a>
--   <a>vertexSet</a>   . vertices == Set.<a>fromList</a>
--   </pre>
vertices :: Graph g => [Vertex g] -> g

-- | Construct the graph from a list of edges. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   edges []          == <a>empty</a>
--   edges [(x,y)]     == <a>edge</a> x y
--   <a>edgeCount</a> . edges == <a>length</a> . <a>nub</a>
--   </pre>
edges :: Graph g => [(Vertex g, Vertex g)] -> g

-- | Overlay a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   overlays []        == <a>empty</a>
--   overlays [x]       == x
--   overlays [x,y]     == <a>overlay</a> x y
--   overlays           == <a>foldr</a> <a>overlay</a> <a>empty</a>
--   <a>isEmpty</a> . overlays == <a>all</a> <a>isEmpty</a>
--   </pre>
overlays :: Graph g => [g] -> g

-- | Connect a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   connects []        == <a>empty</a>
--   connects [x]       == x
--   connects [x,y]     == <a>connect</a> x y
--   connects           == <a>foldr</a> <a>connect</a> <a>empty</a>
--   <a>isEmpty</a> . connects == <a>all</a> <a>isEmpty</a>
--   </pre>
connects :: Graph g => [g] -> g

-- | Generalised graph folding: recursively collapse a <a>Fold</a> 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: <i>O(s)</i> applications of given functions. As
--   an example, the complexity of <a>size</a> is <i>O(s)</i>, since all
--   functions have cost <i>O(1)</i>.
--   
--   <pre>
--   foldg <a>empty</a> <a>vertex</a>        <a>overlay</a> <a>connect</a>        == id
--   foldg <a>empty</a> <a>vertex</a>        <a>overlay</a> (flip <a>connect</a>) == <a>transpose</a>
--   foldg []    return        (++)    (++)           == <a>toList</a>
--   foldg 0     (const 1)     (+)     (+)            == <a>length</a>
--   foldg 1     (const 1)     (+)     (+)            == <a>size</a>
--   foldg True  (const False) (&amp;&amp;)    (&amp;&amp;)           == <a>isEmpty</a>
--   </pre>
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold a -> b

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Here is the current implementation:
--   
--   <pre>
--   isSubgraphOf x y = <a>overlay</a> x y == y
--   </pre>
--   
--   The complexity therefore depends on the complexity of equality testing
--   of the specific graph instance.
--   
--   <pre>
--   isSubgraphOf <a>empty</a>         x             == True
--   isSubgraphOf (<a>vertex</a> x)    <a>empty</a>         == False
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path</a> xs)     (<a>circuit</a> xs)  == True
--   </pre>
isSubgraphOf :: (Graph g, Eq g) => g -> g -> Bool

-- | Check if a graph is empty. A convenient alias for <a>null</a>.
--   Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   isEmpty <a>empty</a>                       == True
--   isEmpty (<a>overlay</a> <a>empty</a> <a>empty</a>)       == True
--   isEmpty (<a>vertex</a> x)                  == False
--   isEmpty (<a>removeVertex</a> x $ <a>vertex</a> x) == True
--   isEmpty (<a>removeEdge</a> x y $ <a>edge</a> x y) == False
--   </pre>
isEmpty :: Fold a -> Bool

-- | The <i>size</i> of a graph, i.e. the number of leaves of the
--   expression including <a>empty</a> leaves. Complexity: <i>O(s)</i>
--   time.
--   
--   <pre>
--   size <a>empty</a>         == 1
--   size (<a>vertex</a> x)    == 1
--   size (<a>overlay</a> x y) == size x + size y
--   size (<a>connect</a> x y) == size x + size y
--   size x             &gt;= 1
--   size x             &gt;= <a>vertexCount</a> x
--   </pre>
size :: Fold a -> Int

-- | Check if a graph contains a given vertex. A convenient alias for
--   <a>elem</a>. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasVertex x <a>empty</a>            == False
--   hasVertex x (<a>vertex</a> x)       == True
--   hasVertex 1 (<a>vertex</a> 2)       == False
--   hasVertex x . <a>removeVertex</a> x == const False
--   </pre>
hasVertex :: Eq a => a -> Fold a -> Bool

-- | Check if a graph contains a given edge. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasEdge x y <a>empty</a>            == False
--   hasEdge x y (<a>vertex</a> z)       == False
--   hasEdge x y (<a>edge</a> x y)       == True
--   hasEdge x y . <a>removeEdge</a> x y == const False
--   hasEdge x y                  == <a>elem</a> (x,y) . <a>edgeList</a>
--   </pre>
hasEdge :: Ord a => a -> a -> Fold a -> Bool

-- | The number of vertices in a graph. Complexity: <i>O(s * log(n))</i>
--   time.
--   
--   <pre>
--   vertexCount <a>empty</a>      == 0
--   vertexCount (<a>vertex</a> x) == 1
--   vertexCount            == <a>length</a> . <a>vertexList</a>
--   </pre>
vertexCount :: Ord a => Fold a -> Int

-- | The number of edges in a graph. Complexity: <i>O(s + m * log(m))</i>
--   time. Note that the number of edges <i>m</i> of a graph can be
--   quadratic with respect to the expression size <i>s</i>.
--   
--   <pre>
--   edgeCount <a>empty</a>      == 0
--   edgeCount (<a>vertex</a> x) == 0
--   edgeCount (<a>edge</a> x y) == 1
--   edgeCount            == <a>length</a> . <a>edgeList</a>
--   </pre>
edgeCount :: Ord a => Fold a -> Int

-- | The sorted list of vertices of a given graph. Complexity: <i>O(s *
--   log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexList <a>empty</a>      == []
--   vertexList (<a>vertex</a> x) == [x]
--   vertexList . <a>vertices</a> == <a>nub</a> . <a>sort</a>
--   </pre>
vertexList :: Ord a => Fold a -> [a]

-- | The sorted list of edges of a graph. Complexity: <i>O(s + m *
--   log(m))</i> time and <i>O(m)</i> memory. Note that the number of edges
--   <i>m</i> of a graph can be quadratic with respect to the expression
--   size <i>s</i>.
--   
--   <pre>
--   edgeList <a>empty</a>          == []
--   edgeList (<a>vertex</a> x)     == []
--   edgeList (<a>edge</a> x y)     == [(x,y)]
--   edgeList (<tt>star</tt> 2 [3,1]) == [(2,1), (2,3)]
--   edgeList . <a>edges</a>        == <a>nub</a> . <a>sort</a>
--   edgeList . <a>transpose</a>    == <a>sort</a> . map <a>swap</a> . edgeList
--   </pre>
edgeList :: Ord a => Fold a -> [(a, a)]

-- | The set of vertices of a given graph. Complexity: <i>O(s * log(n))</i>
--   time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexSet <a>empty</a>      == Set.<a>empty</a>
--   vertexSet . <a>vertex</a>   == Set.<a>singleton</a>
--   vertexSet . <a>vertices</a> == Set.<a>fromList</a>
--   vertexSet . <tt>clique</tt>   == Set.<a>fromList</a>
--   </pre>
vertexSet :: Ord a => Fold a -> Set a

-- | The set of vertices of a given graph. Like <a>vertexSet</a> but
--   specialised for graphs with vertices of type <a>Int</a>. Complexity:
--   <i>O(s * log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexIntSet <a>empty</a>      == IntSet.<a>empty</a>
--   vertexIntSet . <a>vertex</a>   == IntSet.<a>singleton</a>
--   vertexIntSet . <a>vertices</a> == IntSet.<a>fromList</a>
--   vertexIntSet . <tt>clique</tt>   == IntSet.<a>fromList</a>
--   </pre>
vertexIntSet :: Fold Int -> IntSet

-- | The set of edges of a given graph. Complexity: <i>O(s * log(m))</i>
--   time and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeSet <a>empty</a>      == Set.<a>empty</a>
--   edgeSet (<a>vertex</a> x) == Set.<a>empty</a>
--   edgeSet (<a>edge</a> x y) == Set.<a>singleton</a> (x,y)
--   edgeSet . <a>edges</a>    == Set.<a>fromList</a>
--   </pre>
edgeSet :: Ord a => Fold a -> Set (a, a)

-- | The <i>path</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   path []    == <a>empty</a>
--   path [x]   == <a>vertex</a> x
--   path [x,y] == <a>edge</a> x y
--   </pre>
path :: Graph g => [Vertex g] -> g

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   circuit []    == <a>empty</a>
--   circuit [x]   == <a>edge</a> x x
--   circuit [x,y] == <a>edges</a> [(x,y), (y,x)]
--   </pre>
circuit :: Graph g => [Vertex g] -> g

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   clique []         == <a>empty</a>
--   clique [x]        == <a>vertex</a> x
--   clique [x,y]      == <a>edge</a> x y
--   clique [x,y,z]    == <a>edges</a> [(x,y), (x,z), (y,z)]
--   clique (xs ++ ys) == <a>connect</a> (clique xs) (clique ys)
--   </pre>
clique :: Graph g => [Vertex g] -> g

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(L1 +
--   L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i> are the
--   lengths of the given lists.
--   
--   <pre>
--   biclique []      []      == <a>empty</a>
--   biclique [x]     []      == <a>vertex</a> x
--   biclique []      [y]     == <a>vertex</a> y
--   biclique [x1,x2] [y1,y2] == <a>edges</a> [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
--   biclique xs      ys      == <a>connect</a> (<a>vertices</a> xs) (<a>vertices</a> ys)
--   </pre>
biclique :: Graph g => [Vertex g] -> [Vertex g] -> g

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O(L)</i> time, memory and size, where <i>L</i>
--   is the length of the given list.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges</a> [(x,y), (x,z)]
--   star x ys    == <a>connect</a> (<a>vertex</a> x) (<a>vertices</a> ys)
--   </pre>
star :: Graph g => Vertex g -> [Vertex g] -> g

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges</a> [(y,x), (z,x)]
--   starTranspose x ys    == <a>connect</a> (<a>vertices</a> ys) (<a>vertex</a> x)
--   starTranspose x ys    == transpose (<a>star</a> x ys)
--   </pre>
starTranspose :: Graph g => Vertex g -> [Vertex g] -> g

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O(T)</i> time, memory and size, where
--   <i>T</i> is the size of the given tree (i.e. the number of vertices in
--   the tree).
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path</a> [x,y,z]
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges</a> [(1,2), (1,3), (3,4), (3,5)]
--   </pre>
tree :: Graph g => Tree (Vertex g) -> g

-- | The <i>forest graph</i> constructed from a given <a>Forest</a> data
--   structure. Complexity: <i>O(F)</i> time, memory and size, where
--   <i>F</i> is the size of the given forest (i.e. the number of vertices
--   in the forest).
--   
--   <pre>
--   forest []                                                  == <a>empty</a>
--   forest [x]                                                 == <a>tree</a> x
--   forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == <a>edges</a> [(1,2), (1,3), (4,5)]
--   forest                                                     == <a>overlays</a> . map <a>tree</a>
--   </pre>
forest :: Graph g => Forest (Vertex g) -> g

-- | Construct a <i>mesh graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   mesh xs     []   == <a>empty</a>
--   mesh []     ys   == <a>empty</a>
--   mesh [x]    [y]  == <a>vertex</a> (x, y)
--   mesh xs     ys   == <a>box</a> (<tt>path</tt> xs) (<tt>path</tt> ys)
--   mesh [1..3] "ab" == <a>edges</a> [ ((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')) ]
--   </pre>
mesh :: (Graph g, Vertex g ~ (a, b)) => [a] -> [b] -> g

-- | Construct a <i>torus graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   torus xs    []   == <a>empty</a>
--   torus []    ys   == <a>empty</a>
--   torus [x]   [y]  == <a>edge</a> (x, y) (x, y)
--   torus xs    ys   == <a>box</a> (<tt>circuit</tt> xs) (<tt>circuit</tt> ys)
--   torus [1,2] "ab" == <a>edges</a> [ ((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')) ]
--   </pre>
torus :: (Graph g, Vertex g ~ (a, b)) => [a] -> [b] -> g

-- | Construct a <i>De Bruijn graph</i> of a given non-negative dimension
--   using symbols from a given alphabet. Complexity: <i>O(A^(D + 1))</i>
--   time, memory and size, where <i>A</i> is the size of the alphabet and
--   <i>D</i> is the dimension of the graph.
--   
--   <pre>
--             deBruijn 0 xs               == <a>edge</a> [] []
--   n &gt; 0 ==&gt; deBruijn n []               == <a>empty</a>
--             deBruijn 1 [0,1]            == <a>edges</a> [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
--             deBruijn 2 "0"              == <a>edge</a> "00" "00"
--             deBruijn 2 "01"             == <a>edges</a> [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
--                                                  , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
--             <a>transpose</a>   (deBruijn n xs) == <a>gmap</a> <a>reverse</a> $ deBruijn n xs
--             <a>vertexCount</a> (deBruijn n xs) == (<a>length</a> $ <a>nub</a> xs)^n
--   n &gt; 0 ==&gt; <a>edgeCount</a>   (deBruijn n xs) == (<a>length</a> $ <a>nub</a> xs)^(n + 1)
--   </pre>
deBruijn :: (Graph g, Vertex g ~ [a]) => Int -> [a] -> g

-- | Remove a vertex from a given graph. Complexity: <i>O(s)</i> time,
--   memory and size.
--   
--   <pre>
--   removeVertex x (<a>vertex</a> x)       == <a>empty</a>
--   removeVertex 1 (<a>vertex</a> 2)       == <a>vertex</a> 2
--   removeVertex x (<a>edge</a> x x)       == <a>empty</a>
--   removeVertex 1 (<a>edge</a> 1 2)       == <a>vertex</a> 2
--   removeVertex x . removeVertex x == removeVertex x
--   </pre>
removeVertex :: (Eq (Vertex g), Graph g) => Vertex g -> Fold (Vertex g) -> g

-- | Remove an edge from a given graph. Complexity: <i>O(s)</i> time,
--   memory and size.
--   
--   <pre>
--   removeEdge x y (<a>edge</a> x y)       == <a>vertices</a> [x, y]
--   removeEdge x y . removeEdge x y == removeEdge x y
--   removeEdge x y . <a>removeVertex</a> x == <a>removeVertex</a> x
--   removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
--   removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2
--   <a>size</a> (removeEdge x y z)         &lt;= 3 * <a>size</a> z
--   </pre>
removeEdge :: (Eq (Vertex g), Graph g) => Vertex g -> Vertex g -> Fold (Vertex g) -> g

-- | The function <tt><a>replaceVertex</a> x y</tt> replaces vertex
--   <tt>x</tt> with vertex <tt>y</tt> in a given graph expression. If
--   <tt>y</tt> already exists, <tt>x</tt> and <tt>y</tt> will be merged.
--   Complexity: <i>O(s)</i> time, memory and size.
--   
--   <pre>
--   replaceVertex x x            == id
--   replaceVertex x y (<a>vertex</a> x) == <a>vertex</a> y
--   replaceVertex x y            == <a>mergeVertices</a> (== x) y
--   </pre>
replaceVertex :: (Eq (Vertex g), Graph g) => Vertex g -> Vertex g -> Fold (Vertex g) -> g

-- | Merge vertices satisfying a given predicate into a given vertex.
--   Complexity: <i>O(s)</i> time, memory and size, assuming that the
--   predicate takes <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   mergeVertices (const False) x    == id
--   mergeVertices (== x) y           == <a>replaceVertex</a> x y
--   mergeVertices even 1 (0 * 2)     == 1 * 1
--   mergeVertices odd  1 (3 + 4 * 5) == 4 * 1
--   </pre>
mergeVertices :: Graph g => (Vertex g -> Bool) -> Vertex g -> Fold (Vertex g) -> g

-- | Split a vertex into a list of vertices with the same connectivity.
--   Complexity: <i>O(s + k * L)</i> time, memory and size, where <i>k</i>
--   is the number of occurrences of the vertex in the expression and
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   splitVertex x []                  == <a>removeVertex</a> x
--   splitVertex x [x]                 == id
--   splitVertex x [y]                 == <a>replaceVertex</a> x y
--   splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
--   </pre>
splitVertex :: (Eq (Vertex g), Graph g) => Vertex g -> [Vertex g] -> Fold (Vertex g) -> g

-- | Transpose a given graph. Complexity: <i>O(s)</i> time, memory and
--   size.
--   
--   <pre>
--   transpose <a>empty</a>       == <a>empty</a>
--   transpose (<a>vertex</a> x)  == <a>vertex</a> x
--   transpose (<a>edge</a> x y)  == <a>edge</a> y x
--   transpose . transpose == id
--   transpose (<a>box</a> x y)   == <a>box</a> (transpose x) (transpose y)
--   <a>edgeList</a> . transpose  == <a>sort</a> . map <a>swap</a> . <a>edgeList</a>
--   </pre>
transpose :: Graph g => Fold (Vertex g) -> g

-- | Transform a given graph by applying a function to each of its
--   vertices. This is similar to <a>fmap</a> but can be used with
--   non-fully-parametric graphs.
--   
--   <pre>
--   gmap f <a>empty</a>      == <a>empty</a>
--   gmap f (<a>vertex</a> x) == <a>vertex</a> (f x)
--   gmap f (<a>edge</a> x y) == <a>edge</a> (f x) (f y)
--   gmap id           == id
--   gmap f . gmap g   == gmap (f . g)
--   </pre>
gmap :: Graph g => (a -> Vertex g) -> Fold a -> g

-- | Transform a given graph by substituting each of its vertices with a
--   subgraph. This is similar to Monad's bind <a>&gt;&gt;=</a> but can be
--   used with non-fully-parametric graphs.
--   
--   <pre>
--   bind <a>empty</a> f         == <a>empty</a>
--   bind (<a>vertex</a> x) f    == f x
--   bind (<a>edge</a> x y) f    == <a>connect</a> (f x) (f y)
--   bind (<a>vertices</a> xs) f == <a>overlays</a> (<a>map</a> f xs)
--   bind x (const <a>empty</a>) == <a>empty</a>
--   bind x <a>vertex</a>        == x
--   bind (bind x f) g    == bind x (\y -&gt; bind (f y) g)
--   </pre>
bind :: Graph g => Fold a -> (a -> g) -> g

-- | Construct the <i>induced subgraph</i> of a given graph by removing the
--   vertices that do not satisfy a given predicate. Complexity:
--   <i>O(s)</i> time, memory and size, assuming that the predicate takes
--   <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   induce (const True ) x      == x
--   induce (const False) x      == <a>empty</a>
--   induce (/= x)               == <a>removeVertex</a> x
--   induce p . induce q         == induce (\x -&gt; p x &amp;&amp; q x)
--   <tt>isSubgraphOf</tt> (induce p x) x == True
--   </pre>
induce :: Graph g => (Vertex g -> Bool) -> Fold (Vertex g) -> g

-- | 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
--   <i>O(s)</i> graph comparisons. It is guaranteed that the size of the
--   result does not exceed the size of the given expression. Below the
--   operator <tt>~&gt;</tt> denotes the <i>is simplified to</i> relation.
--   
--   <pre>
--   simplify             == id
--   <a>size</a> (simplify x)    &lt;= <a>size</a> x
--   simplify <a>empty</a>       ~&gt; <a>empty</a>
--   simplify 1           ~&gt; 1
--   simplify (1 + 1)     ~&gt; 1
--   simplify (1 + 2 + 1) ~&gt; 1 + 2
--   simplify (1 * 1 * 1) ~&gt; 1 * 1
--   </pre>
simplify :: (Eq g, Graph g) => Fold (Vertex g) -> g

-- | Compute the <i>Cartesian product</i> of graphs. Complexity: <i>O(s1 *
--   s2)</i> time, memory and size, where <i>s1</i> and <i>s2</i> are the
--   sizes of the given graphs.
--   
--   <pre>
--   box (<tt>path</tt> [0,1]) (<tt>path</tt> "ab") == <a>edges</a> [ ((0,'a'), (0,'b'))
--                                         , ((0,'a'), (1,'a'))
--                                         , ((0,'b'), (1,'b'))
--                                         , ((1,'a'), (1,'b')) ]
--   </pre>
--   
--   Up to an isomorphism between the resulting vertex types, this
--   operation is <i>commutative</i>, <i>associative</i>,
--   <i>distributes</i> over <a>overlay</a>, has singleton graphs as
--   <i>identities</i> and <a>empty</a> as the <i>annihilating zero</i>.
--   Below <tt>~~</tt> stands for the equality up to an isomorphism, e.g.
--   <tt>(x, ()) ~~ x</tt>.
--   
--   <pre>
--   box x y               ~~ box y x
--   box x (box y z)       ~~ box (box x y) z
--   box x (<a>overlay</a> y z)   == <a>overlay</a> (box x y) (box x z)
--   box x (<a>vertex</a> ())     ~~ x
--   box x <a>empty</a>           ~~ <a>empty</a>
--   <a>transpose</a>   (box x y) == box (<a>transpose</a> x) (<a>transpose</a> y)
--   <a>vertexCount</a> (box x y) == <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (box x y) &lt;= <a>vertexCount</a> x * <a>edgeCount</a> y + <a>edgeCount</a> x * <a>vertexCount</a> y
--   </pre>
box :: (Graph g, Vertex g ~ (a, b)) => Fold a -> Fold b -> g
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 Algebra.Graph.Class.Graph (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 Algebra.Graph.HigherKinded.Class.Graph Algebra.Graph.Fold.Fold
instance Data.Foldable.Foldable Algebra.Graph.Fold.Fold
instance Data.Traversable.Traversable Algebra.Graph.Fold.Fold
instance Algebra.Graph.Class.ToGraph (Algebra.Graph.Fold.Fold a)
instance Algebra.Graph.HigherKinded.Class.ToGraph Algebra.Graph.Fold.Fold


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the core data type <a>Graph</a> and associated
--   algorithms. For graphs that are known to be <i>non-empty</i> at
--   compile time, see <a>Algebra.Graph.NonEmpty</a>. <a>Graph</a> is an
--   instance of type classes defined in modules <a>Algebra.Graph.Class</a>
--   and <a>Algebra.Graph.HigherKinded.Class</a>, which can be used for
--   polymorphic graph construction and manipulation.
module Algebra.Graph

-- | The <a>Graph</a> data type is a deep embedding of the core graph
--   construction primitives <a>empty</a>, <a>vertex</a>, <a>overlay</a>
--   and <a>connect</a>. We define a <a>Num</a> instance as a convenient
--   notation for working with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   The <a>Eq</a> instance is currently implemented using the
--   <a>AdjacencyMap</a> as the <i>canonical graph representation</i> and
--   satisfies all axioms of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative and associative:<pre> x + y == y + x
--   x + (y + z) == (x + y) + z</pre></li>
--   <li><a>connect</a> is associative and has <a>empty</a> as the
--   identity:<pre> x * empty == x empty * x == x x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   </ul>
--   
--   The following useful theorems can be proved from the above set of
--   axioms.
--   
--   <ul>
--   <li><a>overlay</a> has <a>empty</a> as the identity and is
--   idempotent:<pre> x + empty == x empty + x == x x + x == x</pre></li>
--   <li>Absorption and saturation of <a>connect</a>:<pre>x * y + x + y ==
--   x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> will denote the number of vertices in the graph, <i>m</i>
--   will denote the number of edges in the graph, and <i>s</i> will denote
--   the <i>size</i> of the corresponding <a>Graph</a> expression. For
--   example, if <tt>g</tt> is a <a>Graph</a> then <i>n</i>, <i>m</i> and
--   <i>s</i> can be computed as follows:
--   
--   <pre>
--   n == <a>vertexCount</a> g
--   m == <a>edgeCount</a> g
--   s == <a>size</a> g
--   </pre>
--   
--   Note that <a>size</a> is slightly different from the <a>length</a>
--   method of the <a>Foldable</a> type class, as the latter does not count
--   <a>empty</a> leaves of the expression:
--   
--   <pre>
--   <a>length</a> <a>empty</a>           == 0
--   <a>size</a>   <a>empty</a>           == 1
--   <a>length</a> (<a>vertex</a> x)      == 1
--   <a>size</a>   (<a>vertex</a> x)      == 1
--   <a>length</a> (<a>empty</a> + <a>empty</a>) == 0
--   <a>size</a>   (<a>empty</a> + <a>empty</a>) == 2
--   </pre>
--   
--   The <a>size</a> of any graph is positive, and the difference
--   <tt>(<a>size</a> g - <a>length</a> g)</tt> corresponds to the number
--   of occurrences of <a>empty</a> in an expression <tt>g</tt>.
--   
--   Converting a <a>Graph</a> to the corresponding <a>AdjacencyMap</a>
--   takes <i>O(s + m * log(m))</i> time and <i>O(s + m)</i> 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 <i>empty graph</i>. An alias for the constructor
--   <a>Empty</a>. Complexity: <i>O(1)</i> time, memory and size.
--   
--   <pre>
--   <a>isEmpty</a>     empty == True
--   <a>hasVertex</a> x empty == False
--   <a>vertexCount</a> empty == 0
--   <a>edgeCount</a>   empty == 0
--   <a>size</a>        empty == 1
--   </pre>
empty :: Graph a

-- | Construct the graph comprising <i>a single isolated vertex</i>. An
--   alias for the constructor <a>Vertex</a>. Complexity: <i>O(1)</i> time,
--   memory and size.
--   
--   <pre>
--   <a>isEmpty</a>     (vertex x) == False
--   <a>hasVertex</a> x (vertex x) == True
--   <a>vertexCount</a> (vertex x) == 1
--   <a>edgeCount</a>   (vertex x) == 0
--   <a>size</a>        (vertex x) == 1
--   </pre>
vertex :: a -> Graph a

-- | Construct the graph comprising <i>a single edge</i>. Complexity:
--   <i>O(1)</i> time, memory and size.
--   
--   <pre>
--   edge x y               == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   <a>hasEdge</a> x y (edge x y) == True
--   <a>edgeCount</a>   (edge x y) == 1
--   <a>vertexCount</a> (edge 1 1) == 1
--   <a>vertexCount</a> (edge 1 2) == 2
--   </pre>
edge :: a -> a -> Graph a

-- | <i>Overlay</i> two graphs. An alias for the constructor
--   <a>Overlay</a>. This is a commutative, associative and idempotent
--   operation with the identity <a>empty</a>. Complexity: <i>O(1)</i> time
--   and memory, <i>O(s1 + s2)</i> size.
--   
--   <pre>
--   <a>isEmpty</a>     (overlay x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (overlay x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (overlay x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (overlay x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (overlay x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (overlay x y) &lt;= <a>edgeCount</a> x   + <a>edgeCount</a> y
--   <a>size</a>        (overlay x y) == <a>size</a> x        + <a>size</a> y
--   <a>vertexCount</a> (overlay 1 2) == 2
--   <a>edgeCount</a>   (overlay 1 2) == 0
--   </pre>
overlay :: Graph a -> Graph a -> Graph a

-- | <i>Connect</i> two graphs. An alias for the constructor
--   <a>Connect</a>. This is an associative operation with the identity
--   <a>empty</a>, which distributes over <a>overlay</a> and obeys the
--   decomposition axiom. Complexity: <i>O(1)</i> time and memory, <i>O(s1
--   + s2)</i> size. Note that the number of edges in the resulting graph
--   is quadratic with respect to the number of vertices of the arguments:
--   <i>m = O(m1 + m2 + n1 * n2)</i>.
--   
--   <pre>
--   <a>isEmpty</a>     (connect x y) == <a>isEmpty</a>   x   &amp;&amp; <a>isEmpty</a>   y
--   <a>hasVertex</a> z (connect x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (connect x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (connect x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &lt;= <a>vertexCount</a> x * <a>vertexCount</a> y + <a>edgeCount</a> x + <a>edgeCount</a> y
--   <a>size</a>        (connect x y) == <a>size</a> x        + <a>size</a> y
--   <a>vertexCount</a> (connect 1 2) == 2
--   <a>edgeCount</a>   (connect 1 2) == 1
--   </pre>
connect :: Graph a -> Graph a -> Graph a

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L)</i> time, memory and size, where <i>L</i> is the
--   length of the given list.
--   
--   <pre>
--   vertices []            == <a>empty</a>
--   vertices [x]           == <a>vertex</a> x
--   <a>hasVertex</a> x . vertices == <a>elem</a> x
--   <a>vertexCount</a> . vertices == <a>length</a> . <a>nub</a>
--   <a>vertexSet</a>   . vertices == Set.<a>fromList</a>
--   </pre>
vertices :: [a] -> Graph a

-- | Construct the graph from a list of edges. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   edges []          == <a>empty</a>
--   edges [(x,y)]     == <a>edge</a> x y
--   <a>edgeCount</a> . edges == <a>length</a> . <a>nub</a>
--   </pre>
edges :: [(a, a)] -> Graph a

-- | Overlay a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   overlays []        == <a>empty</a>
--   overlays [x]       == x
--   overlays [x,y]     == <a>overlay</a> x y
--   overlays           == <a>foldr</a> <a>overlay</a> <a>empty</a>
--   <a>isEmpty</a> . overlays == <a>all</a> <a>isEmpty</a>
--   </pre>
overlays :: [Graph a] -> Graph a

-- | Connect a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   connects []        == <a>empty</a>
--   connects [x]       == x
--   connects [x,y]     == <a>connect</a> x y
--   connects           == <a>foldr</a> <a>connect</a> <a>empty</a>
--   <a>isEmpty</a> . connects == <a>all</a> <a>isEmpty</a>
--   </pre>
connects :: [Graph a] -> Graph a

-- | Generalised <a>Graph</a> folding: recursively collapse a <a>Graph</a>
--   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: <i>O(s)</i> applications of given functions. As
--   an example, the complexity of <a>size</a> is <i>O(s)</i>, since all
--   functions have cost <i>O(1)</i>.
--   
--   <pre>
--   foldg <a>empty</a> <a>vertex</a>        <a>overlay</a> <a>connect</a>        == id
--   foldg <a>empty</a> <a>vertex</a>        <a>overlay</a> (flip <a>connect</a>) == <a>transpose</a>
--   foldg []    return        (++)    (++)           == <a>toList</a>
--   foldg 0     (const 1)     (+)     (+)            == <a>length</a>
--   foldg 1     (const 1)     (+)     (+)            == <a>size</a>
--   foldg True  (const False) (&amp;&amp;)    (&amp;&amp;)           == <a>isEmpty</a>
--   </pre>
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Complexity: <i>O(s + m * log(m))</i> time. Note that the number of
--   edges <i>m</i> of a graph can be quadratic with respect to the
--   expression size <i>s</i>.
--   
--   <pre>
--   isSubgraphOf <a>empty</a>         x             == True
--   isSubgraphOf (<a>vertex</a> x)    <a>empty</a>         == False
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path</a> xs)     (<a>circuit</a> xs)  == True
--   </pre>
isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool

-- | Structural equality on graph expressions. Complexity: <i>O(s)</i>
--   time.
--   
--   <pre>
--       x === x         == True
--       x === x + <a>empty</a> == False
--   x + y === x + y     == True
--   1 + 2 === 2 + 1     == False
--   x + y === x * y     == False
--   </pre>
(===) :: Eq a => Graph a -> Graph a -> Bool
infix 4 ===

-- | Check if a graph is empty. A convenient alias for <a>null</a>.
--   Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   isEmpty <a>empty</a>                       == True
--   isEmpty (<a>overlay</a> <a>empty</a> <a>empty</a>)       == True
--   isEmpty (<a>vertex</a> x)                  == False
--   isEmpty (<a>removeVertex</a> x $ <a>vertex</a> x) == True
--   isEmpty (<a>removeEdge</a> x y $ <a>edge</a> x y) == False
--   </pre>
isEmpty :: Graph a -> Bool

-- | The <i>size</i> of a graph, i.e. the number of leaves of the
--   expression including <a>empty</a> leaves. Complexity: <i>O(s)</i>
--   time.
--   
--   <pre>
--   size <a>empty</a>         == 1
--   size (<a>vertex</a> x)    == 1
--   size (<a>overlay</a> x y) == size x + size y
--   size (<a>connect</a> x y) == size x + size y
--   size x             &gt;= 1
--   size x             &gt;= <a>vertexCount</a> x
--   </pre>
size :: Graph a -> Int

-- | Check if a graph contains a given vertex. A convenient alias for
--   <a>elem</a>. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasVertex x <a>empty</a>            == False
--   hasVertex x (<a>vertex</a> x)       == True
--   hasVertex 1 (<a>vertex</a> 2)       == False
--   hasVertex x . <a>removeVertex</a> x == const False
--   </pre>
hasVertex :: Eq a => a -> Graph a -> Bool

-- | Check if a graph contains a given edge. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasEdge x y <a>empty</a>            == False
--   hasEdge x y (<a>vertex</a> z)       == False
--   hasEdge x y (<a>edge</a> x y)       == True
--   hasEdge x y . <a>removeEdge</a> x y == const False
--   hasEdge x y                  == <a>elem</a> (x,y) . <a>edgeList</a>
--   </pre>
hasEdge :: Ord a => a -> a -> Graph a -> Bool

-- | The number of vertices in a graph. Complexity: <i>O(s * log(n))</i>
--   time.
--   
--   <pre>
--   vertexCount <a>empty</a>      == 0
--   vertexCount (<a>vertex</a> x) == 1
--   vertexCount            == <a>length</a> . <a>vertexList</a>
--   </pre>
vertexCount :: Ord a => Graph a -> Int

-- | The number of edges in a graph. Complexity: <i>O(s + m * log(m))</i>
--   time. Note that the number of edges <i>m</i> of a graph can be
--   quadratic with respect to the expression size <i>s</i>.
--   
--   <pre>
--   edgeCount <a>empty</a>      == 0
--   edgeCount (<a>vertex</a> x) == 0
--   edgeCount (<a>edge</a> x y) == 1
--   edgeCount            == <a>length</a> . <a>edgeList</a>
--   </pre>
edgeCount :: Ord a => Graph a -> Int

-- | The sorted list of vertices of a given graph. Complexity: <i>O(s *
--   log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexList <a>empty</a>      == []
--   vertexList (<a>vertex</a> x) == [x]
--   vertexList . <a>vertices</a> == <a>nub</a> . <a>sort</a>
--   </pre>
vertexList :: Ord a => Graph a -> [a]

-- | The sorted list of edges of a graph. Complexity: <i>O(s + m *
--   log(m))</i> time and <i>O(m)</i> memory. Note that the number of edges
--   <i>m</i> of a graph can be quadratic with respect to the expression
--   size <i>s</i>.
--   
--   <pre>
--   edgeList <a>empty</a>          == []
--   edgeList (<a>vertex</a> x)     == []
--   edgeList (<a>edge</a> x y)     == [(x,y)]
--   edgeList (<a>star</a> 2 [3,1]) == [(2,1), (2,3)]
--   edgeList . <a>edges</a>        == <a>nub</a> . <a>sort</a>
--   edgeList . <a>transpose</a>    == <a>sort</a> . map <a>swap</a> . edgeList
--   </pre>
edgeList :: Ord a => Graph a -> [(a, a)]

-- | The set of vertices of a given graph. Complexity: <i>O(s * log(n))</i>
--   time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexSet <a>empty</a>      == Set.<a>empty</a>
--   vertexSet . <a>vertex</a>   == Set.<a>singleton</a>
--   vertexSet . <a>vertices</a> == Set.<a>fromList</a>
--   vertexSet . <a>clique</a>   == Set.<a>fromList</a>
--   </pre>
vertexSet :: Ord a => Graph a -> Set a

-- | The set of vertices of a given graph. Like <a>vertexSet</a> but
--   specialised for graphs with vertices of type <a>Int</a>. Complexity:
--   <i>O(s * log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexIntSet <a>empty</a>      == IntSet.<a>empty</a>
--   vertexIntSet . <a>vertex</a>   == IntSet.<a>singleton</a>
--   vertexIntSet . <a>vertices</a> == IntSet.<a>fromList</a>
--   vertexIntSet . <a>clique</a>   == IntSet.<a>fromList</a>
--   </pre>
vertexIntSet :: Graph Int -> IntSet

-- | The set of edges of a given graph. Complexity: <i>O(s * log(m))</i>
--   time and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeSet <a>empty</a>      == Set.<a>empty</a>
--   edgeSet (<a>vertex</a> x) == Set.<a>empty</a>
--   edgeSet (<a>edge</a> x y) == Set.<a>singleton</a> (x,y)
--   edgeSet . <a>edges</a>    == Set.<a>fromList</a>
--   </pre>
edgeSet :: Ord a => Graph a -> Set (a, a)

-- | The <i>path</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   path []        == <a>empty</a>
--   path [x]       == <a>vertex</a> x
--   path [x,y]     == <a>edge</a> x y
--   path . <a>reverse</a> == <a>transpose</a> . path
--   </pre>
path :: [a] -> Graph a

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   circuit []        == <a>empty</a>
--   circuit [x]       == <a>edge</a> x x
--   circuit [x,y]     == <a>edges</a> [(x,y), (y,x)]
--   circuit . <a>reverse</a> == <a>transpose</a> . circuit
--   </pre>
circuit :: [a] -> Graph a

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   clique []         == <a>empty</a>
--   clique [x]        == <a>vertex</a> x
--   clique [x,y]      == <a>edge</a> x y
--   clique [x,y,z]    == <a>edges</a> [(x,y), (x,z), (y,z)]
--   clique (xs ++ ys) == <a>connect</a> (clique xs) (clique ys)
--   clique . <a>reverse</a>  == <a>transpose</a> . clique
--   </pre>
clique :: [a] -> Graph a

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(L1 +
--   L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i> are the
--   lengths of the given lists.
--   
--   <pre>
--   biclique []      []      == <a>empty</a>
--   biclique [x]     []      == <a>vertex</a> x
--   biclique []      [y]     == <a>vertex</a> y
--   biclique [x1,x2] [y1,y2] == <a>edges</a> [(x1,y1), (x1,y2), (x2,y1), (x2,y2)]
--   biclique xs      ys      == <a>connect</a> (<a>vertices</a> xs) (<a>vertices</a> ys)
--   </pre>
biclique :: [a] -> [a] -> Graph a

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O(L)</i> time, memory and size, where <i>L</i>
--   is the length of the given list.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges</a> [(x,y), (x,z)]
--   star x ys    == <a>connect</a> (<a>vertex</a> x) (<a>vertices</a> ys)
--   </pre>
star :: a -> [a] -> Graph a

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges</a> [(y,x), (z,x)]
--   starTranspose x ys    == <a>connect</a> (<a>vertices</a> ys) (<a>vertex</a> x)
--   starTranspose x ys    == <a>transpose</a> (<a>star</a> x ys)
--   </pre>
starTranspose :: a -> [a] -> Graph a

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O(T)</i> time, memory and size, where
--   <i>T</i> is the size of the given tree (i.e. the number of vertices in
--   the tree).
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path</a> [x,y,z]
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges</a> [(1,2), (1,3), (3,4), (3,5)]
--   </pre>
tree :: Tree a -> Graph a

-- | The <i>forest graph</i> constructed from a given <a>Forest</a> data
--   structure. Complexity: <i>O(F)</i> time, memory and size, where
--   <i>F</i> is the size of the given forest (i.e. the number of vertices
--   in the forest).
--   
--   <pre>
--   forest []                                                  == <a>empty</a>
--   forest [x]                                                 == <a>tree</a> x
--   forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == <a>edges</a> [(1,2), (1,3), (4,5)]
--   forest                                                     == <a>overlays</a> . map <a>tree</a>
--   </pre>
forest :: Forest a -> Graph a

-- | Construct a <i>mesh graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   mesh xs     []   == <a>empty</a>
--   mesh []     ys   == <a>empty</a>
--   mesh [x]    [y]  == <a>vertex</a> (x, y)
--   mesh xs     ys   == <a>box</a> (<a>path</a> xs) (<a>path</a> ys)
--   mesh [1..3] "ab" == <a>edges</a> [ ((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')) ]
--   </pre>
mesh :: [a] -> [b] -> Graph (a, b)

-- | Construct a <i>torus graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   torus xs    []   == <a>empty</a>
--   torus []    ys   == <a>empty</a>
--   torus [x]   [y]  == <a>edge</a> (x, y) (x, y)
--   torus xs    ys   == <a>box</a> (<a>circuit</a> xs) (<a>circuit</a> ys)
--   torus [1,2] "ab" == <a>edges</a> [ ((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')) ]
--   </pre>
torus :: [a] -> [b] -> Graph (a, b)

-- | Construct a <i>De Bruijn graph</i> of a given non-negative dimension
--   using symbols from a given alphabet. Complexity: <i>O(A^(D + 1))</i>
--   time, memory and size, where <i>A</i> is the size of the alphabet and
--   <i>D</i> is the dimension of the graph.
--   
--   <pre>
--             deBruijn 0 xs               == <a>edge</a> [] []
--   n &gt; 0 ==&gt; deBruijn n []               == <a>empty</a>
--             deBruijn 1 [0,1]            == <a>edges</a> [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
--             deBruijn 2 "0"              == <a>edge</a> "00" "00"
--             deBruijn 2 "01"             == <a>edges</a> [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
--                                                  , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
--             <a>transpose</a>   (deBruijn n xs) == <a>fmap</a> <a>reverse</a> $ deBruijn n xs
--             <a>vertexCount</a> (deBruijn n xs) == (<a>length</a> $ <a>nub</a> xs)^n
--   n &gt; 0 ==&gt; <a>edgeCount</a>   (deBruijn n xs) == (<a>length</a> $ <a>nub</a> xs)^(n + 1)
--   </pre>
deBruijn :: Int -> [a] -> Graph [a]

-- | Remove a vertex from a given graph. Complexity: <i>O(s)</i> time,
--   memory and size.
--   
--   <pre>
--   removeVertex x (<a>vertex</a> x)       == <a>empty</a>
--   removeVertex 1 (<a>vertex</a> 2)       == <a>vertex</a> 2
--   removeVertex x (<a>edge</a> x x)       == <a>empty</a>
--   removeVertex 1 (<a>edge</a> 1 2)       == <a>vertex</a> 2
--   removeVertex x . removeVertex x == removeVertex x
--   </pre>
removeVertex :: Eq a => a -> Graph a -> Graph a

-- | Remove an edge from a given graph. Complexity: <i>O(s)</i> time,
--   memory and size.
--   
--   <pre>
--   removeEdge x y (<a>edge</a> x y)       == <a>vertices</a> [x, y]
--   removeEdge x y . removeEdge x y == removeEdge x y
--   removeEdge x y . <a>removeVertex</a> x == <a>removeVertex</a> x
--   removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
--   removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2
--   <a>size</a> (removeEdge x y z)         &lt;= 3 * <a>size</a> z
--   </pre>
removeEdge :: Eq a => a -> a -> Graph a -> Graph a

-- | The function <tt><a>replaceVertex</a> x y</tt> replaces vertex
--   <tt>x</tt> with vertex <tt>y</tt> in a given <a>Graph</a>. If
--   <tt>y</tt> already exists, <tt>x</tt> and <tt>y</tt> will be merged.
--   Complexity: <i>O(s)</i> time, memory and size.
--   
--   <pre>
--   replaceVertex x x            == id
--   replaceVertex x y (<a>vertex</a> x) == <a>vertex</a> y
--   replaceVertex x y            == <a>mergeVertices</a> (== x) y
--   </pre>
replaceVertex :: Eq a => a -> a -> Graph a -> Graph a

-- | Merge vertices satisfying a given predicate into a given vertex.
--   Complexity: <i>O(s)</i> time, memory and size, assuming that the
--   predicate takes <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   mergeVertices (const False) x    == id
--   mergeVertices (== x) y           == <a>replaceVertex</a> x y
--   mergeVertices even 1 (0 * 2)     == 1 * 1
--   mergeVertices odd  1 (3 + 4 * 5) == 4 * 1
--   </pre>
mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a

-- | Split a vertex into a list of vertices with the same connectivity.
--   Complexity: <i>O(s + k * L)</i> time, memory and size, where <i>k</i>
--   is the number of occurrences of the vertex in the expression and
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   splitVertex x []                  == <a>removeVertex</a> x
--   splitVertex x [x]                 == id
--   splitVertex x [y]                 == <a>replaceVertex</a> x y
--   splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
--   </pre>
splitVertex :: Eq a => a -> [a] -> Graph a -> Graph a

-- | Transpose a given graph. Complexity: <i>O(s)</i> time, memory and
--   size.
--   
--   <pre>
--   transpose <a>empty</a>       == <a>empty</a>
--   transpose (<a>vertex</a> x)  == <a>vertex</a> x
--   transpose (<a>edge</a> x y)  == <a>edge</a> y x
--   transpose . transpose == id
--   transpose (<a>box</a> x y)   == <a>box</a> (transpose x) (transpose y)
--   <a>edgeList</a> . transpose  == <a>sort</a> . map <a>swap</a> . <a>edgeList</a>
--   </pre>
transpose :: Graph a -> Graph a

-- | Construct the <i>induced subgraph</i> of a given graph by removing the
--   vertices that do not satisfy a given predicate. Complexity:
--   <i>O(s)</i> time, memory and size, assuming that the predicate takes
--   <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   induce (const True ) x      == x
--   induce (const False) x      == <a>empty</a>
--   induce (/= x)               == <a>removeVertex</a> x
--   induce p . induce q         == induce (\x -&gt; p x &amp;&amp; q x)
--   <a>isSubgraphOf</a> (induce p x) x == True
--   </pre>
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 <i>O(s)</i> graph
--   comparisons. It is guaranteed that the size of the result does not
--   exceed the size of the given expression.
--   
--   <pre>
--   simplify              == id
--   <a>size</a> (simplify x)     &lt;= <a>size</a> x
--   simplify <a>empty</a>       <a>===</a> <a>empty</a>
--   simplify 1           <a>===</a> 1
--   simplify (1 + 1)     <a>===</a> 1
--   simplify (1 + 2 + 1) <a>===</a> 1 + 2
--   simplify (1 * 1 * 1) <a>===</a> 1 * 1
--   </pre>
simplify :: Ord a => Graph a -> Graph a

-- | Compute the <i>Cartesian product</i> of graphs. Complexity: <i>O(s1 *
--   s2)</i> time, memory and size, where <i>s1</i> and <i>s2</i> are the
--   sizes of the given graphs.
--   
--   <pre>
--   box (<a>path</a> [0,1]) (<a>path</a> "ab") == <a>edges</a> [ ((0,'a'), (0,'b'))
--                                         , ((0,'a'), (1,'a'))
--                                         , ((0,'b'), (1,'b'))
--                                         , ((1,'a'), (1,'b')) ]
--   </pre>
--   
--   Up to an isomorphism between the resulting vertex types, this
--   operation is <i>commutative</i>, <i>associative</i>,
--   <i>distributes</i> over <a>overlay</a>, has singleton graphs as
--   <i>identities</i> and <a>empty</a> as the <i>annihilating zero</i>.
--   Below <tt>~~</tt> stands for the equality up to an isomorphism, e.g.
--   <tt>(x, ()) ~~ x</tt>.
--   
--   <pre>
--   box x y               ~~ box y x
--   box x (box y z)       ~~ box (box x y) z
--   box x (<a>overlay</a> y z)   == <a>overlay</a> (box x y) (box x z)
--   box x (<a>vertex</a> ())     ~~ x
--   box x <a>empty</a>           ~~ <a>empty</a>
--   <a>transpose</a>   (box x y) == box (<a>transpose</a> x) (<a>transpose</a> y)
--   <a>vertexCount</a> (box x y) == <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (box x y) &lt;= <a>vertexCount</a> x * <a>edgeCount</a> y + <a>edgeCount</a> x * <a>vertexCount</a> y
--   </pre>
box :: Graph a -> Graph b -> Graph (a, b)
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 Algebra.Graph.Class.Graph (Algebra.Graph.Graph a)
instance Algebra.Graph.Class.ToGraph (Algebra.Graph.Graph a)
instance Algebra.Graph.HigherKinded.Class.ToGraph Algebra.Graph.Graph
instance Algebra.Graph.HigherKinded.Class.Graph Algebra.Graph.Graph
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


-- | <b>Alga</b> is a library for algebraic construction and manipulation
--   of graphs in Haskell. See <a>this paper</a> for the motivation behind
--   the library, the underlying theory, and implementation details.
--   
--   This module defines the data type <a>NonEmptyGraph</a> for graphs that
--   are known to be non-empty at compile time. The naming convention
--   generally follows that of <a>Data.List.NonEmpty</a>: we use suffix
--   <tt>1</tt> to indicate the functions whose interface must be changed
--   compared to <a>Algebra.Graph</a>, e.g. <a>vertices1</a>.
module Algebra.Graph.NonEmpty

-- | The <a>NonEmptyGraph</a> data type is a deep embedding of the core
--   graph construction primitives <a>vertex</a>, <a>overlay</a> and
--   <a>connect</a>. As one can guess from the name, the empty graph cannot
--   be represented using this data type. See module <a>Algebra.Graph</a>
--   for a graph data type that allows for the construction of the empty
--   graph.
--   
--   We define a <a>Num</a> instance as a convenient notation for working
--   with graphs:
--   
--   <pre>
--   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))
--   </pre>
--   
--   Note that the <a>signum</a> method of the <a>Num</a> type class cannot
--   be implemented.
--   
--   The <a>Eq</a> instance is currently implemented using the
--   <a>AdjacencyMap</a> as the <i>canonical graph representation</i> and
--   satisfies the following laws of algebraic graphs:
--   
--   <ul>
--   <li><a>overlay</a> is commutative, associative and idempotent:<pre> x
--   + y == y + x x + (y + z) == (x + y) + z x + x == x</pre></li>
--   <li><a>connect</a> is associative:<pre>x * (y * z) == (x * y) *
--   z</pre></li>
--   <li><a>connect</a> distributes over <a>overlay</a>:<pre>x * (y + z) ==
--   x * y + x * z (x + y) * z == x * z + y * z</pre></li>
--   <li><a>connect</a> can be decomposed:<pre>x * y * z == x * y + x * z +
--   y * z</pre></li>
--   <li><a>connect</a> satisfies absorption and saturation:<pre>x * y + x
--   + y == x * y x * x * x == x * x</pre></li>
--   </ul>
--   
--   When specifying the time and memory complexity of graph algorithms,
--   <i>n</i> will denote the number of vertices in the graph, <i>m</i>
--   will denote the number of edges in the graph, and <i>s</i> will denote
--   the <i>size</i> of the corresponding <a>NonEmptyGraph</a> expression,
--   defined as the number of vertex leaves. For example, if <tt>g</tt> is
--   a <a>NonEmptyGraph</a> then <i>n</i>, <i>m</i> and <i>s</i> can be
--   computed as follows:
--   
--   <pre>
--   n == <a>vertexCount</a> g
--   m == <a>edgeCount</a> g
--   s == <a>size</a> g
--   </pre>
--   
--   The <a>size</a> of any graph is positive and coincides with the result
--   of <a>length</a> method of the <a>Foldable</a> type class. We define
--   <a>size</a> only for the consistency with the API of other graph
--   representations, such as <a>Algebra.Graph</a>.
--   
--   Converting a <a>NonEmptyGraph</a> to the corresponding
--   <a>AdjacencyMap</a> takes <i>O(s + m * log(m))</i> time and <i>O(s +
--   m)</i> 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 <a>Graph</a> into <a>NonEmptyGraph</a>. Returns
--   <a>Nothing</a> if the argument is <a>empty</a>. Complexity:
--   <i>O(s)</i> time, memory and size.
--   
--   <pre>
--   toNonEmptyGraph <a>empty</a>       == Nothing
--   toNonEmptyGraph (<a>toGraph</a> x) == Just (x :: NonEmptyGraph a)
--   </pre>
toNonEmptyGraph :: Graph a -> Maybe (NonEmptyGraph a)

-- | Construct the graph comprising <i>a single isolated vertex</i>. An
--   alias for the constructor <a>Vertex</a>. Complexity: <i>O(1)</i> time,
--   memory and size.
--   
--   <pre>
--   <a>hasVertex</a> x (vertex x) == True
--   <a>vertexCount</a> (vertex x) == 1
--   <a>edgeCount</a>   (vertex x) == 0
--   <a>size</a>        (vertex x) == 1
--   </pre>
vertex :: a -> NonEmptyGraph a

-- | Construct the graph comprising <i>a single edge</i>. Complexity:
--   <i>O(1)</i> time, memory and size.
--   
--   <pre>
--   edge x y               == <a>connect</a> (<a>vertex</a> x) (<a>vertex</a> y)
--   <a>hasEdge</a> x y (edge x y) == True
--   <a>edgeCount</a>   (edge x y) == 1
--   <a>vertexCount</a> (edge 1 1) == 1
--   <a>vertexCount</a> (edge 1 2) == 2
--   </pre>
edge :: a -> a -> NonEmptyGraph a

-- | <i>Overlay</i> two graphs. An alias for the constructor
--   <a>Overlay</a>. This is a commutative, associative and idempotent
--   operation. Complexity: <i>O(1)</i> time and memory, <i>O(s1 + s2)</i>
--   size.
--   
--   <pre>
--   <a>hasVertex</a> z (overlay x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (overlay x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (overlay x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (overlay x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (overlay x y) &lt;= <a>edgeCount</a> x   + <a>edgeCount</a> y
--   <a>size</a>        (overlay x y) == <a>size</a> x        + <a>size</a> y
--   <a>vertexCount</a> (overlay 1 2) == 2
--   <a>edgeCount</a>   (overlay 1 2) == 0
--   </pre>
overlay :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a

-- | Overlay a possibly empty graph with a non-empty graph. If the first
--   argument is <a>empty</a>, the function returns the second argument;
--   otherwise it is semantically the same as <a>overlay</a>. Complexity:
--   <i>O(s1)</i> time and memory, and <i>O(s1 + s2)</i> size.
--   
--   <pre>
--                  overlay1 <a>empty</a> x == x
--   x /= <a>empty</a> ==&gt; overlay1 x     y == overlay (fromJust $ toNonEmptyGraph x) y
--   </pre>
overlay1 :: Graph a -> NonEmptyGraph a -> NonEmptyGraph a

-- | <i>Connect</i> two graphs. An alias for the constructor
--   <a>Connect</a>. This is an associative operation, which distributes
--   over <a>overlay</a> and obeys the decomposition axiom. Complexity:
--   <i>O(1)</i> time and memory, <i>O(s1 + s2)</i> size. Note that the
--   number of edges in the resulting graph is quadratic with respect to
--   the number of vertices of the arguments: <i>m = O(m1 + m2 + n1 *
--   n2)</i>.
--   
--   <pre>
--   <a>hasVertex</a> z (connect x y) == <a>hasVertex</a> z x || <a>hasVertex</a> z y
--   <a>vertexCount</a> (connect x y) &gt;= <a>vertexCount</a> x
--   <a>vertexCount</a> (connect x y) &lt;= <a>vertexCount</a> x + <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> x
--   <a>edgeCount</a>   (connect x y) &gt;= <a>edgeCount</a> y
--   <a>edgeCount</a>   (connect x y) &gt;= <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (connect x y) &lt;= <a>vertexCount</a> x * <a>vertexCount</a> y + <a>edgeCount</a> x + <a>edgeCount</a> y
--   <a>size</a>        (connect x y) == <a>size</a> x        + <a>size</a> y
--   <a>vertexCount</a> (connect 1 2) == 2
--   <a>edgeCount</a>   (connect 1 2) == 1
--   </pre>
connect :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a

-- | Construct the graph comprising a given list of isolated vertices.
--   Complexity: <i>O(L)</i> time, memory and size, where <i>L</i> is the
--   length of the given list.
--   
--   <pre>
--   vertices1 (x <a>:|</a> [])     == <a>vertex</a> x
--   <a>hasVertex</a> x . vertices1 == <a>elem</a> x
--   <a>vertexCount</a> . vertices1 == <a>length</a> . <a>nub</a>
--   <a>vertexSet</a>   . vertices1 == Set.<a>fromList</a> . <a>toList</a>
--   </pre>
vertices1 :: NonEmpty a -> NonEmptyGraph a

-- | Construct the graph from a list of edges. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   edges1 ((x,y) <a>:|</a> []) == <a>edge</a> x y
--   <a>edgeCount</a> . edges1   == <a>length</a> . <a>nub</a>
--   </pre>
edges1 :: NonEmpty (a, a) -> NonEmptyGraph a

-- | Overlay a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   overlays1 (x <a>:|</a> [] ) == x
--   overlays1 (x <a>:|</a> [y]) == <a>overlay</a> x y
--   </pre>
overlays1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a

-- | Connect a given list of graphs. Complexity: <i>O(L)</i> time and
--   memory, and <i>O(S)</i> size, where <i>L</i> is the length of the
--   given list, and <i>S</i> is the sum of sizes of the graphs in the
--   list.
--   
--   <pre>
--   connects1 (x <a>:|</a> [] ) == x
--   connects1 (x <a>:|</a> [y]) == <a>connect</a> x y
--   </pre>
connects1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a

-- | Generalised graph folding: recursively collapse a <a>NonEmptyGraph</a>
--   by applying the provided functions to the leaves and internal nodes of
--   the expression. The order of arguments is: vertex, overlay and
--   connect. Complexity: <i>O(s)</i> applications of given functions. As
--   an example, the complexity of <a>size</a> is <i>O(s)</i>, since all
--   functions have cost <i>O(1)</i>.
--   
--   <pre>
--   foldg1 (const 1) (+)  (+)  == <a>size</a>
--   foldg1 (==x)     (||) (||) == <a>hasVertex</a> x
--   </pre>
foldg1 :: (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> NonEmptyGraph a -> b

-- | The <a>isSubgraphOf</a> function takes two graphs and returns
--   <a>True</a> if the first graph is a <i>subgraph</i> of the second.
--   Complexity: <i>O(s + m * log(m))</i> time. Note that the number of
--   edges <i>m</i> of a graph can be quadratic with respect to the
--   expression size <i>s</i>.
--   
--   <pre>
--   isSubgraphOf x             (<a>overlay</a> x y) == True
--   isSubgraphOf (<a>overlay</a> x y) (<a>connect</a> x y) == True
--   isSubgraphOf (<a>path1</a> xs)    (<a>circuit1</a> xs) == True
--   </pre>
isSubgraphOf :: Ord a => NonEmptyGraph a -> NonEmptyGraph a -> Bool

-- | Structural equality on graph expressions. Complexity: <i>O(s)</i>
--   time.
--   
--   <pre>
--       x === x     == True
--   x + y === x + y == True
--   1 + 2 === 2 + 1 == False
--   x + y === x * y == False
--   </pre>
(===) :: Eq a => NonEmptyGraph a -> NonEmptyGraph a -> Bool
infix 4 ===

-- | The <i>size</i> of a graph, i.e. the number of leaves of the
--   expression. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   size (<a>vertex</a> x)    == 1
--   size (<a>overlay</a> x y) == size x + size y
--   size (<a>connect</a> x y) == size x + size y
--   size x             &gt;= 1
--   size x             &gt;= <a>vertexCount</a> x
--   </pre>
size :: NonEmptyGraph a -> Int

-- | Check if a graph contains a given vertex. A convenient alias for
--   <a>elem</a>. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasVertex x (<a>vertex</a> x) == True
--   hasVertex 1 (<a>vertex</a> 2) == False
--   </pre>
hasVertex :: Eq a => a -> NonEmptyGraph a -> Bool

-- | Check if a graph contains a given edge. Complexity: <i>O(s)</i> time.
--   
--   <pre>
--   hasEdge x y (<a>vertex</a> z)       == False
--   hasEdge x y (<a>edge</a> x y)       == True
--   hasEdge x y . <a>removeEdge</a> x y == const False
--   hasEdge x y                  == <a>elem</a> (x,y) . <a>edgeList</a>
--   </pre>
hasEdge :: Ord a => a -> a -> NonEmptyGraph a -> Bool

-- | The number of vertices in a graph. Complexity: <i>O(s * log(n))</i>
--   time.
--   
--   <pre>
--   vertexCount (<a>vertex</a> x) == 1
--   vertexCount x          &gt;= 1
--   vertexCount            == <a>length</a> . <a>vertexList1</a>
--   </pre>
vertexCount :: Ord a => NonEmptyGraph a -> Int

-- | The number of edges in a graph. Complexity: <i>O(s + m * log(m))</i>
--   time. Note that the number of edges <i>m</i> of a graph can be
--   quadratic with respect to the expression size <i>s</i>.
--   
--   <pre>
--   edgeCount (<a>vertex</a> x) == 0
--   edgeCount (<a>edge</a> x y) == 1
--   edgeCount            == <a>length</a> . <a>edgeList</a>
--   </pre>
edgeCount :: Ord a => NonEmptyGraph a -> Int

-- | The sorted list of vertices of a given graph. Complexity: <i>O(s *
--   log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexList1 (<a>vertex</a> x)  == x <a>:|</a> []
--   vertexList1 . <a>vertices1</a> == <a>nub</a> . <a>sort</a>
--   </pre>
vertexList1 :: Ord a => NonEmptyGraph a -> NonEmpty a

-- | The sorted list of edges of a graph. Complexity: <i>O(s + m *
--   log(m))</i> time and <i>O(m)</i> memory. Note that the number of edges
--   <i>m</i> of a graph can be quadratic with respect to the expression
--   size <i>s</i>.
--   
--   <pre>
--   edgeList (<a>vertex</a> x)     == []
--   edgeList (<a>edge</a> x y)     == [(x,y)]
--   edgeList (<a>star</a> 2 [3,1]) == [(2,1), (2,3)]
--   edgeList . <a>edges1</a>       == <a>nub</a> . <a>sort</a> . <a>toList</a>
--   edgeList . <a>transpose</a>    == <a>sort</a> . map <a>swap</a> . edgeList
--   </pre>
edgeList :: Ord a => NonEmptyGraph a -> [(a, a)]

-- | The set of vertices of a given graph. Complexity: <i>O(s * log(n))</i>
--   time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexSet . <a>vertex</a>    == Set.<a>singleton</a>
--   vertexSet . <a>vertices1</a> == Set.<a>fromList</a> . <a>toList</a>
--   vertexSet . <a>clique1</a>   == Set.<a>fromList</a> . <a>toList</a>
--   </pre>
vertexSet :: Ord a => NonEmptyGraph a -> Set a

-- | The set of vertices of a given graph. Like <a>vertexSet</a> but
--   specialised for graphs with vertices of type <a>Int</a>. Complexity:
--   <i>O(s * log(n))</i> time and <i>O(n)</i> memory.
--   
--   <pre>
--   vertexIntSet . <a>vertex</a>    == IntSet.<a>singleton</a>
--   vertexIntSet . <a>vertices1</a> == IntSet.<a>fromList</a> . <a>toList</a>
--   vertexIntSet . <a>clique1</a>   == IntSet.<a>fromList</a> . <a>toList</a>
--   </pre>
vertexIntSet :: NonEmptyGraph Int -> IntSet

-- | The set of edges of a given graph. Complexity: <i>O(s * log(m))</i>
--   time and <i>O(m)</i> memory.
--   
--   <pre>
--   edgeSet (<a>vertex</a> x) == Set.<a>empty</a>
--   edgeSet (<a>edge</a> x y) == Set.<a>singleton</a> (x,y)
--   edgeSet . <a>edges1</a>   == Set.<a>fromList</a> . <a>toList</a>
--   </pre>
edgeSet :: Ord a => NonEmptyGraph a -> Set (a, a)

-- | The <i>path</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   path1 (x <a>:|</a> [] ) == <a>vertex</a> x
--   path1 (x <a>:|</a> [y]) == <a>edge</a> x y
--   path1 . <a>reverse</a>  == <a>transpose</a> . path1
--   </pre>
path1 :: NonEmpty a -> NonEmptyGraph a

-- | The <i>circuit</i> on a list of vertices. Complexity: <i>O(L)</i>
--   time, memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   circuit1 (x <a>:|</a> [] ) == <a>edge</a> x x
--   circuit1 (x <a>:|</a> [y]) == <a>edges1</a> ((x,y) <a>:|</a> [(y,x)])
--   circuit1 . <a>reverse</a>  == <a>transpose</a> . circuit1
--   </pre>
circuit1 :: NonEmpty a -> NonEmptyGraph a

-- | The <i>clique</i> on a list of vertices. Complexity: <i>O(L)</i> time,
--   memory and size, where <i>L</i> is the length of the given list.
--   
--   <pre>
--   clique1 (x <a>:|</a> []   ) == <a>vertex</a> x
--   clique1 (x <a>:|</a> [y]  ) == <a>edge</a> x y
--   clique1 (x <a>:|</a> [y,z]) == <a>edges1</a> ((x,y) <a>:|</a> [(x,z), (y,z)])
--   clique1 (xs <a>&lt;&gt;</a> ys)   == <a>connect</a> (clique1 xs) (clique1 ys)
--   clique1 . <a>reverse</a>    == <a>transpose</a> . clique1
--   </pre>
clique1 :: NonEmpty a -> NonEmptyGraph a

-- | The <i>biclique</i> on two lists of vertices. Complexity: <i>O(L1 +
--   L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i> are the
--   lengths of the given lists.
--   
--   <pre>
--   biclique1 (x1 <a>:|</a> [x2]) (y1 <a>:|</a> [y2]) == <a>edges1</a> ((x1,y1) <a>:|</a> [(x1,y2), (x2,y1), (x2,y2)])
--   biclique1 xs            ys          == <a>connect</a> (<a>vertices1</a> xs) (<a>vertices1</a> ys)
--   </pre>
biclique1 :: NonEmpty a -> NonEmpty a -> NonEmptyGraph a

-- | The <i>star</i> formed by a centre vertex connected to a list of
--   leaves. Complexity: <i>O(L)</i> time, memory and size, where <i>L</i>
--   is the length of the given list.
--   
--   <pre>
--   star x []    == <a>vertex</a> x
--   star x [y]   == <a>edge</a> x y
--   star x [y,z] == <a>edges1</a> ((x,y) <a>:|</a> [(x,z)])
--   </pre>
star :: a -> [a] -> NonEmptyGraph a

-- | The <i>star transpose</i> formed by a list of leaves connected to a
--   centre vertex. Complexity: <i>O(L)</i> time, memory and size, where
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   starTranspose x []    == <a>vertex</a> x
--   starTranspose x [y]   == <a>edge</a> y x
--   starTranspose x [y,z] == <a>edges1</a> ((y,x) <a>:|</a> [(z,x)])
--   starTranspose x ys    == <a>transpose</a> (<a>star</a> x ys)
--   </pre>
starTranspose :: a -> [a] -> NonEmptyGraph a

-- | The <i>tree graph</i> constructed from a given <a>Tree</a> data
--   structure. Complexity: <i>O(T)</i> time, memory and size, where
--   <i>T</i> is the size of the given tree (i.e. the number of vertices in
--   the tree).
--   
--   <pre>
--   tree (Node x [])                                         == <a>vertex</a> x
--   tree (Node x [Node y [Node z []]])                       == <a>path1</a> (x <a>:|</a> [y,z])
--   tree (Node x [Node y [], Node z []])                     == <a>star</a> x [y,z]
--   tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == <a>edges1</a> ((1,2) <a>:|</a> [(1,3), (3,4), (3,5)])
--   </pre>
tree :: Tree a -> NonEmptyGraph a

-- | Construct a <i>mesh graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   mesh1 (x <a>:|</a> [])    (y <a>:|</a> [])    == <a>vertex</a> (x, y)
--   mesh1 xs           ys           == <a>box</a> (<a>path1</a> xs) (<a>path1</a> ys)
--   mesh1 (1 <a>:|</a> [2,3]) ('a' <a>:|</a> "b") == <a>edges1</a> (<a>fromList</a> [ ((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')) ])
--   </pre>
mesh1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (a, b)

-- | Construct a <i>torus graph</i> from two lists of vertices. Complexity:
--   <i>O(L1 * L2)</i> time, memory and size, where <i>L1</i> and <i>L2</i>
--   are the lengths of the given lists.
--   
--   <pre>
--   torus1 (x <a>:|</a> [])  (y <a>:|</a> [])    == <a>edge</a> (x, y) (x, y)
--   torus1 xs         ys           == <a>box</a> (<a>circuit1</a> xs) (<a>circuit1</a> ys)
--   torus1 (1 <a>:|</a> [2]) ('a' <a>:|</a> "b") == <a>edges1</a> (<a>fromList</a> [ ((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')) ])
--   </pre>
torus1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (a, b)

-- | Remove a vertex from a given graph. Returns <tt>Nothing</tt> if the
--   resulting graph is empty. Complexity: <i>O(s)</i> time, memory and
--   size.
--   
--   <pre>
--   removeVertex1 x (<a>vertex</a> x)          == Nothing
--   removeVertex1 1 (<a>vertex</a> 2)          == Just (<a>vertex</a> 2)
--   removeVertex1 x (<a>edge</a> x x)          == Nothing
--   removeVertex1 1 (<a>edge</a> 1 2)          == Just (<a>vertex</a> 2)
--   removeVertex1 x <a>&gt;=&gt;</a> removeVertex1 x == removeVertex1 x
--   </pre>
removeVertex1 :: Eq a => a -> NonEmptyGraph a -> Maybe (NonEmptyGraph a)

-- | Remove an edge from a given graph. Complexity: <i>O(s)</i> time,
--   memory and size.
--   
--   <pre>
--   removeEdge x y (<a>edge</a> x y)       == <a>vertices1</a> (x <a>:|</a> [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
--   <a>size</a> (removeEdge x y z)         &lt;= 3 * <a>size</a> z
--   </pre>
removeEdge :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a

-- | The function <tt><a>replaceVertex</a> x y</tt> replaces vertex
--   <tt>x</tt> with vertex <tt>y</tt> in a given <a>NonEmptyGraph</a>. If
--   <tt>y</tt> already exists, <tt>x</tt> and <tt>y</tt> will be merged.
--   Complexity: <i>O(s)</i> time, memory and size.
--   
--   <pre>
--   replaceVertex x x            == id
--   replaceVertex x y (<a>vertex</a> x) == <a>vertex</a> y
--   replaceVertex x y            == <a>mergeVertices</a> (== x) y
--   </pre>
replaceVertex :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a

-- | Merge vertices satisfying a given predicate into a given vertex.
--   Complexity: <i>O(s)</i> time, memory and size, assuming that the
--   predicate takes <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   mergeVertices (const False) x    == id
--   mergeVertices (== x) y           == <a>replaceVertex</a> x y
--   mergeVertices even 1 (0 * 2)     == 1 * 1
--   mergeVertices odd  1 (3 + 4 * 5) == 4 * 1
--   </pre>
mergeVertices :: (a -> Bool) -> a -> NonEmptyGraph a -> NonEmptyGraph a

-- | Split a vertex into a list of vertices with the same connectivity.
--   Complexity: <i>O(s + k * L)</i> time, memory and size, where <i>k</i>
--   is the number of occurrences of the vertex in the expression and
--   <i>L</i> is the length of the given list.
--   
--   <pre>
--   splitVertex1 x (x <a>:|</a> [] )               == id
--   splitVertex1 x (y <a>:|</a> [] )               == <a>replaceVertex</a> x y
--   splitVertex1 1 (0 <a>:|</a> [1]) $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
--   </pre>
splitVertex1 :: Eq a => a -> NonEmpty a -> NonEmptyGraph a -> NonEmptyGraph a

-- | Transpose a given graph. Complexity: <i>O(s)</i> time, memory and
--   size.
--   
--   <pre>
--   transpose (<a>vertex</a> x)  == <a>vertex</a> x
--   transpose (<a>edge</a> x y)  == <a>edge</a> y x
--   transpose . transpose == id
--   transpose (<a>box</a> x y)   == <a>box</a> (transpose x) (transpose y)
--   <a>edgeList</a> . transpose  == <a>sort</a> . map <a>swap</a> . <a>edgeList</a>
--   </pre>
transpose :: NonEmptyGraph a -> NonEmptyGraph a

-- | Construct the <i>induced subgraph</i> of a given graph by removing the
--   vertices that do not satisfy a given predicate. Returns
--   <tt>Nothing</tt> if the resulting graph is empty. Complexity:
--   <i>O(s)</i> time, memory and size, assuming that the predicate takes
--   <i>O(1)</i> to be evaluated.
--   
--   <pre>
--   induce1 (const True ) x == Just x
--   induce1 (const False) x == Nothing
--   induce1 (/= x)          == <a>removeVertex1</a> x
--   induce1 p <a>&gt;=&gt;</a> induce1 q == induce1 (\x -&gt; p x &amp;&amp; q x)
--   </pre>
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 <i>O(s)</i> graph
--   comparisons. It is guaranteed that the size of the result does not
--   exceed the size of the given expression.
--   
--   <pre>
--   simplify              == id
--   <a>size</a> (simplify x)     &lt;= <a>size</a> x
--   simplify 1           <a>===</a> 1
--   simplify (1 + 1)     <a>===</a> 1
--   simplify (1 + 2 + 1) <a>===</a> 1 + 2
--   simplify (1 * 1 * 1) <a>===</a> 1 * 1
--   </pre>
simplify :: Ord a => NonEmptyGraph a -> NonEmptyGraph a

-- | Compute the <i>Cartesian product</i> of graphs. Complexity: <i>O(s1 *
--   s2)</i> time, memory and size, where <i>s1</i> and <i>s2</i> are the
--   sizes of the given graphs.
--   
--   <pre>
--   box (<a>path1</a> $ <a>fromList</a> [0,1]) (<a>path1</a> $ <a>fromList</a> "ab") == <a>edges1</a> (<a>fromList</a> [ ((0,'a'), (0,'b'))
--                                                                            , ((0,'a'), (1,'a'))
--                                                                            , ((0,'b'), (1,'b'))
--                                                                            , ((1,'a'), (1,'b')) ])
--   </pre>
--   
--   Up to an isomorphism between the resulting vertex types, this
--   operation is <i>commutative</i>, <i>associative</i>,
--   <i>distributes</i> over <a>overlay</a>, and has singleton graphs as
--   <i>identities</i>. Below <tt>~~</tt> stands for the equality up to an
--   isomorphism, e.g. <tt>(x, ()) ~~ x</tt>.
--   
--   <pre>
--   box x y               ~~ box y x
--   box x (box y z)       ~~ box (box x y) z
--   box x (<a>overlay</a> y z)   == <a>overlay</a> (box x y) (box x z)
--   box x (<a>vertex</a> ())     ~~ x
--   <a>transpose</a>   (box x y) == box (<a>transpose</a> x) (<a>transpose</a> y)
--   <a>vertexCount</a> (box x y) == <a>vertexCount</a> x * <a>vertexCount</a> y
--   <a>edgeCount</a>   (box x y) &lt;= <a>vertexCount</a> x * <a>edgeCount</a> y + <a>edgeCount</a> x * <a>vertexCount</a> y
--   </pre>
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.Class.ToGraph (Algebra.Graph.NonEmpty.NonEmptyGraph a)
instance Algebra.Graph.HigherKinded.Class.ToGraph Algebra.Graph.NonEmpty.NonEmptyGraph
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


-- | 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
--   <a>Algebra.Graph.Relation.Reflexive</a>,
--   <a>Algebra.Graph.Relation.Symmetric</a>,
--   <a>Algebra.Graph.Relation.Transitive</a> and
--   <a>Algebra.Graph.Relation.Preorder</a> instead.
module Algebra.Graph.Relation.InternalDerived

-- | The <a>ReflexiveRelation</a> data type represents a <i>reflexive
--   binary relation</i> over a set of elements. Reflexive relations
--   satisfy all laws of the <a>Reflexive</a> type class and, in
--   particular, the <i>self-loop</i> axiom:
--   
--   <pre>
--   <a>vertex</a> x == <a>vertex</a> x * <a>vertex</a> x
--   </pre>
--   
--   The <a>Show</a> instance produces reflexively closed expressions:
--   
--   <pre>
--   show (1     :: ReflexiveRelation Int) == "edge 1 1"
--   show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"
--   </pre>
newtype ReflexiveRelation a
ReflexiveRelation :: Relation a -> ReflexiveRelation a
[fromReflexive] :: ReflexiveRelation a -> Relation a

-- | The <a>SymmetricRelation</a> data type represents a <i>symmetric
--   binary relation</i> over a set of elements. Symmetric relations
--   satisfy all laws of the <a>Undirected</a> type class and, in
--   particular, the commutativity of connect:
--   
--   <pre>
--   <a>connect</a> x y == <a>connect</a> y x
--   </pre>
--   
--   The <a>Show</a> instance produces symmetrically closed expressions:
--   
--   <pre>
--   show (1     :: SymmetricRelation Int) == "vertex 1"
--   show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"
--   </pre>
newtype SymmetricRelation a
SymmetricRelation :: Relation a -> SymmetricRelation a
[fromSymmetric] :: SymmetricRelation a -> Relation a

-- | The <a>TransitiveRelation</a> data type represents a <i>transitive
--   binary relation</i> over a set of elements. Transitive relations
--   satisfy all laws of the <a>Transitive</a> type class and, in
--   particular, the <i>closure</i> axiom:
--   
--   <pre>
--   y /= <a>empty</a> ==&gt; x * y + x * z + y * z == x * y + y * z
--   </pre>
--   
--   For example, the following holds:
--   
--   <pre>
--   <a>path</a> xs == (<a>clique</a> xs :: TransitiveRelation Int)
--   </pre>
--   
--   The <a>Show</a> instance produces transitively closed expressions:
--   
--   <pre>
--   show (1 * 2         :: TransitiveRelation Int) == "edge 1 2"
--   show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"
--   </pre>
newtype TransitiveRelation a
TransitiveRelation :: Relation a -> TransitiveRelation a
[fromTransitive] :: TransitiveRelation a -> Relation a

-- | The <a>PreorderRelation</a> data type represents a <i>binary relation
--   that is both reflexive and transitive</i>. Preorders satisfy all laws
--   of the <a>Preorder</a> type class and, in particular, the
--   <i>self-loop</i> axiom:
--   
--   <pre>
--   <a>vertex</a> x == <a>vertex</a> x * <a>vertex</a> x
--   </pre>
--   
--   and the <i>closure</i> axiom:
--   
--   <pre>
--   y /= <a>empty</a> ==&gt; x * y + x * z + y * z == x * y + y * z
--   </pre>
--   
--   For example, the following holds:
--   
--   <pre>
--   <a>path</a> xs == (<a>clique</a> xs :: PreorderRelation Int)
--   </pre>
--   
--   The <a>Show</a> instance produces reflexively and transitively closed
--   expressions:
--   
--   <pre>
--   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)]"
--   </pre>
newtype PreorderRelation a
PreorderRelation :: Relation a -> PreorderRelation a
[fromPreorder] :: PreorderRelation a -> Relation a
instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.PreorderRelation a)
instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a)
instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a)
instance (GHC.Num.Num a, GHC.Classes.Ord 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 preorder relations. Use
--   <a>Algebra.Graph.Class</a> for polymorphic construction and
--   manipulation.
module Algebra.Graph.Relation.Preorder

-- | The <a>PreorderRelation</a> data type represents a <i>binary relation
--   that is both reflexive and transitive</i>. Preorders satisfy all laws
--   of the <a>Preorder</a> type class and, in particular, the
--   <i>self-loop</i> axiom:
--   
--   <pre>
--   <a>vertex</a> x == <a>vertex</a> x * <a>vertex</a> x
--   </pre>
--   
--   and the <i>closure</i> axiom:
--   
--   <pre>
--   y /= <a>empty</a> ==&gt; x * y + x * z + y * z == x * y + y * z
--   </pre>
--   
--   For example, the following holds:
--   
--   <pre>
--   <a>path</a> xs == (<a>clique</a> xs :: PreorderRelation Int)
--   </pre>
--   
--   The <a>Show</a> instance produces reflexively and transitively closed
--   expressions:
--   
--   <pre>
--   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)]"
--   </pre>
data PreorderRelation a

-- | Construct a preorder relation from a <a>Relation</a>. Complexity:
--   <i>O(1)</i> time.
fromRelation :: Relation a -> PreorderRelation a

-- | Extract the underlying relation. Complexity: <i>O(n * m * log(m))</i>
--   time.
toRelation :: Ord a => PreorderRelation a -> Relation a


-- | An abstract implementation of reflexive binary relations. Use
--   <a>Algebra.Graph.Class</a> for polymorphic construction and
--   manipulation.
module Algebra.Graph.Relation.Reflexive

-- | The <a>ReflexiveRelation</a> data type represents a <i>reflexive
--   binary relation</i> over a set of elements. Reflexive relations
--   satisfy all laws of the <a>Reflexive</a> type class and, in
--   particular, the <i>self-loop</i> axiom:
--   
--   <pre>
--   <a>vertex</a> x == <a>vertex</a> x * <a>vertex</a> x
--   </pre>
--   
--   The <a>Show</a> instance produces reflexively closed expressions:
--   
--   <pre>
--   show (1     :: ReflexiveRelation Int) == "edge 1 1"
--   show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"
--   </pre>
data ReflexiveRelation a

-- | Construct a reflexive relation from a <a>Relation</a>. Complexity:
--   <i>O(1)</i> time.
fromRelation :: Relation a -> ReflexiveRelation a

-- | Extract the underlying relation. Complexity: <i>O(n*log(m))</i> time.
toRelation :: Ord a => ReflexiveRelation a -> Relation a


-- | An abstract implementation of symmetric binary relations. Use
--   <a>Algebra.Graph.Class</a> for polymorphic construction and
--   manipulation.
module Algebra.Graph.Relation.Symmetric

-- | The <a>SymmetricRelation</a> data type represents a <i>symmetric
--   binary relation</i> over a set of elements. Symmetric relations
--   satisfy all laws of the <a>Undirected</a> type class and, in
--   particular, the commutativity of connect:
--   
--   <pre>
--   <a>connect</a> x y == <a>connect</a> y x
--   </pre>
--   
--   The <a>Show</a> instance produces symmetrically closed expressions:
--   
--   <pre>
--   show (1     :: SymmetricRelation Int) == "vertex 1"
--   show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"
--   </pre>
data SymmetricRelation a

-- | Construct a symmetric relation from a <a>Relation</a>. Complexity:
--   <i>O(1)</i> time.
fromRelation :: Relation a -> SymmetricRelation a

-- | Extract the underlying relation. Complexity: <i>O(m*log(m))</i> time.
toRelation :: Ord a => SymmetricRelation a -> Relation a

-- | The set of <i>neighbours</i> of an element <tt>x</tt> is the set of
--   elements that are related to it, i.e. <tt>neighbours x == { a | aRx
--   }</tt>. In the context of undirected graphs, this corresponds to the
--   set of <i>adjacent</i> vertices of vertex <tt>x</tt>.
--   
--   <pre>
--   neighbours x <a>empty</a>      == Set.<a>empty</a>
--   neighbours x (<a>vertex</a> x) == Set.<a>empty</a>
--   neighbours x (<a>edge</a> x y) == Set.<a>fromList</a> [y]
--   neighbours y (<a>edge</a> x y) == Set.<a>fromList</a> [x]
--   </pre>
neighbours :: Ord a => a -> SymmetricRelation a -> Set a


-- | An abstract implementation of transitive binary relations. Use
--   <a>Algebra.Graph.Class</a> for polymorphic construction and
--   manipulation.
module Algebra.Graph.Relation.Transitive

-- | The <a>TransitiveRelation</a> data type represents a <i>transitive
--   binary relation</i> over a set of elements. Transitive relations
--   satisfy all laws of the <a>Transitive</a> type class and, in
--   particular, the <i>closure</i> axiom:
--   
--   <pre>
--   y /= <a>empty</a> ==&gt; x * y + x * z + y * z == x * y + y * z
--   </pre>
--   
--   For example, the following holds:
--   
--   <pre>
--   <a>path</a> xs == (<a>clique</a> xs :: TransitiveRelation Int)
--   </pre>
--   
--   The <a>Show</a> instance produces transitively closed expressions:
--   
--   <pre>
--   show (1 * 2         :: TransitiveRelation Int) == "edge 1 2"
--   show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"
--   </pre>
data TransitiveRelation a

-- | Construct a transitive relation from a <a>Relation</a>. Complexity:
--   <i>O(1)</i> time.
fromRelation :: Relation a -> TransitiveRelation a

-- | Extract the underlying relation. Complexity: <i>O(n * m * log(m))</i>
--   time.
toRelation :: Ord a => TransitiveRelation a -> Relation a
