dagg

package module
v0.0.4-0...-10add5c Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 26, 2022 License: MPL-2.0 Imports: 6 Imported by: 0

README

Golang DAG[ T ] (Directed Acyclic Graph)

This is a generic DAG based largely on the work of Hashicorp. The intent of this library is to allow for anyone to create a DAG using any datatype so long as it implements Hashcode() string, that does not require casting the interface upon getting from the dag. The files in this code were taken from this commit

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AsVertexList 

func AsVertexList[T Hashable](s Set[T]) []T

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

func StronglyConnected 

func StronglyConnected[T Hashable](g *Graph[T]) [][]T

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[T Hashable](raw T) string

VertexName returns the name of a vertex.

Types

type AcyclicGraph 

type AcyclicGraph[T Hashable] struct {
	Graph[T]
}

AcyclicGraph is a specialization of Graph that cannot have cycles.

func (*AcyclicGraph[T]) Ancestors 

func (g *AcyclicGraph[T]) Ancestors(v T) (Set[T], error)

Returns a Set that includes every Vertex yielded by walking up from the provided starting Vertex v. Ancestors will include all root vertexes that can be reached by walking up from v.

func (*AcyclicGraph[T]) Cycles 

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

func (*AcyclicGraph[T]) DepthFirstWalk 

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

DepthFirstWalk does a depth-first walk of the graph starting from the vertices in start.

func (*AcyclicGraph[T]) Descendents 

func (g *AcyclicGraph[T]) Descendents(v T) (Set[T], error)

Returns a Set that includes every Vertex yielded by walking down from the provided starting Vertex v. Descendents will NOT include root vertexes that can be reached by walking up from v.

func (*AcyclicGraph[T]) DirectedGraph 

func (g *AcyclicGraph[T]) DirectedGraph() Grapher

func (*AcyclicGraph[T]) ReverseDepthFirstWalk 

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

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

func (*AcyclicGraph[T]) Roots 

func (g *AcyclicGraph[T]) Roots() ([]T, error)

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

Complexity: O(V)

func (*AcyclicGraph[T]) SortedDepthFirstWalk 

func (g *AcyclicGraph[T]) SortedDepthFirstWalk(start []T, f DepthWalkFunc[T]) error

SortedDepthFirstWalk does a depth-first walk of the graph starting from the vertices in start, always iterating the nodes in a consistent order.

func (*AcyclicGraph[T]) SortedReverseDepthFirstWalk 

func (g *AcyclicGraph[T]) SortedReverseDepthFirstWalk(start []T, f DepthWalkFunc[T]) error

SortedReverseDepthFirstWalk does a depth-first walk _up_ the graph starting from the vertices in start, always iterating the nodes in a consistent order.

func (*AcyclicGraph[T]) TransitiveReduction 

func (g *AcyclicGraph[T]) 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[T]) Validate 

func (g *AcyclicGraph[T]) Validate() error

Validate validates the DAG. A DAG is valid if it has at least one root and no cycles.

type DepthWalkFunc 

type DepthWalkFunc[T Hashable] func(T, int) error

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

type DotNode 

type DotNode struct {
	Name  string
	Attrs map[string]string
}

DotNode provides a structure for Vertices to return in order to specify their dot format.

type DotOpts 

type DotOpts struct {
	// Allows some nodes to decide to only show themselves when the user has
	// requested the "verbose" graph.
	Verbose bool

	// Highlight Cycles
	DrawCycles bool

	// How many levels to expand modules as we draw
	MaxDepth int
	// contains filtered or unexported fields
}

DotOpts are the options for generating a dot formatted Graph.

type Edge 

type Edge[T Hashable] interface {
	Source() T
	Target() T

	Hashable
}

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

func BasicEdge 

func BasicEdge[T Hashable](source, target T) Edge[T]

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

type Graph 

type Graph[T Hashable] struct {
	// contains filtered or unexported fields
}

Graph is used to represent a dependency graph.

func (*Graph[T]) Add 

func (g *Graph[T]) Add(v T) T

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

func (*Graph[T]) Connect 

