(graph)
return path
Compute and return the critical path in an acyclic directed weighted graph.
    
    @attention: This function is only meaningful for directed weighted acyclic graphs
    
    @type graph: digraph 
    @param graph: Digraph
    
    @rtype: List
    @return: List containing all the nodes in the path (or an empty array if the graph
        contains a cycle)
Compute and return the critical path in an acyclic directed weighted graph.
Compute and return the critical path in an acyclic directed weighted graph .
def critical_path(graph):
    """
    Compute and return the critical path in an acyclic directed weighted graph.
    
    @attention: This function is only meaningful for directed weighted acyclic graphs
    
    @type graph: digraph 
    @param graph: Digraph
    
    @rtype: List
    @return: List containing all the nodes in the path (or an empty array if the graph
        contains a cycle)
    """
    #if the graph contains a cycle we return an empty array
    if not len(find_cycle(graph)) == 0:
        return []
    
    #this empty dictionary will contain a tuple for every single node
    #the tuple contains the information about the most costly predecessor 
    #of the given node and the cost of the path to this node
    #(predecessor, cost)
    node_tuples = {}
        
    topological_nodes = topological_sorting(graph)
    
    #all the tuples must be set to a default value for every node in the graph
    for node in topological_nodes: 
        node_tuples.update( {node :(None, 0)}  )
    
    #run trough all the nodes in a topological order
    for node in topological_nodes:
        predecessors =[]
        #we must check all the predecessors
        for pre in graph.incidents(node):
            max_pre = node_tuples[pre][1]
            predecessors.append( (pre, graph.edge_weight( (pre, node) ) + max_pre )   )
        
        max = 0; max_tuple = (None, 0)
        for i in predecessors:#look for the most costly predecessor
            if i[1] >= max:
                max = i[1]
                max_tuple = i
        #assign the maximum value to the given node in the node_tuples dictionary
        node_tuples[node] = max_tuple                 
    
    #find the critical node
    max = 0; critical_node = None
    for k,v in list(node_tuples.items()):
        if v[1] >= max:
            max= v[1]
            critical_node = k
            
    
    path = []
    #find the critical path with backtracking trought the dictionary
    def mid_critical_path(end):
        if node_tuples[end][0] != None:
            path.append(end)
            mid_critical_path(node_tuples[end][0])
        else:
            path.append(end)
    #call the recursive function
    mid_critical_path(critical_node)
    
    path.reverse()
    return path
def critical_path ( graph ) : #if the graph contains a cycle we return an empty array if not len ( find_cycle ( graph ) ) == 0 : return [ ] #this empty dictionary will contain a tuple for every single node #the tuple contains the information about the most costly predecessor  #of the given node and the cost of the path to this node #(predecessor, cost) node_tuples = { } topological_nodes = topological_sorting ( graph ) #all the tuples must be set to a default value for every node in the graph for node in topological_nodes : node_tuples . update ( { node : ( None , 0 ) } ) #run trough all the nodes in a topological order for node in topological_nodes : predecessors = [ ] #we must check all the predecessors for pre in graph . incidents ( node ) : max_pre = node_tuples [ pre ] [ 1 ] predecessors . append ( ( pre , graph . edge_weight ( ( pre , node ) ) + max_pre ) ) max = 0 max_tuple = ( None , 0 ) for i in predecessors : #look for the most costly predecessor if i [ 1 ] >= max : max = i [ 1 ] max_tuple = i #assign the maximum value to the given node in the node_tuples dictionary node_tuples [ node ] = max_tuple #find the critical node max = 0 critical_node = None for k , v in list ( node_tuples . items ( ) ) : if v [ 1 ] >= max : max = v [ 1 ] critical_node = k path = [ ] #find the critical path with backtracking trought the dictionary def mid_critical_path ( end ) : if node_tuples [ end ] [ 0 ] != None : path . append ( end ) mid_critical_path ( node_tuples [ end ] [ 0 ] ) else : path . append ( end ) #call the recursive function mid_critical_path ( critical_node ) path . reverse ( ) return path