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


-- | Graph structure with type parameters for nodes and edges
--   
--   This graph structure is based on <a>Data.Map</a> and allows any
--   <a>Ord</a> type for nodes and allows directed, undirected and more
--   edge types. There is no need to map nodes to integer numbers. This
--   makes handling in applications much more comfortable, thus the package
--   name.
--   
--   Currently the package does not contain any advanced algorithm, just
--   the data structure and some manipulation functions.
--   
--   The edge type can be freely chosen. This allows great flexibility but
--   it is a bit more cumbersome to do in Haskell 98. Examples of edge
--   types:
--   
--   <ul>
--   <li><tt>DirEdge</tt>: Edges in a directed graph</li>
--   <li><tt>UndirEdge</tt>: Edges in an undirected graph</li>
--   <li><tt>EitherEdge</tt>: For graphs containing both directed and
--   undirected edges</li>
--   <li>You may define an edge type with an additional identifier in order
--   to support multiple edges between the same pair of nodes.</li>
--   <li>Using type functions on the node type you may even define an edge
--   type for nodes from a Cartesian product, where only "horizontal" and
--   "vertical" edges are allowed.</li>
--   </ul>
--   
--   For examples see the <tt>linear-circuit</tt> package and its tests.
--   The <tt>ResistorCube</tt> test demonstrates non-integer node types and
--   the <tt>Tree</tt> test demonstrates multigraphs.
--   
--   The package is plain Haskell 98.
--   
--   Related packages:
--   
--   <ul>
--   <li><tt>fgl</tt>: standard package for graph processing with many
--   graph algorithms but cumbersome data structure with Int numbered
--   nodes</li>
--   </ul>
@package comfort-graph
@version 0.0.3

module Data.Graph.Comfort
data Graph edge node edgeLabel nodeLabel
type LabeledNode n label = (n, label)
type LabeledEdge edge node label = (edge node, label)
class (Foldable edge, Ord1 edge) => Edge edge
from, to :: Edge edge => edge node -> node
from, to :: Edge edge => edge node -> node
defaultEdgeFoldMap :: (Edge edge, Monoid a) => edge a -> a
data DirEdge node
DirEdge :: node -> node -> DirEdge node
data UndirEdge node
UndirEdge :: node -> node -> UndirEdge node
undirEdge :: (Ord node) => node -> node -> UndirEdge node
data EitherEdge node
EDirEdge :: (DirEdge node) -> EitherEdge node
EUndirEdge :: (UndirEdge node) -> EitherEdge node
empty :: Graph edge node edgeLabel nodeLabel
fromList :: (Edge e, Ord n) => [LabeledNode n nl] -> [LabeledEdge e n el] -> Graph e n el nl
fromMap :: (Edge e, Ord n) => Map n nl -> Map (e n) el -> Graph e n el nl
graphMap :: Graph edge node edgeLabel nodeLabel -> Map node (InOutMap edge node edgeLabel nodeLabel)
nodeLabels :: (Edge e, Ord n) => Graph e n el nl -> Map n nl
nodeSet :: Graph e n el nl -> Set n
nodes :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> [node]
nodeEdges :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Map node (Set (edge node), nodeLabel, Set (edge node))
edgeLabels :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Map (edge node) edgeLabel
edgeSet :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Set (edge node)
edges :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> [edge node]
isEmpty :: Graph e n el nl -> Bool
lookupNode :: (Ord n) => n -> Graph e n el nl -> Maybe nl
lookupEdge :: (Edge e, Ord n) => e n -> Graph e n el nl -> Maybe el

-- | Direct predecessors of a node, i.e. nodes with an outgoing edge to the
--   queried node.
predecessors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n]

-- | Direct successors of a node, i.e. nodes with an incoming edge from the
--   queried node.
successors :: (Edge e, Ord n) => Graph e n el nl -> n -> [n]
adjacentEdgeSet :: (Edge e, Ord n) => Graph e n el nl -> n -> Set (e n)

