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


-- | A graph library offering mutable, immutable, and inductive graphs
--   
--   This library provides mutable (in ST or IO), immutable, and inductive
--   graphs. There are multiple graphs implementations provided to support
--   different use cases and time/space tradeoffs. It is a design goal of
--   haggle to be flexible and allow users to "pay as they go". Node and
--   edge labels are optional. Haggle also aims to be safer than fgl: there
--   are no partial functions in the API.
@package haggle
@version 0.2

module Data.Graph.Haggle.Classes

-- | An abstract representation of a vertex.
--   
--   Note that the representation is currently exposed. Do not rely on
--   this, as it is subject to change.
data Vertex
vertexId :: Vertex -> Int

-- | An edge between two vertices.
data Edge
edgeSource :: Edge -> Vertex
edgeDest :: Edge -> Vertex

-- | The interface supported by a mutable graph.
class MGraph g where {
    
    -- | The type generated by <a>freeze</a>ing a mutable graph
    type family ImmutableGraph g;
}

-- | List all of the vertices in the graph.
getVertices :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m [Vertex]

-- | List the successors for the given <a>Vertex</a>.
getSuccessors :: (MGraph g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Vertex]

-- | Get all of the <a>Edge</a>s with the given <a>Vertex</a> as their
--   source.
getOutEdges :: (MGraph g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Edge]

-- | Return the number of vertices in the graph
countVertices :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m Int

-- | Return the number of edges in the graph
countEdges :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m Int

