Metadata-Version: 2.2
Name: tarjan
Version: 0.2.4
Summary: Implementation of Tarjan's algorithm: resolve cyclic deps
Home-page: http://github.com/bwesterb/py-tarjan/
Author: Bas Westerbaan
Author-email: bas@westerbaan.name
Classifier: Development Status :: 5 - Production/Stable
Classifier: License :: OSI Approved :: GNU Lesser General Public License v3 (LGPLv3)
Classifier: Programming Language :: Python :: 2.7
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
License-File: LICENSE
Dynamic: author
Dynamic: author-email
Dynamic: classifier
Dynamic: description
Dynamic: home-page
Dynamic: summary

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
-------

.. image:: https://raw.githubusercontent.com/bwesterb/py-tarjan/master/doc/example.png

.. code::

   >>> 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`:

.. code::

    >>> 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

.. code::

    pip install tarjan

or from this source distribution, run

.. code::

    python setup.py install

.. image:: https://travis-ci.org/bwesterb/py-tarjan.png
   :target: https://travis-ci.org/bwesterb/py-tarjan

Tarjan Changelog
================

0.2.4 (2023-04-14)
------------------

- Support Python 3.8 - 3.11
- Drop support for Python 2.6, 3.2 - 3.7
- Change license to LGPLv3
- Switch to Github actions
- Add flake8 linting


0.2.3.2 (2016-12-28)
--------------------

- Python 3.6 support


0.2.3.1 (2015-11-22)
--------------------

- Python 3.4 & 3.5 support


0.2.3 (2015-02-19)
------------------

- Fix packaging bug [#6]


0.2.2 (2015-02-18)
------------------

- Removed dynamic version specifier
- Converted docs to rst for better docs on pypi

Thanks-to: Patrick Gerken (github.com/d03cc)
