Modulealgebraic-graphs-0.8Haskell2010

Data.Graph.Typed

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module provides primitives for interoperability between this library and the Data.Graph module of the containers library. It is for internal use only and may be removed without notice at any point.

1 type
7 values

Packagealgebraic-graphs-0.8
Exports8
LanguageHaskell2010
LicenceMIT
SourceTyped.hs

Data type and construction

3 declarations

datadata GraphKL a

GraphKL encapsulates King-Launchbury graphs, which are implemented in the Data.Graph module of the containers library.

Constructors

GraphKL
- toGraphKL :: Graph
  Array-based graph representation (King and Launchbury, 1995).
- fromVertexKL :: Vertex -> a
  A mapping of Data.Graph.Vertex to vertices of type a. This is partial and may fail if the vertex is out of bounds.
- toVertexKL :: a -> Maybe Vertex
  A mapping from vertices of type a to Data.Graph.Vertex. Returns Nothing if the argument is not in the graph.

valuefromAdjacencyMap :: Ord a => AdjacencyMap a -> GraphKL a

Build GraphKL from an AdjacencyMap. If fromAdjacencyMap g == h then the following holds:

map (fromVertexKL h) (vertices $ toGraphKL h)                               == vertexList g
map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g
toGraphKL (fromAdjacencyMap (1 * 2 + 3 * 1))                                == array (0,2) [(0,[1]), (1,[]), (2,[0])]
toGraphKL (fromAdjacencyMap (1 * 2 + 2 * 1))                                == array (0,1) [(0,[1]), (1,[0])]

valuefromAdjacencyIntMap :: AdjacencyIntMap -> GraphKL Int

Build GraphKL from an AdjacencyIntMap. If fromAdjacencyIntMap g == h then the following holds:

map (fromVertexKL h) (vertices $ toGraphKL h)                               == toAscList (vertexIntSet g)
map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g
toGraphKL (fromAdjacencyIntMap (1 * 2 + 3 * 1))                             == array (0,2) [(0,[1]), (1,[]), (2,[0])]
toGraphKL (fromAdjacencyIntMap (1 * 2 + 2 * 1))                             == array (0,1) [(0,[1]), (1,[0])]

Basic algorithms

5 declarations

valuedfsForest :: GraphKL a -> Forest a

Compute the depth-first search forest of a graph.

In the following examples we will use the helper function:

(%) :: Ord a => (GraphKL a -> b) -> AdjacencyMap a -> b
f % x = f (fromAdjacencyMap x)

for greater clarity.

forest (dfsForest % edge 1 1)           == vertex 1
forest (dfsForest % edge 1 2)           == edge 1 2
forest (dfsForest % edge 2 1)           == vertices [1,2]
isSubgraphOf (forest $ dfsForest % x) x == True
dfsForest % forest (dfsForest % x)      == dfsForest % x
dfsForest % vertices vs                 == map (\v -> Node v []) (nub $ sort vs)
dfsForest % (3 * (1 + 4) * (1 + 5))     == [ Node { rootLabel = 1
                                                  , subForest = [ Node { rootLabel = 5
                                                                       , subForest = [] }]}
                                           , Node { rootLabel = 3
                                                  , subForest = [ Node { rootLabel = 4
                                                                       , subForest = [] }]}]

valuedfsForestFrom :: GraphKL a -> [a] -> Forest a

Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable.

In the following examples we will use the helper function:

(%) :: Ord a => (GraphKL a -> b) -> AdjacencyMap a -> b
f % x = f (fromAdjacencyMap x)

for greater clarity.

forest $ (dfsForestFrom % edge 1 1) [1]          == vertex 1
forest $ (dfsForestFrom % edge 1 2) [0]          == empty
forest $ (dfsForestFrom % edge 1 2) [1]          == edge 1 2
forest $ (dfsForestFrom % edge 1 2) [2]          == vertex 2
forest $ (dfsForestFrom % edge 1 2) [2,1]        == vertices [1,2]
isSubgraphOf (forest $ dfsForestFrom % x $ vs) x == True
dfsForestFrom % x $ vertexList x                 == dfsForest % x
dfsForestFrom % vertices vs $ vs                 == map (\v -> Node v []) (nub vs)
dfsForestFrom % x $ []                           == []
dfsForestFrom % (3 * (1 + 4) * (1 + 5)) $ [1,4]  == [ Node { rootLabel = 1
                                                           , subForest = [ Node { rootLabel = 5
                                                                                , subForest = [] }
                                                    , Node { rootLabel = 4
                                                           , subForest = [] }]

valuedfs :: GraphKL a -> [a] -> [a]

Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order.

In the following examples we will use the helper function:

(%) :: Ord a => (GraphKL a -> b) -> AdjacencyMap a -> b
f % x = f (fromAdjacencyMap x)

for greater clarity.

dfs % edge 1 1 $ [1]   == [1]
dfs % edge 1 2 $ [0]   == []
dfs % edge 1 2 $ [1]   == [1,2]
dfs % edge 1 2 $ [2]   == [2]
dfs % edge 1 2 $ [1,2] == [1,2]
dfs % edge 1 2 $ [2,1] == [2,1]
dfs % x        $ []    == []

dfs % (3 * (1 + 4) * (1 + 5)) $ [1,4]     == [1,5,4]
Data.List.and [ hasVertex v x | v <- dfs % x $ vs ] == True

valuetopSort :: GraphKL a -> [a]

Compute the topological sort of a graph. Note that this function returns a result even if the graph is cyclic.

In the following examples we will use the helper function:

(%) :: Ord a => (GraphKL a -> b) -> AdjacencyMap a -> b
f % x = f (fromAdjacencyMap x)

for greater clarity.

topSort % (1 * 2 + 3 * 1) == [3,1,2]
topSort % (1 * 2 + 2 * 1) == [1,2]

valuescc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a)