package tarjan

import "go-hep.org/x/hep/fwk/utils/tarjan"

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 ¶

• func Connections(graph map[any][]any) [][]any

Examples ¶

• Connections

Functions ¶

func Connections ¶

func Connections(graph map[any][]any) [][]any

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.

{
	graph := make(map[any][]any)
	graph["1"] = []any{"2"}
	graph["2"] = []any{"3"}
	graph["3"] = []any{"1"}
	graph["4"] = []any{"2", "3", "5"}
	graph["5"] = []any{"4", "6"}
	graph["6"] = []any{"3", "7"}
	graph["7"] = []any{"6"}
	graph["8"] = []any{"5", "7", "8"}

	o := Connections(graph)
	output := sortConnections(o)
	fmt.Println(output)

	// Output:
	// [[1 2 3] [6 7] [4 5] [8]]
}

[[1 2 3] [6 7] [4 5] [8]]

Source Files ¶

tarjan.go