Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.dag

# -*- coding: utf-8 -*-
from fractions import gcd
import networkx as nx
from networkx.utils.decorators import *
"""Algorithms for directed acyclic graphs (DAGs)."""
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>',
'Dan Schult (dschult@colgate.edu)',
'Ben Edwards (bedwards@cs.unm.edu)'])
__all__ = ['descendants',
'ancestors',
'topological_sort',
'topological_sort_recursive',
'is_directed_acyclic_graph',
'is_aperiodic',
'transitive_closure',
'antichains',
'dag_longest_path',
'dag_longest_path_length']

[docs]def descendants(G, source):
"""Return all nodes reachable from source in G.

Parameters
----------
G : NetworkX DiGraph
source : node in G

Returns
-------
des : set()
The descendants of source in G
"""
if not G.has_node(source):
raise nx.NetworkXError("The node %s is not in the graph." % source)
des = set(nx.shortest_path_length(G, source=source).keys()) - set([source])
return des

[docs]def ancestors(G, source):
"""Return all nodes having a path to source in G.

Parameters
----------
G : NetworkX DiGraph
source : node in G

Returns
-------
ancestors : set()
The ancestors of source in G
"""
if not G.has_node(source):
raise nx.NetworkXError("The node %s is not in the graph." % source)
anc = set(nx.shortest_path_length(G, target=source).keys()) - set([source])
return anc

[docs]def is_directed_acyclic_graph(G):
"""Return True if the graph G is a directed acyclic graph (DAG) or
False if not.

Parameters
----------
G : NetworkX graph
A graph

Returns
-------
is_dag : bool
True if G is a DAG, false otherwise
"""
if not G.is_directed():
return False
try:
topological_sort(G, reverse=True)
return True
except nx.NetworkXUnfeasible:
return False

[docs]def topological_sort(G, nbunch=None, reverse=False):
"""Return a list of nodes in topological sort order.

A topological sort is a nonunique permutation of the nodes
such that an edge from u to v implies that u appears before v in the
topological sort order.

Parameters
----------
G : NetworkX digraph
A directed graph

nbunch : container of nodes (optional)
Explore graph in specified order given in nbunch

reverse : bool, optional
Return postorder instead of preorder if True.
Reverse mode is a bit more efficient.

Raises
------
NetworkXError
Topological sort is defined for directed graphs only. If the
graph G is undirected, a NetworkXError is raised.

NetworkXUnfeasible
If G is not a directed acyclic graph (DAG) no topological sort
exists and a NetworkXUnfeasible exception is raised.

Notes
-----
This algorithm is based on a description and proof in
The Algorithm Design Manual _ .

--------
is_directed_acyclic_graph

References
----------
..  Skiena, S. S. The Algorithm Design Manual  (Springer-Verlag, 1998).
http://www.amazon.com/exec/obidos/ASIN/0387948600/ref=ase_thealgorithmrepo/
"""
if not G.is_directed():
raise nx.NetworkXError(
"Topological sort not defined on undirected graphs.")

# nonrecursive version
seen = set()
order = []
explored = set()

if nbunch is None:
nbunch = G.nodes_iter()
for v in nbunch:     # process all vertices in G
if v in explored:
continue
fringe = [v]   # nodes yet to look at
while fringe:
w = fringe[-1]  # depth first search
if w in explored:  # already looked down this branch
fringe.pop()
continue
# Check successors for cycles and for new nodes
new_nodes = []
for n in G[w]:
if n not in explored:
if n in seen:  # CYCLE !!
raise nx.NetworkXUnfeasible("Graph contains a cycle.")
new_nodes.append(n)
if new_nodes:   # Add new_nodes to fringe
fringe.extend(new_nodes)
else:           # No new nodes so w is fully explored
order.append(w)
fringe.pop()    # done considering this node
if reverse:
return order
else:
return list(reversed(order))

[docs]def topological_sort_recursive(G, nbunch=None, reverse=False):
"""Return a list of nodes in topological sort order.

A topological sort is a nonunique permutation of the nodes such
that an edge from u to v implies that u appears before v in the
topological sort order.

Parameters
----------
G : NetworkX digraph

nbunch : container of nodes (optional)
Explore graph in specified order given in nbunch

reverse : bool, optional
Return postorder instead of preorder if True.
Reverse mode is a bit more efficient.

Raises
------
NetworkXError
Topological sort is defined for directed graphs only. If the
graph G is undirected, a NetworkXError is raised.

NetworkXUnfeasible
If G is not a directed acyclic graph (DAG) no topological sort
exists and a NetworkXUnfeasible exception is raised.

Notes
-----
This is a recursive version of topological sort.

--------
topological_sort
is_directed_acyclic_graph

"""
if not G.is_directed():
raise nx.NetworkXError(
"Topological sort not defined on undirected graphs.")

def _dfs(v):

