From 7b66a7810b7086abb169cdbc00405c47a904bb32 Mon Sep 17 00:00:00 2001
From: Matt Renaud
Date: Wed, 7 Mar 2018 16:26:05 0800
Subject: [PATCH] Improve Data.Graph documentation. (#532)
* Improve module docs
* Reorders function documentation order
* Adds examples
* Don't use Table type alias, use Array Vertex a instead.

Data/Graph.hs  216 ++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 173 insertions(+), 43 deletions()
diff git a/Data/Graph.hs b/Data/Graph.hs
index a02a262..ad97132 100644
 a/Data/Graph.hs
+++ b/Data/Graph.hs
@@ 23,45 +23,71 @@
 Maintainer : libraries@haskell.org
 Portability : portable

 A version of the graph algorithms described in:
+ = Finite Graphs

 /Structuring DepthFirst Search Algorithms in Haskell/,
 by David King and John Launchbury.
+ The @'Graph'@ type is an adjacency list representation of a finite, directed
+ graph with vertices of type @Int@.
+
+ The @'SCC'@ type represents a
+
+ of a graph.
+
+ == Implementation
+
+ The implementation is based on
+
+ * /Structuring DepthFirst Search Algorithms in Haskell/,
+ by David King and John Launchbury.


module Data.Graph(

  * External interface
+module Data.Graph (
  At present the only one with a "nice" external interface
 stronglyConnComp, stronglyConnCompR, SCC(..), flattenSCC, flattenSCCs,
+  * Graphs
+ Graph
+ , Bounds
+ , Edge
+ , Vertex
+ , Table
  * Graphs
+  ** Graph Construction
+ , graphFromEdges
+ , graphFromEdges'
+ , buildG
 Graph, Table, Bounds, Edge, Vertex,
+  ** Graph Properties
+ , vertices
+ , edges
+ , outdegree
+ , indegree
  ** Building graphs
+  ** Graph Transformations
+ , transposeG
 graphFromEdges, graphFromEdges', buildG, transposeG,
  reverseE,
+  ** Graph Algorithms
+ , dfs
+ , dff
+ , topSort
+ , components
+ , scc
+ , bcc
+ , reachable
+ , path
  ** Graph properties
 vertices, edges,
 outdegree, indegree,
+  * Strongly Connected Components
+ , SCC(..)
  * Algorithms
+  ** Construction
+ , stronglyConnComp
+ , stronglyConnCompR
 dfs, dff,
 topSort,
 components,
 scc,
 bcc,
  tree, back, cross, forward,
 reachable, path,
+  ** Conversion
+ , flattenSCC
+ , flattenSCCs
 module Data.Tree
+  * Trees
+ , module Data.Tree
) where
@@ 69,7 +95,6 @@ module Data.Graph(
# define USE_ST_MONAD 1
#endif
 Extensions
#if USE_ST_MONAD
import Control.Monad.ST
import Data.Array.ST (STUArray, newArray, readArray, writeArray)
@@ 108,7 +133,7 @@ import Data.Typeable

 
 External interface
+ Strongly Connected Components
 

@@ 246,31 +271,58 @@ stronglyConnCompR edges0
  Abstract representation of vertices.
type Vertex = Int
  Table indexed by a contiguous set of vertices.
+
+ /Note: This is included for backwards compatibility./
type Table a = Array Vertex a
  Adjacency list representation of a graph, mapping each vertex to its
 list of successors.
type Graph = Table [Vertex]
  The bounds of a 'Table'.
+type Graph = Array Vertex [Vertex]
+  The bounds of an @Array@.
type Bounds = (Vertex, Vertex)
  An edge from the first vertex to the second.
type Edge = (Vertex, Vertex)
  All vertices of a graph.
+  Returns the list of vertices in the graph.
+
+ ==== __Examples__
+
+ > vertices (buildG (0,1) []) == []
+
+ > vertices (buildG (0,2) [(0,1),(1,2)]) == [0,1,2]
vertices :: Graph > [Vertex]
vertices = indices
  All edges of a graph.
+  Returns the list of edges in the graph.
+
+ ==== __Examples__
+
+ > edges (buildG (0,1) []) == []
+
+ > edges (buildG (0,2) [(0,1),(1,2)]) == [(0,1),(1,2)]
edges :: Graph > [Edge]
edges g = [ (v, w)  v < vertices g, w < g!v ]
mapT :: (Vertex > a > b) > Table a > Table b
+mapT :: (Vertex > a > b) > Array Vertex a > Array Vertex b
mapT f t = array (bounds t) [ (,) v (f v (t!v))  v < indices t ]
  Build a graph from a list of edges.
+
+ Warning: This function will cause a runtime exception if a vertex in the edge
+ list is not within the given @Bounds@.
+
+ ==== __Examples__
+
+ > buildG (0,1) [] == array (0,1) []
+ > buildG (0,2) [(0,1), (1,2)] == array (0,1) [(0,[1]),(1,[2])]
+ > buildG (0,2) [(0,1), (0,2), (1,2)] == array (0,2) [(0,[2,1]),(1,[2]),(2,[])]
buildG :: Bounds > [Edge] > Graph
buildG bounds0 edges0 = accumArray (flip (:)) [] bounds0 edges0
  The graph obtained by reversing all edges.
+
+ ==== __Examples__
+
+ > transposeG (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,[]),(1,[0]),(2,[1])]
transposeG :: Graph > Graph
transposeG g = buildG (bounds g) (reverseE g)
@@ 278,12 +330,24 @@ reverseE :: Graph > [Edge]
reverseE g = [ (w, v)  (v, w) < edges g ]
  A table of the count of edges from each node.
outdegree :: Graph > Table Int
+
+ ==== __Examples__
+
+ > outdegree (buildG (0,1) []) == array (0,1) []
+
+ > outdegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,1),(1,1),(2,0)]
+outdegree :: Graph > Array Vertex Int
outdegree = mapT numEdges
where numEdges _ ws = length ws
  A table of the count of edges into each node.
