graph

package module
v0.0.0-...-8ecfec1 Latest Latest
Warning

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

 Go to latest Published: Jun 6, 2021 License: BSD-2-Clause Imports: 2 Imported by: 74

README

Your basic graph GoDoc

Golang library of basic graph algorithms

Topological ordering

Topological ordering, image by David Eppstein, CC0 1.0.

This library offers efficient and well-tested algorithms for

  • breadth-first and depth-first search,
  • topological ordering,
  • strongly and weakly connected components,
  • bipartion,
  • shortest paths,
  • maximum flow,
  • Euler walks,
  • and minimum spanning trees.

The algorithms can be applied to any graph data structure implementing the two Iterator methods: Order, which returns the number of vertices, and Visit, which iterates over the neighbors of a vertex.

All algorithms operate on directed graphs with a fixed number of vertices, labeled from 0 to n-1, and edges with integer cost. An undirected edge {v, w} of cost c is represented by the two directed edges (v, w) and (w, v), both of cost c. A self-loop, an edge connecting a vertex to itself, is both directed and undirected.

Graph data structures

The type Mutable represents a directed graph with a fixed number of vertices and weighted edges that can be added or removed. The implementation uses hash maps to associate each vertex in the graph with its adjacent vertices. This gives constant time performance for all basic operations.

The type 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.

Virtual graphs

The subpackage graph/build offers a tool for building graphs of type Virtual.

In a virtual graph no vertices or edges are stored in memory, they are instead computed as needed. New virtual graphs are constructed by composing and filtering a set of standard graphs, or by writing functions that describe the edges of a graph.

The following standard graphs are predefined:

  • empty graphs,
  • complete graphs and complete bipartite graphs,
  • grid graphs and complete k-ary trees,
  • cycle graphs and circulant graphs,
  • and hypergraphs.

The following operations are supported:

  • adding and deleting sets of edges,
  • adding cost functions,
  • filtering graphs by edge functions,
  • complement, intersection and union,
  • subgraphs,
  • connecting graphs at a single vertex,
  • joining two graphs by a set of edges,
  • matching two graphs by a set of edges,
  • cartesian product and tensor product.

Non-virtual graphs can be imported, and used as building blocks, by the Specific function. Virtual graphs don't need to be “exported‬”; they implement the Iterator interface and hence can be used directly by any algorithm in the graph package.

Installation

Once you have installed Go, run this command to install the graph package:

go get github.com/yourbasic/graph
Documentation

There is an online reference for the package at godoc.org/github.com/yourbasic/graph.

Roadmap
  • The API of this library is frozen.
  • Bug fixes and performance enhancement can be expected.
  • New functionality might be included.
  • Version numbers adhere to semantic versioning.

The only accepted reason to modify the API of this package is to handle issues that can't be resolved in any other reasonable way.

New features and performance enhancements are limited to basic algorithms and data structures, akin to the ones that you might find in a computer science textbook.

Stefan Nilsson – korthaj

Documentation

Overview

Package graph contains generic implementations of basic graph algorithms.

Generic graph algorithms

The algorithms in this library can be applied to any graph data structure implementing the two Iterator methods: Order, which returns the number of vertices, and Visit, which iterates over the neighbors of a vertex.

All algorithms operate on directed graphs with a fixed number of vertices, labeled from 0 to n-1, and edges with integer cost. An undirected edge {v, w} of cost c is represented by the two directed edges (v, w) and (w, v), both of cost c. A self-loop, an edge connecting a vertex to itself, is both directed and undirected.

Graph data structures

The type Mutable represents a directed graph with a fixed number of vertices and weighted edges that can be added or removed. The implementation uses hash maps to associate each vertex in the graph with its adjacent vertices. This gives constant time performance for all basic operations.

The type 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.

Virtual graphs

The subpackage graph/build offers a tool for building virtual graphs. In a virtual graph no vertices or edges are stored in memory, they are instead computed as needed. New virtual graphs are constructed by composing and filtering a set of standard graphs, or by writing functions that describe the edges of a graph.

