dag

Documentation

Index

• func StronglyConnected(g *Graph) [][]Vertex
• func VertexName(raw Vertex) string
• type AcyclicGraph
  • func (g *AcyclicGraph) Ancestors(v Vertex) (*Set, error)
  • func (g *AcyclicGraph) Cycles() [][]Vertex
  • func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error
  • func (g *AcyclicGraph) Descendents(v Vertex) (*Set, error)
  • func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error
  • func (g *AcyclicGraph) Root() (Vertex, error)
  • func (g *AcyclicGraph) TransitiveReduction()
  • func (g *AcyclicGraph) Validate() error
  • func (g *AcyclicGraph) Walk(cb WalkFunc) error
• type DepthWalkFunc
• type Edge
  • func BasicEdge(source, target Vertex) Edge
• type Graph
  • func (g *Graph) Add(v Vertex) Vertex
  • func (g *Graph) Connect(edge Edge)
  • func (g *Graph) DownEdges(v Vertex) *Set
  • func (g *Graph) Edges() []Edge
  • func (g *Graph) HasEdge(e Edge) bool
  • func (g *Graph) HasVertex(v Vertex) bool
  • func (g *Graph) Remove(v Vertex) Vertex
  • func (g *Graph) RemoveEdge(edge Edge)
  • func (g *Graph) Replace(original, replacement Vertex) bool
  • func (g *Graph) String() string
  • func (g *Graph) StringWithNodeTypes() string
  • func (g *Graph) UpEdges(v Vertex) *Set
  • func (g *Graph) Vertices() []Vertex
• type Hashable
• type NamedVertex
• type Set
  • func (s *Set) Add(v interface{})
  • func (s *Set) Delete(v interface{})
  • func (s *Set) Include(v interface{}) bool
  • func (s *Set) Intersection(other *Set) *Set
  • func (s *Set) Len() int
  • func (s *Set) List() []interface{}
• type Vertex
  • func AsVertexList(s *Set) []Vertex
• type WalkFunc

Functions

func StronglyConnected

func StronglyConnected(g *Graph) [][]Vertex

StronglyConnected returns the list of strongly connected components within the Graph g. This information is primarily used by this package for cycle detection, but strongly connected components have widespread use.

func VertexName

func VertexName(raw Vertex) string

VertexName returns the name of a vertex.

Types

type AcyclicGraph

type AcyclicGraph struct {
	Graph
}

AcyclicGraph is a specialization of Graph that cannot have cycles. With this property, we get the property of sane graph traversal.

func (*AcyclicGraph) Ancestors

func (g *AcyclicGraph) Ancestors(v Vertex) (*Set, error)

Returns a Set that includes every Vertex yielded by walking down from the provided starting Vertex v.

func (*AcyclicGraph) Cycles

func (g *AcyclicGraph) Cycles() [][]Vertex

func (*AcyclicGraph) DepthFirstWalk

func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error

depthFirstWalk does a depth-first walk of the graph starting from the vertices in start. This is not exported now but it would make sense to export this publicly at some point.

func (*AcyclicGraph) Descendents

func (g *AcyclicGraph) Descendents(v Vertex) (*Set, error)

Returns a Set that includes every Vertex yielded by walking up from the provided starting Vertex v.

func (*AcyclicGraph) ReverseDepthFirstWalk

func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error

reverseDepthFirstWalk does a depth-first walk _up_ the graph starting from the vertices in start.

func (*AcyclicGraph) Root

func (g *AcyclicGraph) Root() (Vertex, error)

Root returns the root of the DAG, or an error.

Complexity: O(V)

func (*AcyclicGraph) TransitiveReduction

func (g *AcyclicGraph) TransitiveReduction()

TransitiveReduction performs the transitive reduction of graph g in place. The transitive reduction of a graph is a graph with as few edges as possible with the same reachability as the original graph. This means that if there are three nodes A => B => C, and A connects to both B and C, and B connects to C, then the transitive reduction is the same graph with only a single edge between A and B, and a single edge between B and C.

The graph must be valid for this operation to behave properly. If Validate() returns an error, the behavior is undefined and the results will likely be unexpected.

Complexity: O(V(V+E)), or asymptotically O(VE)

