graph

Documentation

Index

• type Graph
  • func FromBasicBlocks(fun *ssa.Function) Graph[int]
  • func FromCallGraph(cg *callgraph.Graph, prune bool) Graph[*ssa.Function]
  • func Of[T any](mapFactory mapFactory[T], edgesOf edgesOf[T]) Graph[T]
  • func OfHashable[K comparable](edgesOf edgesOf[K]) Graph[K]
  • 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
  • func (lca LCA[T]) Find(node interface{}) *lcaRep
  • func (lca LCA[T]) MakeSet(node interface{})
  • func (lca LCA[T]) TarjanOLCA(u T)
  • func (lca LCA[T]) Union(x, y interface{})
• type SCC
• type SCCDecomposition
  • func (scc SCCDecomposition[T]) ComponentOf(node T) SCC
  • func (scc SCCDecomposition[T]) Convolution() WrappedGraph[SCC, T]
  • func (scc SCCDecomposition[T]) ToGraph() Graph[SCC]
• type VisualizationConfig
• type WrappedGraph
  • func (G WrappedGraph[W, T]) Edges(node T) []W
  • func (G WrappedGraph[W, T]) Underlying() Graph[W]

Types

type Graph

type Graph[T any] struct {
	// contains filtered or unexported fields
}

func FromBasicBlocks

func FromBasicBlocks(fun *ssa.Function) Graph[int]

Nodes are BB indices.

func FromCallGraph

func FromCallGraph(cg *callgraph.Graph, prune bool) Graph[*ssa.Function]

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 Of

func Of[T any](mapFactory mapFactory[T], edgesOf edgesOf[T]) Graph[T]

func OfHashable

func OfHashable[K comparable](edgesOf edgesOf[K]) Graph[K]

func (Graph[T]) BFS

func (G Graph[T]) BFS(start T, f traversalFunc[T]) bool

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

func (G Graph[T]) BFSV(f traversalFunc[T], starts ...T) bool

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]) Edges

func (G Graph[T]) Edges(node T) []T

func (Graph[T]) FullTarjanOLCA

func (G Graph[T]) FullTarjanOLCA(root T) LCA[T]

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 (G Graph[T]) TarjanOLCA(root T, P map[interface{}]set) LCA[T]

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]) Find

func (lca LCA[T]) Find(node interface{}) *lcaRep

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)

func (LCA[T]) Union

func (lca LCA[T]) Union(x, y interface{})

type SCC

type SCC = int

An alias for component type (in case representation changes)

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

type WrappedGraph[W, T any] struct {
	Graph[W]
	// contains filtered or unexported fields
}

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]