Skip to main content
This is a pre-production deployment of Warehouse. Changes made here affect the production instance of PyPI (pypi.python.org).
Help us improve Python packaging - Donate today!

Implementation of Tarjan's algorithm: resolve cyclic deps

Project Description

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:

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

easy_install tarjan

or from this source distribution, run

python setup.py install

Tarjan Changelog

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)

Release History

Release History

This version
History Node

0.2.3.2

History Node

0.2.3.1

History Node

0.2.3

History Node

0.2.2

History Node

0.2.1

History Node

0.2.0

History Node

0.1.2

History Node

0.1.1

History Node

0.1.0

Download Files

Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
tarjan-0.2.3.2.tar.gz (4.1 kB) Copy SHA256 Checksum SHA256 Source Dec 28, 2016

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting