graphAlgs.Topological Class Reference

Collaboration diagram for graphAlgs.Topological:

Public Member Functions
	__init__ (self, G, roots=[])
	order (self)
	isDAG (self)

Public Attributes
list	marked = [False for i in range(G.V)]
list	order_ = []

Detailed Description

order the nodes of a digraph in topological (i.e. execution) order.

Definition at line 83 of file graphAlgs.py.

Constructor & Destructor Documentation

__init__()

graphAlgs.Topological.__init__	(		self,
			G,
			roots = [] )

Definition at line 86 of file graphAlgs.py.

    def __init__(self, G, roots=[]):
        self.marked = [False for i in range(G.V)]
        self.order_ = []
        cycleFinder = DirectedCycle(G)
        if not cycleFinder.has_cycle():
            dfs = DepthFirstOrder(G, roots)
 
            # if all edges were reversed, this would be
            # self.order = dfs.reversePost();
            self.order_ = dfs.post()
        

Member Function Documentation

isDAG()

graphAlgs.Topological.isDAG

(

self

)

Definition at line 100 of file graphAlgs.py.

    def isDAG(self):
        return len(self.order_) != 0

order()

graphAlgs.Topological.order

(

self

)

Definition at line 97 of file graphAlgs.py.

    def order(self):
        return self.order_
 

Member Data Documentation

marked

list graphAlgs.Topological.marked = [False for i in range(G.V)]

Definition at line 87 of file graphAlgs.py.

order_

graphAlgs.Topological.order_ = []

Definition at line 88 of file graphAlgs.py.

---

The documentation for this class was generated from the following file:

• graphAlgs.py