-- | <i>Deprecated: Use adjacentEdgeSet instead.</i>
adjacentEdges :: (Edge e, Ord n) => Graph e n el nl -> n -> Set (e n)
isLoop :: (Edge edge, Eq node) => edge node -> Bool
pathExists :: (Edge edge, Ord node) => node -> node -> Graph edge node edgeLabel nodeLabel -> Bool
isConsistent :: (Ord n, Eq el) => Graph DirEdge n el nl -> Bool
mapNode :: (nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapNodeWithKey :: (n -> nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
mapEdge :: (el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl
mapEdgeWithKey :: (e n -> el0 -> el1) -> Graph e n el0 nl -> Graph e n el1 nl
mapNodeWithInOut :: (Edge e, Ord n) => (InOut e n el nl0 -> nl1) -> Graph e n el nl0 -> Graph e n el nl1
type InOut e n el nl = ([LabeledEdge e n el], LabeledNode n nl, [LabeledEdge e n el])
filterEdgeWithKey :: (Edge e, Ord n) => (e n -> el -> Bool) -> Graph e n el nl -> Graph e n el nl

-- | Same restrictions as in <a>traverse</a>.
traverseNode :: (Applicative f, Edge e, Ord n) => (nl0 -> f nl1) -> Graph e n el nl0 -> f (Graph e n el nl1)

-- | Same restrictions as in <a>traverse</a>.
traverseEdge :: (Applicative f, Edge e, Ord n) => (el0 -> f el1) -> Graph e n el0 nl -> f (Graph e n el1 nl)

-- | Don't rely on a particular order of traversal!
traverse :: (Applicative f, Edge e, Ord n) => (nl0 -> f nl1) -> (el0 -> f el1) -> Graph e n el0 nl0 -> f (Graph e n el1 nl1)

-- | Node and edge sets must be equal.
checkedZipWith :: (Edge edge, Ord node) => Caller -> (nodeLabel0 -> nodeLabel1 -> nodeLabel2) -> (edgeLabel0 -> edgeLabel1 -> edgeLabel2) -> Graph edge node edgeLabel0 nodeLabel0 -> Graph edge node edgeLabel1 nodeLabel1 -> Graph edge node edgeLabel2 nodeLabel2

-- | The node sets must be disjoint.
union :: (Edge edge, Ord node) => Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel -> Graph edge node edgeLabel nodeLabel
class Edge edge => Reverse edge
reverseEdge :: Reverse edge => edge node -> edge node
reverse :: (Reverse e, Ord n) => Graph e n el nl -> Graph e n el nl
reverseEdge :: Reverse edge => edge node -> edge node

-- | The index map must be an injection, that is, nodes must not collaps.
--   Also the node and edge index maps must be consistent, i.e.
--   
--   <pre>
--   from (edgeMap e) == nodeMap (from e)
--   to   (edgeMap e) == nodeMap (to   e)
--   </pre>
--   
--   Strictly spoken, we would need the node map only for isolated nodes,
--   but we use it for all nodes for simplicity.
mapKeys :: (Edge edge1, Ord node0, Ord node1) => (node0 -> node1) -> (edge0 node0 -> edge1 node1) -> Graph edge0 node0 edgeLabel nodeLabel -> Graph edge1 node1 edgeLabel nodeLabel

-- | You may only use this for filtering edges and use more specialised
--   types as a result. You must not alter source and target nodes of
--   edges.
mapMaybeEdgeKeys :: (Edge e1, Ord n) => (e0 n -> Maybe (e1 n)) -> Graph e0 n el nl -> Graph e1 n el nl

-- | Same restrictions as in <a>mapMaybeEdgeKeys</a>.
mapEdgeKeys :: (Edge e1, Ord n) => (e0 n -> e1 n) -> Graph e0 n el nl -> Graph e1 n el nl

-- | Node to be deleted must be contained in the graph.
deleteNode :: (Edge e, Ord n) => n -> Graph e n el nl -> Graph e n el nl

-- | Could be implemented more efficiently.
deleteNodeSet :: (Edge e, Ord n) => Set n -> Graph e n el nl -> Graph e n el nl
deleteEdge :: (Edge e, Ord n) => e n -> Graph e n el nl -> Graph e n el nl

-- | In the current implementation existing nodes are replaced with new
--   labels and existing edges are maintained. However, I think we should
--   better have an extra function for this purpose and you should not rely
--   on this behavior.
insertNode :: (Ord n) => n -> nl -> Graph e n el nl -> Graph e n el nl
insertEdge :: (Edge e, Ord n) => e n -> el -> Graph e n el nl -> Graph e n el nl

-- | In the current implementation existing edges are replaced with new
--   labels. However, I think we should better have an extra function for
--   this purpose and you should not rely on this behavior. It is an
--   unchecked error if edges between non-existing nodes are inserted.
insertEdgeSet :: (Edge e, Ord n) => Map (e n) el -> Graph e n el nl -> Graph e n el nl
instance (GHC.Classes.Ord nodeLabel, GHC.Classes.Ord edgeLabel, GHC.Classes.Ord node, Data.Functor.Classes.Ord1 edge) => GHC.Classes.Ord (Data.Graph.Comfort.Graph edge node edgeLabel nodeLabel)
instance (GHC.Classes.Eq nodeLabel, GHC.Classes.Eq edgeLabel, GHC.Classes.Eq node, Data.Functor.Classes.Eq1 edge) => GHC.Classes.Eq (Data.Graph.Comfort.Graph edge node edgeLabel nodeLabel)
instance GHC.Show.Show node => GHC.Show.Show (Data.Graph.Comfort.EitherEdge node)
instance GHC.Classes.Ord node => GHC.Classes.Ord (Data.Graph.Comfort.EitherEdge node)
instance GHC.Classes.Eq node => GHC.Classes.Eq (Data.Graph.Comfort.EitherEdge node)
instance GHC.Show.Show node => GHC.Show.Show (Data.Graph.Comfort.UndirEdge node)
instance GHC.Classes.Ord node => GHC.Classes.Ord (Data.Graph.Comfort.UndirEdge node)
instance GHC.Classes.Eq node => GHC.Classes.Eq (Data.Graph.Comfort.UndirEdge node)
instance GHC.Show.Show node => GHC.Show.Show (Data.Graph.Comfort.DirEdge node)
instance GHC.Classes.Ord node => GHC.Classes.Ord (Data.Graph.Comfort.DirEdge node)
instance GHC.Classes.Eq node => GHC.Classes.Eq (Data.Graph.Comfort.DirEdge node)
instance (Data.Graph.Comfort.Edge e, GHC.Classes.Ord n, Data.Functor.Classes.Show1 e, GHC.Show.Show n, GHC.Show.Show el, GHC.Show.Show nl) => GHC.Show.Show (Data.Graph.Comfort.Graph e n el nl)
instance (Data.Graph.Comfort.Edge edge, GHC.Classes.Ord node) => Data.Semigroup.Semigroup (Data.Graph.Comfort.Graph edge node edgeLabel nodeLabel)
instance (Data.Graph.Comfort.Edge edge, GHC.Classes.Ord node) => GHC.Base.Monoid (Data.Graph.Comfort.Graph edge node edgeLabel nodeLabel)
instance Data.Graph.Comfort.Reverse Data.Graph.Comfort.DirEdge
instance Data.Graph.Comfort.Edge Data.Graph.Comfort.EitherEdge
instance Data.Functor.Classes.Eq1 Data.Graph.Comfort.EitherEdge
instance Data.Functor.Classes.Ord1 Data.Graph.Comfort.EitherEdge
instance Data.Functor.Classes.Show1 Data.Graph.Comfort.EitherEdge
instance Data.Foldable.Foldable Data.Graph.Comfort.EitherEdge
instance Data.Graph.Comfort.Edge Data.Graph.Comfort.UndirEdge
instance Data.Functor.Classes.Eq1 Data.Graph.Comfort.UndirEdge
instance Data.Functor.Classes.Ord1 Data.Graph.Comfort.UndirEdge
instance Data.Functor.Classes.Show1 Data.Graph.Comfort.UndirEdge
instance Data.Foldable.Foldable Data.Graph.Comfort.UndirEdge
instance (Test.QuickCheck.Arbitrary.Arbitrary n, GHC.Classes.Ord n) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Graph.Comfort.UndirEdge n)
instance Data.Graph.Comfort.Edge Data.Graph.Comfort.DirEdge
instance Data.Functor.Classes.Eq1 Data.Graph.Comfort.DirEdge
instance Data.Functor.Classes.Ord1 Data.Graph.Comfort.DirEdge
instance Data.Functor.Classes.Show1 Data.Graph.Comfort.DirEdge
instance GHC.Base.Functor Data.Graph.Comfort.DirEdge
instance Data.Foldable.Foldable Data.Graph.Comfort.DirEdge
instance Test.QuickCheck.Arbitrary.Arbitrary n => Test.QuickCheck.Arbitrary.Arbitrary (Data.Graph.Comfort.DirEdge n)