-- | Edge existence test; this has a default implementation, but can be
--   overridden if an implementation can support a better-than-linear
--   version.
checkEdgeExists :: (MGraph g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> m Bool

-- | Freeze the mutable graph into an immutable graph.
freeze :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m (ImmutableGraph g)
class (MGraph g) => MAddEdge g

-- | Add a new <a>Edge</a> to the graph from <tt>src</tt> to <tt>dst</tt>.
--   If either the source or destination is not in the graph, returns
--   Nothing. Otherwise, the <a>Edge</a> reference is returned.
addEdge :: (MAddEdge g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> m (Maybe Edge)
class (MGraph g) => MAddVertex g

-- | Add a new <a>Vertex</a> to the graph, returning its handle.
addVertex :: (MAddVertex g, PrimMonad m, MonadRef m) => g m -> m Vertex

-- | An interface for graphs that allow vertex and edge removal. Note that
--   implementations are not required to reclaim storage from removed
--   vertices (just make them inaccessible).
class (MGraph g) => MRemovable g
removeVertex :: (MRemovable g, PrimMonad m, MonadRef m) => g m -> Vertex -> m ()
removeEdgesBetween :: (MRemovable g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> m ()
removeEdge :: (MRemovable g, PrimMonad m, MonadRef m) => g m -> Edge -> m ()

-- | An interface for graphs that support looking at predecessor (incoming
--   edges) efficiently.
class (MGraph g) => MBidirectional g
getPredecessors :: (MBidirectional g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Vertex]
getInEdges :: (MBidirectional g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Edge]
class (MGraph g) => MLabeledEdge g where {
    type family MEdgeLabel g;
}
getEdgeLabel :: (MLabeledEdge g, PrimMonad m, MonadRef m) => g m -> Edge -> m (Maybe (MEdgeLabel g))
unsafeGetEdgeLabel :: (MLabeledEdge g, PrimMonad m, MonadRef m) => g m -> Edge -> m (MEdgeLabel g)
addLabeledEdge :: (MLabeledEdge g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> MEdgeLabel g -> m (Maybe Edge)
class (MGraph g) => MLabeledVertex g where {
    type family MVertexLabel g;
}
getVertexLabel :: (MLabeledVertex g, PrimMonad m, MonadRef m) => g m -> Vertex -> m (Maybe (MVertexLabel g))
addLabeledVertex :: (MLabeledVertex g, PrimMonad m, MonadRef m) => g m -> MVertexLabel g -> m Vertex
getLabeledVertices :: (MLabeledVertex g, PrimMonad m, MonadRef m) => g m -> m [(Vertex, MVertexLabel g)]

-- | The basic interface of immutable graphs.
class Graph g
vertices :: Graph g => g -> [Vertex]
edges :: Graph g => g -> [Edge]
successors :: Graph g => g -> Vertex -> [Vertex]
outEdges :: Graph g => g -> Vertex -> [Edge]
maxVertexId :: Graph g => g -> Int
isEmpty :: Graph g => g -> Bool

-- | This has a default implementation in terms of <a>outEdges</a>, but is
--   part of the class so that instances can offer a more efficient
--   implementation when possible.
edgesBetween :: Graph g => g -> Vertex -> Vertex -> [Edge]
edgeExists :: Graph g => g -> Vertex -> Vertex -> Bool
class (Graph g) => Thawable g where {
    type family MutableGraph g :: (Type -> Type) -> Type;
}
thaw :: (Thawable g, PrimMonad m, MonadRef m) => g -> m (MutableGraph g m)

-- | The interface for immutable graphs with efficient access to incoming
--   edges.
class (Graph g) => Bidirectional g
predecessors :: Bidirectional g => g -> Vertex -> [Vertex]
inEdges :: Bidirectional g => g -> Vertex -> [Edge]

-- | The interface for immutable graphs with labeled edges.
class (Graph g) => HasEdgeLabel g where {
    type family EdgeLabel g;
}
edgeLabel :: HasEdgeLabel g => g -> Edge -> Maybe (EdgeLabel g)
labeledEdges :: HasEdgeLabel g => g -> [(Edge, EdgeLabel g)]
labeledOutEdges :: HasEdgeLabel g => g -> Vertex -> [(Edge, EdgeLabel g)]

-- | The interface for immutable graphs with labeled vertices.
class (Graph g) => HasVertexLabel g where {
    type family VertexLabel g;
}
vertexLabel :: HasVertexLabel g => g -> Vertex -> Maybe (VertexLabel g)
labeledVertices :: HasVertexLabel g => g -> [(Vertex, VertexLabel g)]
class (HasEdgeLabel g, Bidirectional g) => BidirectionalEdgeLabel g
labeledInEdges :: BidirectionalEdgeLabel g => g -> Vertex -> [(Edge, EdgeLabel g)]
class (Graph g, HasEdgeLabel g, HasVertexLabel g) => InductiveGraph g

-- | The empty inductive graph
emptyGraph :: InductiveGraph g => g

-- | The call
--   
--   <pre>
--   let (c, g') = match g v
--   </pre>
--   
--   decomposes the graph into the <a>Context</a> c of <tt>v</tt> and the
--   rest of the graph <tt>g'</tt>.
match :: InductiveGraph g => g -> Vertex -> Maybe (Context g, g)

-- | Return the context of a <a>Vertex</a>
context :: InductiveGraph g => g -> Vertex -> Maybe (Context g)

-- | Insert a new labeled <a>Vertex</a> into the graph.
insertLabeledVertex :: InductiveGraph g => g -> VertexLabel g -> (Vertex, g)

-- | Must return <a>Nothing</a> if either the source or destination
--   <a>Vertex</a> is not in the graph. Also returns <a>Nothing</a> if the
--   edge already exists and the underlying graph does not support parallel
--   edges.
--   
--   Otherwise return the inserted <a>Edge</a> and updated graph.
insertLabeledEdge :: InductiveGraph g => g -> Vertex -> Vertex -> EdgeLabel g -> Maybe (Edge, g)

-- | Delete the given <a>Edge</a>. In a multigraph, this lets you remove a
--   single parallel edge between two vertices.
deleteEdge :: InductiveGraph g => g -> Edge -> g

-- | Delete all edges between a pair of vertices.
deleteEdgesBetween :: InductiveGraph g => g -> Vertex -> Vertex -> g

-- | Like <a>insertLabeledEdge</a>, but overwrite any existing edges.
--   Equivalent to:
--   
--   <pre>
--   let g' = deleteEdgesBetween g v1 v2
--   in insertLabeledEdge g v1 v2 lbl
--   </pre>
replaceLabeledEdge :: InductiveGraph g => g -> Vertex -> Vertex -> EdgeLabel g -> Maybe (Edge, g)

-- | Remove a <a>Vertex</a> from the graph
deleteVertex :: InductiveGraph g => g -> Vertex -> g

-- | Contexts represent the "context" of a <a>Vertex</a>, which includes
--   the incoming edges of the <a>Vertex</a>, the label of the
--   <a>Vertex</a>, and the outgoing edges of the <a>Vertex</a>.
data Context g
Context :: [(EdgeLabel g, Vertex)] -> VertexLabel g -> [(EdgeLabel g, Vertex)] -> Context g


-- | This graph implementation is a directed (multi-)graph that only tracks
--   successors. This encoding is very compact. It is a multi-graph because
--   it allows parallel edges between vertices. If you require only simple
--   graphs, careful edge insertion is required (or another graph type
--   might be more appropriate).
--   
--   Limitations:
--   
--   <ul>
--   <li>Removing nodes and edges is not currently possible.</li>
--   <li>Predecessors are not accessible</li>
--   <li>Edge existence tests are <i>linear</i> in the number of edges for
--   the source node.</li>
--   </ul>
module Data.Graph.Haggle.Digraph

-- | This is a compact (mutable) directed graph.
data MDigraph m
data Digraph

-- | Create a new empty mutable graph with a small amount of storage
--   reserved for vertices and edges.
newMDigraph :: (PrimMonad m, MonadRef m) => m (MDigraph m)

-- | Create a new empty graph with storage reserved for <tt>szVerts</tt>
--   vertices and <tt>szEdges</tt> edges.
--   
--   <pre>
--   g &lt;- newSizedMDigraph szVerts szEdges
--   </pre>
newSizedMDigraph :: (PrimMonad m, MonadRef m) => Int -> Int -> m (MDigraph m)
instance Control.DeepSeq.NFData Data.Graph.Haggle.Digraph.Digraph
instance Data.Graph.Haggle.Classes.MGraph Data.Graph.Haggle.Digraph.MDigraph
instance Data.Graph.Haggle.Classes.Thawable Data.Graph.Haggle.Digraph.Digraph
instance Data.Graph.Haggle.Classes.Graph Data.Graph.Haggle.Digraph.Digraph
instance Data.Graph.Haggle.Classes.MAddVertex Data.Graph.Haggle.Digraph.MDigraph
instance Data.Graph.Haggle.Classes.MAddEdge Data.Graph.Haggle.Digraph.MDigraph


-- | This graph is an efficient representation of bidirectional graphs with
--   parallel edges.
--   
--   This is in contrast to <a>SimpleBiDigraph</a>, which can only handle
--   simple graphs (i.e., without parallel edges).
--   
--   The representation is slightly less efficient as a result.
module Data.Graph.Haggle.BiDigraph

-- | A mutable bidirectional graph
data MBiDigraph m

-- | An immutable bidirectional graph
data BiDigraph

-- | Allocate a new mutable bidirectional graph with a default size
newMBiDigraph :: (PrimMonad m, MonadRef m) => m (MBiDigraph m)

-- | Allocate a new mutable bidirectional graph with space reserved for
--   nodes and edges. This can be more efficient and avoid resizing.
newSizedMBiDigraph :: (PrimMonad m, MonadRef m) => Int -> Int -> m (MBiDigraph m)
instance Data.Graph.Haggle.Classes.MGraph Data.Graph.Haggle.BiDigraph.MBiDigraph
instance Data.Graph.Haggle.Classes.Thawable Data.Graph.Haggle.BiDigraph.BiDigraph
instance Data.Graph.Haggle.Classes.Graph Data.Graph.Haggle.BiDigraph.BiDigraph
instance Data.Graph.Haggle.Classes.Bidirectional Data.Graph.Haggle.BiDigraph.BiDigraph
instance Data.Graph.Haggle.Classes.MAddVertex Data.Graph.Haggle.BiDigraph.MBiDigraph
instance Data.Graph.Haggle.Classes.MAddEdge Data.Graph.Haggle.BiDigraph.MBiDigraph
instance Data.Graph.Haggle.Classes.MBidirectional Data.Graph.Haggle.BiDigraph.MBiDigraph


-- | This graph is based on the implementation in fgl (using big-endian
--   patricia-tries -- IntMap).
--   
--   This formulation does not support parallel edges.
module Data.Graph.Haggle.PatriciaTree

-- | The <a>PatriciaTree</a> is a graph implementing the
--   <a>InductiveGraph</a> interface (as well as the other immutable graph
--   interfaces). It is based on the graph type provided by fgl.
--   
--   Inductive graphs support more interesting decompositions than the
--   other graph interfaces in this library, at the cost of less compact
--   representations and some additional overhead on some operations, as
--   most must go through the <a>match</a> operator.
--   
--   This graph type is most useful for incremental construction in pure
--   code. It also supports node removal from pure code.
data PatriciaTree nl el
instance (Control.DeepSeq.NFData nl, Control.DeepSeq.NFData el) => Control.DeepSeq.NFData (Data.Graph.Haggle.PatriciaTree.PatriciaTree nl el)
instance Data.Bifunctor.Bifunctor Data.Graph.Haggle.PatriciaTree.PatriciaTree
instance Data.Graph.Haggle.Classes.Graph (Data.Graph.Haggle.PatriciaTree.PatriciaTree nl el)
instance Data.Graph.Haggle.Classes.HasEdgeLabel (Data.Graph.Haggle.PatriciaTree.PatriciaTree nl el)
instance Data.Graph.Haggle.Classes.HasVertexLabel (Data.Graph.Haggle.PatriciaTree.PatriciaTree nl el)
instance Data.Graph.Haggle.Classes.Bidirectional (Data.Graph.Haggle.PatriciaTree.PatriciaTree nl el)
instance Data.Graph.Haggle.Classes.BidirectionalEdgeLabel (Data.Graph.Haggle.PatriciaTree.PatriciaTree nl el)
instance Data.Graph.Haggle.Classes.InductiveGraph (Data.Graph.Haggle.PatriciaTree.PatriciaTree nl el)
instance (Control.DeepSeq.NFData nl, Control.DeepSeq.NFData el) => Control.DeepSeq.NFData (Data.Graph.Haggle.PatriciaTree.Ctx nl el)


-- | This is a simple graph (it does not allow parallel edges). To support
--   this efficiently, it is less compact than <tt>Digraph</tt> or
--   <a>BiDigraph</a>. As a consequence, edge existence tests are efficient
--   (logarithmic in the number of edges leaving the source vertex).
module Data.Graph.Haggle.SimpleBiDigraph
data MSimpleBiDigraph m
data SimpleBiDigraph
newMSimpleBiDigraph :: (PrimMonad m, MonadRef m) => m (MSimpleBiDigraph m)
newSizedMSimpleBiDigraph :: (PrimMonad m, MonadRef m) => Int -> Int -> m (MSimpleBiDigraph m)
instance Control.DeepSeq.NFData Data.Graph.Haggle.SimpleBiDigraph.SimpleBiDigraph
instance Data.Graph.Haggle.Classes.MGraph Data.Graph.Haggle.SimpleBiDigraph.MSimpleBiDigraph
instance Data.Graph.Haggle.Classes.Thawable Data.Graph.Haggle.SimpleBiDigraph.SimpleBiDigraph
instance Data.Graph.Haggle.Classes.Graph Data.Graph.Haggle.SimpleBiDigraph.SimpleBiDigraph
instance Data.Graph.Haggle.Classes.Bidirectional Data.Graph.Haggle.SimpleBiDigraph.SimpleBiDigraph
instance Data.Graph.Haggle.Classes.MAddVertex Data.Graph.Haggle.SimpleBiDigraph.MSimpleBiDigraph
instance Data.Graph.Haggle.Classes.MAddEdge Data.Graph.Haggle.SimpleBiDigraph.MSimpleBiDigraph
instance Data.Graph.Haggle.Classes.MBidirectional Data.Graph.Haggle.SimpleBiDigraph.MSimpleBiDigraph


-- | This is a simple module to handle a common pattern: constructing
--   graphs where vertex labels map uniquely to vertices.
--   
--   The primary functions in this module are <a>vertexForLabel</a> and
--   <a>vertexForLabelRef</a>, which take a vertex label and return the
--   <a>Vertex</a> for that label (allocating a new <a>Vertex</a>) if
--   necessary. The first of those functions explicitly threads the mapping
--   as inputs and outputs. The second manages a mutable ref side-by-side
--   with the underlying graph.
--   
--   After the graph is fully constructed, this mapping is often still
--   useful.
module Data.Graph.Haggle.VertexMap

-- | A simple mapping from labels to their <a>Vertex</a>
data VertexMap nl
emptyVertexMap :: VertexMap nl

-- | <pre>
--   (v, m') &lt;- vertexForLabel g m lbl
--   </pre>
--   
--   Looks up the <a>Vertex</a> for <tt>lbl</tt> in <tt>g</tt>. If no
--   <a>Vertex</a> in <tt>g</tt> has that label, a new <a>Vertex</a> is
--   allocated and returned. The updated vertex mapping <tt>m'</tt> is
--   returned, too.
vertexForLabel :: (MLabeledVertex g, Ord (MVertexLabel g), PrimMonad m, MonadRef m) => g m -> VertexMap (MVertexLabel g) -> MVertexLabel g -> m (Vertex, VertexMap (MVertexLabel g))

-- | A pure lookup to convert a <a>Vertex</a> label into a <a>Vertex</a>.
--   If the label is not in the graph, returns <a>Nothing</a>.
lookupVertexForLabel :: Ord nl => nl -> VertexMap nl -> Maybe Vertex

-- | Build a <a>VertexMap</a> from a <a>Graph</a> with <a>Vertex</a>
--   labels.
vertexMapFromGraph :: (HasVertexLabel g, Ord (VertexLabel g)) => g -> VertexMap (VertexLabel g)

-- | A <a>VertexMap</a> wrapped up in a mutable ref for possibly easier
--   access in <a>vertexMapFromRef</a>.
data VertexMapRef nl m

-- | Allocate a new <a>VertexMap</a> buried in a mutable ref.
newVertexMapRef :: (PrimMonad m, MonadRef m) => m (VertexMapRef nl m)

-- | Just like <a>vertexForLabel</a>, but holding the mapping in a ref
--   instead of threading it. Usage is simpler:
--   
--   <pre>
--   v &lt;- vertexForLabelRef g m lbl
--   </pre>
vertexForLabelRef :: (MLabeledVertex g, Ord (MVertexLabel g), PrimMonad m, MonadRef m) => g m -> VertexMapRef (MVertexLabel g) m -> MVertexLabel g -> m Vertex

-- | Extract the pure <a>VertexMap</a> from the mutable ref. This is useful
--   to retain the mapping after the graph is fully constructed.
vertexMapFromRef :: (PrimMonad m, MonadRef m) => VertexMapRef nl m -> m (VertexMap nl)
instance Control.DeepSeq.NFData nl => Control.DeepSeq.NFData (Data.Graph.Haggle.VertexMap.VertexMap nl)


-- | An adapter to create graphs with labeled vertices and unlabeled edges.
--   
--   See <tt>LabeledGraph</tt> for an overview. The only significant
--   difference is that this graph only supports adding unlabeled edges,
--   and thus you must use <a>addEdge</a> instead of
--   <tt>addLabeledEdge</tt>.
module Data.Graph.Haggle.VertexLabelAdapter
data VertexLabeledMGraph g nl m
data VertexLabeledGraph g nl
newVertexLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => m (g m) -> m (VertexLabeledMGraph g nl m)
newSizedVertexLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => (Int -> Int -> m (g m)) -> Int -> Int -> m (VertexLabeledMGraph g nl m)
mapVertexLabel :: VertexLabeledGraph g nl -> (nl -> nl') -> VertexLabeledGraph g nl'

-- | Build a new (immutable) graph from a list of edges. Edges are defined
--   by pairs of <i>node labels</i>. A new <tt>Vertex</tt> will be
--   allocated for each node label.
--   
--   The type of the constructed graph is controlled by the first argument,
--   which is a constructor for a mutable graph.
--   
--   Example:
--   
--   <pre>
--   import Data.Graph.Haggle.VertexLabelAdapter
--   import Data.Graph.Haggle.SimpleBiDigraph
--   
--   let g = fromEdgeList newMSimpleBiDigraph [(0,1), (1,2), (2,3), (3,0)]
--   </pre>
--   
--   <tt>g</tt> has type SimpleBiDigraph.
--   
--   An alternative that is fully polymorphic in the return type would be
--   possible, but it would require type annotations on the result of
--   <a>fromEdgeList</a>, which could be very annoying.
fromEdgeList :: (MGraph g, MAddEdge g, MAddVertex g, Ord nl) => (forall s. ST s (g (ST s))) -> [(nl, nl)] -> (VertexLabeledGraph (ImmutableGraph g) nl, VertexMap nl)
instance (Control.DeepSeq.NFData g, Control.DeepSeq.NFData nl) => Control.DeepSeq.NFData (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledGraph g nl)
instance Data.Graph.Haggle.Classes.Graph g => Data.Graph.Haggle.Classes.Graph (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledGraph g nl)
instance Data.Graph.Haggle.Classes.Thawable g => Data.Graph.Haggle.Classes.Thawable (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledGraph g nl)
instance Data.Graph.Haggle.Classes.Bidirectional g => Data.Graph.Haggle.Classes.Bidirectional (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledGraph g nl)
instance Data.Graph.Haggle.Classes.Graph g => Data.Graph.Haggle.Classes.HasVertexLabel (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledGraph g nl)
instance Data.Graph.Haggle.Classes.MGraph g => Data.Graph.Haggle.Classes.MGraph (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledMGraph g nl)
instance Data.Graph.Haggle.Classes.MAddVertex g => Data.Graph.Haggle.Classes.MLabeledVertex (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledMGraph g nl)
instance Data.Graph.Haggle.Classes.MBidirectional g => Data.Graph.Haggle.Classes.MBidirectional (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledMGraph g nl)
instance Data.Graph.Haggle.Classes.MAddEdge g => Data.Graph.Haggle.Classes.MAddEdge (Data.Graph.Haggle.VertexLabelAdapter.VertexLabeledMGraph g nl)

module Data.Graph.Haggle.LabelAdapter

-- | An adapter adding support for both vertex and edge labels for mutable
--   graphs.
data LabeledMGraph g nl el m

-- | An adapter adding support for both vertex and edge labels for
--   immutable graphs.
data LabeledGraph g nl el
newLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => m (g m) -> m (LabeledMGraph g nl el m)
newSizedLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => (Int -> Int -> m (g m)) -> Int -> Int -> m (LabeledMGraph g nl el m)
mapEdgeLabel :: LabeledGraph g nl el -> (el -> el') -> LabeledGraph g nl el'
mapVertexLabel :: LabeledGraph g nl el -> (nl -> nl') -> LabeledGraph g nl' el

-- | Construct a graph from a labeled list of edges. The node endpoint
--   values are used as vertex labels, and the last element of the triple
--   is used as an edge label.
fromLabeledEdgeList :: (Ord nl, MGraph g, MAddVertex g, MAddEdge g) => (forall s. ST s (g (ST s))) -> [(nl, nl, el)] -> (LabeledGraph (ImmutableGraph g) nl el, VertexMap nl)


-- | This adapter adds edge labels (but not vertex labels) to graphs.
--   
--   It only supports <a>addLabeledEdge</a>, not <tt>addEdge</tt>. See
--   <tt>LabeledGraph</tt> for more details.
module Data.Graph.Haggle.EdgeLabelAdapter
data EdgeLabeledMGraph g el s
data EdgeLabeledGraph g el
newEdgeLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => m (g m) -> m (EdgeLabeledMGraph g nl m)
newSizedEdgeLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => (Int -> Int -> m (g m)) -> Int -> Int -> m (EdgeLabeledMGraph g el m)
mapEdgeLabel :: EdgeLabeledGraph g el -> (el -> el') -> EdgeLabeledGraph g el'
instance (Control.DeepSeq.NFData g, Control.DeepSeq.NFData el) => Control.DeepSeq.NFData (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledGraph g el)
instance Data.Graph.Haggle.Classes.Graph g => Data.Graph.Haggle.Classes.Graph (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledGraph g el)
instance Data.Graph.Haggle.Classes.Thawable g => Data.Graph.Haggle.Classes.Thawable (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledGraph g el)
instance Data.Graph.Haggle.Classes.Bidirectional g => Data.Graph.Haggle.Classes.Bidirectional (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledGraph g el)
instance Data.Graph.Haggle.Classes.Bidirectional g => Data.Graph.Haggle.Classes.BidirectionalEdgeLabel (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledGraph g el)
instance Data.Graph.Haggle.Classes.Graph g => Data.Graph.Haggle.Classes.HasEdgeLabel (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledGraph g el)
instance Data.Graph.Haggle.Classes.MGraph g => Data.Graph.Haggle.Classes.MGraph (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledMGraph g el)
instance Data.Graph.Haggle.Classes.MBidirectional g => Data.Graph.Haggle.Classes.MBidirectional (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledMGraph g el)
instance Data.Graph.Haggle.Classes.MAddVertex g => Data.Graph.Haggle.Classes.MAddVertex (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledMGraph g el)
instance Data.Graph.Haggle.Classes.MAddEdge g => Data.Graph.Haggle.Classes.MLabeledEdge (Data.Graph.Haggle.EdgeLabelAdapter.EdgeLabeledMGraph g el)


-- | Haggle is a Haskell graph library.
--   
--   The main idea behind haggle is that graphs are constructed with
--   mutation (either in <a>IO</a> or <tt>ST</tt>). After the graph is
--   constructed, it is frozen into an immutable graph. This split is a
--   major difference between haggle and the other major Haskell graph
--   library, fgl, which is formulated in terms of inductive graphs that
--   can always be modified in a purely-functional way. Supporting the
--   inductive graph interface severely limits implementation choices and
--   optimization opportunities, so haggle tries a different approach.
--   
--   Furthermore, the types of vertices (nodes in FGL) and edges are held
--   as abstract in haggle, allowing for changes later if necessary. That
--   said, changes are unlikely and the representations are exposed (with
--   no guarantees) through an Internal module.
--   
--   Enough talk, example time:
--   
--   <pre>
--   import Control.Monad ( replicateM )
--   import Data.Graph.Haggle
--   import Data.Graph.Haggle.Digraph
--   import Data.Graph.Haggle.Algorithms.DFS
--   
--   main :: IO ()
--   main = do
--     g &lt;- newMDigraph
--     [v0, v1, v2] &lt;- replicateM 3 (addVertex g)
--     e1 &lt;- addEdge g v0 v1
--     e2 &lt;- addEdge g v1 v2
--     gi &lt;- freeze g
--     print (dfs gi v1) -- [V 1, V 2] since the first vertex is 0
--   </pre>
--   
--   The example builds a graph with three vertices and performs a DFS from
--   the middle vertex. Note that the DFS algorithm is implemented on
--   immutable graphs, so we freeze the mutable graph before traversing it.
--   The graph type in this example is a directed graph.
--   
--   There are other graph variants that support efficient access to
--   predecessor edges: bidirectional graphs. There are also simple graph
--   variants that prohibit parallel edges.
--   
--   The core graph implementations support only vertices and edges.
--   <i>Adapters</i> add support for <tt>Vertex</tt> and <tt>Edge</tt>
--   labels. See <tt>EdgeLabelAdapter</tt>, <tt>VertexLabelAdapter</tt>,
--   and <tt>LabelAdapter</tt> (which supports both). This split allows the
--   core implementations of graphs and graph algorithms to be fast and
--   compact (since they do not need to allocate storage for or manipulate
--   labels). The adapters store labels on the side, similarly to the
--   property maps of Boost Graph Library. Also note that the adapters are
--   strongly typed. To add edges to a graph with edge labels, you must
--   call <a>addLabeledEdge</a> instead of <a>addEdge</a>. Likewise for
--   graphs with vertex labels and
--   <a>addLabeledVertex</a>/<a>addVertex</a>. This requirement is enforced
--   in the type system so that labels cannot become out-of-sync with the
--   structure of the graph. The adapters each work with any type of
--   underlying graph.
module Data.Graph.Haggle

-- | This is a compact (mutable) directed graph.
data MDigraph m

-- | Create a new empty mutable graph with a small amount of storage
--   reserved for vertices and edges.
newMDigraph :: (PrimMonad m, MonadRef m) => m (MDigraph m)

-- | Create a new empty graph with storage reserved for <tt>szVerts</tt>
--   vertices and <tt>szEdges</tt> edges.
--   
--   <pre>
--   g &lt;- newSizedMDigraph szVerts szEdges
--   </pre>
newSizedMDigraph :: (PrimMonad m, MonadRef m) => Int -> Int -> m (MDigraph m)

-- | A mutable bidirectional graph
data MBiDigraph m

-- | Allocate a new mutable bidirectional graph with a default size
newMBiDigraph :: (PrimMonad m, MonadRef m) => m (MBiDigraph m)

-- | Allocate a new mutable bidirectional graph with space reserved for
--   nodes and edges. This can be more efficient and avoid resizing.
newSizedMBiDigraph :: (PrimMonad m, MonadRef m) => Int -> Int -> m (MBiDigraph m)
data MSimpleBiDigraph m
newMSimpleBiDigraph :: (PrimMonad m, MonadRef m) => m (MSimpleBiDigraph m)
newSizedMSimpleBiDigraph :: (PrimMonad m, MonadRef m) => Int -> Int -> m (MSimpleBiDigraph m)
data EdgeLabeledMGraph g el s
newEdgeLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => m (g m) -> m (EdgeLabeledMGraph g nl m)
newSizedEdgeLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => (Int -> Int -> m (g m)) -> Int -> Int -> m (EdgeLabeledMGraph g el m)
data VertexLabeledMGraph g nl m
newVertexLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => m (g m) -> m (VertexLabeledMGraph g nl m)
newSizedVertexLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => (Int -> Int -> m (g m)) -> Int -> Int -> m (VertexLabeledMGraph g nl m)

-- | An adapter adding support for both vertex and edge labels for mutable
--   graphs.
data LabeledMGraph g nl el m
newLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => m (g m) -> m (LabeledMGraph g nl el m)
newSizedLabeledGraph :: (MGraph g, PrimMonad m, MonadRef m) => (Int -> Int -> m (g m)) -> Int -> Int -> m (LabeledMGraph g nl el m)
data Digraph

-- | An immutable bidirectional graph
data BiDigraph
data SimpleBiDigraph
data EdgeLabeledGraph g el
data VertexLabeledGraph g nl

-- | Build a new (immutable) graph from a list of edges. Edges are defined
--   by pairs of <i>node labels</i>. A new <tt>Vertex</tt> will be
--   allocated for each node label.
--   
--   The type of the constructed graph is controlled by the first argument,
--   which is a constructor for a mutable graph.
--   
--   Example:
--   
--   <pre>
--   import Data.Graph.Haggle.VertexLabelAdapter
--   import Data.Graph.Haggle.SimpleBiDigraph
--   
--   let g = fromEdgeList newMSimpleBiDigraph [(0,1), (1,2), (2,3), (3,0)]
--   </pre>
--   
--   <tt>g</tt> has type SimpleBiDigraph.
--   
--   An alternative that is fully polymorphic in the return type would be
--   possible, but it would require type annotations on the result of
--   <a>fromEdgeList</a>, which could be very annoying.
fromEdgeList :: (MGraph g, MAddEdge g, MAddVertex g, Ord nl) => (forall s. ST s (g (ST s))) -> [(nl, nl)] -> (VertexLabeledGraph (ImmutableGraph g) nl, VertexMap nl)

-- | An adapter adding support for both vertex and edge labels for
--   immutable graphs.
data LabeledGraph g nl el

-- | Construct a graph from a labeled list of edges. The node endpoint
--   values are used as vertex labels, and the last element of the triple
--   is used as an edge label.
fromLabeledEdgeList :: (Ord nl, MGraph g, MAddVertex g, MAddEdge g) => (forall s. ST s (g (ST s))) -> [(nl, nl, el)] -> (LabeledGraph (ImmutableGraph g) nl el, VertexMap nl)

-- | The <a>PatriciaTree</a> is a graph implementing the
--   <a>InductiveGraph</a> interface (as well as the other immutable graph
--   interfaces). It is based on the graph type provided by fgl.
--   
--   Inductive graphs support more interesting decompositions than the
--   other graph interfaces in this library, at the cost of less compact
--   representations and some additional overhead on some operations, as
--   most must go through the <a>match</a> operator.
--   
--   This graph type is most useful for incremental construction in pure
--   code. It also supports node removal from pure code.
data PatriciaTree nl el

-- | An abstract representation of a vertex.
--   
--   Note that the representation is currently exposed. Do not rely on
--   this, as it is subject to change.
data Vertex
vertexId :: Vertex -> Int

-- | An edge between two vertices.
data Edge
edgeSource :: Edge -> Vertex
edgeDest :: Edge -> Vertex
getVertices :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m [Vertex]
getSuccessors :: (MGraph g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Vertex]
getOutEdges :: (MGraph g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Edge]
countVertices :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m Int
countEdges :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m Int
checkEdgeExists :: (MGraph g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> m Bool
freeze :: (MGraph g, PrimMonad m, MonadRef m) => g m -> m (ImmutableGraph g)
addVertex :: (MAddVertex g, PrimMonad m, MonadRef m) => g m -> m Vertex
addEdge :: (MAddEdge g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> m (Maybe Edge)
getEdgeLabel :: (MLabeledEdge g, PrimMonad m, MonadRef m) => g m -> Edge -> m (Maybe (MEdgeLabel g))
unsafeGetEdgeLabel :: (MLabeledEdge g, PrimMonad m, MonadRef m) => g m -> Edge -> m (MEdgeLabel g)
addLabeledEdge :: (MLabeledEdge g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> MEdgeLabel g -> m (Maybe Edge)
getVertexLabel :: (MLabeledVertex g, PrimMonad m, MonadRef m) => g m -> Vertex -> m (Maybe (MVertexLabel g))
addLabeledVertex :: (MLabeledVertex g, PrimMonad m, MonadRef m) => g m -> MVertexLabel g -> m Vertex
getLabeledVertices :: (MLabeledVertex g, PrimMonad m, MonadRef m) => g m -> m [(Vertex, MVertexLabel g)]
removeVertex :: (MRemovable g, PrimMonad m, MonadRef m) => g m -> Vertex -> m ()
removeEdgesBetween :: (MRemovable g, PrimMonad m, MonadRef m) => g m -> Vertex -> Vertex -> m ()
removeEdge :: (MRemovable g, PrimMonad m, MonadRef m) => g m -> Edge -> m ()
getPredecessors :: (MBidirectional g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Vertex]
getInEdges :: (MBidirectional g, PrimMonad m, MonadRef m) => g m -> Vertex -> m [Edge]
mapEdgeLabel :: LabeledGraph g nl el -> (el -> el') -> LabeledGraph g nl el'
mapVertexLabel :: LabeledGraph g nl el -> (nl -> nl') -> LabeledGraph g nl' el
vertices :: Graph g => g -> [Vertex]
edges :: Graph g => g -> [Edge]
successors :: Graph g => g -> Vertex -> [Vertex]
outEdges :: Graph g => g -> Vertex -> [Edge]
edgesBetween :: Graph g => g -> Vertex -> Vertex -> [Edge]
edgeExists :: Graph g => g -> Vertex -> Vertex -> Bool
isEmpty :: Graph g => g -> Bool
thaw :: (Thawable g, PrimMonad m, MonadRef m) => g -> m (MutableGraph g m)
predecessors :: Bidirectional g => g -> Vertex -> [Vertex]
inEdges :: Bidirectional g => g -> Vertex -> [Edge]
edgeLabel :: HasEdgeLabel g => g -> Edge -> Maybe (EdgeLabel g)
labeledEdges :: HasEdgeLabel g => g -> [(Edge, EdgeLabel g)]
labeledOutEdges :: HasEdgeLabel g => g -> Vertex -> [(Edge, EdgeLabel g)]
vertexLabel :: HasVertexLabel g => g -> Vertex -> Maybe (VertexLabel g)
labeledVertices :: HasVertexLabel g => g -> [(Vertex, VertexLabel g)]
labeledInEdges :: BidirectionalEdgeLabel g => g -> Vertex -> [(Edge, EdgeLabel g)]
emptyGraph :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g
match :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> Vertex -> Maybe (Context g, g)
context :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> Vertex -> Maybe (Context g)
insertLabeledVertex :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> VertexLabel g -> (Vertex, g)
insertLabeledEdge :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> Vertex -> Vertex -> EdgeLabel g -> Maybe (Edge, g)
deleteEdge :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> Edge -> g
deleteEdgesBetween :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> Vertex -> Vertex -> g
replaceLabeledEdge :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> Vertex -> Vertex -> EdgeLabel g -> Maybe (Edge, g)
deleteVertex :: (InductiveGraph g, Graph g, HasEdgeLabel g, HasVertexLabel g) => g -> Vertex -> g

-- | Contexts represent the "context" of a <a>Vertex</a>, which includes
--   the incoming edges of the <a>Vertex</a>, the label of the
--   <a>Vertex</a>, and the outgoing edges of the <a>Vertex</a>.
data Context g
Context :: [(EdgeLabel g, Vertex)] -> VertexLabel g -> [(EdgeLabel g, Vertex)] -> Context g

-- | The interface supported by a mutable graph.
class MGraph g

-- | The type generated by <a>freeze</a>ing a mutable graph
type family ImmutableGraph g
class (MGraph g) => MAddVertex g
class (MGraph g) => MAddEdge g
class (MGraph g) => MLabeledEdge g
type family MEdgeLabel g
class (MGraph g) => MLabeledVertex g
type family MVertexLabel g

-- | An interface for graphs that allow vertex and edge removal. Note that
--   implementations are not required to reclaim storage from removed
--   vertices (just make them inaccessible).
class (MGraph g) => MRemovable g

-- | An interface for graphs that support looking at predecessor (incoming
--   edges) efficiently.
class (MGraph g) => MBidirectional g

-- | The basic interface of immutable graphs.
class Graph g
class (Graph g) => Thawable g
type family MutableGraph g :: (Type -> Type) -> Type

-- | The interface for immutable graphs with efficient access to incoming
--   edges.
class (Graph g) => Bidirectional g

-- | The interface for immutable graphs with labeled edges.
class (Graph g) => HasEdgeLabel g
type family EdgeLabel g

-- | The interface for immutable graphs with labeled vertices.
class (Graph g) => HasVertexLabel g
type family VertexLabel g
class (HasEdgeLabel g, Bidirectional g) => BidirectionalEdgeLabel g
class (Graph g, HasEdgeLabel g, HasVertexLabel g) => InductiveGraph g


-- | Depth-first search and derived operations.
--   
--   All of the search variants take a list of <a>Vertex</a> that serves as
--   roots for the search.
--   
--   The [x] variants (<a>xdfsWith</a> and <a>xdffWith</a>) are the most
--   general and are fully configurable in direction and action. They take
--   a "direction" function that tells the search what vertices are next
--   from the current <a>Vertex</a>. They also take a summarization
--   function to convert a <a>Vertex</a> into some other value. This could
--   be <a>id</a> or a function to extract a label, if supported by your
--   graph type.
--   
--   The [r] variants are reverse searches, while the [u] variants are
--   undirected.
--   
--   A depth-first forest is a collection (list) of depth-first trees. A
--   depth-first tree is an n-ary tree rooted at a vertex that contains the
--   vertices reached in a depth-first search from that root. The edges in
--   the tree are a subset of the edges in the graph.
module Data.Graph.Haggle.Algorithms.DFS

-- | The most general DFS
xdfsWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [c]

-- | Forward parameterized DFS
dfsWith :: Graph g => g -> (Vertex -> c) -> [Vertex] -> [c]

-- | Forward DFS
dfs :: Graph g => g -> [Vertex] -> [Vertex]

-- | Reverse parameterized DFS
rdfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c]

-- | Reverse DFS
rdfs :: Bidirectional g => g -> [Vertex] -> [Vertex]

-- | Undirected parameterized DFS. This variant follows both incoming and
--   outgoing edges from each <a>Vertex</a>.
udfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c]

-- | Undirected DFS
udfs :: Bidirectional g => g -> [Vertex] -> [Vertex]

-- | The most general depth-first forest.
xdffWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [Tree c]
dffWith :: Graph g => g -> (Vertex -> c) -> [Vertex] -> [Tree c]
dff :: Graph g => g -> [Vertex] -> [Tree Vertex]
rdffWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [Tree c]
rdff :: Bidirectional g => g -> [Vertex] -> [Tree Vertex]
udffWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [Tree c]
udff :: Bidirectional g => g -> [Vertex] -> [Tree Vertex]

-- | Return a list of each connected component in the graph
components :: Bidirectional g => g -> [[Vertex]]

-- | The number of components in the graph
noComponents :: Bidirectional g => g -> Int

-- | True if there is only a single component in the graph.
isConnected :: Bidirectional g => g -> Bool

-- | Topologically sort the graph; the input must be a DAG.
topsort :: Graph g => g -> [Vertex]

-- | Return a list of each <i>strongly-connected component</i> in the
--   graph. In a strongly-connected component, every vertex is reachable
--   from every other vertex.
scc :: Bidirectional g => g -> [[Vertex]]

-- | Compute the set of vertices reachable from a root <a>Vertex</a>.
reachable :: Graph g => Vertex -> g -> [Vertex]


-- | Compute the dominators in a graph from a root node.
--   
--   The set of dominators for a <a>Vertex</a> in a graph is always with
--   regard to a <tt>root</tt> <a>Vertex</a>, given as input to the
--   algorithm. <a>Vertex</a> <tt>d</tt> dominates <a>Vertex</a> <tt>v</tt>
--   if every path from the <tt>root</tt> to <tt>v</tt> must go through
--   <tt>d</tt>. <tt>d</tt> strictly dominates <tt>v</tt> if <tt>d</tt>
--   dominates <tt>v</tt> and is not <tt>v</tt>. The immediate dominator of
--   <tt>v</tt> is the unique <a>Vertex</a> that strictly dominates
--   <tt>v</tt> and does not strictly dominate any other <a>Vertex</a> that
--   dominates <tt>v</tt>.
--   
--   This implementation is ported from FGL
--   (<a>http://hackage.haskell.org/package/fgl</a>) and is substantially
--   similar. The major change is that it uses the vector library instead
--   of array.
--   
--   The algorithm is based on "A Simple, Fast Dominance Algorithm" by
--   Cooper, Harvey, and Kennedy
--   
--   <a>http://www.cs.rice.edu/~keith/EMBED/dom.pdf</a>
--   
--   This is not Tarjan's algorithm; supposedly this is faster in practice
--   for most graphs.
module Data.Graph.Haggle.Algorithms.Dominators

-- | Compute the immediate dominators in the graph from the <tt>root</tt>
--   <a>Vertex</a>. Each <a>Vertex</a> reachable from the <tt>root</tt>
--   will be paired with its immediate dominator. Note that there is no
--   entry in the result pairing for the root <a>Vertex</a> because it has
--   no immediate dominator.
--   
--   If the root vertex is not in the graph, an empty list is returned.
immediateDominators :: Graph g => g -> Vertex -> [(Vertex, Vertex)]

-- | Compute all of the dominators for each <a>Vertex</a> reachable from
--   the <tt>root</tt>. Each reachable <a>Vertex</a> is paired with the
--   list of nodes that dominate it, including the <a>Vertex</a> itself.
--   The <tt>root</tt> is only dominated by itself.
dominators :: Graph g => g -> Vertex -> [(Vertex, [Vertex])]