topograph-1: Directed acyclic graphs.

Copyright | (c) 2018 Oleg Grenrus
License | BSD-3-Clause
Safe Haskell | None
Language | Haskell2010

Topograph

Contents

- Graph
- Transpose
- Transitive reduction
- Transitive closure
- DFS
- All paths
- Path lengths
- Query
- Utilities

Description

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

Synopsis

- data G v i = G {
  - gVertices :: [i]
  - gFromVertex :: i -> v
  - gToVertex :: v -> Maybe i
  - gEdges :: i -> [i]
  - gDiff :: i -> i -> Int
  - gVerticeCount :: Int
  - gVertexIndex :: i -> Int
  }
- runG :: forall v r. Ord v => Map v (Set v) -> (forall i. Ord i => G v i -> r) -> Either [v] r
- runG' :: forall v r. Ord v => Map v (Set v) -> (forall i. Ord i => G v i -> r) -> Maybe r
- transpose :: forall v i. Ord i => G v i -> G v (Down i)
- reduction :: Ord i => G v i -> G v i
- closure :: Ord i => G v i -> G v i
- dfs :: forall v i. Ord i => G v i -> i -> [[i]]
- dfsTree :: forall v i. Ord i => G v i -> i -> Tree i
- allPaths :: forall v i. Ord i => G v i -> i -> i -> [[i]]
- allPaths' :: forall v i. Ord i => G v i -> i -> i -> [i] -> [[i]]
- allPathsTree :: forall v i. Ord i => G v i -> i -> i -> Maybe (Tree i)
- shortestPathLengths :: Ord i => G v i -> i -> [Int]
- longestPathLengths :: Ord i => G v i -> i -> [Int]
- edgesSet :: Ord i => G v i -> Set (i, i)
- adjacencyMap :: Ord v => G v i -> Map v (Set v)
- adjacencyList :: Ord v => G v i -> [(v, [v])]
- pairs :: [a] -> [(a, a)]
- treePairs :: Tree a -> [(a, a)]

# 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 |

Fields

- gVertices :: [i]

  all vertices, in topological order.

- gFromVertex :: i -> v

  O(1). retrieve original vertex data

- gToVertex :: v -> Maybe i

  O(log n).

- gEdges :: i -> [i]

  O(1). Outgoing edges. Note: target indices are larger than source index.

- gDiff :: i -> i -> Int

  O(1). Upper bound of the path length. Negative means there aren't path.

- gVerticeCount :: Int

  O(1). ``gVerticeCount` g = `length` (`gVertices` g)`

- gVertexIndex :: 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.

runG Source #

Arguments

:: 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

#### 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' Source #

Arguments

:: 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`.