dag

Imports

Imports #

"cmp"
"fmt"
"slices"
"strings"

Type Aliases

syntaxError type #

type syntaxError string

Structs

Graph struct #

type Graph struct {
Nodes []string
byLabel map[string]int
edges map[string]map[string]bool
}

rule struct #

A rule is a line in the DAG language where "less < def" or "less !< def".

type rule struct {
less []string
op string
def []string
}

rulesParser struct #

A rulesParser parses the depsRules syntax described above.

type rulesParser struct {
lineno int
lastWord string
text string
}

Functions

AddEdge method #

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

DelEdge method #

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

Edges method #

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

Error method #

func (e syntaxError) Error() string

HasEdge method #

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

Parse function #

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 Parse(dag string) (*Graph, error)

Topo method #

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

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

TransitiveReduction method #

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

func (g *Graph) TransitiveReduction()

Transpose method #

Transpose reverses all edges in g.

func (g *Graph) Transpose()

addNode method #

func (g *Graph) addNode(label string) bool

newGraph function #

func newGraph() *Graph

nextList method #

nextList parses and returns a comma-separated list of names.

func (p *rulesParser) nextList() (list []string, token string)

nextToken method #

nextToken returns the next token in the deps rules, one of ";" "," "<" "!<" or a name.

func (p *rulesParser) nextToken() string

parseRules function #

parseRules parses the rules of a DAG.

func parseRules(rules string) (out []rule, err error)

syntaxError method #

syntaxError reports a parsing error.

func (p *rulesParser) syntaxError(msg string)

Generated with Arrow