graphAlgs.DirectedCycle Class Reference

Collaboration diagram for graphAlgs.DirectedCycle:

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

Public Attributes
list	onStack = [False for i in range(G.V)]
list	marked = [False for i in range(G.V)]
list	edgeTo = [-1 for i in range(G.V)]
list	cycle_ = []

Detailed Description

determine whether a digraph has a cycle

Definition at line 4 of file graphAlgs.py.

Constructor & Destructor Documentation

__init__()

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

graphAlgs.DirectedCycle.cycle

(

self

)

Definition at line 21 of file graphAlgs.py.

    def cycle(self):
        return self.cycle_
 

dfs_()

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

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

list graphAlgs.DirectedCycle.edgeTo = [-1 for i in range(G.V)]

Definition at line 10 of file graphAlgs.py.

marked

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

Definition at line 9 of file graphAlgs.py.

onStack

list graphAlgs.DirectedCycle.onStack = [False for i in range(G.V)]

Definition at line 8 of file graphAlgs.py.

---

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

• graphAlgs.py