Tutorial

The Basics example shows how to build a plain graph and how to efficiently use the Visit iterator, the key abstraction of this package.

The DFS example contains a full implementation of depth-first search.

Example (Basics)

Build a plain graph and visit all of its edges. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	// Build a graph with four vertices and four undirected edges.
	// (Each of these edges are, in fact, represented by two directed
	// edges pointing in opposite directions.)
	g := graph.New(4)
	g.AddBoth(0, 1) //  0 -- 1
	g.AddBoth(0, 2) //  |    |
	g.AddBoth(2, 3) //  2 -- 3
	g.AddBoth(1, 3)

	// The vertices of all graphs in this package are numbered 0..n-1.
	// The edge iterator is a method called Visit; it calls a function
	// for each neighbor of a given vertex. Together with the Order
	// method — which returns the number of vertices in a graph — it
	// constitutes an Iterator. All algorithms in this package operate
	// on any graph implementing this interface.

	// Visit all edges of a graph.
	for v := 0; v < g.Order(); v++ {
		g.Visit(v, func(w int, c int64) (skip bool) {
			// Visiting edge (v, w) of cost c.
			return
		})
	}

	// The immutable data structure created by Sort has an Iterator
	// that returns neighbors in increasing order.

	// Visit the edges in order.
	for v := 0; v < g.Order(); v++ {
		graph.Sort(g).Visit(v, func(w int, c int64) (skip bool) {
			// Visiting edge (v, w) of cost c.
			return
		})
	}

	// The return value of an iterator function is used to break
	// out of the iteration. Visit, in turn, returns a boolean
	// indicating if it was aborted.

	// Skip the iteration at the first edge (v, w) with w equal to 3.
	for v := 0; v < g.Order(); v++ {
		aborted := graph.Sort(g).Visit(v, func(w int, c int64) (skip bool) {
			fmt.Println(v, w)
			if w == 3 {
				skip = true // Aborts the call to Visit.
			}
			return
		})
		if aborted {
			break
		}
	}
}

Output:

0 1
0 2
1 0
1 3
Example (DFS)

Show how to use this package by implementing a complete depth-first search. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

const (
	White = iota
	Gray
	Black
)

// The package doesn't support vertex labeling. However,
// since vertices are always numbered 0..n-1, it's easy
// to add this type of data on the side. This implementation
// of depth-first search uses separate slices to keep track of
// vertex colors, predecessors and discovery times.
type DFSData struct {
	Time     int
	Color    []int
	Prev     []int
	Discover []int
	Finish   []int
}

func DFS(g graph.Iterator) DFSData {
	n := g.Order() // Order returns the number of vertices.
	d := DFSData{
		Time:     0,
		Color:    make([]int, n),
		Prev:     make([]int, n),
		Discover: make([]int, n),
		Finish:   make([]int, n),
	}
	for v := 0; v < n; v++ {
		d.Color[v] = White
		d.Prev[v] = -1
	}
	for v := 0; v < n; v++ {
		if d.Color[v] == White {
			d.dfsVisit(g, v)
		}
	}
	return d
}

func (d *DFSData) dfsVisit(g graph.Iterator, v int) {
	d.Color[v] = Gray
	d.Time++
	d.Discover[v] = d.Time
	// Visit calls a function for each neighbor w of v,
	// with c equal to the cost of the edge (v, w).
	// The iteration is aborted if the function returns true.
	g.Visit(v, func(w int, c int64) (skip bool) {
		if d.Color[w] == White {
			d.Prev[w] = v
			d.dfsVisit(g, w)
		}
		return
	})
	d.Color[v] = Black
	d.Time++
	d.Finish[v] = d.Time
}

// Show how to use this package by implementing a complete depth-first search.
func main() {
	// Build a small directed graph:
	//
	//   0 ---> 1 <--> 2     3
	//
	g := graph.New(4)
	g.Add(0, 1)
	g.AddBoth(1, 2)

	fmt.Println(g)
	fmt.Println(DFS(g))
}

