# dag: Compile-time, type-safe directed acyclic graphs.

This is a type-safe approach for a directed acyclic graph.

Edge construction is incremental, creating a "schema":

import Data.Graph.DAG.Edge -- | Edges are statically defined: edges = ECons (Edge :: EdgeValue "foo" "bar") $ ECons (Edge :: EdgeValue "bar" "baz") $ ECons (Edge :: EdgeValue "foo" "baz") unique -- ENil, but casted for uniquely edged graphs

The nodes are separate from edges; graph may be not connected:

data Cool = AllRight | Radical | SuperDuper nodes = nadd "foo" AllRight $ nadd "bar" Radical $ nadd "baz" SuperDuper $ nempty

Some type tomfoolery:

*Data.Graph.DAG> :t edges edges :: EdgeSchema '['EdgeType "foo" "bar", 'EdgeType "bar" "baz", 'EdgeType "foo" "baz"] -- Type list of edges '['("foo", '["bar", "baz"]), '("bar", '["baz"])] -- potential loops 'True -- uniqueness *Data.Graph.DAG> :t getSpanningTrees $ edges getSpanningTrees $ edges :: Data.Proxy.Proxy '['Node "foo" '['Node "bar" '['Node "baz" '[]] ,'Node "baz" '[]] ,'Node "bar" '['Node "baz" '[]] ,'Node "baz" '[]] *Data.Graph.DAG> reflect $ getSpanningTrees $ edges [Node "foo" [Node "bar" [Node "baz" []] ,Node "baz" []] ,Node "bar" [Node "baz" []] ,Node "baz" []]

We can also look at the edges, first-class:

*Data.Graph.DAG> fcEdges edges [("foo","bar"),("foo","baz"),("bar","baz")]

Note that a `NodeSchema`

's keys don't have to be in-sync with it's paired
`EdgeSchema`

. After we have both, we can construct a `DAG`

:

graph = DAG edges nodes

Now we can do fun things, like get the spanning tree of a node:

*Data.Graph.DAG> gtree "foo" graph Just (AllRight :@-> [Radical :@-> [SuperDuper :@-> []] ,SuperDuper :@-> []])

This library is still very naive, but it will give us compile-time enforcement of acyclicity (and uniqueness) in these graphs - ideal for dependency graphs.

The main deficiency of this graph is that our `EdgeSchema`

can't be
*deconstructed* soundly - there is just too much information loss between the
value and type levels. This means we can't delete edges or look inside, but we
can still add edges or work with the resulting structure.

Versions | 0.0.1, 0.0.2, 0.0.2.1, 0.1, 0.1.0.1, 0.1.0.2 (info) |
---|---|

Dependencies | base (>=4.7 && <5), constraints, singletons [details] |

License | BSD-3-Clause |

Author | Athan Clark <athan.clark@gmail.com> |

Maintainer | Athan Clark <athan.clark@gmail.com> |

Source repo | head: git clone https://github.com/athanclark/dag |

Uploaded | by athanclark at Fri Jan 23 18:19:26 UTC 2015 |

Distributions | NixOS:0.1.0.2 |

Downloads | 1965 total (16 in the last 30 days) |

Rating | (no votes yet) [estimated by rule of succession] |

Your Rating | |

Status | Docs uploaded by user Build status unknown [no reports yet] Hackage Matrix CI |

## Modules

[Index]

## Downloads

- dag-0.1.0.2.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)