Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ComputeSCC ¶
func ComputeSCC[T comparable](graph Graph[T]) [][]T
ComputeSCC computes strongly connected components of a graph and returns them.
Types ¶
type DFSWalk ¶
type DFSWalk[T comparable] struct { // contains filtered or unexported fields }
DFSWalk persists the state of the dfs state so that we can use it computing components
func (*DFSWalk[T]) Explore ¶
func (d *DFSWalk[T]) Explore(node T) []T
Explore walks the dfs tree root at node and returns all the nodes reachable from node including itself
func (*DFSWalk[T]) ExploreGraph ¶
func (d *DFSWalk[T]) ExploreGraph(node T) []NodeStatus[T]
ExploreGraph traverses the entire graph starting at node. Returned NodeStatus contains newly finished nodes at the end of the slice, so traversing the slice in reverse order gives the nodes in the decreasing order of finish time
type Edge ¶
type Edge[T comparable] struct { Src, Dst T }
type Graph ¶
type Graph[T comparable] struct { // contains filtered or unexported fields }
Graph We don't really need a generic type but an int would suffice as node id and let caller keep the mapping. Created a generic parameter so that I provide a string for demonstration.
func CreateGraph ¶
func CreateGraph[T comparable](edges []Edge[T], additionalNodes ...T) Graph[T]
CreateGraph addtionalNodes are for nodes which are isolated (no incoming and outgoing rawEdges)
func (*Graph[T]) Neighbours ¶
func (g *Graph[T]) Neighbours(node T) []T
type NodeStatus ¶
type NodeStatus[T comparable] struct { // contains filtered or unexported fields }
Source Files