Output:

4 [(0 1) {1 2}]
{8 [2 2 2 2] [-1 0 1 -1] [1 2 3 7] [6 5 4 8]}

Index

Examples

Constants

View Source 
const (
	Max int64 = 1<<63 - 1
	Min int64 = -1 << 63
)

The maximum and minimum value of an edge cost.

Variables

This section is empty.

Functions

func Acyclic 

func Acyclic(g Iterator) bool

Acyclic tells if g has no cycles.

func BFS 

func BFS(g Iterator, v int, do func(v, w int, c int64))

BFS traverses g in breadth-first order starting at v. When the algorithm follows an edge (v, w) and finds a previously unvisited vertex w, it calls do(v, w, c) with c equal to the cost of the edge (v, w).

Example

Find the shortest distances from a vertex in an unweighted graph. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	gm := graph.New(6)
	gm.AddBoth(0, 1) //  0--1--2
	gm.AddBoth(0, 3) //  |  |  |
	gm.AddBoth(1, 2) //  3--4  5
	gm.AddBoth(1, 4)
	gm.AddBoth(2, 5)
	gm.AddBoth(3, 4)
	g := graph.Sort(gm)

	dist := make([]int, g.Order())
	graph.BFS(g, 0, func(v, w int, _ int64) {
		fmt.Println(v, "to", w)
		dist[w] = dist[v] + 1
	})
	fmt.Println("dist:", dist)
}

Output:

0 to 1
0 to 3
1 to 2
1 to 4
2 to 5
dist: [0 1 2 1 2 3]

func Bipartition 

func Bipartition(g Iterator) (part []int, ok bool)

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 Components 

func Components(g Iterator) [][]int

Components produces a partition of g's vertices into its (weakly) connected components.

Example

Find the weakly connected components in a directed graph. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	g := graph.New(6)
	g.AddBoth(0, 1) //  0 <--> 1 ---> 2
	g.Add(1, 2)     //                ^
	g.Add(4, 3)     //                |
	g.AddBoth(5, 2) //  3 <--- 4      5

	fmt.Println(graph.Components(g))
}

Output:

[[0 1 2 5] [3 4]]

func Connected 

func Connected(g Iterator) bool

Connected tells if g has exactly one (weakly) connected component.

func Equal 

func Equal(g, h Iterator) bool

Equal tells if g and h have the same number of vertices, and the same edges with the same costs.

func EulerDirected 

func EulerDirected(g Iterator) (walk []int, ok bool)

EulerDirected returns an Euler walk in a directed graph. If no such walk exists, it returns an empty walk and sets ok to false.

Example

Find an Euler walk in a directed graph. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	//  0 <--> 1 --> 2     3
	g := graph.New(4)
	g.AddBoth(0, 1)
	g.Add(1, 2)

	fmt.Println(graph.EulerDirected(g))
}

Output:

[1 0 1 2] true

func EulerUndirected 

func EulerUndirected(g Iterator) (walk []int, ok bool)

EulerUndirected returns an Euler walk following undirected edges in only one direction. If no such walk exists, it returns an empty walk and sets ok to false.

Example

Find an Euler walk in an undirected graph. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	//  0  1
	//     |
	//  2--3---
	//     |  |
	//     ----
	g := graph.New(4)
	g.AddBoth(1, 3)
	g.AddBoth(2, 3)
	g.AddBoth(3, 3)

	fmt.Println(graph.EulerUndirected(g))
}

Output:

[1 3 3 2] true

func MST 

func MST(g Iterator) (parent []int)

MST computes a minimum spanning tree for each connected component of an undirected weighted graph. The forest of spanning trees is returned as a slice of parent pointers: parent[v] is either the parent of v in a tree, or -1 if v is the root of a tree.

The time complexity is O(|E|⋅log|V|), where |E| is the number of edges and |V| the number of vertices in the graph.

func ShortestPath 

func ShortestPath(g Iterator, v, w int) (path []int, dist int64)

