# -*- coding: utf-8 -*-
"""
Algorithms for directed acyclic graphs (DAGs).
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
___revision__ = ""
# Copyright (C) 2006-2009 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__ = ['topological_sort',
'topological_sort_recursive',
'is_directed_acyclic_graph']
import networkx
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 topological_sort(G) is None:
return False
else:
return True
def topological_sort(G,nbunch=None):
"""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
Notes
-----
If G is not a directed acyclic graph (DAG) no topological sort exists
and the Python keyword None is returned.
This algorithm is based on a description and proof in
The Algorithm Design Manual [1]_ .
See also
--------
is_directed_acyclic_graph
References
----------
.. [1] Skiena, S. S. The Algorithm Design Manual (Springer-Verlag, 1998).
http://www.amazon.com/exec/obidos/ASIN/0387948600/ref=ase_thealgorithmrepo/
"""
# nonrecursive version
seen={}
order_explored=[] # provide order and
explored={} # fast search without more general priorityDictionary
if nbunch is None:
nbunch = G.nodes_iter()
for v in G: # 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
seen[w]=1 # mark as seen
# Check successors for cycles and for new nodes
new_nodes=[]
for n in G[w]:
if n not in explored:
if n in seen: return #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
explored[w]=1
order_explored.insert(0,w) # reverse order explored
fringe.pop() # done considering this node
return order_explored
def topological_sort_recursive(G,nbunch=None):
"""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
Notes
-----
If G is not a directed acyclic graph (DAG) no topological sort exists
and the Python keyword None is returned.
This is a recursive version of topological sort.
See also
--------
topological_sort
is_directed_acyclic_graph
"""
# function for recursive dfs
def _dfs(G,seen,explored,v):
seen.add(v)
for w in G[v]:
if w not in seen:
if not _dfs(G,seen,explored,w):
return
elif w in seen and w not in explored:
# cycle Found--- no topological sort
return False
explored.insert(0,v) # inverse order of when explored
return v
seen=set()
explored=[]
if nbunch is None:
nbunch = G.nodes_iter()
for v in nbunch: # process all nodes
if v not in explored:
if not _dfs(G,seen,explored,v):
return
return explored
|