graph

Documentation

Overview

Package graph provides functionality for directed graphs.

Index

• type Edge
• type Graph
  • func New[V comparable](vertices ...V) *Graph[V]
  • func (g *Graph[V]) Add(edge Edge[V])
  • func (g *Graph[V]) InDegree(vtx V) int
  • func (g *Graph[V]) IsAcyclic() ([]V, bool)
  • func (g *Graph[V]) Neighbors(vtx V) []V
  • func (g *Graph[V]) Remove(edge Edge[V])
  • func (g *Graph[V]) Roots() []V
• type LabeledGraph
  • func NewLabeledGraph[V comparable](vertices []V) *LabeledGraph[V]
  • func (lg *LabeledGraph[V]) DownwardTraversal(ctx context.Context, processVertexFunc func(context.Context, V) error) error
  • func (lg *LabeledGraph[V]) UpwardTraversal(ctx context.Context, processVertexFunc func(context.Context, V) error) error
• type TopologicalSorter
  • func TopologicalOrder[V comparable](digraph *Graph[V]) (*TopologicalSorter[V], error)
  • func (alg *TopologicalSorter[V]) Rank(vtx V) (int, bool)

Types

type Edge

type Edge[V comparable] struct {
	From V
	To   V
}

Edge represents one edge of a directed graph.

type Graph

type Graph[V comparable] struct {
	// contains filtered or unexported fields
}

Graph represents a directed graph.

func New

func New[V comparable](vertices ...V) *Graph[V]

New initiates a new Graph.

func (*Graph[V]) Add

func (g *Graph[V]) Add(edge Edge[V])

Add adds a connection between two vertices.

func (*Graph[V]) InDegree

func (g *Graph[V]) InDegree(vtx V) int

InDegree returns the number of incoming edges to vtx.

func (*Graph[V]) IsAcyclic

func (g *Graph[V]) IsAcyclic() ([]V, bool)

IsAcyclic checks if the graph is acyclic. If not, return the first detected cycle.

func (*Graph[V]) Neighbors

func (g *Graph[V]) Neighbors(vtx V) []V

Neighbors returns the list of connected vertices from vtx.

func (*Graph[V]) Remove

func (g *Graph[V]) Remove(edge Edge[V])

Remove deletes a connection between two vertices.

func (*Graph[V]) Roots

func (g *Graph[V]) Roots() []V

Roots returns a slice of vertices with no incoming edges.

type LabeledGraph

type LabeledGraph[V comparable] struct {
	*Graph[V]
	// contains filtered or unexported fields
}

LabeledGraph extends a generic Graph by associating a label (or status) with each vertex. It is concurrency-safe, utilizing a mutex lock for synchronized access.

func NewLabeledGraph

func NewLabeledGraph[V comparable](vertices []V) *LabeledGraph[V]

NewLabeledGraph initializes a LabeledGraph with specified vertices and set the status of each vertex to unvisited.

func (*LabeledGraph[V]) DownwardTraversal

func (lg *LabeledGraph[V]) DownwardTraversal(ctx context.Context, processVertexFunc func(context.Context, V) error) error

DownwardTraversal performs a traversal from root nodes (with no parents) to leaf nodes (with parents). It applies processVertexFunc to each vertex, skipping those with specified statuses. It conducts concurrent processing of vertices and returns an error for any encountered issues.

func (*LabeledGraph[V]) UpwardTraversal

func (lg *LabeledGraph[V]) UpwardTraversal(ctx context.Context, processVertexFunc func(context.Context, V) error) error

UpwardTraversal performs a traversal from leaf nodes (with no children) to root nodes (with children). It processes each vertex using processVertexFunc, and skips processing for vertices with specific statuses. The traversal is concurrent, handling vertices in parallel, and returns an error if any issue occurs.

type TopologicalSorter

type TopologicalSorter[V comparable] struct {
	// contains filtered or unexported fields
}

TopologicalSorter ranks vertices using Kahn's algorithm: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm However, if two vertices can be scheduled in parallel then the same rank is returned.

func TopologicalOrder

func TopologicalOrder[V comparable](digraph *Graph[V]) (*TopologicalSorter[V], error)

TopologicalOrder determines whether the directed graph is acyclic, and if so then finds a topological-order, or a linear order, of the vertices. Note that this function will modify the original graph.

If there is an edge from vertex V to U, then V must happen before U and results in rank of V < rank of U. When there are ties (two vertices can be scheduled in parallel), the vertices are given the same rank. If the digraph contains a cycle, then an error is returned.

An example graph and their ranks is shown below to illustrate: . ├── a rank: 0 │ ├── c rank: 1 │ │ └── f rank: 2 │ └── d rank: 1 └── b rank: 0

└── e      rank: 1

func (*TopologicalSorter[V]) Rank

func (alg *TopologicalSorter[V]) Rank(vtx V) (int, bool)

Rank returns the order of the vertex. The smallest order starts at 0. The second boolean return value is used to indicate whether the vertex exists in the graph.