def critical_path(graph):
<EOL>if not len(find_cycle(graph)) == <NUM_LIT:0>:<EOL><INDENT>return []<EOL><DEDENT>node_tuples = {}<EOL>topological_nodes = topological_sorting(graph)<EOL>for node in topological_nodes: <EOL><INDENT>node_tuples.update( {node :(None, <NUM_LIT:0>)}  )<EOL><DEDENT>for node in topological_nodes:<EOL><INDENT>predecessors =[]<EOL>for pre in graph.incidents(node):<EOL><INDENT>max_pre = node_tuples[pre][<NUM_LIT:1>]<EOL>predecessors.append( (pre, graph.edge_weight( (pre, node) ) + max_pre )   )<EOL><DEDENT>max = <NUM_LIT:0>; max_tuple = (None, <NUM_LIT:0>)<EOL>for i in predecessors:<EOL><INDENT>if i[<NUM_LIT:1>] >= max:<EOL><INDENT>max = i[<NUM_LIT:1>]<EOL>max_tuple = i<EOL><DEDENT><DEDENT>node_tuples[node] = max_tuple                 <EOL><DEDENT>max = <NUM_LIT:0>; critical_node = None<EOL>for k,v in list(node_tuples.items()):<EOL><INDENT>if v[<NUM_LIT:1>] >= max:<EOL><INDENT>max= v[<NUM_LIT:1>]<EOL>critical_node = k<EOL><DEDENT><DEDENT>path = []<EOL>def mid_critical_path(end):<EOL><INDENT>if node_tuples[end][<NUM_LIT:0>] != None:<EOL><INDENT>path.append(end)<EOL>mid_critical_path(node_tuples[end][<NUM_LIT:0>])<EOL><DEDENT>else:<EOL><INDENT>path.append(end)<EOL><DEDENT><DEDENT>mid_critical_path(critical_node)<EOL>path.reverse()<EOL>return path<EOL>
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)