graph

package
v0.13.1 Latest Latest
Warning

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

 Go to latest Published: Nov 10, 2025 License: ISC Imports: 6 Imported by: 0

README

Graph

Test Cases

The example graphs used in test files are shown below.

Undirected

undirected graph

Directed

directed graph

Weighted Undirected

weighted undirected graph

Weighted Directed

weighted directed graph

Flow Network

flow network graph

Documentation

Overview

Package graph implements graph data structures and algorithms.

There are four different type of graphs implementd:

  • Undirected Graph
  • Directed Graph
  • Weighted Undirected Graph
  • Weighted Directed Graph

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type ConnectedComponents 

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

ConnectedComponents is used for determining all the connected components in a an undirected graph. A connected component is a maximal set of connected vertices (every two vertices are connected with a path between them).

func (*ConnectedComponents) Components 

func (c *ConnectedComponents) Components() [][]int

Components returns the vertices partitioned in the connected components.

func (*ConnectedComponents) ID 

func (c *ConnectedComponents) ID(v int) int

ID returns the component id of a vertex.

func (*ConnectedComponents) IsConnected 

func (c *ConnectedComponents) IsConnected(v, w int) bool

IsConnected determines if two vertices v and w are connected.

type Directed 

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

Directed represents a directed graph data type.

func NewDirected 

func NewDirected(V int, edges ...[2]int) *Directed

NewDirected creates a new directed graph.

func (*Directed) AddEdge 

func (g *Directed) AddEdge(v, w int)

AddEdge adds a new edge to the graph.

func (*Directed) Adj 

func (g *Directed) Adj(v int) []int

Adj returns the vertices adjacent from vertex.

func (*Directed) DOT added in v0.10.0 

func (g *Directed) DOT() string

DOT generates a DOT representation of the graph.

func (*Directed) DirectedCycle 

func (g *Directed) DirectedCycle() *DirectedCycle

DirectedCycle determines if the graph has a cyclic path.

func (*Directed) E 

func (g *Directed) E() int

E returns the number of edges.

func (*Directed) InDegree 

func (g *Directed) InDegree(v int) int

InDegree returns the number of directed edges incident to a vertex.

func (*Directed) Orders 

func (g *Directed) Orders(strategy TraversalStrategy) *Orders

Orders determines ordering of vertices in the graph.

func (*Directed) OutDegree 

func (g *Directed) OutDegree(v int) int

OutDegree returns the number of directed edges incident from a vertex.

func (*Directed) Paths 

func (g *Directed) Paths(s int, strategy TraversalStrategy) *Paths

Paths finds all paths from a source vertex to every other vertex.

func (*Directed) Reverse 

func (g *Directed) Reverse() *Directed

Reverse returns the reverse of the directed graph.

func (*Directed) StronglyConnectedComponents 

func (g *Directed) StronglyConnectedComponents() *StronglyConnectedComponents

StronglyConnectedComponents determines all the strongly-connected components in the graph.

func (*Directed) Topological 

func (g *Directed) Topological() *Topological

Topological determines the topological sort of the graph. If the graph has a directed cycle (not DAG), it does not have a topological order.

func (*Directed) Traverse 

func (g *Directed) Traverse(s int, strategy TraversalStrategy, visitors *Visitors)

Traverse is used for visiting all vertices and edges in graph.

func (*Directed) V 

func (g *Directed) V() int

V returns the number of vertices.

type DirectedCycle 

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

DirectedCycle is used for determining if a directed graph has a cycle. A cycle is a path whose first and last vertices are the same.

func (*DirectedCycle) Cycle 

func (c *DirectedCycle) Cycle() ([]int, bool)

Cycle returns a cyclic path. If no cycle exists, the second return value will be false.

type DirectedEdge 

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

DirectedEdge represents a weighted directed edge data type.

func (DirectedEdge) From 

func (e DirectedEdge) From() int

From returns the vertex this edge points from.

func (DirectedEdge) To 

func (e DirectedEdge) To() int

To returns the vertex this edge points to.

func (DirectedEdge) Weight 

func (e DirectedEdge) Weight() float64

Weight returns the weight of this edge.

type FlowEdge 

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

FlowEdge represents a capacitated edge data type.

func (*FlowEdge) AddResidualFlowTo 

func (e *FlowEdge) AddResidualFlowTo(v int, delta float64) bool

AddResidualFlowTo changes the flow on the edge in the direction to the given vertex. If vertex is the tail vertex (backward edge), this decreases the flow on the edge by delta. If vertex is the head vertex (forward edge), this increases the flow on the edge by delta. If delta is valid, edge will be modified and true will be returned. If delta is not valid, edge will not be modified and false will be returned.

