topograph-1: Directed acyclic graphs.

Topograph

Description

Tools to work with Directed Acyclic Graphs, by taking advantage of topological sorting.

Synopsis

# Graph

Graph used in examples:

>>> let example :: Map Char (Set Char); example = M.map S.fromList $M.fromList [('a', "bxde"), ('b', "d"), ('x', "de"), ('d', "e"), ('e', "")]  >>> :set -XRecordWildCards >>> import Data.Monoid (All (..)) >>> import Data.Foldable (traverse_) >>> import Data.List (elemIndex) >>> import Data.Tree (Tree (..))  ## Few functions to be used in examples To make examples slightly shorter: >>> let fmap2 = fmap . fmap >>> let fmap3 = fmap . fmap2 >>> let traverse2_ = traverse_ . traverse_ >>> let traverse3_ = traverse_ . traverse2_  To display trees: >>> let dispTree :: Show a => Tree a -> IO (); dispTree = go 0 where go i (T.Node x xs) = putStrLn (replicate (i * 2) ' ' ++ show x) >> traverse_ (go (succ i)) xs  data G v i Source # 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 Expand 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]


Constructors

 G FieldsgVertices :: [i]all vertices, in topological order.gFromVertex :: i -> vO(1). retrieve original vertex datagToVertex :: v -> Maybe iO(log n).gEdges :: i -> [i]O(1). Outgoing edges. Note: target indices are larger than source index.gDiff :: i -> i -> IntO(1). Upper bound of the path length. Negative means there aren't path.gVerticeCount :: IntO(1). gVerticeCount g = length (gVertices g)gVertexIndex :: i -> IntO(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.

Arguments

 :: forall v r. Ord v => Map v (Set v) Adjacency Map -> (forall i. Ord i => G v i -> r) function on linear indices -> Either [v] r Return the result or a cycle in the graph.

Run action on topologically sorted representation of the graph.

### Examples

Expand

>>> 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"  Arguments  :: forall v r. Ord v => Map v (Set v) Adjacency Map -> (forall i. Ord i => G v i -> r) function on linear indices -> Maybe r Return the result or Nothing if there is a cycle. Like runG but returns Maybe # Transpose transpose :: forall v i. Ord i => G v i -> G v (Down i) Source # Graph with all edges reversed. >>> runG example$ adjacencyList . transpose
Right [('a',""),('b',"a"),('d',"abx"),('e',"adx"),('x',"a")]


### Properties

Expand

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")]


# Transitive reduction

reduction :: Ord i => G v i -> G v i Source #

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")]  # Transitive closure closure :: Ord i => G v i -> G v i Source # 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")]


# DFS

dfs :: forall v i. Ord i => G v i -> i -> [[i]] Source #

Depth-first paths starting at a vertex.

>>> runG example $\g@G{..} -> fmap3 gFromVertex$ dfs g <$> gToVertex 'x' Right (Just ["xde","xe"])  dfsTree :: forall v i. Ord i => G v i -> i -> Tree i Source # like dfs but returns a Tree. >>> traverse2_ dispTree$ runG example $\g@G{..} -> fmap2 gFromVertex$ dfsTree g <$> gToVertex 'x' 'x' 'd' 'e' 'e'  # All paths allPaths :: forall v i. Ord i => G v i -> i -> i -> [[i]] Source # 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] -> [[i]] Source # 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",""])


allPathsTree :: forall v i. Ord i => G v i -> i -> i -> Maybe (Tree i) Source #

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 = []})))  # Path lengths shortestPathLengths :: Ord i => G v i -> i -> [Int] Source # 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])  longestPathLengths :: Ord i => G v i -> i -> [Int] Source # 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])


# Query

edgesSet :: Ord i => G v i -> Set (i, i) Source #

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"]


adjacencyMap :: Ord v => G v i -> Map v (Set v) Source #

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")])


adjacencyList :: Ord v => G v i -> [(v, [v])] Source #

Adjacency list representation of G.

>>> runG example adjacencyList
Right [('a',"bdex"),('b',"d"),('d',"e"),('e',""),('x',"de")]


# Utilities

pairs :: [a] -> [(a, a)] Source #

Consequtive pairs.

>>> pairs [1..10]
[(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]

>>> pairs []
[]


treePairs :: Tree a -> [(a, a)] Source #

Like pairs but for Tree.