README
¶
Graph Algorithms in Go
This repository contains implementations of various graph algorithms written in Go. I’ve written them to learn about these algorithms.
Implemented
- Data structues
- Graph and Digraph
- Flow network
- Set
- Sorting algorithms
- Spanning tree algorithms
- Shortest path algorithms
- Search algorithms
- Connected components algorithms
- Network algorithms
- Residual network
Contributors
- Julianna Gobolos-Szabo (Topological sorting)
Documentation
¶
Index ¶
- Variables
- func BFS(g *Graph, start Vertex, walkFunc BFSWalkFunc)
- func DFS(g *Graph, start Vertex, walkFunc DFSWalkFunc)
- func Dijkstra(g *Graph, start, end Vertex) *list.List
- func FloydWarshall(g *Graph) map[Vertex]map[Vertex]float64
- func TarjanStrongCC(g *Graph) *list.List
- func TopologicalSort(g *Graph) (topologicalOrder *list.List, topologicalClasses map[Vertex]int, err error)
- type BFSWalkFunc
- type DFSWalkFunc
- type Edge
- type Graph
- func (g *Graph) AddEdge(v1, v2 Vertex, c float64)
- func (g *Graph) AddVertex(v Vertex)
- func (g *Graph) Dump()
- func (g *Graph) EdgesIter() chan Edge
- func (g *Graph) Equals(g2 *Graph) bool
- func (g *Graph) HalfedgesIter(v Vertex) chan Halfedge
- func (g *Graph) NEdges() int
- func (g *Graph) NVertices() int
- func (g *Graph) SortedEdges() SortedEdges
- func (g *Graph) VerticesIter() chan Vertex
- type Halfedge
- type Network
- type Set
- func (s *Set) Add(element interface{}) bool
- func (s *Set) Any() interface{}
- func (s *Set) Contains(element interface{}) bool
- func (s *Set) Each(f func(interface{}, *bool))
- func (s *Set) Equals(s2 *Set) bool
- func (s *Set) Iter() chan interface{}
- func (s *Set) Len() int
- func (s *Set) Merge(s2 *Set)
- func (s *Set) Remove(element interface{}) bool
- type SortedEdges
- type Vertex
Constants ¶
This section is empty.
Variables ¶
var ErrNoDAG = errors.New("graphs: graph is not a DAG")
Functions ¶
func BFS ¶
func BFS(g *Graph, start Vertex, walkFunc BFSWalkFunc)
func DFS ¶
func DFS(g *Graph, start Vertex, walkFunc DFSWalkFunc)
func FloydWarshall ¶
FloydWarshall implements the Floyd–Warshall algorithm. It returns the cost matrix for each vertex to each other vertex of the given graph. It does not check for negative weight cycles.
func TarjanStrongCC ¶
TarjanStrongCC returns a list of sets of vertices. Each set is a strongly connected component of the graph.
Types ¶
type BFSWalkFunc ¶
type DFSWalkFunc ¶
type Graph ¶
A Graph is defined by its vertices and edges stored as an adjacency set.
func Kruskal ¶
Kruskal implements Kruskal’s algorithm. It returns a minimal spanning tree for the given graph.
func Prim ¶
Prim implements Prim’s algorithm. It returns a minimal spanning tree for the given graph, starting with vertex start.
func (*Graph) AddEdge ¶
AddEdge adds an edge to the graph. The edge connects vertex v1 and vertex v2 with cost c.
func (*Graph) Equals ¶
Equals returns whether the graph is equal to the given graph. Two graphs are equal of their adjacency is equal.
func (*Graph) HalfedgesIter ¶
HalfedgesIter returns a channel with all halfedges for the given start vertex.
func (*Graph) SortedEdges ¶
func (g *Graph) SortedEdges() SortedEdges
SortedEdges returns an array of edges sorted by their cost.
func (*Graph) VerticesIter ¶
VerticesIter returns a channel where all vertices are sent to.
type Halfedge ¶
A Halfedge is an edge where just the end vertex is stored. The start vertex is inferred from the context.
type Network ¶
type Network struct {
Graph *Graph
Source Vertex
Sink Vertex
Flow map[Edge]uint
Capacity map[Edge]uint
}
func NewNetwork ¶
func (*Network) ResidualNetwork ¶
func (*Network) SetCapacity ¶
func (*Network) SetFlowAndCapacity ¶
type Set ¶
type Set map[interface{}]struct{}
A Set is a container that contains each element just once.
func NewSetWithElements ¶
func NewSetWithElements(elements ...interface{}) *Set
NewSetWithElements creates a new set with the given arguments as elements.
func (*Set) Add ¶
Add adds an element to the set. It returns true if the element has been added and false if the set already contained that element.
func (*Set) Iter ¶
func (s *Set) Iter() chan interface{}
Iter returns a channel where all elements of the set are sent to.
type SortedEdges ¶
type SortedEdges []Edge
SortedEdges is an array of edges that can be sorted by their cost.
func (SortedEdges) Len ¶
func (se SortedEdges) Len() int
func (SortedEdges) Less ¶
func (se SortedEdges) Less(i, j int) bool
func (SortedEdges) Swap ¶
func (se SortedEdges) Swap(i, j int)
type Vertex ¶
type Vertex interface{}
A Vertex can be just anything.
func BellmanFord ¶
BellmanFord implements the Bellman-Ford algorithm. It returns the shortest-weight path from start to end vertex as a slice, or nil if the graph contains a negative-weight cycle.
Source Files