func (*FlowEdge) Capacity 

func (e *FlowEdge) Capacity() float64

Capacity returns the capacity of the edge.

func (*FlowEdge) Flow 

func (e *FlowEdge) Flow() float64

Flow returns the flow on the edge.

func (*FlowEdge) From 

func (e *FlowEdge) From() int

From returns the tail vertex of the edge.

func (*FlowEdge) Other 

func (e *FlowEdge) Other(v int) int

Other returns the other vertex of this edge.

func (*FlowEdge) ResidualCapacityTo 

func (e *FlowEdge) ResidualCapacityTo(v int) float64

ResidualCapacityTo returns the residual capacity of the edge in the direction to the given vertex.

func (*FlowEdge) To 

func (e *FlowEdge) To() int

To returns the head vertex of the edge.

type FlowNetwork 

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

FlowNetwork represents a capacitated network graph data type. Each directed edge has a real number capacity and flow.

func NewFlowNetwork 

func NewFlowNetwork(V int, edges ...FlowEdge) *FlowNetwork

NewFlowNetwork creates a new capacitated network graph.

func (*FlowNetwork) AddEdge 

func (g *FlowNetwork) AddEdge(e FlowEdge)

AddEdge adds a new edge to the network.

func (*FlowNetwork) Adj 

func (g *FlowNetwork) Adj(v int) []FlowEdge

Adj returns the edges both pointing to and from a vertex.

func (*FlowNetwork) DOT added in v0.10.0 

func (g *FlowNetwork) DOT() string

DOT generates a DOT representation of the graph.

func (*FlowNetwork) E 

func (g *FlowNetwork) E() int

E returns the number of edges.

func (*FlowNetwork) Edges 

func (g *FlowNetwork) Edges() []FlowEdge

Edges returns all directed edges in the graph.

func (*FlowNetwork) V 

func (g *FlowNetwork) V() int

V returns the number of vertices.

type MinimumSpanningTree 

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

MinimumSpanningTree is used for calculating the minimum spanning trees (forest) of a weighted undirected graph. Given an edge-weighted undirected graph G with positive edge weights, an MST of G is a sub-graph T that is: 

Tree: connected and acyclic
Spanning: includes all of the vertices
Minimum: sum of the edge wights are minimum

func (*MinimumSpanningTree) Edges 

func (mst *MinimumSpanningTree) Edges() []UndirectedEdge

Edges returns the edges in a minimum spanning tree (or forest).

func (*MinimumSpanningTree) Weight 

func (mst *MinimumSpanningTree) Weight() float64

Weight returns the sum of the edge weights in a minimum spanning tree (or forest).

type OptimizationStrategy 

type OptimizationStrategy int

OptimizationStrategy is the strategy for optimizing weighted graphs. 

const (
	// None ignores edge weights.
	None OptimizationStrategy = iota
	// Minimize picks the edges with minimum weight.
	Minimize
	// Maximize picks the edges with maximum weight.
	Maximize
)

type Orders 

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

Orders is used for determining ordering of vertices in a graph.

func (*Orders) PostOrder 

func (o *Orders) PostOrder() []int

PostOrder returns the post ordering of vertices.

func (*Orders) PostRank 

func (o *Orders) PostRank(v int) int

PostRank returns the rank of a vertex in post ordering.

func (*Orders) PreOrder 

func (o *Orders) PreOrder() []int

PreOrder returns the pre ordering of vertices.

func (*Orders) PreRank 

func (o *Orders) PreRank(v int) int

PreRank returns the rank of a vertex in pre ordering.

func (*Orders) ReversePostOrder 

func (o *Orders) ReversePostOrder() []int

ReversePostOrder returns the reverse post ordering of vertices.

type Paths 

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

Paths is used for finding all paths from a source vertex to every other vertex in a graph. A path is a sequence of vertices connected by edges.

func (*Paths) To 

func (p *Paths) To(v int) ([]int, bool)

To returns a path between the source vertex (s) and vertex (v). If no such path exists, the second return value will be false.

type ShortestPathTree 

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

ShortestPathTree is used for calculating the shortest path tree of a weighted directed graph. A shortest path from vertex s to vertex t in a weighted directed graph is a directed path from s to t such that no other path has a lower weight.

func (*ShortestPathTree) PathTo 

func (spt *ShortestPathTree) PathTo(v int) ([]DirectedEdge, float64, bool)

