# bwesterb/py-tarjan

Python implementation of Tarjan's strongly connected components algorithm.
Switch branches/tags
Nothing to show
Latest commit 60b0e3a Jan 27, 2018
 Failed to load latest commit information. doc Aug 4, 2014 src Aug 4, 2014 .gitignore Sep 5, 2011 .travis.yml Dec 28, 2016 CHANGES.rst Dec 28, 2016 LICENSE Jan 27, 2018 MANIFEST.in Feb 19, 2015 README.rst Jan 12, 2018 setup.py

# Python implementation of Tarjan's algorithm

Tarjan's algorithm takes as input a directed (possibly cyclic!) graph and returns as output its strongly connected components in a topological order.

## Example

```>>> tarjan({1:[2],2:[1,5],3:[4],4:[3,5],5:[6],6:[7],7:[8],8:[6,9],9:[]})
[[9], [8, 7, 6], [5], [2, 1], [4, 3]]
```

## Uses

### Cyclic dependencies

In various cases, dependencies might be cyclic and a group of interdependant actions must be executed simultaneously. It is not uncommon that the simulataneous execution is costly. With Tarjan's algorithm, one can determine an efficient order in which to execute the groups of interdependant actions.

### Transitive closure

Using Tarjan's algorithm, one can efficiently compute the transitive closure of a graph. (Given a graph G, the transitive closure of G is a graph that contains the same vertices and contains an edge from v to w if and only if there is a path from v to w in G.)

The transitive closure is implemented in tarjan.tc:

```>>> from tarjan.tc import tc
>>> tc({1:[2],2:[1,5],3:[4],4:[3,5],5:[6],6:[7],7:[8],8:[6,9],9:[]})
{1: (1, 2, 5, 6, 7, 8, 9),
2: (1, 2, 5, 6, 7, 8, 9),
3: (3, 4, 5, 6, 7, 8, 9),
4: (3, 4, 5, 6, 7, 8, 9),
5: (8, 9, 6, 7),
6: (8, 9, 6, 7),
7: (8, 9, 6, 7),
8: (8, 9, 6, 7),
9: ()}
```

### Expand group hierarchies

Given a graph of groups, one can use the transitive closure to determine all indirect members of a group. (Someone is an indirect member of a group, if it is a member of a group that is a member of a group that ... is a member of the group.)

## Installation

Simply execute

```pip install tarjan
```

or from this source distribution, run

```python setup.py install
```