grapho

README

grapho

grapho is a Go implementation of Graph Theory data structures and algorithms. The full documentation can be found here

Graphs

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.

Algorithms

Search:

• 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).

Minimum Spanning Tree:

• 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)

TODO:

• Multigraph
• Minimum Cut
• Topological short
• Coloring algorithms
• Strongly Connected Components
• Eulerian path/circuit
• Flow Networks
• ...

Contributing

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!

License

This library is distributed under the BSD-style license found in the LICENSE file.

Documentation

Index

• func IsConnected(g *Graph) bool
• func NullHeuristic(node, goal uint64) int
• func Search(graph *Graph, start, goal uint64, algo SearchAlgorithm, heuristic Heuristic) ([]uint64, error)
• type Attr
  • func NewAttr() Attr
• type Edge
  • func NewEdge(weight int, attr Attr) *Edge
• type Graph
  • func MinimumSpanningTree(graph *Graph, algo MstAlgorithm) (*Graph, error)
  • func NewGraph(directed bool) *Graph
  • func PrimMst(graph *Graph) (*Graph, error)
  • func (g *Graph) AddEdge(u, v uint64, weight int, attr Attr)
  • func (g *Graph) AddNode(node uint64, attr Attr)
  • func (g *Graph) DeleteEdge(u, v uint64)
  • func (g *Graph) DeleteNode(node uint64)
  • func (g *Graph) Edge(u, v uint64) (*Edge, bool)
  • func (g *Graph) IsDirected() bool
  • func (g *Graph) Len() int
  • func (g *Graph) Neighbors(node uint64) ([]uint64, bool)
  • func (g *Graph) Node(node uint64) (Attr, bool)
  • func (g *Graph) Nodes() []uint64
• type Heuristic
• type MstAlgorithm
• type OpenQueue
  • func (q *OpenQueue) Push(item interface{}, priority int)
• type OpenSet
• type OpenStack
  • func (s *OpenStack) Push(item interface{}, priority int)
• type SearchAlgorithm

Functions

func IsConnected

func IsConnected(g *Graph) bool

Connected returns whether the Graph is fully connected or not.

func NullHeuristic

func NullHeuristic(node, goal uint64) int

func Search

func Search(graph *Graph, start, goal uint64, algo SearchAlgorithm, heuristic Heuristic) ([]uint64, error)

Search find a path between two nodes. The type of search is determined by the Algorithm algo If the Graph contains no path between the nodes, an error is returned

Types

type Attr

type Attr map[string]interface{}

Attr is a set of attributes associated to a node/edge. Keys are strings. Values can be anything.

func NewAttr

func NewAttr() Attr

NewAttr creates an empty set of attributes.

type Edge

type Edge struct {
	Weight int  // Edge weight (cost)
	Attr   Attr // Edge attribute set
}

Edge represents a relationship between two nodes.

func NewEdge

func NewEdge(weight int, attr Attr) *Edge

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph implementation. Each pair of nodes can only hold one edge between them (no parallel edges).

func MinimumSpanningTree

func MinimumSpanningTree(graph *Graph, algo MstAlgorithm) (*Graph, error)

MinimumSpanningTree calculates the MST using the specified algorithm

func NewGraph

func NewGraph(directed bool) *Graph

NewGraph creates an empty Graph.

func PrimMst

func PrimMst(graph *Graph) (*Graph, error)

PrimMst calculates the MST using PRIM algorithm (heap-based implementation).

func (*Graph) AddEdge

func (g *Graph) AddEdge(u, v uint64, weight int, attr Attr)

AddEdge adds an edge (with its attributes) between nodes u and v If the nodes don't exist, they will be automatically created. If an u-v edge already existed, its attributes will be overridden.

func (*Graph) AddNode

func (g *Graph) AddNode(node uint64, attr Attr)

AddNode adds the given node to the Graph. If the node already exists, it will override its attributes.

func (*Graph) DeleteEdge

func (g *Graph) DeleteEdge(u, v uint64)

DeleteEdge removes the u-v edge, if exists. If any of the nodes don't exist, nothing happens.

func (*Graph) DeleteNode

func (g *Graph) DeleteNode(node uint64)

DeleteNode removes a node entry from the Graph. Any edge associated with it will be removed too.

func (*Graph) Edge

func (g *Graph) Edge(u, v uint64) (*Edge, bool)

Edge returns the Edge associated with the u-v node pair. An extra bool flag determines whether the edge was found. In undirected graphs, the edge u-v is be the same as v-u.

func (*Graph) IsDirected

func (g *Graph) IsDirected() bool

IsDirected returns whether the Graph is directed or not.

func (*Graph) Len

func (g *Graph) Len() int

Len returns the number of nodes in the Graph

func (*Graph) Neighbors

func (g *Graph) Neighbors(node uint64) ([]uint64, bool)

Neighbors returns the list of nodes containing edges between the given node and them, ordered by ascending node uint64 value An extra bool flag determines whether the node was found.

func (*Graph) Node

func (g *Graph) Node(node uint64) (Attr, bool)

Node returns the attributes associated with a given node, and a bool flag set to true if the node was found, false otherwise.

func (*Graph) Nodes

func (g *Graph) Nodes() []uint64

Nodes returns the list of nodes in the Graph (unsorted).

type Heuristic

type Heuristic func(node, goal uint64) int

Heuristic calculates the estimated cost between two nodes

type MstAlgorithm

type MstAlgorithm uint

const (
	Prim MstAlgorithm = iota
)

type OpenQueue

type OpenQueue struct{ *container.Queue }

Wrap Queue to match OpenSet interface signature

func (*OpenQueue) Push

func (q *OpenQueue) Push(item interface{}, priority int)

type OpenSet

type OpenSet interface {
	Push(item interface{}, priority int)
	Pop() interface{}
	Len() int
}

OpenSet defines the functions that any container used to keep track of non-expanded nodes must implement

type OpenStack

type OpenStack struct{ *container.Stack }

Wrap Stack to match OpenSet interface signature

func (*OpenStack) Push

func (s *OpenStack) Push(item interface{}, priority int)

type SearchAlgorithm

type SearchAlgorithm uint

Algorithm binds each search type to a constant unsigned integer

const (
	BreadthFirstSearch SearchAlgorithm = iota
	DepthFirstSearch
	Dijkstra
	Astar
)