dag

Documentation

Overview

Package dag implements a language for expressing directed acyclic graphs.

The general syntax of a rule is:

a, b < c, d;

which means c and d come after a and b in the partial order (that is, there are edges from c and d to a and b), but doesn't provide a relative order between a vs b or c vs d.

The rules can chain together, as in:

e < f, g < h;

which is equivalent to

e < f, g;
f, g < h;

Except for the special bottom element "NONE", each name must appear exactly once on the right-hand side of any rule. That rule serves as the definition of the allowed successor for that name. The definition must appear before any uses of the name on the left-hand side of a rule. (That is, the rules themselves must be ordered according to the partial order, for easier reading by people.)

Negative assertions double-check the partial order:

i !< j

means that it must NOT be the case that i < j. Negative assertions may appear anywhere in the rules, even before i and j have been defined.

Comments begin with #.

Index

• type Graph
  • func Parse(dag string) (*Graph, error)
  • func (g *Graph) AddEdge(from, to string)
  • func (g *Graph) DelEdge(from, to string)
  • func (g *Graph) Edges(from string) []string
  • func (g *Graph) HasEdge(from, to string) bool
  • func (g *Graph) Topo() []string
  • func (g *Graph) TransitiveReduction()
  • func (g *Graph) Transpose()

Types

type Graph

type Graph struct {
	Nodes []string
	// contains filtered or unexported fields
}

func Parse

func Parse(dag string) (*Graph, error)

Parse parses the DAG language and returns the transitive closure of the described graph. In the returned graph, there is an edge from "b" to "a" if b < a (or a > b) in the partial order.

func (*Graph) AddEdge

func (g *Graph) AddEdge(from, to string)

func (*Graph) DelEdge

func (g *Graph) DelEdge(from, to string)

func (*Graph) Edges

func (g *Graph) Edges(from string) []string

func (*Graph) HasEdge

func (g *Graph) HasEdge(from, to string) bool

func (*Graph) Topo

func (g *Graph) Topo() []string

Topo returns a topological sort of g. This function is deterministic.

func (*Graph) TransitiveReduction

func (g *Graph) TransitiveReduction()

TransitiveReduction removes edges from g that are transitively reachable. g must be transitively closed.

func (*Graph) Transpose

func (g *Graph) Transpose()

Transpose reverses all edges in g.