PathTo returns shortest path from the source vertex (s) to vertex (v). The second return value is distance from the source vertex (s) to vertex (v). If no such path exists, the last return value will be false.

type StronglyConnectedComponents 

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

StronglyConnectedComponents is used for determining all the strongly connected components in a directed graph. A strongly connected component is a maximal set of strongly connected vertices (every two vertices are strongly connected with paths in both directions between them).

func (*StronglyConnectedComponents) Components 

func (c *StronglyConnectedComponents) Components() [][]int

Components returns the vertices partitioned in the connected components.

func (*StronglyConnectedComponents) ID 

func (c *StronglyConnectedComponents) ID(v int) int

ID returns the component id of a vertex.

func (*StronglyConnectedComponents) IsStronglyConnected 

func (c *StronglyConnectedComponents) IsStronglyConnected(v, w int) bool

IsStronglyConnected determines if two vertices v and w are strongly connected.

type Topological 

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

Topological is used for determining the topological order of a directed acyclic graph (DAG). A directed graph has a topological order if and only if it is a DAG (no directed cycle exists).

func (*Topological) Order 

func (t *Topological) Order() ([]int, bool)

Order returns a topological order of the directed graph. If the directed graph does not have a topologial order (has a cycle), the second return value will be false.

func (*Topological) Rank 

func (t *Topological) Rank(v int) (int, bool)

Rank returns the rank of a vertex in the topological order. If the directed graph does not have a topologial order (has a cycle), the second return value will be false.

type TraversalStrategy 

type TraversalStrategy int

TraversalStrategy is the strategy for traversing vertices in a graph. 

const (
	// DFS is recursive depth-first search traversal.
	DFS TraversalStrategy = iota
	// DFSi is iterative depth-first search traversal.
	DFSi
	// BFS is breadth-first search traversal.
	BFS
)

type Undirected 

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

Undirected represents an undirected graph data type.

func NewUndirected 

func NewUndirected(V int, edges ...[2]int) *Undirected

NewUndirected creates a new undirected graph.

func (*Undirected) AddEdge 

func (g *Undirected) AddEdge(v, w int)

AddEdge adds a new edge to the graph.

func (*Undirected) Adj 

func (g *Undirected) Adj(v int) []int

Adj returns the vertices adjacent from vertex.

func (*Undirected) ConnectedComponents 

func (g *Undirected) ConnectedComponents() *ConnectedComponents

ConnectedComponents determines all the connected components in the graph.

func (*Undirected) DOT added in v0.10.0 

func (g *Undirected) DOT() string

DOT generates a DOT representation of the graph.

func (*Undirected) Degree 

func (g *Undirected) Degree(v int) int

Degree returns the degree of a vertex.

func (*Undirected) E 

func (g *Undirected) E() int

E returns the number of edges.

func (*Undirected) Orders 

func (g *Undirected) Orders(strategy TraversalStrategy) *Orders

Orders determines ordering of vertices in the graph.

func (*Undirected) Paths 

func (g *Undirected) Paths(s int, strategy TraversalStrategy) *Paths

Paths finds all paths from a source vertex to every other vertex.

func (*Undirected) Traverse 

func (g *Undirected) Traverse(s int, strategy TraversalStrategy, visitors *Visitors)

Traverse is used for visiting all vertices and edges in graph.

func (*Undirected) V 

func (g *Undirected) V() int

V returns the number of vertices.

type UndirectedEdge 

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

UndirectedEdge represents a weighted undirected edge data type.

func (UndirectedEdge) Either 

func (e UndirectedEdge) Either() int

Either returns either of this edge's vertices.

func (UndirectedEdge) Other 

func (e UndirectedEdge) Other(v int) int

Other returns the other vertex of this edge.

func (UndirectedEdge) Weight 

func (e UndirectedEdge) Weight() float64

Weight returns the weight of this edge.

type Visitors 

type Visitors struct {
	VertexPreOrder  func(int) bool
	VertexPostOrder func(int) bool
	EdgePreOrder    func(int, int, float64) bool
}

Visitors provides a method for visiting vertices and edges when traversing a graph. VertexPreOrder is called when visiting a vertex in a graph. VertexPostOrder is called when visiting a vertex in a graph. EdgePreOrder is called when visiting an edge in a graph. The graph traversal will immediately stop if the return value from any of these functions is false.

type WeightedDirected 

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

WeightedDirected represents a weighted directed graph data type.

func NewWeightedDirected 

func NewWeightedDirected(V int, edges ...DirectedEdge) *WeightedDirected

NewWeightedDirected creates a new weighted directed graph.

