tredge 0.0.1

Python module for finding transitive edges in a directed acyclic graph

tredge

This is tiny yet fast module to get set of explicitly defined transitive edges from a directed acyclic graph. Given a DAG with edges child<--parent represented as dictionary (keys are children, values are iterables with parents), or as iterable of iterables representing edges ((child, parent)), or file object pointing to tab-delimited file with 2 columns (child, parent), it returns set of transitive edges found there. Original intent of this package was to use it for removing redundant edges from tree structures.

Usage:

import tredge

g = {
    'b': set(['a']),
    'c': set(['a']),
    'd': set(['b', 'c', 'a']),
    'e': set(['d', 'a'])
}
result = tredge.transitive_edges(g)
print(result)

# {('d', 'a'), ('e', 'a')}

or

import tredge

g = [
    ('b', 'a'),
    ('c', 'a'),
    ('d', 'b'),
    ('d', 'c'),
    ('e', 'd'),
    ('e', 'a'),
    ('d', 'a')
]
result = tredge.transitive_edges(g)
print(result)

# {('d', 'a'), ('e', 'a')}

or

"""input_file.tab:
b	a
c	a
d	b
d	c
e	d
e	a
d	a
"""

import tredge

with open('input_file.tab', mode='r', encoding='utf8') as g:
    result = tredge.transitive_edges(g)
print(result)

# {('d', 'a'), ('e', 'a')}