scc

package
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Sep 9, 2025 License: Apache-2.0 Imports: 5 Imported by: 0

Documentation

Overview

Package scc contains an implementation of Tarjan's algorithm, which converts a directed graph into a DAG of strongly-connected components (subgraphs such that every node is reachable from every other node).

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Component 

type Component[Node comparable] struct {
	// contains filtered or unexported fields
}

Component is a strongly connected component.

func (*Component[Node]) Deps 

func (c *Component[Node]) Deps() iter.Seq[*Component[Node]]

Deps ranges over the direct dependencies of this component.

func (*Component[Node]) Index 

func (c *Component[Node]) Index() int

Index returns this component's position in topological order.

func (*Component[Node]) Members 

func (c *Component[Node]) Members() []Node

Members returns the members of a component.

type DAG 

type DAG[Node comparable] struct {
	// contains filtered or unexported fields
}

DAG represents the strongly connected component DAG of some arbitrary directed graph.

func Sort 

func Sort[Node comparable](root Node, graph Graph[Node]) *DAG[Node]

Sort sorts the strongly connected components of a directed graph represented by deps, using Tarjan's algorithm.

func (*DAG[Node]) ForNode 

func (d *DAG[Node]) ForNode(node Node) *Component[Node]

ForNode returns the component for some node, or nil if that node is not in the graph.

func (*DAG[Node]) Topological 

func (d *DAG[Node]) Topological() iter.Seq[*Component[Node]]

To range over the components some node depends on.

type Graph 

type Graph[Node any] func(Node) iter.Seq[Node]

Graph is a "local" representation of a directed graph, which exposes the outgoing edges (i.e., dependencies) from some node.

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.