func (*WeightedDirected) AddEdge 

func (g *WeightedDirected) AddEdge(e DirectedEdge)

AddEdge adds a new edge to the graph.

func (*WeightedDirected) Adj 

func (g *WeightedDirected) Adj(v int) []DirectedEdge

Adj returns the vertices adjacent from vertex.

func (*WeightedDirected) DOT added in v0.10.0 

func (g *WeightedDirected) DOT() string

DOT generates a DOT representation of the graph.

func (*WeightedDirected) E 

func (g *WeightedDirected) E() int

E returns the number of edges.

func (*WeightedDirected) Edges 

func (g *WeightedDirected) Edges() []DirectedEdge

Edges returns all directed edges in the graph.

func (*WeightedDirected) InDegree 

func (g *WeightedDirected) InDegree(v int) int

InDegree returns the number of directed edges incident to a vertex.

func (*WeightedDirected) Orders 

func (g *WeightedDirected) Orders(strategy TraversalStrategy) *Orders

Orders determines ordering of vertices in the graph.

func (*WeightedDirected) OutDegree 

func (g *WeightedDirected) OutDegree(v int) int

OutDegree returns the number of directed edges incident from a vertex.

func (*WeightedDirected) Paths 

func (g *WeightedDirected) Paths(s int, strategy TraversalStrategy) *Paths

Paths finds all paths from a source vertex to every other vertex.

func (*WeightedDirected) Reverse 

func (g *WeightedDirected) Reverse() *WeightedDirected

Reverse returns the reverse of the directed graph.

func (*WeightedDirected) ShortestPathTree 

func (g *WeightedDirected) ShortestPathTree(s int) *ShortestPathTree

ShortestPathTree calculates the shortest path tree of the graph.

func (*WeightedDirected) StronglyConnectedComponents 

func (g *WeightedDirected) StronglyConnectedComponents() *StronglyConnectedComponents

StronglyConnectedComponents determines all the connected components in the graph.

func (*WeightedDirected) Traverse 

func (g *WeightedDirected) Traverse(s int, strategy TraversalStrategy, visitors *Visitors)

Traverse is used for visiting all vertices and edges in graph.

func (*WeightedDirected) V 

func (g *WeightedDirected) V() int

V returns the number of vertices.

type WeightedUndirected 

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

WeightedUndirected represents a weighted undirected graph data type.

func NewWeightedUndirected 

func NewWeightedUndirected(V int, edges ...UndirectedEdge) *WeightedUndirected

NewWeightedUndirected creates a new weighted undirected graph.

func (*WeightedUndirected) AddEdge 

func (g *WeightedUndirected) AddEdge(e UndirectedEdge)

AddEdge adds a new edge to the graph.

func (*WeightedUndirected) Adj 

func (g *WeightedUndirected) Adj(v int) []UndirectedEdge

Adj returns the vertices adjacent from vertex.

func (*WeightedUndirected) ConnectedComponents 

func (g *WeightedUndirected) ConnectedComponents() *ConnectedComponents

ConnectedComponents determines all the connected components in the graph.

func (*WeightedUndirected) DOT added in v0.10.0 

func (g *WeightedUndirected) DOT() string

DOT generates a DOT representation of the graph.

func (*WeightedUndirected) Degree 

func (g *WeightedUndirected) Degree(v int) int

Degree returns the degree of a vertex.

func (*WeightedUndirected) E 

func (g *WeightedUndirected) E() int

E returns the number of edges.

func (*WeightedUndirected) Edges 

func (g *WeightedUndirected) Edges() []UndirectedEdge

Edges returns all edges in the graph.

func (*WeightedUndirected) MinimumSpanningTree 

func (g *WeightedUndirected) MinimumSpanningTree() *MinimumSpanningTree

MinimumSpanningTree calculates the minimum spanning tree (or forest) of the graph.

func (*WeightedUndirected) Orders 

func (g *WeightedUndirected) Orders(strategy TraversalStrategy) *Orders

Orders determines ordering of vertices in the graph.

func (*WeightedUndirected) Paths 

func (g *WeightedUndirected) Paths(s int, strategy TraversalStrategy) *Paths

Paths finds all paths from a source vertex to every other vertex.

func (*WeightedUndirected) Traverse 

func (g *WeightedUndirected) Traverse(s int, strategy TraversalStrategy, visitors *Visitors)

Traverse is used for visiting all vertices and edges in graph.

func (*WeightedUndirected) V 

func (g *WeightedUndirected) V() int

V returns the number of vertices.

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.