Documentation
¶
Overview ¶
Package graph provides functionality for directed graphs.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func WithStatus ¶ added in v1.32.1
func WithStatus[V comparable](status string) func(g *LabeledGraph[V])
WithStatus sets the status of each vertex in the Graph.
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, opts ...LabeledGraphOption[V]) *LabeledGraph[V]
NewLabeledGraph initializes a LabeledGraph with specified vertices and optional configurations. It creates a base Graph with the vertices and applies any LabeledGraphOption to configure additional properties.
func (*LabeledGraph[V]) DownwardTraversal ¶ added in v1.32.1
func (lg *LabeledGraph[V]) DownwardTraversal(ctx context.Context, processVertexFunc func(context.Context, V) error, adjacentVertexSkipStatus, requiredVertexStatus string) error
DownwardTraversal performs a downward traversal on the graph starting from root nodes (nodes with no parents) and moving towards leaf nodes (nodes with parents). It applies the specified process function to each vertex in the graph, skipping vertices with the "adjacentVertexSkipStatus" status, and continuing traversal until reaching vertices with the "requiredVertexStatus" status. The traversal is concurrent and may process vertices in parallel. Returns an error if the traversal encounters any issues.
func (*LabeledGraph[V]) UpwardTraversal ¶ added in v1.32.1
func (lg *LabeledGraph[V]) UpwardTraversal(ctx context.Context, processVertexFunc func(context.Context, V) error, nextVertexSkipStatus, requiredVertexStatus string) error
UpwardTraversal performs an upward traversal on the graph starting from leaves (nodes with no children) and moving towards root nodes (nodes with children). It applies the specified process function to each vertex in the graph, skipping vertices with the "adjacentVertexSkipStatus" status, and continuing traversal until reaching vertices with the "requiredVertexStatus" status. The traversal is concurrent and may process vertices in parallel. Returns an error if the traversal encounters any issues, or nil if successful.
type LabeledGraphOption ¶ added in v1.32.1
type LabeledGraphOption[V comparable] func(g *LabeledGraph[V])
LabeledGraphOption allows you to initialize Graph with additional properties.
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