graphAlgs.DepthFirstOrder Class Reference

Collaboration diagram for graphAlgs.DepthFirstOrder:

Public Member Functions
	__init__ (self, G, roots=[])
	pre (self)
	post (self)
	reversePost (self)
	dfs_ (self, G, v)

Public Attributes
list	marked = [False for v in range(G.V)]
list	pre_ = []
list	post_ = []
list	reversePost_ = []

Detailed Description

Carry out a depth first traversal of a graph, noting the order
nodes are processed.

Definition at line 45 of file graphAlgs.py.

Constructor & Destructor Documentation

__init__()

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

Definition at line 49 of file graphAlgs.py.

    def __init__(self, G, roots = []):
        self.marked = [False for v in range(G.V)]
        self.pre_ = []
        self.post_ = []
        self.reversePost_ = []
        
        if not roots:
            for v in range(G.V):
                if not self.marked[v]:
                    self.dfs_(G, v)
        else:
            for v in roots:
                if not self.marked[v]:
                    self.dfs_(G, v)
 
        self.reversePost_ = self.post_[:]
        self.reversePost_.reverse()
        

Member Function Documentation

dfs_()

graphAlgs.DepthFirstOrder.dfs_	(		self,
			G,
			v )

Definition at line 71 of file graphAlgs.py.

    def dfs_(self, G, v):
        self.pre_.append(v)
        self.marked[v] = True
 
        for w in G.adj(v):
            if not self.marked[w]:
                self.dfs_(G, w)
                
    
        self.post_.append(v)
    
 

post()

graphAlgs.DepthFirstOrder.post

(

self

)

Definition at line 68 of file graphAlgs.py.

    def post(self): return self.post_

pre()

graphAlgs.DepthFirstOrder.pre

(

self

)

Definition at line 67 of file graphAlgs.py.

    def pre(self): return self.pre_

reversePost()

graphAlgs.DepthFirstOrder.reversePost

(

self

)

Definition at line 69 of file graphAlgs.py.

    def reversePost(self): return self.reversePost_
 

Member Data Documentation

marked

list graphAlgs.DepthFirstOrder.marked = [False for v in range(G.V)]

Definition at line 50 of file graphAlgs.py.

post_

list graphAlgs.DepthFirstOrder.post_ = []

Definition at line 52 of file graphAlgs.py.

pre_

list graphAlgs.DepthFirstOrder.pre_ = []

Definition at line 51 of file graphAlgs.py.

reversePost_

list graphAlgs.DepthFirstOrder.reversePost_ = []

Definition at line 53 of file graphAlgs.py.

---

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

• graphAlgs.py