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

    func Connections(graph map[interface{}][]interface{}) [][]interface{}

      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
      Output:
      
      [[1 2 3] [6 7] [4 5] [8]]
      

      Types

      This section is empty.

      Source Files