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 BellmanFord(g Graph, start, end Vertex) []Vertex
- func DFS(g Graph, start Vertex, walkFunc DFSWalkFunc)
- func Dijkstra(g Graph, start, end Vertex) *list.List
- func FloydWarshall(g Graph) map[string]map[string]float64
- func Kruskal(g Graph) Graph
- func Prim(g Graph, start Vertex) Graph
- func TarjanStrongCC(g Graph) *list.List
- func TopologicalSort(g Graph) (topologicalOrder *list.List, topologicalClasses map[string]int, err error)
- type BFSWalkFunc
- type DFSWalkFunc
- 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
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 BellmanFord ¶
func BellmanFord(g Graph, start, end Vertex) []Vertex
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.
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 Kruskal ¶
func Kruskal(g Graph) Graph
Kruskal implements Kruskal’s algorithm. It returns a minimal spanning tree for the given graph.
func Prim ¶
func Prim(g Graph, start Vertex) Graph
Prim implements Prim’s algorithm. It returns a minimal spanning tree for the given graph, starting with vertex start.
func TarjanStrongCC ¶
TarjanStrongCC returns a list of sets of vertices. Each set is a strongly connected component of the graph.
Types ¶
type BFSWalkFunc ¶
type BFSWalkFunc func(Vertex, *bool)
type DFSWalkFunc ¶
type DFSWalkFunc func(Vertex, *bool)
type Network ¶
type Network struct {
Graph Graph
Source Vertex
Sink Vertex
Flow map[string]uint // by edge id
Capacity map[string]uint // by edge id
}
func NewNetwork ¶
func NewNetwork(graph Graph, source, sink Vertex) *Network
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.
Source Files