Documentation
¶
Overview ¶
Package graph provides functionality for directed graphs.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 (*Graph[V]) IsAcyclic ¶
IsAcyclic checks if the graph is acyclic. If not, return the first detected cycle.
func (*Graph[V]) Neighbors ¶ added in v1.18.0
func (g *Graph[V]) Neighbors(vtx V) []V
Neighbors returns the list of connected vertices from vtx.
type LabeledGraph ¶ added in v1.32.1
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 ¶ added in v1.32.1
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 ¶ added in v1.32.1
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 ¶ added in v1.32.1
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 ¶ added in v1.18.0
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 ¶ added in v1.18.0
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 ¶ added in v1.18.0
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.
Source Files