graph

This go library provides packages with primitives and functions for common graph operations. It's designed to be graph structure agnostic, it depends only on required API for each operation declared as interface (similar to standard Go sort package).

Packages

Search

Package search provides graph search operations:

• DepthFirstSearch(Graph g, v int, visitor Visitor) - implements DFS stack-based algorithm for graph g from vertex v using visitor.
• BreathFirstSearch(g Graph, v int, visitor Visitor) - implements BFS queue-based algorithm for graph g from vertex v using visitor.
• HasCicle(g Graph) - detects if graph g has any cicle.
• SimplePaths(g Graph, from, to int) - finds all simple paths (without cicles) in graph g from vertex from to to.

Graph type for search package should be able to say its size of vertices and edges, and iterate all neighors for each vertex:

type Graph interface {
	// Size of vertices and edges
	Size() (vertices, edges int)

	// Neighbors of vertex
	Neighbors(v int) []int
}

The search package provides standard visitors for DFS and BFS like:

• NewFullVisitor(Graph) which allows to visit all vertices
• NewShortPathVisitor(g Graph, vertex int) which stops when destination vertex is visited.

Users are free to implement custom visitor as Visitor interface.