README
¶
dag
Generic graph algorithms that work with any data structure.
Installation
import "github.com/linyows/probe/dag"
Algorithms
Cycle Detection
Detects cycles in a graph using Depth-First Search (DFS) with a recursion stack.
| Function | Description | Complexity |
|---|---|---|
DetectCycleFn |
Detect cycle and return the cycle path | O(V + E) |
Usage
Pass a list of IDs and a dependency getter function. Works with any data structure.
// Dependencies: A → B → C → A
getDeps := func(id string) []string {
switch id {
case "A":
return []string{"B"}
case "B":
return []string{"C"}
case "C":
return []string{"A"}
default:
return nil
}
}
allIDs := []string{"A", "B", "C"}
if cycle := dag.DetectCycleFn(allIDs, getDeps); cycle != nil {
fmt.Println("Cycle found:", cycle) // [A B C]
}
Documentation
¶
Overview ¶
Package dag provides generic graph algorithms that work with any data structure.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DetectCycleFn ¶
func DetectCycleFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID
DetectCycleFn detects a cycle in a graph using a higher-order function. Returns the cycle path if found, nil otherwise.
Parameters:
- allIDs: All node identifiers in the graph
- getDeps: Function that returns dependencies (children) for a given node
Example:
getDeps := func(id string) []string {
switch id {
case "A": return []string{"B", "C"}
case "B": return []string{"C"}
default: return nil
}
}
cycle := DetectCycleFn([]string{"A", "B", "C"}, getDeps)
Types ¶
This section is empty.
Source Files
Click to show internal directories.
Click to hide internal directories.