ShortestPath computes a shortest path from v to w. Only edges with non-negative costs are included. The number dist is the length of the path, or -1 if w cannot be reached.

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.

Example

Find a shortest path between two vertices in a graph. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	g := graph.New(6)
	g.AddBothCost(0, 1, 8) //  0==1--2
	g.AddBothCost(0, 3, 2) //  |  |  |
	g.AddBothCost(1, 2, 2) //  3--4==5
	g.AddBothCost(1, 4, 2) //
	g.AddBothCost(2, 5, 2) //  -- cost 2
	g.AddBothCost(3, 4, 2) //  == cost 8
	g.AddBothCost(4, 5, 8)

	path, dist := graph.ShortestPath(g, 0, 5)
	fmt.Println("path:", path, "length:", dist)
}

Output:

path: [0 3 4 1 2 5] length: 10

func ShortestPaths 

func ShortestPaths(g Iterator, v int) (parent []int, dist []int64)

ShortestPaths computes the shortest paths from v to all other vertices. Only edges with non-negative 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 -1 if w cannot be reached.

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(g Iterator) string

String returns a description of g with two elements: the number of vertices, followed by a sorted list of all edges.

Example

Print a graph. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	g0 := graph.New(0)
	fmt.Println(g0)

	g1 := graph.New(1)
	g1.Add(0, 0)
	fmt.Println(g1)

	g4 := graph.New(4) //             8
	g4.AddBoth(0, 1)   //  0 <--> 1 <--- 2      3
	g4.AddCost(2, 1, 8)
	fmt.Println(g4)
}

Output:

0 []
1 [(0 0)]
4 [{0 1} (2 1):8]

func StrongComponents 

func StrongComponents(g Iterator) [][]int

StrongComponents produces a partition of g's vertices into its strongly connected components.

A component is strongly connected if all its vertices are reachable from every other vertex in the component. Each vertex of the graph appears in exactly one of the strongly connected components, and any vertex that is not on a directed cycle forms a strongly connected component all by itself.

Example

Find the strongly connected components in a directed graph. 

package main

import (
	"fmt"
	"github.com/yourbasic/graph"
)

func main() {
	g := graph.New(6)
	g.AddBoth(0, 1) //  0 <--> 1 <--> 2
	g.AddBoth(1, 2) //  ^      ^      ^
	g.Add(3, 0)     //  |      |      |
	g.AddBoth(3, 4) //  3 <--> 4 ---> 5
	g.Add(4, 1)
	g.Add(4, 5)
	g.Add(5, 2)

	fmt.Println(graph.StrongComponents(g))
}

Output:

[[2 1 0] [5] [4 3]]

func TopSort 

func TopSort(g Iterator) (order []int, ok bool)

TopSort returns a topological ordering of the vertices in a directed acyclic graph; if the graph is not acyclic, no such ordering exists and ok is set to false.

In a topological order v comes before w for every directed edge from v to w.

Types

type Immutable 

type Immutable 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 

func Sort(g Iterator) *Immutable

Sort returns an immutable copy of g with a Visit method that returns its neighbors in increasing numerical order.

func Transpose 

func Transpose(g Iterator) *Immutable

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.

func (*Immutable) Degree 

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

Degree returns the number of outward directed edges from v.

func (*Immutable) Edge 

func (g *Immutable) Edge(v, w int) bool

Edge tells if there is an edge from v to w.

func (*Immutable) Order 

func (g *Immutable) Order() int

Order returns the number of vertices in the graph.

func (*Immutable) String 

func (g *Immutable) String() string

String returns a string representation of the graph.

func (*Immutable) Visit 

func (g *Immutable) Visit(v int, do func(w int, c int64) bool) bool

Visit calls the do function for each neighbor w of v, with c equal to the cost of the edge from v to w. The neighbors are visited in increasing numerical order. If do returns true, Visit returns immediately, skipping any remaining neighbors, and returns true.

func (*Immutable) VisitFrom 

