🔍 Code Extractor

Performs stackless topological sorting on a directed acyclic graph (DAG), organizing nodes into levels based on their dependencies.

Purpose

This function takes a graph represented as a dictionary where keys are nodes and values are lists of their dependencies (children). It returns a list of lists, where each inner list contains nodes at the same dependency level. Nodes with no dependencies are at level 0, nodes depending only on level 0 nodes are at level 1, and so on. This is useful for determining execution order in dependency graphs, build systems, or task scheduling where certain operations must complete before others can begin.

Source Code

def sort_topologically(graph):
    """
    Stackless topological sorting.

    graph = {
        3: [1],
        5: [3],
        4: [2],
        6: [4],
    }

    sort_topologically(graph)
    [[1, 2], [3, 4], [5, 6]]
    """
    levels_by_name = {}
    names_by_level = defaultdict(list)

    def add_level_to_name(name, level):
        levels_by_name[name] = level
        names_by_level[level].append(name)


    def walk_depth_first(name):
        stack = [name]
        while(stack):
            name = stack.pop()
            if name in levels_by_name:
                continue

            if name not in graph or not graph[name]:
                level = 0
                add_level_to_name(name, level)
                continue

            children = graph[name]

            children_not_calculated = [child for child in children if child not in levels_by_name]
            if children_not_calculated:
                stack.append(name)
                stack.extend(children_not_calculated)
                continue

            level = 1 + max(levels_by_name[lname] for lname in children)
            add_level_to_name(name, level)

    for name in graph:
        walk_depth_first(name)

    return list(itertools.takewhile(lambda x: x is not None,
                                    (names_by_level.get(i, None)
                                     for i in itertools.count())))

Parameters

Parameter Details

graph: A dictionary representing a directed graph where each key is a node name/identifier and its value is a list of node names that are its dependencies (children/predecessors). Nodes with no dependencies can have an empty list or be omitted from the graph. Example: {3: [1], 5: [3], 4: [2], 6: [4]} means node 3 depends on node 1, node 5 depends on node 3, etc.

Return Value

Returns a list of lists, where each inner list represents a level in the topological sort. The first inner list (level 0) contains all nodes with no dependencies. Each subsequent level contains nodes whose dependencies are all satisfied by previous levels. Nodes within the same level can be processed in parallel. Example return: [[1, 2], [3, 4], [5, 6]] means nodes 1 and 2 have no dependencies, nodes 3 and 4 depend on level 0 nodes, and nodes 5 and 6 depend on level 1 nodes.

Dependencies

• itertools
• collections

Required Imports

import itertools
from collections import defaultdict

Usage Example

from collections import defaultdict
import itertools

def sort_topologically(graph):
    levels_by_name = {}
    names_by_level = defaultdict(list)

    def add_level_to_name(name, level):
        levels_by_name[name] = level
        names_by_level[level].append(name)

    def walk_depth_first(name):
        stack = [name]
        while(stack):
            name = stack.pop()
            if name in levels_by_name:
                continue
            if name not in graph or not graph[name]:
                level = 0
                add_level_to_name(name, level)
                continue
            children = graph[name]
            children_not_calculated = [child for child in children if child not in levels_by_name]
            if children_not_calculated:
                stack.append(name)
                stack.extend(children_not_calculated)
                continue
            level = 1 + max(levels_by_name[lname] for lname in children)
            add_level_to_name(name, level)

    for name in graph:
        walk_depth_first(name)

    return list(itertools.takewhile(lambda x: x is not None,
                                    (names_by_level.get(i, None)
                                     for i in itertools.count())))

# Example usage
graph = {
    3: [1],
    5: [3],
    4: [2],
    6: [4]
}

result = sort_topologically(graph)
print(result)  # Output: [[1, 2], [3, 4], [5, 6]]

Best Practices

• Ensure the input graph is a directed acyclic graph (DAG). Cycles will cause the algorithm to fail or produce incorrect results.
• The graph dictionary should map parent nodes to their child dependencies, not the other way around.
• Nodes that appear only as dependencies (children) but not as keys in the graph dictionary are treated as having no dependencies (level 0).
• The function uses a stackless depth-first approach to avoid recursion limits on large graphs.
• Nodes at the same level are independent and can be processed in parallel if needed.
• The function modifies internal state but does not modify the input graph.

Tags

Similar Components

AI-powered semantic similarity - components with related functionality:

• function layer_sort 52.8% similar

  Computes a global topological ordering of layers from a HoloMap containing CompositeOverlay objects by analyzing layer dependencies and sorting them.

  From: /tf/active/vicechatdev/patches/util.py

• function is_cyclic 50.1% similar

  Detects whether a directed graph contains a cycle using depth-first search with path tracking.

  From: /tf/active/vicechatdev/patches/util.py

• function dimension_sort 47.7% similar

  Sorts an ordered dictionary by specified dimension keys, supporting both standard Python tuple sorting and categorical ordering for dimensions with predefined values.

  From: /tf/active/vicechatdev/patches/util.py

• function group_select 42.0% similar

  Recursively groups a list of key tuples into a nested dictionary structure to optimize indexing operations by avoiding duplicate key lookups.

  From: /tf/active/vicechatdev/patches/util.py

• function layer_groups 42.0% similar

  Groups elements from an ordering list into a dictionary based on a slice of each element's specification, using the first 'length' items as the grouping key.

  From: /tf/active/vicechatdev/patches/util.py