dep

Documentation

Overview

Package dep provides dependency graph analysis and manipulation logic.

Following the design style in `gonum/graph/flow`, type `graph.Directed` is wrapped in a new struct named `DependencyGraph` which includes two unexported fields:

- roots: map of root nodes where the key is the ID - leafs: map of leaf nodes where the key is the ID

Basic features, such as retrieving a map of roots/leafs, inducing a subgraph for a leaf or retrieving a valid schedule (topological sort) are already implemented. However, it'd be interesting to extend it with other common operations; `InduceAllIn`, `Reduce`, `Closure` and `Schedule` are on the roadmap.

References:

• Dependency graph: https://en.wikipedia.org/wiki/Dependency_graph
• Directed acyclic graph: https://en.wikipedia.org/wiki/Directed_acyclic_graph
• Induced subgraph: https://en.wikipedia.org/wiki/Induced_subgraph
• Transitive reduction: https://en.wikipedia.org/wiki/Transitive_reduction
• Transitive closure: https://en.wikipedia.org/wiki/Transitive_closure
• Topological sorting: https://en.wikipedia.org/wiki/Topological_sorting -- Kahn's algoritm: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm -- Coffman–Graham algorithm: https://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm

Index

• type DependencyGraph
  • func NewDependencyGraph(g *simple.DirectedGraph) *DependencyGraph
  • func (d *DependencyGraph) Induce(ns map[int64]graph.Node) map[int64]*DependencyGraph
  • func (d *DependencyGraph) InduceDir(ns map[int64]graph.Node, fw, rv bool) map[int64]*DependencyGraph
  • func (d *DependencyGraph) IsLeaf(id int64) bool
  • func (d *DependencyGraph) IsMid(id int64) bool
  • func (d *DependencyGraph) IsRoot(id int64) bool
  • func (d *DependencyGraph) Leafs() map[int64]graph.Node
  • func (d *DependencyGraph) Roots() map[int64]graph.Node
  • func (d *DependencyGraph) Sort() ([]graph.Node, error)
• type Inducer
  • func NewInducer(d *DependencyGraph) *Inducer
  • func (i *Inducer) Induce(d *DependencyGraph, u graph.Node, fw, rv bool)

Types

type DependencyGraph

type DependencyGraph struct {
	*simple.DirectedGraph
	// contains filtered or unexported fields
}

DependencyGraph is a dependency graph; a kind of directed acyclic graph (DAG).

func NewDependencyGraph

func NewDependencyGraph(g *simple.DirectedGraph) *DependencyGraph

NewDependencyGraph returns a DependencyGraph. If 'g' is nil, a new graph is created with 'simple.NewDirectedGraph'.

func (*DependencyGraph) Induce

func (d *DependencyGraph) Induce(ns map[int64]graph.Node) map[int64]*DependencyGraph

Induce induces a different subgraph for each of the given nodes of the dependency graph, where the node is a root (walk forward) or a leaf (reverse walk).

Complexity: O(len(ns) * (V + E))

func (*DependencyGraph) InduceDir

func (d *DependencyGraph) InduceDir(ns map[int64]graph.Node, fw, rv bool) map[int64]*DependencyGraph

InduceDir induces a different subgraph for each of the given nodes of the dependency graph, where the node can be any vertex (root, leaf or mid). It is possible to traverse the graph forward, in reverse or in both directions. Not that the following contexts will produce a subgraph with a single node: - a root node with reverse walk only - a leaf node with forward walk only - any node with neither forward nor reverse walk. a warning is shown in this case.

Complexity: O(len(ns) * (V + E))

func (*DependencyGraph) IsLeaf

func (d *DependencyGraph) IsLeaf(id int64) bool

IsLeaf returns true if the given id corresponds to a node which is a leaf.

Complexity: O(1) or O(V)

func (*DependencyGraph) IsMid

func (d *DependencyGraph) IsMid(id int64) bool

IsMid returns true if the given id corresponds to a mid node (i.e. neither a root nor a leaf).

Complexity: O(2) or O(V)

func (*DependencyGraph) IsRoot

func (d *DependencyGraph) IsRoot(id int64) bool

IsRoot returns true if the given id corresponds to a node which is a root.

Complexity: O(1) or O(V)

func (*DependencyGraph) Leafs

func (d *DependencyGraph) Leafs() map[int64]graph.Node

Leafs returns a map containing the nodes without outgoing edges (i.e. leaf nodes).

Complexity: O(1) or O(V)

func (*DependencyGraph) Roots

func (d *DependencyGraph) Roots() map[int64]graph.Node

Roots returns a map containing the nodes without incoming edges (i.e. root nodes).

Complexity: O(1) or O(V)

func (*DependencyGraph) Sort

func (d *DependencyGraph) Sort() ([]graph.Node, error)

Sort returns the topological order computed through 'topo.Sort', which implements reversed Tarjan SCC. On failure, the set or sets of nodes that are in directed cycles are provided, i.e. circular dependencies in the graph.

Complexity: O(V,E)

type Inducer

type Inducer struct {
	traverse.DepthFirst
	Graph *DependencyGraph
}

Inducer is a wrapper around 'traverse.DepthFirst' to induce a subgraph from a dependency graph; a kind of directed acyclic graph (DAG).

func NewInducer

func NewInducer(d *DependencyGraph) *Inducer

NewInducer returns a Inducer for a dependency graph.

func (*Inducer) Induce

func (i *Inducer) Induce(d *DependencyGraph, u graph.Node, fw, rv bool)

Induce walks a graph starting from a given node and generates a subgraph by copying all the traversed edges (and the nodes touched by them). 'fw' and 'rv' allow to select whether a forward walk is executed, a reverse walk or both of them.