algo

package
v0.4.9 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 18, 2026 License: MIT Imports: 9 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func StronglyConnectedComponents 

func StronglyConnectedComponents(ctx context.Context, digraph container.DirectedGraph) ([]cardinality.Duplex[uint64], map[uint64]uint64)

Types

type ComponentGraph added in v0.4.0 

type ComponentGraph struct {
	// contains filtered or unexported fields
}

func NewComponentGraph added in v0.4.0 

func NewComponentGraph(ctx context.Context, originGraph container.DirectedGraph) ComponentGraph

func (ComponentGraph) CollectComponentMembers added in v0.4.0 

func (s ComponentGraph) CollectComponentMembers(componentID uint64, members cardinality.Duplex[uint64])

func (ComponentGraph) ComponentHistogram added in v0.4.0 

func (s ComponentGraph) ComponentHistogram(originNodes []uint64) map[uint64]uint64

func (ComponentGraph) ComponentMembers added in v0.4.8 

func (s ComponentGraph) ComponentMembers(componentID uint64) cardinality.Duplex[uint64]

func (ComponentGraph) ComponentReachable added in v0.4.0 

func (s ComponentGraph) ComponentReachable(startComponent, endComponent uint64, direction graph.Direction) bool

func (ComponentGraph) ComponentSearch added in v0.4.0 

func (s ComponentGraph) ComponentSearch(startComponent, endComponent uint64, direction graph.Direction) bool

func (ComponentGraph) ContainingComponent added in v0.4.0 

func (s ComponentGraph) ContainingComponent(memberID uint64) (uint64, bool)

func (ComponentGraph) Digraph added in v0.4.0 

func (s ComponentGraph) Digraph() container.DirectedGraph

func (ComponentGraph) HasMember added in v0.4.0 

func (s ComponentGraph) HasMember(memberID uint64) bool

func (ComponentGraph) KnownMembers added in v0.4.0 

func (s ComponentGraph) KnownMembers() cardinality.Duplex[uint64]

func (ComponentGraph) OriginReachable added in v0.4.0 

func (s ComponentGraph) OriginReachable(startID, endID uint64) bool

type ReachabilityCache added in v0.4.0 

type ReachabilityCache struct {
	// contains filtered or unexported fields
}

ReachabilityCache holds a component graph derived from a directed graph and two caches (inbound and outbound) that store the reachability set for each component. The caches are sized by the caller and automatically evict the least‑recently‑used entries when full.

func FetchFilteredReachabilityCache added in v0.4.0 

func FetchFilteredReachabilityCache(ctx context.Context, db graph.Database, traversalKinds ...graph.Kind) (*ReachabilityCache, error)

FetchFilteredReachabilityCache builds a ReachabilityCache for a graph that contains only edges of the supplied kinds. It is a convenience wrapper around FetchReachabilityCache that constructs the appropriate criteria.

func FetchReachabilityCache added in v0.4.0 

func FetchReachabilityCache(ctx context.Context, db graph.Database, criteria graph.Criteria) (*ReachabilityCache, error)

FetchReachabilityCache builds a ReachabilityCache for the entire directed graph represented by the supplied database and criteria. The cache size is set to roughly 15% of the number of nodes in the graph (rounded down).

func NewReachabilityCache added in v0.4.0 

func NewReachabilityCache(ctx context.Context, digraph container.DirectedGraph, maxCacheSize int) *ReachabilityCache

NewReachabilityCache creates a ReachabilityCache for the supplied directed graph. The component graph is built first, then two bounded caches are allocated with the given maxCacheSize (the maximum number of component reachability entries to retain).

func (*ReachabilityCache) CanReach added in v0.4.0 

func (s *ReachabilityCache) CanReach(startID, endID uint64, direction graph.Direction) bool

CanReach determines whether a directed path exists from startID to endID in the original graph, following the supplied direction (inbound or outbound). The method works on the component graph: if both IDs belong to known components, it asks the component graph whether the start component can reach the end component.

func (*ReachabilityCache) OrReach added in v0.4.2 

func (s *ReachabilityCache) OrReach(node uint64, direction graph.Direction, duplex cardinality.Duplex[uint64])

OrReach OR‑s the reachability set of the given node (in the supplied direction) into the provided duplex bitmap. The node itself is removed from the result so that only other reachable members remain.

func (*ReachabilityCache) ReachOfComponentContainingMember added in v0.4.2 

func (s *ReachabilityCache) ReachOfComponentContainingMember(member uint64, direction graph.Direction) cardinality.Duplex[uint64]

ReachOfComponentContainingMember returns the reach of the component containing the given member and direction as a single bitwise ORed bitmap. For large scale digraphs use of this function may come at a high computational cost. If this function is utilized in a tight loop, consider utilizing ReachSliceOfComponentContainingMember with commutative bitmap operations.

func (*ReachabilityCache) ReachSliceOfComponentContainingMember added in v0.4.8 

func (s *ReachabilityCache) ReachSliceOfComponentContainingMember(member uint64, direction graph.Direction) []cardinality.Duplex[uint64]

ReachSliceOfComponentContainingMember returns the reach of the component containing the given member and direction as a slice of membership bitmaps. These bitmaps are not combined for the purposes of maintaining performance when dealing with large scale digraphs. The computation cost of producing a single bitmap far exceeds the cost of iteratively scanning the returned slice of bitmaps. Additionally, the returned slice may be used by commutative bitmap operations.

func (*ReachabilityCache) Stats added in v0.4.0 

func (s *ReachabilityCache) Stats() cache.Stats

Stats returns the combined cache statistics for both inbound and outbound component‑reach caches.

func (*ReachabilityCache) XorReach added in v0.4.2 

func (s *ReachabilityCache) XorReach(node uint64, direction graph.Direction, duplex cardinality.Duplex[uint64])

XorReach XOR‑s the reachability set of the given node (in the supplied direction) into the provided duplex bitmap. The node itself is removed from the result before the XOR operation.

type ReachabilityCacheStats added in v0.4.0 

type ReachabilityCacheStats struct {
	Cached uint64
	Hits   uint64
}

ReachabilityCacheStats aggregates cache statistics for both inbound and outbound component‑reach caches.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.