-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Directed acyclic graphs. -- -- 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 build-in: dfs, transpose, transitive -- closure, transitive reduction... Some algorithms even become -- not-so-hard to implement, like a longest path! @package topograph @version 1 -- | Tools to work with Directed Acyclic Graphs, by taking advantage of -- topological sorting. module Topograph -- | Graph representation. -- -- The runG creates a G v i structure. Note, that -- i is kept free, so you cannot construct i which -- isn't in the gVertices. Therefore operations, like -- gFromVertex are total (and fast). -- --

Properties

-- -- 
--   gVerticeCount g = length (gVertices g)
--
-- -- 
--   >>> runG example $ \G {..} -> (length gVertices, gVerticeCount)
--   Right (5,5)
--
-- -- 
--   Just (gVertexIndex g x) = elemIndex x (gVertices g)
--
-- -- 
--   >>> runG example $ \G {..} -> map (`elemIndex` gVertices) gVertices
--   Right [Just 0,Just 1,Just 2,Just 3,Just 4]
--
-- -- 
--   >>> runG example $ \G {..} -> map gVertexIndex gVertices
--   Right [0,1,2,3,4]
--
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] -- | O(1). retrieve original vertex data [gFromVertex] :: G v i -> i -> v -- | O(log n). [gToVertex] :: G v i -> v -> Maybe i -- | O(1). Outgoing edges. Note: target indices are larger than -- source index. [gEdges] :: G v i -> i -> [i] -- | O(1). Upper bound of the path length. Negative means there -- aren't path. [gDiff] :: G v i -> i -> i -> Int -- | O(1). gVerticeCount g = length -- (gVertices g) [gVerticeCount] :: G v i -> Int -- | O(1). Just (verticeIndex g x) = -- elemIndex x (gVertices g). Note, there are no -- efficient way to convert Int into i, convertion back -- and forth is discouraged on purpose. [gVertexIndex] :: G v i -> i -> Int -- | Run action on topologically sorted representation of the graph. -- --

Examples

-- --

Topological sorting

-- -- 
--   >>> runG example $ \G {..} -> map gFromVertex gVertices
--   Right "axbde"
--
-- -- Vertices are sorted -- -- 
--   >>> runG example $ \G {..} -> map gFromVertex $ sort gVertices
--   Right "axbde"
--
-- --

Outgoing edges

-- -- 
--   >>> runG example $ \G {..} -> map (map gFromVertex . gEdges) gVertices
--   Right ["xbde","de","d","e",""]
--
-- -- Note: target indices are always larger than source vertex' index: -- -- 
--   >>> runG example $ \G {..} -> getAll $ foldMap (\a -> foldMap (\b -> All (a < b)) (gEdges a)) gVertices
--   Right True
--
-- --

Not DAG

-- -- 
--   >>> let loop = M.map S.fromList $ M.fromList [('a', "bx"), ('b', "cx"), ('c', "ax"), ('x', "")]
--   
--   >>> runG loop $ \G {..} -> map gFromVertex gVertices
--   Left "abc"
--
-- -- 
--   >>> runG (M.singleton 'a' (S.singleton 'a')) $ \G {..} -> map gFromVertex gVertices
--   Left "aa"
--
runG :: forall v r. Ord v => Map v (Set v) -> (forall i. Ord i => G v i -> r) -> Either [v] r -- | Like runG but returns Maybe runG' :: forall v r. Ord v => Map v (Set v) -> (forall i. Ord i => G v i -> r) -> Maybe r -- | Graph with all edges reversed. -- -- -- 
--   >>> runG example $ adjacencyList . transpose
--   Right [('a',""),('b',"a"),('d',"abx"),('e',"adx"),('x',"a")]
--
-- --

Properties

