graph

package
v0.0.0-...-d78bf3b Latest Latest
Warning

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

 Go to latest Published: Dec 23, 2025 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Overview

Package graph contains utilities for (sparse|dense) (un|)directed (un|)weighted graphs.

One note about the convention: whenever there's a directed edge (u, v), its tail will be called u and its head will be called v.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func WriteDOT 

func WriteDOT[T comparable](g AnyG[T], w io.Writer, name string, directed bool, nodeAttr func(v int) map[string]string, edgeAttr func(u, v int) map[string]string) (err error)

WriteDOT writes the graph out in GraphViz format. The `nodeAttr` and `edgeAttr` callback functions are optional, and can be used to add extra attributes to the node. If the callback returns a "label" attribute, it takes precedence over the usual node name / edge weight.

Types

type Any 

type Any = AnyG[string]

Any is a compatibility alias for AnyG[string]

type AnyG 

type AnyG[T comparable] interface {
	Len() int
	V(T) (int, bool)
	Label(v int) T
	W(u, v int) int
	Succ(u int) iter.Seq[int]
	// contains filtered or unexported methods
}

AnyG represents the common subset of all graph types.

It's useful for writing generic functions on both sparse and dense graphs. Note that there's generally some performance impact, so it's best left for non-sensitive utility functions.

type Builder 

type Builder = BuilderG[string]

Builder is a compatibility alias for BuilderG[string].

func NewBuilder 

func NewBuilder() *Builder

NewBuilder returns a new, empty Builder.

type BuilderG 

type BuilderG[T comparable] struct {
	// contains filtered or unexported fields
}

BuilderG is used to incrementally grow a graph.

Note that there is no checking for duplicate edges by default. The caller should pick one of:

  • Ensure that the input only lists each edge once.
  • Accept that the resulting graph will in fact be a multigraph.
  • Use one of the dense graphs, which use an adjacency matrix (inherently robust for this).
  • TODO: add methods for deduplicating

func NewBuilderG 

func NewBuilderG[T comparable]() *BuilderG[T]

NewBuilder returns a new, empty Builder.

func (*BuilderG[T]) AddEdge 

func (b *BuilderG[T]) AddEdge(from, to int)

AddEdge records a new edge between two vertices in the graph.

func (*BuilderG[T]) AddEdgeL 

func (b *BuilderG[T]) AddEdgeL(from, to T)

AddEdgeL records a new edge between two vertices (denoted by labels, created if necessary).

func (*BuilderG[T]) AddEdgeW 

func (b *BuilderG[T]) AddEdgeW(from, to, w int)

AddEdgeW records a new weighted edge between two vertices in the graph.

func (*BuilderG[T]) AddEdgeWL 

func (b *BuilderG[T]) AddEdgeWL(from, to T, w int)

AddEdgeWL records a new weighted edge between two vertices (denoted by labels, created if necessary).

func (*BuilderG[T]) DenseDigraph 

func (b *BuilderG[T]) DenseDigraph() (g *DenseG[T])

DenseDigraph returns the contents of the builder as an unweighted dense digraph.

func (*BuilderG[T]) DenseDigraphW 

func (b *BuilderG[T]) DenseDigraphW() (g *DenseWG[T])

DenseDigraphW returns the contents of the builder as a weighted dense digraph.

If multiple edges have been recorded between two vertices, their values sum up.

func (*BuilderG[T]) DenseGraph 

func (b *BuilderG[T]) DenseGraph() (g *DenseG[T])

DenseGraph returns the contents of the builder as an unweighted dense undirected graph.

func (*BuilderG[T]) DenseGraphW 

func (b *BuilderG[T]) DenseGraphW() (g *DenseWG[T])

DenseGraphW returns the contents of the builder as a weighted dense undirected graph.

If multiple edges have been recorded between two vertices (in any order), their values sum up.

func (*BuilderG[T]) Len 

func (b *BuilderG[T]) Len() int

Len returns the number of vertices added to the builder so far.

func (*BuilderG[T]) SparseDigraph 

func (b *BuilderG[T]) SparseDigraph() (g *SparseG[T])

SparseDigraph returns the contents of the builder as an unweighted sparse digraph.

func (*BuilderG[T]) SparseDigraphW 

func (b *BuilderG[T]) SparseDigraphW() (g *SparseWG[T])

SparseDigraphW returns the contents of the builder as a weighted sparse digraph.

func (*BuilderG[T]) V 

func (b *BuilderG[T]) V(label T) int

V returns the vertex number corresponding to the given label, creating it if necessary.

type Dense 

type Dense = DenseG[string]

Dense is a compatibility alias for DenseG[string].

type DenseG 

type DenseG[T comparable] struct {
	// contains filtered or unexported fields
}

DenseG represents a dense graph using a boolean adjacency matrix.

func (*DenseG[T]) DelEdge 

func (g *DenseG[T]) DelEdge(u, v int)

DelEdge removes the edge (u, v) from the graph. If the edge did not exist, the call does nothing.

func (*DenseG[T]) E 

func (g *DenseG[T]) E(u, v int) bool

E returns true if the edge (u, v) exists in the graph.

func (DenseG) Label 

func (l DenseG) Label(v int) T

Label returns the label corresponding to a vertex index.

func (DenseG) Len 

func (l DenseG) Len() int

Len returns the number of vertices in the graph.

func (*DenseG[T]) NumPred 

func (g *DenseG[T]) NumPred(v int) (n int)

NumPred returns the total number of successors of u. This is an O(|V|) operation.

