dag

Documentation

Index

• Variables
• type DAG
  • func NewDAG[T comparable]() DAG[T]
• type Vertex
  • func NewVertex[T comparable](id string, value T) *Vertex[T]
  • func (v *Vertex[T]) Degree() int
  • func (v *Vertex[T]) InDegree() int
  • func (v *Vertex[T]) OutDegree() int

Variables

var (
	// ErrVertexNotFound represents vertex not found.
	ErrVertexNotFound = errors.New("vertex not found")

	// ErrVertexAlreadyExists represents vertex already exists.
	ErrVertexAlreadyExists = errors.New("vertex already exists")

	// ErrParnetAlreadyExists represents parent of vertex already exists.
	ErrParnetAlreadyExists = errors.New("parent of vertex already exists")

	// ErrChildAlreadyExists represents child of vertex already exists.
	ErrChildAlreadyExists = errors.New("child of vertex already exists")

	// ErrCycleBetweenVertices represents cycle between vertices.
	ErrCycleBetweenVertices = errors.New("cycle between vertices")
)

Types

type DAG

type DAG[T comparable] interface {
	// AddVertex adds vertex to graph.
	AddVertex(id string, value T) error

	// DeleteVertex deletes vertex graph.
	DeleteVertex(id string)

	// GetVertex gets vertex from graph.
	GetVertex(id string) (*Vertex[T], error)

	// GetVertices returns map of vertices.
	GetVertices() map[string]*Vertex[T]

	// GetRandomVertices returns random map of vertices.
	GetRandomVertices(n uint) []*Vertex[T]

	// GetVertexKeys returns keys of vertices.
	GetVertexKeys() []string

	// GetSourceVertices returns source vertices.
	GetSourceVertices() []*Vertex[T]

	// GetSinkVertices returns sink vertices.
	GetSinkVertices() []*Vertex[T]

	// VertexCount returns count of vertices.
	VertexCount() int

	// AddEdge adds edge between two vertices.
	AddEdge(fromVertexID, toVertexID string) error

	// DeleteEdge deletes edge between two vertices.
	DeleteEdge(fromVertexID, toVertexID string) error

	// CanAddEdge finds whether there are circles through depth-first search.
	CanAddEdge(fromVertexID, toVertexID string) bool

	// DeleteVertexInEdges deletes inedges of vertex.
	DeleteVertexInEdges(id string) error

	// DeleteVertexOutEdges deletes outedges of vertex.
	DeleteVertexOutEdges(id string) error
}

DAG is the interface used for directed acyclic graph.

func NewDAG

func NewDAG[T comparable]() DAG[T]

New returns a new DAG interface.

type Vertex

type Vertex[T comparable] struct {
	ID       string
	Value    T
	Parents  set.SafeSet[*Vertex[T]]
	Children set.SafeSet[*Vertex[T]]
}

Vertex is a vertex of the directed acyclic graph.

func NewVertex

func NewVertex[T comparable](id string, value T) *Vertex[T]

New returns a new Vertex instance.

func (*Vertex[T]) Degree

func (v *Vertex[T]) Degree() int

Degree returns the degree of vertex.

func (*Vertex[T]) InDegree

func (v *Vertex[T]) InDegree() int

InDegree returns the indegree of vertex.

func (*Vertex[T]) OutDegree

func (v *Vertex[T]) OutDegree() int

OutDegree returns the outdegree of vertex.