package graph

import "golang.org/x/tools/internal/graph"

Package graph provides a common abstraction for directed graphs and standard graph algorithms.

In general, this package does not provide or assume any concrete graph representation. It's up to the caller of this package to implement the Graph interface, either directly or as an adapter around another type.

Index ¶

• func AllPaths[NodeID comparable](g Graph[NodeID], src, dst NodeID) map[NodeID]bool
• func Compact[NodeID comparable](g Graph[NodeID]) (CompactGraph, *Index[NodeID])
• func Postorder[NodeID comparable](g Graph[NodeID]) []NodeID
• func Reachable[NodeID comparable](g Graph[NodeID], roots ...NodeID) map[NodeID]bool
• func ReversePostorder[NodeID comparable](g Graph[NodeID]) []NodeID
• func SCCs[NodeID comparable](g Graph[NodeID]) [][]NodeID
• func ShortestPath[NodeID comparable](g Graph[NodeID], src, dst NodeID) []NodeID
• type CompactGraph
• type Graph
• func Transpose[NodeID comparable](g Graph[NodeID]) Graph[NodeID]
• type Index
• func NewIdentityIndex(n int) *Index[int]
• func NewIndex[Key comparable](values iter.Seq[Key]) *Index[Key]
• func (ix *Index[Key]) Index(key Key) int
• func (ix *Index[Key]) Value(index int) Key

Functions ¶

func AllPaths ¶

func AllPaths[NodeID comparable](g Graph[NodeID], src, dst NodeID) map[NodeID]bool

AllPaths returns the set of nodes that are part of at least one path from src to dst.

func Compact ¶

func Compact[NodeID comparable](g Graph[NodeID]) (CompactGraph, *Index[NodeID])

Compact takes a Graph with arbitrary NodeIDs and returns a compact graph.

If g implements CompactGraph, it assumes g is already compact and simply returns g and an identity mapping.

func Postorder ¶

func Postorder[NodeID comparable](g Graph[NodeID]) []NodeID

Postorder returns the sequence of nodes in the spanning DAG of g, in postorder.

For rootless subgraphs, it breaks cycles by starting at the lowest numbered node.

This algorithm runs in O(V + E) time and O(V + E) space.

func Reachable ¶

func Reachable[NodeID comparable](g Graph[NodeID], roots ...NodeID) map[NodeID]bool

Reachable returns the set of nodes reachable from the given roots.

func ReversePostorder ¶

func ReversePostorder[NodeID comparable](g Graph[NodeID]) []NodeID

ReversePostorder returns the nodes of the graph in reverse post-order.

If g is a directed acyclic graph (DAG), the result is a topological sort of g.

See Postorder for how this handles back-edges and cycles.

This algorithm runs in O(V + E) time and O(V + E) space.

func SCCs ¶

func SCCs[NodeID comparable](g Graph[NodeID]) [][]NodeID

SCCs computes the strongly connected components of the graph g.

func ShortestPath ¶

func ShortestPath[NodeID comparable](g Graph[NodeID], src, dst NodeID) []NodeID

ShortestPath returns a shortest path from src to dst in g. It returns the path as a slice of nodes starting with src and ending with dst. If no path is found, it returns nil.

Types ¶

type CompactGraph ¶

type CompactGraph interface {
	Graph[int]
	IsCompact()
}

A CompactGraph is a Graph with nodes that are compactly numbered from [0, NumNodes()).

Compactly numbered graphs are useful for many graph algorithms, and many graph representations are naturally compact.

To compact an arbitrary graph, use Compact.

type Graph ¶

type Graph[NodeID comparable] interface {
	// Nodes yields all nodes in this graph.
	Nodes() iter.Seq[NodeID]

	// NumNodes returns the total number of nodes in this graph.
	NumNodes() int

	// Out yields the out-edges of node. Out must be deterministic, though
	// otherwise there is no constraint on the order of the returned sequence.
	Out(node NodeID) iter.Seq[NodeID]
}

A Graph implements a directed graph where nodes in the graph are identified by the NodeID type.

If a concrete graph type stores additional information about nodes and/or edges, it will conventionally provide methods of the form:

Node(node NodeID) nodeInfo
Edge(from, to NodeID) edgeInfo

func Transpose ¶

func Transpose[NodeID comparable](g Graph[NodeID]) Graph[NodeID]

transpose returns a graph like g but with all edges reversed. Node IDs are identical to the underlying graph.

Transpose preserves compactness.

type Index ¶

type Index[Key comparable] struct {
	// contains filtered or unexported fields
}

An Index is an immutable, bijective map between [0, N) and an ordered list of keys.

func NewIdentityIndex ¶

func NewIdentityIndex(n int) *Index[int]

NewIdentityIndex returns an index that maps [0, n) to [0, n).

func NewIndex ¶

func NewIndex[Key comparable](values iter.Seq[Key]) *Index[Key]

NewIndex returns an index for the specified list of values.

func (*Index[Key]) Index ¶

func (ix *Index[Key]) Index(key Key) int

Index maps a key to an index.

func (*Index[Key]) Value ¶

func (ix *Index[Key]) Value(index int) Key

Value maps an index to a key.

Source Files ¶

allpaths.go compact.go graph.go index.go order.go reachable.go scc.go shortest.go transpose.go

Directories ¶