func (*AcyclicGraph) Validate

func (g *AcyclicGraph) Validate() error

Validate validates the DAG. A DAG is valid if it has a single root with no cycles.

func (*AcyclicGraph) Walk

func (g *AcyclicGraph) Walk(cb WalkFunc) error

Walk walks the graph, calling your callback as each node is visited. This will walk nodes in parallel if it can. Because the walk is done in parallel, the error returned will be a multierror.

type DepthWalkFunc

type DepthWalkFunc func(Vertex, int) error

DepthWalkFunc is a walk function that also receives the current depth of the walk as an argument

type Edge

type Edge interface {
	Source() Vertex
	Target() Vertex

	Hashable
}

Edge represents an edge in the graph, with a source and target vertex.

func BasicEdge

func BasicEdge(source, target Vertex) Edge

BasicEdge returns an Edge implementation that simply tracks the source and target given as-is.

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph is used to represent a dependency graph.

func (*Graph) Add

func (g *Graph) Add(v Vertex) Vertex

Add adds a vertex to the graph. This is safe to call multiple time with the same Vertex.

func (*Graph) Connect

func (g *Graph) Connect(edge Edge)

Connect adds an edge with the given source and target. This is safe to call multiple times with the same value. Note that the same value is verified through pointer equality of the vertices, not through the value of the edge itself.

func (*Graph) DownEdges

func (g *Graph) DownEdges(v Vertex) *Set

DownEdges returns the outward edges from the source Vertex v.

func (*Graph) Edges

func (g *Graph) Edges() []Edge

Edges returns the list of all the edges in the graph.

func (*Graph) HasEdge

func (g *Graph) HasEdge(e Edge) bool

HasEdge checks if the given Edge is present in the graph.

func (*Graph) HasVertex

func (g *Graph) HasVertex(v Vertex) bool

HasVertex checks if the given Vertex is present in the graph.

func (*Graph) Remove

func (g *Graph) Remove(v Vertex) Vertex

Remove removes a vertex from the graph. This will also remove any edges with this vertex as a source or target.

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(edge Edge)

RemoveEdge removes an edge from the graph.

func (*Graph) Replace

func (g *Graph) Replace(original, replacement Vertex) bool

Replace replaces the original Vertex with replacement. If the original does not exist within the graph, then false is returned. Otherwise, true is returned.

func (*Graph) String

func (g *Graph) String() string

String outputs some human-friendly output for the graph structure.

func (*Graph) StringWithNodeTypes

func (g *Graph) StringWithNodeTypes() string

String outputs some human-friendly output for the graph structure.

func (*Graph) UpEdges

func (g *Graph) UpEdges(v Vertex) *Set

UpEdges returns the inward edges to the destination Vertex v.

func (*Graph) Vertices

func (g *Graph) Vertices() []Vertex

Vertices returns the list of all the vertices in the graph.

type Hashable

type Hashable interface {
	Hashcode() interface{}
}

Hashable is the interface used by set to get the hash code of a value. If this isn't given, then the value of the item being added to the set itself is used as the comparison value.

type NamedVertex

type NamedVertex interface {
	Vertex
	Name() string
}

NamedVertex is an optional interface that can be implemented by Vertex to give it a human-friendly name that is used for outputting the graph.

type Set

type Set struct {
	// contains filtered or unexported fields
}

Set is a set data structure.

func (*Set) Add

func (s *Set) Add(v interface{})

Add adds an item to the set

func (*Set) Delete

func (s *Set) Delete(v interface{})

Delete removes an item from the set.

func (*Set) Include

func (s *Set) Include(v interface{}) bool

Include returns true/false of whether a value is in the set.

func (*Set) Intersection

func (s *Set) Intersection(other *Set) *Set

Intersection computes the set intersection with other.

func (*Set) Len

func (s *Set) Len() int

Len is the number of items in the set.

func (*Set) List

func (s *Set) List() []interface{}

List returns the list of set elements.

type Vertex

type Vertex interface{}

Vertex of the graph.

func AsVertexList

func AsVertexList(s *Set) []Vertex

simple convenience helper for converting a dag.Set to a []Vertex

type WalkFunc

type WalkFunc func(Vertex) error

WalkFunc is the callback used for walking the graph.