h*">!     1.0.1(c) 2018, Oleg Grenrus BSD-3-Clause Safe-Inferred%&!e topographGraph representation.The   creates a  v i structure. Note, that i( is kept free, so you cannot construct i which isn't in the . Therefore operations, like  are total (and fast). Properties  g =  ( g);runG example $ \G {..} -> (length gVertices, gVerticeCount) Right (5,5)  ( g x) =  elemIndex x ( g)?runG example $ \G {..} -> map (`elemIndex` gVertices) gVertices*Right [Just 0,Just 1,Just 2,Just 3,Just 4]4runG example $ \G {..} -> map gVertexIndex gVerticesRight [0,1,2,3,4] topograph#all vertices, in topological order. topographO(1). retrieve original vertex data topographO(log n). topographO(1). Outgoing edges. Note: target indices are larger than source index. topographO(1). Upper bound of the path length. Negative means there aren't path. topographO(1).  g =  ( g) topographO(1).  ( verticeIndex g x) =  elemIndex x ( g).. Note, there are no efficient way to convert  into i6, conversion back and forth is discouraged on purpose.  topograph?Run action on topologically sorted representation of the graph.ExamplesTopological sorting3runG example $ \G {..} -> map gFromVertex gVertices Right "axbde"Vertices are sorted:runG example $ \G {..} -> map gFromVertex $ sort gVertices Right "axbde"Outgoing edgesrunG example $ \G {..} -> map (map gFromVertex . gEdges) gVerticesRight ["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 TrueNot DAGlet loop = Map.map Set.fromList $ Map.fromList [('a', "bx"), ('b', "cx"), ('c', "ax"), ('x', "")]0runG loop $ \G {..} -> map gFromVertex gVertices Left "abc"runG (Map.singleton 'a' (Set.singleton 'a')) $ \G {..} -> map gFromVertex gVertices Left "aa"  topographLike   but returns   topographAll paths from a to b. Note that every path has at least 2 elements, start and end. Use  ! for the intermediate steps only.See , 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 [])  topograph  without begin and end elements.runG example $ \g@G{..} -> fmap3 gFromVertex $ allPaths' g <$> gToVertex 'a' <*> gToVertex 'e' <*> pure []#Right (Just ["xd","x","bd","d",""])  topographLike   but return a . All paths from a to b>. Note that every path has at least 2 elements, start and end,#Unfortunately, this is the same as  g <$>  'a'+, as in our example graph, all paths from 'a' end up in 'e'. dag-tree.pnglet t = runG example $ \g@G{..} -> fmap3 gFromVertex $ allPathsTree g <$> gToVertex 'a' <*> gToVertex 'e'fmap3 (foldTree $ \a bs -> if null bs then [[a]] else concatMap (map (a:)) bs) t4Right (Just (Just ["axde","axe","abde","ade","ae"]))"fmap3 (Set.fromList . treePairs) tRight (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 (Set.fromList . concatMap pairs) lsRight (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'0traverse3_ (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' fmap3 gFromVertex $ dfs g <$> gToVertex 'x'Right (Just ["xde","xe"]) topographlike  but returns a .traverse2_ dispTree $ runG example $ \g@G{..} -> fmap2 gFromVertex $ dfsTree g <$> gToVertex 'x''x' 'd' 'e' 'e' topographShortest paths lengths starting from a vertex. The resulting list is of the same length as . 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]) topographLongest paths lengths starting from a vertex. The resulting list is of the same length as .runG example $ \g@G{..} -> longestPathLengths g <$> gToVertex 'a'Right (Just [0,1,1,2,3])3runG example $ \G {..} -> map gFromVertex gVertices Right "axbde"runG example $ \g@G{..} -> longestPathLengths g <$> gToVertex 'b'Right (Just [0,0,0,1,2]) topographGraph with all edges reversed. dag-transpose.png(runG example $ adjacencyList . transpose adjacencyList $ reduction g9Right [('a',"bx"),('b',"d"),('d',"e"),('e',""),('x',"d")]$Taking closure first doesn't matter::runG example $ \g -> adjacencyList $ reduction $ closure g9Right [('a',"bx"),('b',"d"),('d',"e"),('e',""),('x',"d")] topographTransitive closure.,A graph, such that if there is a path from u to v4 in the original graph, then there is an edge from u to v in the closure.&The purple edge is added in a closure: dag-closure.png.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")] topograph.Recover adjacency map representation from the .runG example adjacencyMapRight (fromList [('a',fromList "bdex"),('b',fromList "d"),('d',fromList "e"),('e',fromList ""),('x',fromList "de")]) topograph!Adjacency list representation of .runG example adjacencyList map (\(a,b) -> [gFromVertex a, gFromVertex b]) $ Set.toList $ edgesSet g/Right ["ax","ab","ad","ae","xd","xe","bd","de"] topographLike  but for . topographConsecutive pairs. pairs [1..10]8[(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]pairs [][]  topograph Adjacency Map topographfunction on linear indices topograph*Return the result or a cycle in the graph.  topograph Adjacency Map topographfunction on linear indices topographReturn the result or  if there is a cycle.           !"#$%&'()&topograph-1.0.1-LydfPk3myp135wyHBB7suk Topograph topographG gVertices gFromVertex gToVertexgEdgesgDiff gVerticeCount gVertexIndexrunGrunG'allPaths allPaths' allPathsTreedfsdfsTreeshortestPathLengthslongestPathLengths transpose reductionclosure adjacencyMap adjacencyListedgesSet treePairspairsbase Data.Foldablelength GHC.MaybeJustghc-prim GHC.TypesIntMaybecontainers-0.6.7 Data.TreeTreeNothing