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


-- | Directed acyclic graphs can be sorted topographically. Existence of
--   topographic ordering allows writing many graph algorithms efficiently.
--   And many graphs, e.g. most dependency graphs are acyclic!
--   
--   There are some algorithms built-in: dfs, transpose, transitive
--   closure, transitive reduction... Some algorithms even become
--   not-so-hard to implement, like a longest path!
@package topograph
@version 1.0.1


-- | Tools to work with Directed Acyclic Graphs, by taking advantage of
--   topological sorting.
module Topograph

-- | Graph representation.
--   
--   The <a>runG</a> creates a <tt><a>G</a> v i</tt> structure. Note, that
--   <tt>i</tt> is kept free, so you cannot construct <tt>i</tt> which
--   isn't in the <a>gVertices</a>. Therefore operations, like
--   <a>gFromVertex</a> are total (and fast).
--   
--   <h3><b>Properties</b></h3>
--   
--   <pre>
--   <a>gVerticeCount</a> g = <a>length</a> (<a>gVertices</a> g)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; (length gVertices, gVerticeCount)
--   Right (5,5)
--   </pre>
--   
--   <pre>
--   <a>Just</a> (<a>gVertexIndex</a> g x) = <tt>elemIndex</tt> x (<a>gVertices</a> g)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; map (`elemIndex` gVertices) gVertices
--   Right [Just 0,Just 1,Just 2,Just 3,Just 4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; map gVertexIndex gVertices
--   Right [0,1,2,3,4]
--   </pre>
data G v i
G :: [i] -> (i -> v) -> (v -> Maybe i) -> (i -> [i]) -> (i -> i -> Int) -> Int -> (i -> Int) -> G v i

-- | all vertices, in topological order.
[gVertices] :: G v i -> [i]

-- | <i>O(1)</i>. retrieve original vertex data
[gFromVertex] :: G v i -> i -> v

-- | <i>O(log n)</i>.
[gToVertex] :: G v i -> v -> Maybe i

-- | <i>O(1)</i>. Outgoing edges. Note: target indices are larger than
--   source index.
[gEdges] :: G v i -> i -> [i]

-- | <i>O(1)</i>. Upper bound of the path length. Negative means there
--   aren't path.
[gDiff] :: G v i -> i -> i -> Int

-- | <i>O(1)</i>. <tt><a>gVerticeCount</a> g = <a>length</a>
--   (<a>gVertices</a> g)</tt>
[gVerticeCount] :: G v i -> Int

-- | <i>O(1)</i>. <tt><a>Just</a> (<tt>verticeIndex</tt> g x) =
--   <tt>elemIndex</tt> x (<a>gVertices</a> g)</tt>. Note, there are no
--   efficient way to convert <a>Int</a> into <tt>i</tt>, conversion back
--   and forth is discouraged on purpose.
[gVertexIndex] :: G v i -> i -> Int

-- | Run action on topologically sorted representation of the graph.
--   
--   <h3><b>Examples</b></h3>
--   
--   <h4>Topological sorting</h4>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; map gFromVertex gVertices
--   Right "axbde"
--   </pre>
--   
--   Vertices are sorted
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; map gFromVertex $ sort gVertices
--   Right "axbde"
--   </pre>
--   
--   <h4>Outgoing edges</h4>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; map (map gFromVertex . gEdges) gVertices
--   Right ["xbde","de","d","e",""]
--   </pre>
--   
--   Note: target indices are always larger than source vertex' index:
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; getAll $ foldMap (\a -&gt; foldMap (\b -&gt; All (a &lt; b)) (gEdges a)) gVertices
--   Right True
--   </pre>
--   
--   <h4>Not DAG</h4>
--   
--   <pre>
--   &gt;&gt;&gt; let loop = Map.map Set.fromList $ Map.fromList [('a', "bx"), ('b', "cx"), ('c', "ax"), ('x', "")]
--   
--   &gt;&gt;&gt; runG loop $ \G {..} -&gt; map gFromVertex gVertices
--   Left "abc"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG (Map.singleton 'a' (Set.singleton 'a')) $ \G {..} -&gt; map gFromVertex gVertices
--   Left "aa"
--   </pre>
runG :: Ord v => Map v (Set v) -> (forall i. Ord i => G v i -> r) -> Either [v] r

-- | Like <a>runG</a> but returns <a>Maybe</a>
runG' :: Ord v => Map v (Set v) -> (forall i. Ord i => G v i -> r) -> Maybe r

-- | Graph with all edges reversed.
--   
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ adjacencyList . transpose
--   Right [('a',""),('b',"a"),('d',"abx"),('e',"adx"),('x',"a")]
--   </pre>
--   
--   <h3><b>Properties</b></h3>
--   
--   Commutes with <a>closure</a>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ adjacencyList . closure . transpose
--   Right [('a',""),('b',"a"),('d',"abx"),('e',"abdx"),('x',"a")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ adjacencyList . transpose . closure
--   Right [('a',""),('b',"a"),('d',"abx"),('e',"abdx"),('x',"a")]
--   </pre>
--   
--   Commutes with <a>reduction</a>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ adjacencyList . reduction . transpose
--   Right [('a',""),('b',"a"),('d',"bx"),('e',"d"),('x',"a")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ adjacencyList . transpose . reduction
--   Right [('a',""),('b',"a"),('d',"bx"),('e',"d"),('x',"a")]
--   </pre>
transpose :: forall v i. Ord i => G v i -> G v (Down i)

-- | Transitive reduction.
--   
--   Smallest graph, such that if there is a path from <i>u</i> to <i>v</i>
--   in the original graph, then there is also such a path in the
--   reduction.
--   
--   The green edges are not in the transitive reduction:
--   
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g -&gt; adjacencyList $ reduction g
--   Right [('a',"bx"),('b',"d"),('d',"e"),('e',""),('x',"d")]
--   </pre>
--   
--   Taking closure first doesn't matter:
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g -&gt; adjacencyList $ reduction $ closure g
--   Right [('a',"bx"),('b',"d"),('d',"e"),('e',""),('x',"d")]
--   </pre>
reduction :: Ord i => G v i -> G v i

-- | Transitive closure.
--   
--   A graph, such that if there is a path from <i>u</i> to <i>v</i> in the
--   original graph, then there is an edge from <i>u</i> to <i>v</i> in the
--   closure.
--   
--   The purple edge is added in a closure:
--   
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g -&gt; adjacencyList $ closure g
--   Right [('a',"bdex"),('b',"de"),('d',"e"),('e',""),('x',"de")]
--   </pre>
--   
--   Taking reduction first, doesn't matter:
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g -&gt; adjacencyList $ closure $ reduction g
--   Right [('a',"bdex"),('b',"de"),('d',"e"),('e',""),('x',"de")]
--   </pre>
closure :: Ord i => G v i -> G v i

-- | Depth-first paths starting at a vertex.
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; fmap3 gFromVertex $ dfs g &lt;$&gt; gToVertex 'x'
--   Right (Just ["xde","xe"])
--   </pre>
dfs :: forall v i. Ord i => G v i -> i -> [[i]]

-- | like <a>dfs</a> but returns a <a>Tree</a>.
--   
--   <pre>
--   &gt;&gt;&gt; traverse2_ dispTree $ runG example $ \g@G{..} -&gt; fmap2 gFromVertex $ dfsTree g &lt;$&gt; gToVertex 'x'
--   'x'
--     'd'
--       'e'
--     'e'
--   </pre>
dfsTree :: forall v i. Ord i => G v i -> i -> Tree i

-- | All paths from <tt>a</tt> to <tt>b</tt>. Note that every path has at
--   least 2 elements, start and end. Use <a>allPaths'</a> for the
--   intermediate steps only.
--   
--   See <a>dfs</a>, which returns all paths starting at some vertice. This
--   function returns paths with specified start and end vertices.
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; fmap3 gFromVertex $ allPaths g &lt;$&gt; gToVertex 'a' &lt;*&gt; gToVertex 'e'
--   Right (Just ["axde","axe","abde","ade","ae"])
--   </pre>
--   
--   There are no paths from element to itself:
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; fmap3 gFromVertex $ allPaths g &lt;$&gt; gToVertex 'a' &lt;*&gt; gToVertex 'a'
--   Right (Just [])
--   </pre>
allPaths :: forall v i. Ord i => G v i -> i -> i -> [[i]]

-- | <a>allPaths</a> without begin and end elements.
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; fmap3 gFromVertex $ allPaths' g &lt;$&gt; gToVertex 'a' &lt;*&gt; gToVertex 'e' &lt;*&gt; pure []
--   Right (Just ["xd","x","bd","d",""])
--   </pre>
allPaths' :: forall v i. Ord i => G v i -> i -> i -> [i] -> [[i]]

-- | Like <a>allPaths</a> but return a <a>Tree</a>. All paths from
--   <tt>a</tt> to <tt>b</tt>. Note that every path has at least 2
--   elements, start and end,
--   
--   Unfortunately, this is the same as <tt><a>dfs</a> g &lt;$&gt;
--   <a>gToVertex</a> 'a'</tt>, as in our example graph, all paths from
--   <tt>'a'</tt> end up in <tt>'e'</tt>.
--   
--   
--   <pre>
--   &gt;&gt;&gt; let t = runG example $ \g@G{..} -&gt; fmap3 gFromVertex $ allPathsTree g &lt;$&gt; gToVertex 'a' &lt;*&gt; gToVertex 'e'
--   
--   &gt;&gt;&gt; fmap3 (foldTree $ \a bs -&gt; if null bs then [[a]] else concatMap (map (a:)) bs) t
--   Right (Just (Just ["axde","axe","abde","ade","ae"]))
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fmap3 (Set.fromList . treePairs) t
--   Right (Just (Just (fromList [('a','b'),('a','d'),('a','e'),('a','x'),('b','d'),('d','e'),('x','d'),('x','e')])))
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let ls = runG example $ \g@G{..} -&gt; fmap3 gFromVertex $ allPaths g &lt;$&gt; gToVertex 'a' &lt;*&gt; gToVertex 'e'
--   
--   &gt;&gt;&gt; fmap2 (Set.fromList . concatMap pairs) ls
--   Right (Just (fromList [('a','b'),('a','d'),('a','e'),('a','x'),('b','d'),('d','e'),('x','d'),('x','e')]))
--   </pre>
--   
--   <a>Tree</a> paths show how one can explore the paths.
--   
--   <pre>
--   &gt;&gt;&gt; traverse3_ dispTree t
--   'a'
--     'x'
--       'd'
--         'e'
--       'e'
--     'b'
--       'd'
--         'e'
--     'd'
--       'e'
--     'e'
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; traverse3_ (putStrLn . T.drawTree . fmap show) t
--   'a'
--   |
--   +- 'x'
--   |  |
--   |  +- 'd'
--   |  |  |
--   |  |  `- 'e'
--   |  |
--   |  `- 'e'
--   ...
--   </pre>
--   
--   There are no paths from element to itself, but we'll return a single
--   root node, as <a>Tree</a> cannot be empty.
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; fmap3 gFromVertex $ allPathsTree g &lt;$&gt; gToVertex 'a' &lt;*&gt; gToVertex 'a'
--   Right (Just (Just (Node {rootLabel = 'a', subForest = []})))
--   </pre>
allPathsTree :: forall v i. Ord i => G v i -> i -> i -> Maybe (Tree i)

-- | Shortest paths lengths starting from a vertex. The resulting list is
--   of the same length as <a>gVertices</a>. It's quite efficient to
--   compute all shortest (or longest) paths' lengths at once. Zero means
--   that there are no path.
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; shortestPathLengths g &lt;$&gt; gToVertex 'a'
--   Right (Just [0,1,1,1,1])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; shortestPathLengths g &lt;$&gt; gToVertex 'b'
--   Right (Just [0,0,0,1,2])
--   </pre>
shortestPathLengths :: Ord i => G v i -> i -> [Int]

-- | Longest paths lengths starting from a vertex. The resulting list is of
--   the same length as <a>gVertices</a>.
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; longestPathLengths g &lt;$&gt; gToVertex 'a'
--   Right (Just [0,1,1,2,3])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \G {..} -&gt; map gFromVertex gVertices
--   Right "axbde"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; longestPathLengths g &lt;$&gt; gToVertex 'b'
--   Right (Just [0,0,0,1,2])
--   </pre>
longestPathLengths :: Ord i => G v i -> i -> [Int]

-- | Edges set.
--   
--   <pre>
--   &gt;&gt;&gt; runG example $ \g@G{..} -&gt; map (\(a,b) -&gt; [gFromVertex a, gFromVertex b]) $  Set.toList $ edgesSet g
--   Right ["ax","ab","ad","ae","xd","xe","bd","de"]
--   </pre>
edgesSet :: Ord i => G v i -> Set (i, i)

-- | Recover adjacency map representation from the <a>G</a>.
--   
--   <pre>
--   &gt;&gt;&gt; runG example adjacencyMap
--   Right (fromList [('a',fromList "bdex"),('b',fromList "d"),('d',fromList "e"),('e',fromList ""),('x',fromList "de")])
--   </pre>
adjacencyMap :: Ord v => G v i -> Map v (Set v)

-- | Adjacency list representation of <a>G</a>.
--   
--   <pre>
--   &gt;&gt;&gt; runG example adjacencyList
--   Right [('a',"bdex"),('b',"d"),('d',"e"),('e',""),('x',"de")]
--   </pre>
adjacencyList :: Ord v => G v i -> [(v, [v])]

-- | Consecutive pairs.
--   
--   <pre>
--   &gt;&gt;&gt; pairs [1..10]
--   [(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; pairs []
--   []
--   </pre>
pairs :: [a] -> [(a, a)]

-- | Like <a>pairs</a> but for <a>Tree</a>.
treePairs :: Tree a -> [(a, a)]
