graphAlgs.DirectedCycle Class Reference

Collaboration diagram for graphAlgs.DirectedCycle:

Public Member Functions
def	__init__ (self, G)
def	has_cycle (self)
def	cycle (self)
def	dfs_ (self, G, v)

Public Attributes
	onStack
	marked
	edgeTo
	cycle_

Detailed Description

determine whether a digraph has a cycle

Definition at line 4 of file graphAlgs.py.

Constructor & Destructor Documentation

__init__()

def graphAlgs.DirectedCycle.__init__	(		self,
			G
	)

Definition at line 7 of file graphAlgs.py.

    def __init__(self, G):
        self.onStack = [False for i in range(G.V)]
        self.marked = [False for i in range(G.V)]
        self.edgeTo = [-1 for i in range(G.V)]
        self.cycle_ = []
        
        GV = G.V
        for v in range(GV):
            if not self.marked[v]:
                self.dfs_(G, v)
 

Member Function Documentation

cycle()

def graphAlgs.DirectedCycle.cycle

(

self

)

Definition at line 21 of file graphAlgs.py.

    def cycle(self):
        return self.cycle_
 

dfs_()

def graphAlgs.DirectedCycle.dfs_	(		self,
			G,
			v
	)

Definition at line 24 of file graphAlgs.py.

    def dfs_(self, G, v):
        self.onStack[v] = True
        self.marked[v] = True
 
        for w in G.adj(v):
            if self.cycle_: return
            if not self.marked[w]:
                self.edgeTo[w] = w
                self.dfs_(G, w)
            elif self.onStack[w]:
                x = v
                while x != w:
                    self.cycle_.append(x)
                    x = self.edgeTo(x)
                self.cycle_.append(w)
                self.cycle_.append(v)
 
        self.onStack[v] = False
                
        
 

has_cycle()

def graphAlgs.DirectedCycle.has_cycle

(

self

)

Definition at line 18 of file graphAlgs.py.

    def has_cycle(self):
        return len(self.cycle_) > 0
 

Member Data Documentation

cycle_

graphAlgs.DirectedCycle.cycle_

Definition at line 11 of file graphAlgs.py.

edgeTo

graphAlgs.DirectedCycle.edgeTo

Definition at line 10 of file graphAlgs.py.

marked

graphAlgs.DirectedCycle.marked

Definition at line 9 of file graphAlgs.py.

onStack

graphAlgs.DirectedCycle.onStack

Definition at line 8 of file graphAlgs.py.

---

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

• graphAlgs.py