Documentation
¶
Index ¶
- type Graph
- func (G Graph[T]) BFS(start T, f traversalFunc[T]) bool
- func (G Graph[T]) BFSV(f traversalFunc[T], starts ...T) bool
- func (G Graph[T]) DominatorTree(root T) func(...T) T
- func (G Graph[T]) Edges(node T) []T
- func (G Graph[T]) FullTarjanOLCA(root T) LCA[T]
- func (G Graph[T]) SCC(startNodes []T) SCCDecomposition[T]
- func (G Graph[T]) TarjanOLCA(root T, P map[interface{}]set) LCA[T]
- func (G Graph[T]) ToDotGraph(nodes []T, cfg *VisualizationConfig[T]) *dot.DotGraph
- type LCA
- type SCC
- type SCCDecomposition
- type VisualizationConfig
- type WrappedGraph
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Graph ¶
type Graph[T any] struct { // contains filtered or unexported fields }
func FromCallGraph ¶
Creates a Graph from a callgraph with *ssa.Functions as nodes. Duplicate edges in the callgraph are pruned. If prune is true edges from call sites with at least 10 targets will not be included in the resulting graph.
func OfHashable ¶
func OfHashable[K comparable](edgesOf edgesOf[K]) Graph[K]
func (Graph[T]) BFS ¶
Performs a breadth-first search from the provided start node, calling the provided function (f) for every reachable node, stopping early if f returns true. Returns whether the search stopped early (as a result of f returning true).
func (Graph[T]) BFSV ¶
Performs a breadth-first search from the provided start nodes, calling the provided function (f) for every reachable node, stopping early if f returns true. Returns whether the search stopped early (as a result of f returning true).
func (Graph[T]) DominatorTree ¶
func (G Graph[T]) DominatorTree(root T) func(...T) T
func (Graph[T]) FullTarjanOLCA ¶
func (Graph[T]) SCC ¶
func (G Graph[T]) SCC(startNodes []T) SCCDecomposition[T]
Compute the strongly connected components of the subgraph reachable from the provided start nodes.
func (Graph[T]) TarjanOLCA ¶
func (Graph[T]) ToDotGraph ¶
func (G Graph[T]) ToDotGraph(nodes []T, cfg *VisualizationConfig[T]) *dot.DotGraph
TODO: Option to compute transitive closure from `nodes` TODO: Edge customization (requires modification of Graph type)
type LCA ¶
type LCA[T any] struct { Pairs map[interface{}]set G Graph[T] // contains filtered or unexported fields }
func (LCA[T]) MakeSet ¶
func (lca LCA[T]) MakeSet(node interface{})
Instantiate node in representative map of Union-Find data structure
func (LCA[T]) TarjanOLCA ¶
func (lca LCA[T]) TarjanOLCA(u T)
type SCCDecomposition ¶
type SCCDecomposition[T any] struct { Components [][]T Original Graph[T] // contains filtered or unexported fields }
A DAG decomposition of a graph based on strongly connected components. The nodes in component i are guaranteed to only have edges to nodes in components with index j <= i.
func (SCCDecomposition[T]) ComponentOf ¶
func (scc SCCDecomposition[T]) ComponentOf(node T) SCC
Returns the index of the component the node is a part of.
func (SCCDecomposition[T]) Convolution ¶
func (scc SCCDecomposition[T]) Convolution() WrappedGraph[SCC, T]
Construct SCC convolution as a wrapped Graph.
func (SCCDecomposition[T]) ToGraph ¶
func (scc SCCDecomposition[T]) ToGraph() Graph[SCC]
Returns a graph based on the SCC decomposition. Nodes are component indices (int).
type VisualizationConfig ¶
type VisualizationConfig[T any] struct { // Provides the ID and attributes for dot nodes. // If not provided, the ID is the stringified node. NodeAttrs func(node T) (string, dot.DotAttrs) // If provided, will create clusters for nodes with the same key. // The returned key must be safe to use in a Go map. ClusterKey func(node T) any // Provides the ID and attributes for dot clusters. ClusterAttrs func(key any) (string, dot.DotAttrs) }
type WrappedGraph ¶
A wrapped graph uses a second strategy to access nodes. The overriding edgesOf reflects this strategy, with the overriding cachedEdges caching these results, while the underlying graph still provides access to regular edgesOf and cachedEdges. The embedded graph can be reached via .Underlying()
Example: SCC convolutions can collect and cache edges using nodes in the original graph, by using the edgesOf created during SCC decomposition in the wrapped graph. The underlying graph access and caches edges based on SCC indexes.
func (WrappedGraph[W, T]) Edges ¶
func (G WrappedGraph[W, T]) Edges(node T) []W
func (WrappedGraph[W, T]) Underlying ¶
func (G WrappedGraph[W, T]) Underlying() Graph[W]
Source Files