-- -- Commutes with closure -- -- 
--   >>> runG example $ adjacencyList . closure . transpose
--   Right [('a',""),('b',"a"),('d',"abx"),('e',"abdx"),('x',"a")]
--
-- -- 
--   >>> runG example $ adjacencyList . transpose . closure
--   Right [('a',""),('b',"a"),('d',"abx"),('e',"abdx"),('x',"a")]
--
-- -- Commutes with reduction -- -- 
--   >>> runG example $ adjacencyList . reduction . transpose
--   Right [('a',""),('b',"a"),('d',"bx"),('e',"d"),('x',"a")]
--
-- -- 
--   >>> runG example $ adjacencyList . transpose . reduction
--   Right [('a',""),('b',"a"),('d',"bx"),('e',"d"),('x',"a")]
--
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 u to v -- in the original graph, then there is also such a path in the -- reduction. -- -- The green edges are not in the transitive reduction: -- -- -- 
--   >>> runG example $ \g -> adjacencyList $ reduction g
--   Right [('a',"bx"),('b',"d"),('d',"e"),('e',""),('x',"d")]
--
-- -- Taking closure first doesn't matter: -- -- 
--   >>> runG example $ \g -> adjacencyList $ reduction $ closure g
--   Right [('a',"bx"),('b',"d"),('d',"e"),('e',""),('x',"d")]
--
reduction :: Ord i => G v i -> G v i -- | Transitive closure. -- -- A graph, such that if there is a path from u to v in the -- original graph, then there is an edge from u to v in the -- closure. -- -- The purple edge is added in a closure: -- -- -- 
--   >>> runG example $ \g -> adjacencyList $ closure g
--   Right [('a',"bdex"),('b',"de"),('d',"e"),('e',""),('x',"de")]
--
-- -- Taking reduction first, doesn't matter: -- -- 
--   >>> runG example $ \g -> adjacencyList $ closure $ reduction g
--   Right [('a',"bdex"),('b',"de"),('d',"e"),('e',""),('x',"de")]
--
closure :: Ord i => G v i -> G v i -- | Depth-first paths starting at a vertex. -- -- 
--   >>> runG example $ \g@G{..} -> fmap3 gFromVertex $ dfs g <$> gToVertex 'x'
--   Right (Just ["xde","xe"])
--
dfs :: forall v i. Ord i => G v i -> i -> [[i]] -- | like dfs but returns a Tree. -- -- 
--   >>> traverse2_ dispTree $ runG example $ \g@G{..} -> fmap2 gFromVertex $ dfsTree g <$> gToVertex 'x'
--   'x'
--     'd'
--       'e'
--     'e'
--
dfsTree :: forall v i. Ord i => G v i -> i -> Tree i -- | All paths from a to b. Note that every path has at -- least 2 elements, start and end. Use allPaths' for the -- intermediate steps only. -- -- See dfs, which returns all paths starting at some vertice. This -- function returns paths with specified start and end vertices. -- -- 
--   >>> runG example $ \g@G{..} -> fmap3 gFromVertex $ allPaths g <$> gToVertex 'a' <*> gToVertex 'e'
--   Right (Just ["axde","axe","abde","ade","ae"])
--
-- -- There are no paths from element to itself: -- -- 
--   >>> runG example $ \g@G{..} -> fmap3 gFromVertex $ allPaths g <$> gToVertex 'a' <*> gToVertex 'a'
--   Right (Just [])
--
allPaths :: forall v i. Ord i => G v i -> i -> i -> [[i]] -- | allPaths without begin and end elements. -- -- 
--   >>> runG example $ \g@G{..} -> fmap3 gFromVertex $ allPaths' g <$> gToVertex 'a' <*> gToVertex 'e' <*> pure []
--   Right (Just ["xd","x","bd","d",""])
--
allPaths' :: forall v i. Ord i => G v i -> i -> i -> [i] -> [[i]] -- | Like allPaths but return a Tree. All paths from -- a to b. Note that every path has at least 2 -- elements, start and end, -- -- Unfortunately, this is the same as dfs g <$> -- gToVertex 'a', as in our example graph, all paths from -- 'a' end up in 'e'. -- -- -- 
--   >>> let t = runG example $ \g@G{..} -> fmap3 gFromVertex $ allPathsTree g <$> gToVertex 'a' <*> gToVertex 'e'
--   
--   >>> fmap3 (T.foldTree $ \a bs -> if null bs then [[a]] else concatMap (map (a:)) bs) t
--   Right (Just (Just ["axde","axe","abde","ade","ae"]))
--
-- -- 
--   >>> fmap3 (S.fromList . treePairs) t
--   Right (Just (Just (fromList [('a','b'),('a','d'),('a','e'),('a','x'),('b','d'),('d','e'),('x','d'),('x','e')])))
--
-- -- 
--   >>> let ls = runG example $ \g@G{..} -> fmap3 gFromVertex $ allPaths g <$> gToVertex 'a' <*> gToVertex 'e'
--   
--   >>> fmap2 (S.fromList . concatMap pairs) ls
--   Right (Just (fromList [('a','b'),('a','d'),('a','e'),('a','x'),('b','d'),('d','e'),('x','d'),('x','e')]))
--
-- -- Tree paths show how one can explore the paths. -- -- 
--   >>> traverse3_ dispTree t
--   'a'
--     'x'
--       'd'
--         'e'
--       'e'
--     'b'
--       'd'
--         'e'
--     'd'
--       'e'
--     'e'
--
-- -- 
--   >>> traverse3_ (putStrLn . T.drawTree . fmap show) t
--   'a'
--   |
--   +- 'x'
--   |  |
--   |  +- 'd'
--   |  |  |
--   |  |  `- 'e'
--   |  |
--   |  `- 'e'
--   ...
--
-- -- There are no paths from element to itself, but we'll return a single -- root node, as Tree cannot be empty. -- -- 
--   >>> runG example $ \g@G{..} -> fmap3 gFromVertex $ allPathsTree g <$> gToVertex 'a' <*> gToVertex 'a'
--   Right (Just (Just (Node {rootLabel = 'a', subForest = []})))
--
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 gVertices. It's quite efficient to -- compute all shortest (or longest) paths' lengths at once. Zero means -- that there are no path. -- -- 
--   >>> runG example $ \g@G{..} -> shortestPathLengths g <$> gToVertex 'a'
--   Right (Just [0,1,1,1,1])
--
-- -- 
--   >>> runG example $ \g@G{..} -> shortestPathLengths g <$> gToVertex 'b'
--   Right (Just [0,0,0,1,2])
--
shortestPathLengths :: Ord i => G v i -> i -> [Int] -- | Longest paths lengths starting from a vertex. The resulting list is of -- the same length as gVertices. -- -- 
--   >>> runG example $ \g@G{..} -> longestPathLengths g <$> gToVertex 'a'
--   Right (Just [0,1,1,2,3])
--
-- -- 
--   >>> runG example $ \G {..} -> map gFromVertex gVertices
--   Right "axbde"
--
-- -- 
--   >>> runG example $ \g@G{..} -> longestPathLengths g <$> gToVertex 'b'
--   Right (Just [0,0,0,1,2])
--
longestPathLengths :: Ord i => G v i -> i -> [Int] -- | Edges set. -- -- 
--   >>> runG example $ \g@G{..} -> map (\(a,b) -> [gFromVertex a, gFromVertex b]) $  S.toList $ edgesSet g
--   Right ["ax","ab","ad","ae","xd","xe","bd","de"]
--
edgesSet :: Ord i => G v i -> Set (i, i) -- | Recover adjacency map representation from the G. -- -- 
--   >>> runG example adjacencyMap
--   Right (fromList [('a',fromList "bdex"),('b',fromList "d"),('d',fromList "e"),('e',fromList ""),('x',fromList "de")])
--
adjacencyMap :: Ord v => G v i -> Map v (Set v) -- | Adjacency list representation of G. -- -- 
--   >>> runG example adjacencyList
--   Right [('a',"bdex"),('b',"d"),('d',"e"),('e',""),('x',"de")]
--
adjacencyList :: Ord v => G v i -> [(v, [v])] -- | Consequtive pairs. -- -- 
--   >>> pairs [1..10]
--   [(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]
--
-- -- 
--   >>> pairs []
--   []
--
pairs :: [a] -> [(a, a)] -- | Like pairs but for Tree. treePairs :: Tree a -> [(a, a)]