dag

Documentation

Index

• type Graph
  • func New[K comparable, T any]() *Graph[K, T]
  • func WithCapacity[K comparable, T any](capacity int) *Graph[K, T]
  • func (g *Graph[K, T]) AddEdge(from, to K) error
  • func (g *Graph[K, T]) AddVertex(id K, item T) error
  • func (g *Graph[K, T]) ContainsVertex(id K) bool
  • func (g *Graph[K, T]) GetVertex(id K) (T, error)
  • func (g *Graph[K, T]) Order() int
  • func (g *Graph[K, T]) Size() int
  • func (g *Graph[K, T]) Sort() ([]T, error)

Types

type Graph

type Graph[K comparable, T any] struct {
	// contains filtered or unexported fields
}

Graph is a generic directed acyclic graph, generic over 'K' which is a comparable type to be used as the unique ID for each vertex and 'T' which is the data you wish to store in each vertex of the graph.

The ID must be unique within a Graph.

func New

func New[K comparable, T any]() *Graph[K, T]

New creates and returns a new Graph.

It is generic over 'K' which is a comparable type to be used as the unique ID for each vertex, and 'T' which is the data you wish to store in each vertex of the graph.

So for a graph storing integers with a unique ID that is a string, the signature would be:

graph := dag.New[string, int]()

The ID must be unique within a Graph.

func WithCapacity

func WithCapacity[K comparable, T any](capacity int) *Graph[K, T]

WithCapacity creates and returns a new Graph with the given capacity.

This can be a useful performance improvement if the expected maximum number of elements the graph will hold is known ahead of time as it eliminates the need for reallocation.

func (*Graph[K, T]) AddEdge

func (g *Graph[K, T]) AddEdge(from, to K) error

AddEdge creates a connection from the vertex with id 'from' and one with id 'to'.

For the canonical use of a DAG (dependency graph), a dependency relationship of task "two" depends on task "one" the signature would be:

AddEdge("one", "two")

func (*Graph[K, T]) AddVertex

func (g *Graph[K, T]) AddVertex(id K, item T) error

AddVertex adds an item to the graph as a vertex (or node) in the graph.

If the vertex already exists, an error will be returned.

graph := dag.New[string, int]()
graph.AddVertex("one", 1)

The ID must uniquely identify a single vertex in the Graph.

func (*Graph[K, T]) ContainsVertex

func (g *Graph[K, T]) ContainsVertex(id K) bool

ContainsVertex reports whether a vertex with the given id is present in the graph.

func (*Graph[K, T]) GetVertex

func (g *Graph[K, T]) GetVertex(id K) (T, error)

GetVertex returns the item stored in a vertex.

If the vertex does not exist, an error will be returned.

func (*Graph[K, T]) Order

func (g *Graph[K, T]) Order() int

Order returns the number of vertices in the graph.

func (*Graph[K, T]) Size

func (g *Graph[K, T]) Size() int

Size returns the number of edges in the graph.

func (*Graph[K, T]) Sort

func (g *Graph[K, T]) Sort() ([]T, error)

Sort returns the topological sort of the graph, returning the underlying items in the correct order.

A DAG may have multiple valid topological sorts, the one returned from this function is guaranteed to be valid but is not deterministic.