Spark.Core.Internal.DAGFunctions

A set of utility functions to build and transform DAGs.

Because I could not find a public library for such transforms.

Most krapsh manipulations are converted into graph manipulations.

Documentation

type DagTry a = Either Text a

Separate type of error to make it more general and easier to test.

buildGraph :: forall v e. (GraphOperations v e, Show v, Show e) => v -> DagTry (Graph v e)

Builds a graph by expanding a start vertex.

buildVertexList :: (GraphVertexOperations v, Show v) => v -> DagTry [v]

Starts from a vertex and expands the vertex to reach all the transitive closure of the vertex.

Returns a list in lexicographic order of dependencies: the graph corresponding to this list of elements has one sink (the start element) and potentially multiple sources. The nodes are ordered so that all the parents are visited before the node itself.

buildGraphFromList :: forall v e. (Show v, Show e) => [Vertex v] -> [Edge e] -> DagTry (Graph v e)

Attempts to build a graph from a collection of vertices and edges.

This collection may be invalid (cycles, etc.) and the vertices need not be in topological order.

All the vertices referred by edges must be present in the list of vertices.

graphSinks :: Graph v e -> [Vertex v]

The sinks of a graph (nodes with no descendant).

graphSources :: Graph v e -> [Vertex v]

The sources of a DAG (nodes with no parent).

graphMapVertices :: forall m v e v2. (HasCallStack, Show v2, Show v, Show e, Monad m) => Graph v e -> (v -> [(v2, e)] -> m v2) -> m (Graph v2 e)

A generic transform over the graph that may account for potential failures in the process.

graphMapVertices' :: (Show v, Show e, Show v') => (v -> v') -> Graph v e -> Graph v' e

(internal) Maps the vertices.

vertexMap :: Graph v e -> Map VertexId v

The map of vertices, by vertex id.

graphFlatMapEdges :: Graph v e -> (e -> [e']) -> Graph v e'

(internal) Maps and the edges, and may create more or less.

graphMapEdges :: Graph v e -> (e -> e') -> Graph v e'

(internal) Maps the edges

reverseGraph :: forall v e. (HasCallStack, Show v, Show e) => Graph v e -> Graph v e

Flips the edges of this graph (it is also a DAG)

verticesAndEdges :: Graph v e -> [([(v, e)], v)]