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


-- | Store and manipulate data in a graph.
--   
@package libgraph
@version 1.5

module Data.Graph.Libgraph
data Graph vertex arc
Graph :: vertex -> [vertex] -> [Arc vertex arc] -> Graph vertex arc
root :: Graph vertex arc -> vertex
vertices :: Graph vertex arc -> [vertex]
arcs :: Graph vertex arc -> [Arc vertex arc]
data Arc vertex arc
Arc :: vertex -> vertex -> arc -> Arc vertex arc
source :: Arc vertex arc -> vertex
target :: Arc vertex arc -> vertex
arc :: Arc vertex arc -> arc

-- | Create an arc between two vertices.
(-->) :: vertex -> vertex -> SimpleArc vertex

-- | Direct successors of a vertex.
succs :: Eq vertex => Graph vertex arc -> vertex -> [vertex]

-- | Direct predecessors of a vertex.
preds :: Eq vertex => Graph vertex arc -> vertex -> [vertex]

-- | Is first vertex a successor of second?
isSucc :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool

-- | Is first vertex a predecessor of second?
isPred :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool
mapGraph :: (a -> b) -> Graph a c -> Graph b c
mapArcs :: (a -> b) -> Graph c a -> Graph c b
data Dfs vertex arc
data EdgeType
TreeEdge :: EdgeType
BackEdge :: EdgeType
FwdEdge :: EdgeType
CrossEdge :: EdgeType

-- | Walk graph in depth-first order and number the vertices.
getDfs :: Eq vertex => Graph vertex arc -> Dfs vertex arc

-- | The <a>EdgeType</a> of an <a>Arc</a>.
getEdgetype :: (Eq vertex, Show vertex) => Dfs vertex arc -> Arc vertex arc -> EdgeType

-- | Get list of vertices in the order they were visited by the depth-first
--   search.
getPreorder :: Dfs vertex arc -> [vertex]

-- | Get list of vertices in the order they were last visited by the
--   depth-first search.
getPostorder :: Dfs vertex arc -> [vertex]

-- | Is first vertex a (recursive) parent of second vertex? May fail when
--   one of the vertices is unreachable from the root.
isAncestor :: (Eq vertex, Show vertex) => Dfs vertex arc -> vertex -> vertex -> Maybe Bool
data Domsets vertex arc

-- | Compute dominator sets. N.B. currently a naive algorithm is
--   implemented with time-complexity O(vertex^2).
getDomsets :: Eq vertex => Graph vertex arc -> Domsets vertex arc

-- | Vertices dominating the vertex given as argument.
getDominators :: Eq vertex => vertex -> Domsets vertex arc -> [vertex]
data CycleTree vertex
CycleTree :: vertex -> [CycleTree vertex] -> CycleTree vertex
Reducible :: vertex -> [CycleTree vertex] -> CycleTree vertex
Irreducible :: [CycleTree vertex] -> CycleTree vertex
getCycles :: Ord vertex => CycleNest vertex -> CycleTree vertex

-- | Entry vertices of reducible cycles.
getRedHeaders :: CycleNest vertex -> [vertex]
dagify :: (Ord v, Eq a, Show v) => ([v] -> v) -> Graph v a -> Graph v a
findFaulty :: (Ord v, Eq a, Show v) => (v -> Judgement) -> ([v] -> v) -> Graph v a -> [v]
findFaulty_dag :: (Ord v, Eq a, Show v) => (v -> Judgement) -> Graph v a -> [v]
data Judgement
Right :: Judgement
Wrong :: Judgement
Unassessed :: Judgement

-- | Convert Graph to String with functions to show vertices and arcs.
showWith :: Eq vertex => Graph vertex arc -> (vertex -> (String, String)) -> (Arc vertex arc -> String) -> String
escape :: String -> String

-- | Invoke Graphviz and Imagemagick to display graph on screen.
display :: (Graph vertex arc -> String) -> Graph vertex arc -> IO ()
collapse :: (Show v, Ord v, Eq a) => ([v] -> v) -> Graph v a -> Graph v a
remove :: (Ord v, Show v) => Graph v a -> Graph v a
treeDepth :: Ord v => Graph v a -> Int