graphAlgs.DepthFirstOrder Class Reference

Collaboration diagram for graphAlgs.DepthFirstOrder:

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

Public Attributes
	marked
	pre_
	post_
	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__()

def 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_()

def 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()

def graphAlgs.DepthFirstOrder.post

(

self

)

Definition at line 68 of file graphAlgs.py.

    def post(self): return self.post_

pre()

def graphAlgs.DepthFirstOrder.pre

(

self

)

Definition at line 67 of file graphAlgs.py.

    def pre(self): return self.pre_

reversePost()

def graphAlgs.DepthFirstOrder.reversePost

(

self

)

Definition at line 69 of file graphAlgs.py.

    def reversePost(self): return self.reversePost_
 

Member Data Documentation

marked

graphAlgs.DepthFirstOrder.marked

Definition at line 50 of file graphAlgs.py.

post_

graphAlgs.DepthFirstOrder.post_

Definition at line 52 of file graphAlgs.py.

pre_

graphAlgs.DepthFirstOrder.pre_

Definition at line 51 of file graphAlgs.py.

reversePost_

graphAlgs.DepthFirstOrder.reversePost_

Definition at line 53 of file graphAlgs.py.

---

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

• graphAlgs.py