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

 graph =
   GCons "foo" AllRight $
   GCons "bar" Radical $
   GCons "baz" SuperDuper $
   GNil edges

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" []]

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.

Modules

[Index]

Downloads

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

Maintainer's Corner

Package maintainers

• athanclark

For package maintainers and hackage trustees

• edit package information

Candidates

• No Candidates