úÎ!| z&     (c) 2018, Oleg Grenrus BSD-3-ClauseNone"#SXyR 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)D. Outgoing edges. Note: target indices are larger than source index. topographO(1)C. 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, convertion 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 edgesBrunG example $ \G {..} -> map (map gFromVertex . gEdges) gVerticesRight ["xbde","de","d","e",""]ANote: target indices are always larger than source vertex' index:crunG example $ \G {..} -> getAll $ foldMap (\a -> foldMap (\b -> All (a < b)) (gEdges a)) gVertices Right TrueNot DAG[let loop = M.map S.fromList $ M.fromList [('a', "bx"), ('b', "cx"), ('c', "ax"), ('x', "")]0runG loop $ \G {..} -> map gFromVertex gVertices Left "abc"OrunG (M.singleton 'a' (S.singleton 'a')) $ \G {..} -> map gFromVertex gVertices Left "aa"  topographLike   but returns   topographAll paths from a to bD. Note that every path has at least 2 elements, start and end. Use  ! for the intermediate steps only.See w, 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.jrunG 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.pngilet t = runG example $ \g@G{..} -> fmap3 gFromVertex $ allPathsTree g <$> gToVertex 'a' <*> gToVertex 'e'Rfmap3 (T.foldTree $ \a bs -> if null bs then [[a]] else concatMap (map (a:)) bs) t4Right (Just (Just ["axde","axe","abde","ade","ae"])) fmap3 (S.fromList . treePairs) tpRight (Just (Just (fromList [('a','b'),('a','d'),('a','e'),('a','x'),('b','d'),('d','e'),('x','d'),('x','e')])))flet ls = runG example $ \g@G{..} -> fmap3 gFromVertex $ allPaths g <$> gToVertex 'a' <*> gToVertex 'e''fmap2 (S.fromList . concatMap pairs) lsiRight (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'...TThere are no paths from element to itself, but we'll return a single root node, as Tree cannot be empty.arunG example $ \g@G{..} -> fmap3 gFromVertex $ allPathsTree g <$> gToVertex 'a' <*> gToVertex 'a'<Right (Just (Just (Node {rootLabel = 'a', subForest = []}))) topograph'Depth-first paths starting at a vertex.FrunG example $ \g@G{..} -> 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' topograph\Shortest paths lengths starting from a vertex. The resulting list is of the same length as x. It's quite efficient to compute all shortest (or longest) paths' lengths at once. Zero means that there are no path.BrunG example $ \g@G{..} -> shortestPathLengths g <$> gToVertex 'a'Right (Just [0,1,1,1,1])BrunG example $ \g@G{..} -> shortestPathLengths g <$> gToVertex 'b'Right (Just [0,0,0,1,2]) topograph[Longest paths lengths starting from a vertex. The resulting list is of the same length as .ArunG example $ \g@G{..} -> longestPathLengths g <$> gToVertex 'a'Right (Just [0,1,1,2,3])3runG example $ \G {..} -> map gFromVertex gVertices Right "axbde"ArunG 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<Right [('a',""),('b',"a"),('d',"abx"),('e',"adx"),('x',"a")] PropertiesCommutes with 2runG example $ adjacencyList . closure . transpose=Right [('a',""),('b',"a"),('d',"abx"),('e',"abdx"),('x',"a")]2runG example $ adjacencyList . transpose . closure=Right [('a',""),('b',"a"),('d',"abx"),('e',"abdx"),('x',"a")]Commutes with 4runG example $ adjacencyList . reduction . transpose9Right [('a',""),('b',"a"),('d',"bx"),('e',"d"),('x',"a")]4runG example $ adjacencyList . transpose . reduction9Right [('a',""),('b',"a"),('d',"bx"),('e',"d"),('x',"a")] topographTransitive reduction.3Smallest graph, such that if there is a path from u to vI in the original graph, then there is also such a path in the reduction.4The green edges are not in the transitive reduction: dag-reduction.png0runG example $ \g -> 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 adjacencyMaptRight (fromList [('a',fromList "bdex"),('b',fromList "d"),('d',fromList "e"),('e',fromList ""),('x',fromList "de")]) topograph!Adjacency list representation of .runG example adjacencyList<Right [('a',"bdex"),('b',"d"),('d',"e"),('e',""),('x',"de")] topograph Edges set.brunG example $ \g@G{..} -> map (\(a,b) -> [gFromVertex a, gFromVertex b]) $ S.toList $ edgesSet g/Right ["ax","ab","ad","ae","xd","xe","bd","de"] topographUnwrap  . topographLike  but for . topographConsequtive 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-inplace TopographG gVertices gFromVertex gToVertexgEdgesgDiff gVerticeCount gVertexIndexrunGrunG'allPaths allPaths' allPathsTreedfsdfsTreeshortestPathLengthslongestPathLengths transpose reductionclosure adjacencyMap adjacencyListedgesSet treePairspairsbase Data.Foldablelength GHC.MaybeJustghc-prim GHC.TypesIntMaybecontainers-0.6.0.1 Data.TreeTreegetDownData.OrdDownNothing