func (g *Immutable) VisitFrom(v int, a int, do func(w int, c int64) bool) bool

VisitFrom calls the do function starting from the first neighbor w for which w ≥ a, with c equal to the cost of the edge from v to w. The neighbors are then visited in increasing numerical order. If do returns true, VisitFrom returns immediately, skipping any remaining neighbors, and returns true.

type Iterator 

type Iterator interface {
	// Order returns the number of vertices in a graph.
	Order() int

	// Visit calls the do function for each neighbor w of vertex v,
	// with c equal to the cost of the edge from v to w.
	//
	//  • If do returns true, Visit returns immediately, skipping
	//    any remaining neighbors, and returns true.
	//
	//  • The calls to the do function may occur in any order,
	//    and the order may vary.
	//
	Visit(v int, do func(w int, c int64) (skip bool)) (aborted bool)
}

Iterator describes a weighted graph; an Iterator can be used to describe both ordinary graphs and multigraphs.

func MaxFlow 

func MaxFlow(g Iterator, s, t int) (flow int64, graph Iterator)

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 Mutable 

type Mutable 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 maps to associate each vertex in the graph with its adjacent vertices. This gives constant time performance for all basic operations.

func Copy 

func Copy(g Iterator) *Mutable

Copy returns a copy of g. If g is a multigraph, any duplicate edges in g will be lost.

func New 

func New(n int) *Mutable

New constructs a new graph with n vertices, numbered from 0 to n-1, and no edges.

func (*Mutable) Add 

func (g *Mutable) Add(v, w int)

Add inserts a directed edge from v to w with zero cost. It removes the previous cost if this edge already exists.

func (*Mutable) AddBoth 

func (g *Mutable) AddBoth(v, w int)

AddBoth inserts edges with zero cost between v and w. It removes the previous costs if these edges already exist.

func (*Mutable) AddBothCost 

func (g *Mutable) AddBothCost(v, w int, c int64)

AddBothCost inserts edges with cost c between v and w. It overwrites the previous costs if these edges already exist.

func (*Mutable) AddCost 

func (g *Mutable) AddCost(v, w int, c int64)

AddCost inserts a directed edge from v to w with cost c. It overwrites the previous cost if this edge already exists.

func (*Mutable) Cost 

func (g *Mutable) Cost(v, w int) int64

Cost returns the cost of an edge from v to w, or 0 if no such edge exists.

func (*Mutable) Degree 

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

Degree returns the number of outward directed edges from v.

func (*Mutable) Delete 

func (g *Mutable) Delete(v, w int)

Delete removes an edge from v to w.

func (*Mutable) DeleteBoth 

func (g *Mutable) DeleteBoth(v, w int)

DeleteBoth removes all edges between v and w.

func (*Mutable) Edge 

func (g *Mutable) Edge(v, w int) bool

Edge tells if there is an edge from v to w.

func (*Mutable) Order 

func (g *Mutable) Order() int

Order returns the number of vertices in the graph.

func (*Mutable) String 

func (g *Mutable) String() string

String returns a string representation of the graph.

func (*Mutable) Visit 

func (g *Mutable) Visit(v int, do func(w int, c int64) bool) bool

Visit calls the do function for each neighbor w of v, with c equal to the cost of the edge from v to w. If do returns true, Visit returns immediately, skipping any remaining neighbors, and returns true.

The iteration order is not specified and is not guaranteed to be the same every time. It is safe to delete, but not to add, edges adjacent to v during a call to this method.

type Stats 

type Stats struct {
	Size     int // Number of unique edges.
	Multi    int // Number of duplicate edges.
	Weighted int // Number of edges with non-zero cost.
	Loops    int // Number of self-loops.
	Isolated int // Number of vertices with outdegree zero.
}

Stats holds basic data about an Iterator.

func Check 

func Check(g Iterator) Stats

Check collects data about an Iterator.

Source Files

View all Source files

Directories

Path Synopsis
Package build offers a tool for building virtual graphs.
 Package build offers a tool for building virtual graphs.

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.