for w in G[v]:
if w in ancestors:
raise nx.NetworkXUnfeasible("Graph contains a cycle.")

if w not in explored:
_dfs(w)

ancestors.remove(v)
order.append(v)

ancestors = set()
explored = set()
order = []

if nbunch is None:
nbunch = G.nodes_iter()

for v in nbunch:
if v not in explored:
_dfs(v)

if reverse:
return order
else:
return list(reversed(order))

[docs]def is_aperiodic(G):
"""Return True if G is aperiodic.

A directed graph is aperiodic if there is no integer k > 1 that
divides the length of every cycle in the graph.

Parameters
----------
G : NetworkX DiGraph
Graph

Returns
-------
aperiodic : boolean
True if the graph is aperiodic False otherwise

Raises
------
NetworkXError
If G is not directed

Notes
-----
This uses the method outlined in _, which runs in O(m) time
given m edges in G. Note that a graph is not aperiodic if it is
acyclic as every integer trivial divides length 0 cycles.

References
----------
..  Jarvis, J. P.; Shier, D. R. (1996),
Graph-theoretic analysis of finite Markov chains,
in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling:
A Multidisciplinary Approach, CRC Press.
"""
if not G.is_directed():
raise nx.NetworkXError(
"is_aperiodic not defined for undirected graphs")

s = next(G.nodes_iter())
levels = {s: 0}
this_level = [s]
g = 0
l = 1
while this_level:
next_level = []
for u in this_level:
for v in G[u]:
if v in levels:  # Non-Tree Edge
g = gcd(g, levels[u] - levels[v] + 1)
else:  # Tree Edge
next_level.append(v)
levels[v] = l
this_level = next_level
l += 1
if len(levels) == len(G):  # All nodes in tree
return g == 1
else:
return g == 1 and nx.is_aperiodic(G.subgraph(set(G) - set(levels)))

[docs]@not_implemented_for('undirected')
def transitive_closure(G):
""" Returns transitive closure of a directed graph

The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that
for all v,w in V there is an edge (v,w) in E+ if and only if there
is a non-null path from v to w in G.

Parameters
----------
G : NetworkX DiGraph
Graph

Returns
-------
TC : NetworkX DiGraph
Graph

Raises
------
NetworkXNotImplemented
If G is not directed

References
----------

"""
TC = nx.DiGraph()
for v in G:
TC.add_edges_from((v, u) for u in nx.dfs_preorder_nodes(G, source=v)
if v != u)
return TC

[docs]@not_implemented_for('undirected')
def antichains(G):
"""Generates antichains from a DAG.

An antichain is a subset of a partially ordered set such that any
two elements in the subset are incomparable.

Parameters
----------
G : NetworkX DiGraph
Graph

Returns
-------
antichain : generator object

Raises
------
NetworkXNotImplemented
If G is not directed

NetworkXUnfeasible
If G contains a cycle

Notes
-----
This function was originally developed by Peter Jipsen and Franco Saliola
for the SAGE project. It's included in NetworkX with permission from the
authors. Original SAGE code at:

https://sage.informatik.uni-goettingen.de/src/combinat/posets/hasse_diagram.py

References
----------
..  Free Lattices, by R. Freese, J. Jezek and J. B. Nation,
AMS, Vol 42, 1995, p. 226.
"""
TC = nx.transitive_closure(G)
antichains_stacks = [([], nx.topological_sort(G, reverse=True))]
while antichains_stacks:
(antichain, stack) = antichains_stacks.pop()
# Invariant:
#  - the elements of antichain are independent
#  - the elements of stack are independent from those of antichain
yield antichain
while stack:
x = stack.pop()
new_antichain = antichain + [x]
new_stack = [
t for t in stack if not ((t in TC[x]) or (x in TC[t]))]
antichains_stacks.append((new_antichain, new_stack))

[docs]@not_implemented_for('undirected')
def dag_longest_path(G):
"""Returns the longest path in a DAG

Parameters
----------
G : NetworkX DiGraph
Graph

Returns
-------
path : list
Longest path

Raises
------
NetworkXNotImplemented
If G is not directed

--------
dag_longest_path_length
"""
dist = {}  # stores [node, distance] pair
for node in nx.topological_sort(G):
# pairs of dist,node for all incoming edges
pairs = [(dist[v] + 1, v) for v in G.pred[node]]
if pairs:
dist[node] = max(pairs)
else:
dist[node] = (0, node)
node, (length, _) = max(dist.items(), key=lambda x: x)
path = []
while length > 0:
path.append(node)
length, node = dist[node]
return list(reversed(path))

[docs]@not_implemented_for('undirected')
def dag_longest_path_length(G):
"""Returns the longest path length in a DAG

Parameters
----------
G : NetworkX DiGraph
Graph

Returns
-------
path_length : int
Longest path length

Raises
------
NetworkXNotImplemented
If G is not directed