def find_critical_path()

in common_components/monitoring/json_to_dot.py [0:0]

• 16 lines of code
• 7 McCabe index (conditional complexity)

def find_critical_path(nodes):
    """ Identify the critical path and mark it red

        The critical path is the set of nodes whose time,
        if shorter, would result in the entire graph being
        having shorter term.
    """

    def find_last_node(ids):
        end_time = None
        node_id = None
        for node in ids:
            if end_time is None or nodes[node]["end_time"] > end_time:
                end_time = nodes[node]["end_time"]
                node_id = node

        return node_id

    # Start with all nodes
    upstream_nodes = nodes.keys()

    while True:

        # Find the last node to finish if possible
        last_node = find_last_node(upstream_nodes)
        if last_node is None:
            break

        # Mark as critical
        nodes[last_node]['critical'] = True

        # New upstream nodes
        upstream_nodes = nodes[last_node]['depends_on']