View GitHub Repository pyalgs

Schedule Inspection
Subscribe

DepthFirstOrder.__init__()   A
last analyzed

↳ Parent: DepthFirstOrder

Complexity

Conditions 4

Size

Total Lines 11

Duplication

Lines 0
Ratio 0 %

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 4
c 1
b 0
f 0
dl 0
loc 11
rs 9.2
1 
from pyalgs.data_structures.commons.stack import Stack
2 
from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph, DirectedEdgeWeightedGraph
3 

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    4
                

                                    
                                                    
                
                
                

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    5
                

                                    
                                                    
                
                
                
class DepthFirstOrder(object):

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    6
                

                                    
                                                    
                
                
                

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    7
                

                                    
                                                    
                
                
                
    marked = None

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    8
                

                                    
                                                    
                
                
                
    reversePostOrder = None

            


            
                                                                                                            
                                                                
            
                                    
            
            

                
                    9
                

                                    
                                                    
                
                
                

            


            
                                                                        
                            
            
                                    
            
            

                
                    10
                

                                    
                                                    
                
                
                
    def __init__(self, G):

            


            
                                                                        
                            
            
                                    
            
            

                
                    11
                

                                    
                                                    
                
                
                
        if isinstance(G, DirectedEdgeWeightedGraph):

            


            
                                                                        
                            
            
                                    
            
            

                
                    12
                

                                    
                                                    
                
                
                
            G = G.to_digraph()

            


            
                                                                        
                            
            
                                    
            
            

                
                    13
                

                                    
                                                    
                
                
                

            


            
                                                                        
                            
            
                                    
            
            

                
                    14
                

                                    
                                                    
                
                
                
        self.reversePostOrder = Stack.create()

            


            
                                                                        
                            
            
                                    
            
            

                
                    15
                

                                    
                                                    
                
                
                
        vertex_count = G.vertex_count()

            


            
                                                                        
                            
            
                                    
            
            

                
                    16
                

                                    
                                                    
                
                
                
        self.marked = [False] * vertex_count

            


            
                                                                        
                            
            
                                    
            
            

                
                    17
                

                                    
                                                    
                
                
                

            


            
                                                                        
                            
            
                                    
            
            

                
                    18
                

                                    
                                                    
                
                
                
        for v in range(vertex_count):

            


            
                                                                        
                            
            
                                    
            
            

                
                    19
                

                                    
                                                    
                
                
                
            if not self.marked[v]:

            


            
                                                                        
                            
            
                                    
            
            

                
                    20
                

                                    
                                                    
                
                
                
                self.dfs(G, v)

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    21
                

                                    
                                                    
                
                
                

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    22
                

                                    
                                                    
                
                
                
    def dfs(self, G, v):

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    23
                

                                    
                                                    
                
                
                
        self.marked[v] = True

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    24
                

                                    
                                                    
                
                
                
        for w in G.adj(v):

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    25
                

                                    
                                                    
                
                
                
            if not self.marked[w]:

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    26
                

                                    
                                                    
                
                
                
                self.dfs(G, w)

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    27
                

                                    
                                                    
                
                
                
        self.reversePostOrder.push(v)

            


            
                                                                                                            
                            
            
                                    
            
            

                
                    28
                

                                    
                                                    
                
                
                

            


            
                                                                                                            
                                                                
            
                                    
            
            

                
                    29
                

                                    
                                                    
                
                
                
    def postOrder(self):

            


            
                                                        
            
                                    
            
            

                
                    30
                

                                    
                                                    
                
                
                
        return self.reversePostOrder.iterate()