grapho is a Go implementation of Graph Theory data structures and algorithms. The full documentation can be found here
Graphs, both directed and undirected, are created with the Graph struct:
graph := grapho.NewGraph(false) // true for directed Graphs, false for undirected
Nodes (vertices) and Edges contain a set of attributes Attr, whose key is a string, and the value can be anything (type interface{}). Attr is in essence a map[string]interface{}, and its values are set/get with the regular map syntax:
attr := grapho.NewAttr()
attr["name"] = "Bob"
attr["x"] = 1
Nodes, uniquely identified by a uint64 id, can be added explicitly to the Graph:
graph.AddNode(1, attr)
or implicitly, if adding an Edge references a non-existing Node:
graph.AddEdge(1, 2, nil) // Node '2' will be automatically created
To check all the available methods to manipulate a Graph, see the GoDoc.
- Dijkstra (uniform cost search)
- A* (best-first search with heuristic)
- Breadth-first search
- Depth-first search
For the shortest path implementation, a generic Search function is provided, which takes the desired SearchAlgorithm to be used as a parameter:
path, err := grapho.Search(graph, 1, 8, grapho.Dijkstra, nil)
path, err := grapho.Search(graph, 1, 9, grapho.BreadthFirstSearch, nil)
...
If successful, a uint64 slice will be returned, with the node ids that form the shortest path between the specified nodes. Check out the second return value, for any possible error (i.e. no path found).
- Prim
- TODO: Kruskal
Given a connected, undirected graph, MinimumSpanningTree calculates the minimum cost subgraph that connects all the vertices together:
mst, err := grapho.MinimumSpanningTree(graph, grapho.Prim)
- Multigraph
- Minimum Cut
- Topological short
- Coloring algorithms
- Strongly Connected Components
- Eulerian path/circuit
- Flow Networks
- ...
I have no priority in mind for future algorithms to implement, so if you want to contribute with any Graph Theory algorithm (whether or not in the list above), don't hesitate in opening an issue or sending a pull request!
This library is distributed under the BSD-style license found in the LICENSE file.