func (g *Graph[T]) Connect(edge Edge[T])

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[T]) DirectedGraph 

func (g *Graph[T]) DirectedGraph() Grapher

func (*Graph[T]) Dot 

func (g *Graph[T]) Dot(opts *DotOpts) []byte

Dot returns a dot-formatted representation of the Graph.

func (*Graph[T]) DownEdges 

func (g *Graph[T]) DownEdges(v T) Set[T]

DownEdges returns the vertices connected from the inward edges to Vertex v.

func (*Graph[T]) Edges 

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

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

func (*Graph[T]) EdgesFrom 

func (g *Graph[T]) EdgesFrom(v T) []Edge[T]

EdgesFrom returns the list of edges from the given source.

func (*Graph[T]) EdgesTo 

func (g *Graph[T]) EdgesTo(v T) []Edge[T]

EdgesTo returns the list of edges to the given target.

func (*Graph[T]) HasEdge 

func (g *Graph[T]) HasEdge(e Edge[T]) bool

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

func (*Graph[T]) HasVertex 

func (g *Graph[T]) HasVertex(v T) bool

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

func (*Graph[T]) Remove 

func (g *Graph[T]) Remove(v T) T

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

func (*Graph[T]) RemoveEdge 

func (g *Graph[T]) RemoveEdge(edge Edge[T])

RemoveEdge removes an edge from the graph.

func (*Graph[T]) Replace 

func (g *Graph[T]) Replace(original, replacement T) 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[T]) String 

func (g *Graph[T]) String() string

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

func (*Graph[T]) StringWithNodeTypes 

func (g *Graph[T]) StringWithNodeTypes() string

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

func (*Graph[T]) UpEdges 

func (g *Graph[T]) UpEdges(v T) Set[T]

UpEdges returns the vertices connected to the outward edges from the source Vertex v.

func (*Graph[T]) Vertices 

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

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

type GraphNodeDotter 

type GraphNodeDotter interface {
	// Dot is called to return the dot formatting for the node.
	// The first parameter is the title of the node.
	// The second parameter includes user-specified options that affect the dot
	// graph. See GraphDotOpts below for details.
	DotNode(string, *DotOpts) *DotNode
}

GraphNodeDotter can be implemented by a node to cause it to be included in the dot graph. The Dot method will be called which is expected to return a representation of this node.

type Grapher 

type Grapher interface {
	DirectedGraph() Grapher
}

A Grapher is any type that returns a Grapher, mainly used to identify dag.Graph and dag.AcyclicGraph. In the case of Graph and AcyclicGraph, they return themselves.

type Hashable 

type Hashable interface {
	Hashcode() string
}

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 Named 

type Named interface {
	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[T Hashable] map[string]T

Set is a set data structure.

func (Set[T]) Add 

func (s Set[T]) Add(v T)

Add adds an item to the set

func (Set[T]) Copy 

func (s Set[T]) Copy() Set[T]

Copy returns a shallow copy of the set.

func (Set[T]) Delete 

func (s Set[T]) Delete(v T)

Delete removes an item from the set.

func (Set[T]) Difference 

func (s Set[T]) Difference(other Set[T]) Set[T]

Difference returns a set with the elements that s has but other doesn't.

func (Set[T]) Filter 

func (s Set[T]) Filter(cb func(T) bool) Set[T]

Filter returns a set that contains the elements from the receiver where the given callback returns true.

func (Set[T]) Include 

func (s Set[T]) Include(v T) bool

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

func (Set[T]) Intersection 

func (s Set[T]) Intersection(other Set[T]) Set[T]

Intersection computes the set intersection with other.

func (Set[T]) Len 

func (s Set[T]) Len() int

Len is the number of items in the set.

func (Set[T]) List 

func (s Set[T]) List() []T

List returns the list of set elements.

type Subgrapher 

type Subgrapher interface {
	Subgraph() Grapher
}

Subgrapher allows a Vertex to be a Graph itself, by returning a Grapher.

type WalkFunc 

type WalkFunc[T Hashable] func(T)

WalkFunc is the callback used for walking the graph.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.