README
¶
Grafo
Grafo contains generic implementations of basic graph (theory) algorithms.
See the API Reference.
Grafo is a fork from yourbasic/graph.
Documentation
¶
Overview ¶
Package grafo contains generic implementations of basic graph algorithms.
Most of the functions of this package operates on the Graph[T] interface, a small but powerfull interface that represents a directed weighted graph.
Index ¶
- func Acyclic[T any](g Graph[T]) bool
- func BFS[T any](g Graph[T], v int) iter.Seq[Edge[T]]
- func BellmanFord[T IntegerOrFloat](g Graph[T], v int) (parent []int, dist []T, ok bool)
- func Bipartition[T any](g Graph[T]) (part []int, ok bool)
- func DFS[T any](g Graph[T], v int) iter.Seq[Edge[T]]
- func DFSPostvisit[T any](g Graph[T], v int) iter.Seq[int]
- func DFSPrevisit[T any](g Graph[T], v int) iter.Seq[int]
- func InfFor[T IntegerOrFloat]() T
- func MST[T IntegerOrFloat](g Graph[T]) (parent []int)
- func ShortestPath[T IntegerOrFloat](g Graph[T], v, w int) (path []int, dist T)
- func ShortestPaths[T IntegerOrFloat](g Graph[T], v int) (parent []int, dist []T)
- func String[T IntegerOrFloat](g Graph[T]) string
- func StrongComponents[T any](g Graph[T]) [][]int
- func TopSort[T any](g Graph[T]) (order []int, ok bool)
- type Edge
- type Graph
- type Immutable
- type IntegerOrFloat
- type Mutable
- func (g *Mutable[T]) Add(v, w int, weight T)
- func (g *Mutable[T]) AddBoth(v, w int, weight T)
- func (g *Mutable[T]) Delete(v, w int)
- func (g *Mutable[T]) DeleteBoth(v, w int)
- func (g *Mutable[T]) EdgesFrom(v int) iter.Seq2[int, T]
- func (g *Mutable[T]) Order() int
- func (g *Mutable[T]) Weight(v, w int) T
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BFS ¶
BFS returns an iterator of edges that traverse the graph in Breadth First Search way, starting from vertex v.
Example ¶
This example is inspired on section 5.7 Graph Reductions: Flood Fill of the book https://jeffe.cs.illinois.edu/teaching/algorithms/.
package main
import (
"bytes"
"fmt"
"iter"
"github.com/rschio/grafo"
)
// This example is inspired on section 5.7 Graph Reductions: Flood Fill
// of the book https://jeffe.cs.illinois.edu/teaching/algorithms/.
func main() {
fmt.Println(image)
v := 78
// Find all the vertices of the connected region of v.
// This problem can be reduced to find all vertices reachable from v.
vertices := []int{v}
for e := range grafo.BFS(image, v) {
vertices = append(vertices, e.W)
}
// Change the connected region color to green.
for _, v := range vertices {
row, col := image.rowCol(v)
image[row][col] = '🟩'
}
fmt.Println(image)
}
var image graph = [][]rune{
[]rune("⬜⬛⬜⬜⬛⬜⬜⬜⬜⬜⬜⬜⬜"),
[]rune("⬛⬜⬛⬜⬛⬛⬜⬜⬜⬜⬜⬜⬜"),
[]rune("⬜⬛⬜⬛⬜⬛⬛⬜⬜⬜⬜⬜⬜"),
[]rune("⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬜⬜⬜"),
[]rune("⬛⬛⬜⬜⬜⬛⬛⬛⬜⬜⬜⬜⬜"),
[]rune("⬜⬛⬛⬜⬛⬜⬛⬜⬜⬜⬜⬜⬜"),
[]rune("⬜⬜⬛⬛⬛⬛⬜⬜⬛⬜⬜⬜⬜"),
[]rune("⬜⬜⬜⬜⬛⬜⬜⬜⬜⬜⬜⬜⬜"),
[]rune("⬜⬜⬜⬜⬜⬜⬛⬜⬜⬜⬜⬜⬜"),
[]rune("⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬛⬛"),
[]rune("⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬜⬛⬜"),
[]rune("⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬛⬜⬛"),
[]rune("⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬜⬛⬜"),
}
type graph [][]rune
func (g graph) Order() int { return len(g) * len(g[0]) }
// EdgesFrom return the edges from v.
// To express a connected region we define that v can possibly
// have 4 neighbors that are top, bottom, left and right.
// The edge only exists if the vertices are of the same color of v.
func (g graph) EdgesFrom(v int) iter.Seq2[int, struct{}] {
n := len(g[0])
neighbors := make([]int, 0, 4)
top := v - n
bottom := v + n
left := v - 1
right := v + 1
if top >= 0 {
neighbors = append(neighbors, top)
}
if bottom < g.Order() {
neighbors = append(neighbors, bottom)
}
row := v / n
if left >= 0 && left/n == row {
neighbors = append(neighbors, left)
}
if right/n == row {
neighbors = append(neighbors, right)
}
return func(yield func(w int, weight struct{}) bool) {
color := g.colorOf(v)
for _, neighbor := range neighbors {
if g.colorOf(neighbor) != color {
continue
}
if !yield(neighbor, struct{}{}) {
return
}
}
}
}
func (g graph) String() string {
buf := new(bytes.Buffer)
for _, line := range g {
fmt.Fprintln(buf, string(line[:]))
}
return buf.String()
}
func (g graph) rowCol(v int) (int, int) {
n := len(g[0])
row := v / n
col := v % n
return row, col
}
func (g graph) colorOf(v int) rune {
row, col := g.rowCol(v)
return g[row][col]
}
Output: ⬜⬛⬜⬜⬛⬜⬜⬜⬜⬜⬜⬜⬜ ⬛⬜⬛⬜⬛⬛⬜⬜⬜⬜⬜⬜⬜ ⬜⬛⬜⬛⬜⬛⬛⬜⬜⬜⬜⬜⬜ ⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬜⬜⬜ ⬛⬛⬜⬜⬜⬛⬛⬛⬜⬜⬜⬜⬜ ⬜⬛⬛⬜⬛⬜⬛⬜⬜⬜⬜⬜⬜ ⬜⬜⬛⬛⬛⬛⬜⬜⬛⬜⬜⬜⬜ ⬜⬜⬜⬜⬛⬜⬜⬜⬜⬜⬜⬜⬜ ⬜⬜⬜⬜⬜⬜⬛⬜⬜⬜⬜⬜⬜ ⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬛⬛ ⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬜⬛⬜ ⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬛⬜⬛ ⬜⬜⬜⬜⬜⬜⬜⬜⬜⬛⬜⬛⬜ ⬜⬛⬜⬜⬛🟩🟩🟩🟩🟩🟩🟩🟩 ⬛⬜⬛⬜⬛⬛🟩🟩🟩🟩🟩🟩🟩 ⬜⬛⬜⬛⬜⬛⬛🟩🟩🟩🟩🟩🟩 ⬜⬜⬛⬜⬜⬜⬛🟩🟩🟩🟩🟩🟩 ⬛⬛⬜⬜⬜⬛⬛⬛🟩🟩🟩🟩🟩 🟩⬛⬛⬜⬛⬜⬛🟩🟩🟩🟩🟩🟩 🟩🟩⬛⬛⬛⬛🟩🟩⬛🟩🟩🟩🟩 🟩🟩🟩🟩⬛🟩🟩🟩🟩🟩🟩🟩🟩 🟩🟩🟩🟩🟩🟩⬛🟩🟩🟩🟩🟩🟩 🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩⬛⬛⬛ 🟩🟩🟩🟩🟩🟩🟩🟩🟩⬛⬜⬛⬜ 🟩🟩🟩🟩🟩🟩🟩🟩🟩⬛⬛⬜⬛ 🟩🟩🟩🟩🟩🟩🟩🟩🟩⬛⬜⬛⬜
func BellmanFord ¶
func BellmanFord[T IntegerOrFloat](g Graph[T], v int) (parent []int, dist []T, ok bool)
BellmanFord calculate the shortest path from v to all other vertices. The function returns the a slice of parent, a slice of dist containing the dists between v and the vertex and return ok if there isn't a negative cycle.
The algorithm skip NaN weighted edges.
func Bipartition ¶
Bipartition returns a subset U of g's vertices with the property that every edge of g connects a vertex in U to one outside of U. If g isn't bipartite, it returns an empty slice and sets ok to false.
func DFS ¶
DFS returns an iterator of edges that traverse the graph in Depth First Search way, starting from vertex v.
func DFSPostvisit ¶
DFSPostvisit returns an iterator of vertices in Postvisit order, starting from vertex v.
func DFSPrevisit ¶
DFSPrevisit returns an iterator of vertices in Previsit order, starting from vertex v.
func InfFor ¶
func InfFor[T IntegerOrFloat]() T
InfFor returns the infinite representation for a type T.
For floats it returns math.Inf(1).
For ints/uints it returns the maximum positive value the type can represent, e.g. math.MaxInt64 for int64.
InfFor is useful to check if the returned value of a function is infinite, like the cost of a shortest path or the max flow.
E.g.
if cost == InfFor[int]() {
...
}
func MST ¶
func MST[T IntegerOrFloat](g Graph[T]) (parent []int)
MST find the minimum spanning tree or forest and return a slice with the parent of each vertex. The algorithm ignore edges with NaN weights.
func ShortestPath ¶
func ShortestPath[T IntegerOrFloat](g Graph[T], v, w int) (path []int, dist T)
ShortestPath computes a shortest path from v to w. Only edges with non-negative and non-NaN costs are included. The number dist is the length of the path, or inf if w cannot be reached. (inf is +inf for floats and the maximum value for integers).
The time complexity is O((|E| + |V|)⋅log|V|), where |E| is the number of edges and |V| the number of vertices in the graph.
func ShortestPaths ¶
func ShortestPaths[T IntegerOrFloat](g Graph[T], v int) (parent []int, dist []T)
ShortestPaths computes the shortest paths from v to all other vertices. Only edges with non-negative and non-NaN costs are included. The number parent[w] is the predecessor of w on a shortest path from v to w, or -1 if none exists. The number dist[w] equals the length of a shortest path from v to w, or is inf if w cannot be reached. (inf is +inf for floats and the maximum value for integers).
The time complexity is O((|E| + |V|)⋅log|V|), where |E| is the number of edges and |V| the number of vertices in the graph.
func String ¶
func String[T IntegerOrFloat](g Graph[T]) string
String returns a description of g with two elements: the number of vertices, followed by a sorted list of all edges.
func StrongComponents ¶
StrongComponents returns a slice of g's strong connected components. Each slice contains the vertices of each component.
A component is strongly connected if all its vertices are reachable from every other vertex in the component.
Types ¶
type Graph ¶
type Graph[T any] interface { // Order returns the number of vertices in a graph. Order() int // EdgesFrom returns an iterator that iterates over the outgoing edges of v. // Each iteration returns w and weight of an edge v-[weight]->w, weight is // the weight of the edge. // // The iteration may occur in any order, and the order may vary. EdgesFrom(v int) iter.Seq2[int, T] }
Graph describes a directed weighted graph.
The Graph interface can be used to describe both oridinary graphs and multigraphs.
func MaxFlow ¶
func MaxFlow[T constraints.Integer](g Graph[T], s, t int) (flow T, graph Graph[T])
MaxFlow computes a maximum flow from s to t in a graph with nonnegative edge capacities. The time complexity is O(|E|²⋅|V|), where |E| is the number of edges and |V| the number of vertices in the graph.
type Immutable ¶
type Immutable[T any] struct { // contains filtered or unexported fields }
Immutable is a compact representation of an immutable graph. The implementation uses lists to associate each vertex in the graph with its adjacent vertices. This makes for fast and predictable iteration: the Visit method produces its elements by reading from a fixed sorted precomputed list. This type supports multigraphs.
func Sort ¶
Sort returns an immutable copy of g with a Visit method that returns its neighbors in increasing numerical order.
func Transpose ¶
Transpose returns the transpose graph of g. The transpose graph has the same set of vertices as g, but all of the edges are reversed compared to the orientation of the corresponding edges in g.
type IntegerOrFloat ¶
type Mutable ¶
type Mutable[T any] struct { // contains filtered or unexported fields }
Mutable represents a directed graph with a fixed number of vertices and weighted edges that can be added or removed. The implementation uses hash mpas to associate each vertex in the graph with its adjacent vertices. This gives constant time performance for all basic operations.
func (*Mutable[T]) Add ¶
Add appends the edge v -[weight]-> w to the graph.
If already exists a edge v -> w the old edge is deleted, Mutable does not support parallel edges.
func (*Mutable[T]) AddBoth ¶
AddBoth appends the edges v -[weight]-> w and w -[weight]-> v to the graph.
If already exists a edge v -> w or w -> v the old edge is deleted, Mutable does not support parallel edges.
func (*Mutable[T]) DeleteBoth ¶
DeleteBoth removes all edges between v and w.
Source Files
Directories