indegree :: Graph > Table Int
+
+ ==== __Examples__
+
+ > indegree (buildG (0,1) []) == array (0,1) []
+
+ > indegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,0),(1,1),(2,1)]
+indegree :: Graph > Array Vertex Int
indegree = outdegree . transposeG
  Identical to 'graphFromEdges', except that the return value
@@ 298,8 +362,60 @@ graphFromEdges' x = (a,b) where
  Build a graph from a list of nodes uniquely identified by keys,
 with a list of keys of nodes this node should have edges to.
 The outlist may contain keys that don't correspond to
 nodes of the graph; they are ignored.
+
+ This function takes an adjacency list representing a graph with vertices of
+ type @key@ labeled by values of type @node@ and produces a @Graph@based
+ representation of that list. The @Graph@ result represents the /shape/ of the
+ graph, and the functions describe a) how to retrieve the label and adjacent
+ vertices of a given vertex, and b) how to retrive a vertex given a key.
+
+ @(graph, nodeFromVertex, vertexFromKey) = graphFromEdges edgeList@
+
+ * @graph :: Graph@ is the raw, array based adjacency list for the graph.
+ * @nodeFromVertex :: Vertex > (node, key, [key])@ returns the node
+ associated with the given 0based @Int@ vertex; see /warning/ below.
+ * @vertexFromKey :: key > Maybe Vertex@ returns the @Int@ vertex for the
+ key if it exists in the graph, @Nothing@ otherwise.
+
+ To safely use this API you must either extract the list of vertices directly
+ from the graph or first call @vertexFromKey k@ to check if a vertex
+ corresponds to the key @k@. Once it is known that a vertex exists you can use
+ @nodeFromVertex@ to access the labelled node and adjacent vertices. See below
+ for examples.
+
+ Note: The outlist may contain keys that don't correspond to nodes of the
+ graph; they are ignored.
+
+ Warning: The @nodeFromVertex@ function will cause a runtime exception if the
+ given @Vertex@ does not exist.
+
+ ==== __Examples__
+
+ An empty graph.
+
+ > (graph, nodeFromVertex, vertexFromKey) = graphFromEdges []
+ > graph = array (0,1) []
+
+ A graph where the outlist references unspecified nodes (@'c'@), these are
+ ignored.
+
+ > (graph, _, _) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c'])]
+ > array (0,1) [(0,[1]),(1,[])]
+
+
+ A graph with 3 vertices: ("a") > ("b") > ("c")
+
+ > (graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])]
+ > graph == array (0,2) [(0,[1]),(1,[2]),(2,[])]
+ > nodeFromVertex 0 == ("a",'a',"b")
+ > vertexFromKey 'a' == Just 0
+
+ Get the label for a given key.
+
+ > let getNodePart (n, _, _) = n
+ > (graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])]
+ > getNodePart . nodeFromVertex <$> vertexFromKey 'a' == Just "A"
+
graphFromEdges
:: Ord key
=> [(node, key, [key])]
@@ 452,10 +568,10 @@ preorderF' ts = foldr (.) id $ map preorder' ts
preorderF :: Forest a > [a]
preorderF ts = preorderF' ts []
tabulate :: Bounds > [Vertex] > Table Int
+tabulate :: Bounds > [Vertex] > Array Vertex Int
tabulate bnds vs = array bnds (zipWith (,) vs [1..])
preArr :: Bounds > Forest Vertex > Table Int
+preArr :: Bounds > Forest Vertex > Array Vertex Int
preArr bnds = tabulate bnds . preorderF

@@ 525,12 +641,26 @@ forward g tree' pre = mapT select g
 Algorithm 6: Finding reachable vertices

  A list of vertices reachable from a given vertex.
reachable :: Graph > Vertex > [Vertex]
+  Returns the list of vertices reachable from a given vertex.
+
+ ==== __Examples__
+
+ > reachable (buildG (0,0) []) 0 == [0]
+
+ > reachable (buildG (0,2) [(0,1), (1,2)]) 0 == [0,1,2]
+reachable :: Graph > Vertex > [Vertex]
reachable g v = preorderF (dfs g [v])
  Is the second vertex reachable from the first?
path :: Graph > Vertex > Vertex > Bool
+  Returns @True@ if the second vertex reachable from the first.
+
+ ==== __Examples__
+
+ > path (buildG (0,0) []) 0 0 == True
+
+ > path (buildG (0,2) [(0,1), (1,2)]) 0 2 == True
+
+ > path (buildG (0,2) [(0,1), (1,2)]) 2 0 == False
+path :: Graph > Vertex > Vertex > Bool
path g v w = w `elem` (reachable g v)

@@ 545,7 +675,7 @@ bcc g = (concat . map bicomps . map (do_label g dnum)) forest
where forest = dff g
dnum = preArr (bounds g) forest
do_label :: Graph > Table Int > Tree Vertex > Tree (Vertex,Int,Int)
+do_label :: Graph > Array Vertex Int > Tree Vertex > Tree (Vertex,Int,Int)
do_label g dnum (Node v ts) = Node (v,dnum!v,lv) us
where us = map (do_label g dnum) ts
lv = minimum ([dnum!v] ++ [dnum!w  w < g!v]

1.9.1