func (*DenseG[T]) NumSucc 

func (g *DenseG[T]) NumSucc(u int) (n int)

NumSucc returns the total number of successors of u. This is an O(|V|) operation.

func (*DenseG[T]) Pred 

func (g *DenseG[T]) Pred(v int) iter.Seq[int]

Pred returns an iterator for the predecessors of vertex v.

func (*DenseG[T]) Succ 

func (g *DenseG[T]) Succ(u int) iter.Seq[int]

Succ returns an iterator for the successors of vertex u.

func (*DenseG[T]) TopoSort 

func (g *DenseG[T]) TopoSort(keepEdges bool) []int

TopoSort returns a topological sort order for the graph.

func (DenseG) V 

func (l DenseG) V(name T) (idx int, ok bool)

V returns the vertex index of the vertex with the given name.

func (*DenseG[T]) W 

func (g *DenseG[T]) W(u, v int) int

W returns 1 if an edge exists between the two vertices, or 0 otherwise.

type DenseW 

type DenseW = DenseWG[string]

DenseW is a compatibility alias for DenseWG[string]

type DenseWG 

type DenseWG[T comparable] struct {
	// contains filtered or unexported fields
}

DenseWG represents a dense weighted graph using an integer adjacency matrix.

func (*DenseWG[T]) E 

func (g *DenseWG[T]) E(u, v int) bool

E returns true if the edge (u, v) exists and has a non-zero weight in the graph.

func (DenseWG) Label 

func (l DenseWG) Label(v int) T

Label returns the label corresponding to a vertex index.

func (DenseWG) Len 

func (l DenseWG) Len() int

Len returns the number of vertices in the graph.

func (*DenseWG[T]) Pred 

func (g *DenseWG[T]) Pred(v int) iter.Seq[int]

Pred returns an iterator for the predecessors of vertex v.

func (*DenseWG[T]) Succ 

func (g *DenseWG[T]) Succ(u int) iter.Seq[int]

Succ returns an iterator for the successors of vertex u.

func (*DenseWG[T]) SuccW 

func (g *DenseWG[T]) SuccW(u int) iter.Seq2[int, int]

SuccW returns an iterator for the successors of vertex u, together with their weights.

func (DenseWG) V 

func (l DenseWG) V(name T) (idx int, ok bool)

V returns the vertex index of the vertex with the given name.

func (*DenseWG[T]) W 

func (g *DenseWG[T]) W(u, v int) int

W returns the weight of an edge between two vertices.

type Sparse 

type Sparse = SparseG[string]

Sparse is a compatibility alias for SparseG[string]

type SparseG 

type SparseG[T comparable] struct {
	// contains filtered or unexported fields
}

SparseG represents a sparse graph with adjacency lists.

func (*SparseG[T]) E 

func (g *SparseG[T]) E(u, v int) bool

E returns true if the edge (u, v) exists in the graph.

func (SparseG) Label 

func (l SparseG) Label(v int) T

Label returns the label corresponding to a vertex index.

func (SparseG) Len 

func (l SparseG) Len() int

Len returns the number of vertices in the graph.

func (*SparseG[T]) Succ 

func (g *SparseG[T]) Succ(u int) iter.Seq[int]

Succ returns an iterator for the successors of vertex u.

func (SparseG) V 

func (l SparseG) V(name T) (idx int, ok bool)

V returns the vertex index of the vertex with the given name.

func (*SparseG[T]) W 

func (g *SparseG[T]) W(u, v int) int

W returns 1 if an edge exists between the two vertices, or 0 otherwise.

type SparseW 

type SparseW = SparseWG[string]

SparseW is a compatibility alias for SparseWG[string].

type SparseWG 

type SparseWG[T comparable] struct {
	SparseG[T]
	// contains filtered or unexported fields
}

SparseWG represents a sparse weighted graphs with adjacency and edge weight lists.

func (*SparseWG[T]) E 

func (g *SparseWG[T]) E(u, v int) bool

E returns true if the edge (u, v) exists and has a non-zero weight in the graph.

func (SparseWG) Label 

func (l SparseWG) Label(v int) T

Label returns the label corresponding to a vertex index.

func (SparseWG) Len 

func (l SparseWG) Len() int

Len returns the number of vertices in the graph.

func (*SparseWG[T]) NumSucc 

func (g *SparseWG[T]) NumSucc(u int) int

NumSucc returns the number of successors of u. This is an O(1) operation.

func (*SparseWG[T]) PredI 

func (g *SparseWG[T]) PredI(v, i int) int

PredI returns the i'th predecessor of u (ordered by vertex index). Note that this is an O(|V|+|E|) operation.

func (*SparseWG[T]) SuccI 

func (g *SparseWG[T]) SuccI(u, i int) int

SuccI returns the i'th successor of u. This is an O(1) operation.

func (*SparseWG[T]) SuccW 

func (g *SparseWG[T]) SuccW(u int) iter.Seq2[int, int]

SuccW returns an iterator for the successors of vertex u, together with their weights.

func (*SparseWG[T]) TopoSort 

func (g *SparseWG[T]) TopoSort(keepEdges bool) []int

TopoSort returns a topological sort order for the graph.

func (SparseWG) V 

func (l SparseWG) V(name T) (idx int, ok bool)

V returns the vertex index of the vertex with the given name.

func (*SparseWG[T]) W 

func (g *SparseWG[T]) W(u, v int) int

W returns the weight of an edge between two vertices. Note that this involves a linear scan for the edge in the edge list; if iterating, get the value from the iterator instead.

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.