Documentation
¶
Overview ¶
Package tarjan implements a graph loop detection algorithm called Tarjan's algorithm.
The algorithm takes a input graph and produces a slice where each item is a slice of strongly connected vertices. The input graph is in form of a map where the key is a graph vertex and the value is the edges in for of a slice of vertices.
Algorithm description: http://en.wikipedia.org/wiki/Tarjan’s_strongly_connected_components_algorithm
Based on an implementation by Gustavo Niemeyer (in mgo/txn): http://bazaar.launchpad.net/+branch/mgo/v2/view/head:/txn/tarjan.go
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Connections ¶
Connections creates a slice where each item is a slice of strongly connected vertices.
If a slice item contains only one vertex there are no loops. A loop on the vertex itself is also a connected group.
The example shows the same graph as in the Wikipedia article.
Example ¶
graph := make(map[string][]string) graph["1"] = []string{"2"} graph["2"] = []string{"3"} graph["3"] = []string{"1"} graph["4"] = []string{"2", "3", "5"} graph["5"] = []string{"4", "6"} graph["6"] = []string{"3", "7"} graph["7"] = []string{"6"} graph["8"] = []string{"5", "7", "8"} o := Connections(graph) output := sortConnections(o) fmt.Println(output)
Output: [[1 2 3] [6 7] [4 5] [8]]
Types ¶
This section is empty.