Data Structures
class	Resolver

Functions
Dict[Optional[str], int]	get_topological_weights ("DirectedGraph[Optional[str]]" graph, Set[str] requirement_keys)

Tuple[int, str]	_req_set_item_sorter (Tuple[str, InstallRequirement] item, Dict[Optional[str], int] weights)

Variables
	Result = RLResult[Requirement, Candidate, str]

	logger = logging.getLogger(__name__)

Function Documentation

◆ _req_set_item_sorter()

Tuple[int, str] _req_set_item_sorter	(	Tuple[str, InstallRequirement]	item,
		Dict[Optional[str], int]	weights
	)

protected

Key function used to sort install requirements for installation.

Based on the "weight" mapping calculated in ``get_installation_order()``.
The canonical package name is returned as the second member as a tie-
breaker to ensure the result is predictable, which is useful in tests.

Definition at line 288 of file resolver.py.

) -> Tuple[int, str]:
    """Key function used to sort install requirements for installation.
 
    Based on the "weight" mapping calculated in ``get_installation_order()``.
    The canonical package name is returned as the second member as a tie-
    breaker to ensure the result is predictable, which is useful in tests.
    """
    name = canonicalize_name(item[0])
    return weights[name], name

◆ get_topological_weights()

Dict[Optional[str], int] get_topological_weights	(	"DirectedGraph[Optional[str]]"	graph,
		Set[str]	requirement_keys
	)

Assign weights to each node based on how "deep" they are.

This implementation may change at any point in the future without prior
notice.

We first simplify the dependency graph by pruning any leaves and giving them
the highest weight: a package without any dependencies should be installed
first. This is done again and again in the same way, giving ever less weight
to the newly found leaves. The loop stops when no leaves are left: all
remaining packages have at least one dependency left in the graph.

Then we continue with the remaining graph, by taking the length for the
longest path to any node from root, ignoring any paths that contain a single
node twice (i.e. cycles). This is done through a depth-first search through
the graph, while keeping track of the path to the node.

Cycles in the graph result would result in node being revisited while also
being on its own path. In this case, take no action. This helps ensure we
don't get stuck in a cycle.

When assigning weight, the longer path (i.e. larger length) is preferred.

We are only interested in the weights of packages that are in the
requirement_keys.

Definition at line 199 of file resolver.py.

) -> Dict[Optional[str], int]:
    """Assign weights to each node based on how "deep" they are.
 
    This implementation may change at any point in the future without prior
    notice.
 
    We first simplify the dependency graph by pruning any leaves and giving them
    the highest weight: a package without any dependencies should be installed
    first. This is done again and again in the same way, giving ever less weight
    to the newly found leaves. The loop stops when no leaves are left: all
    remaining packages have at least one dependency left in the graph.
 
    Then we continue with the remaining graph, by taking the length for the
    longest path to any node from root, ignoring any paths that contain a single
    node twice (i.e. cycles). This is done through a depth-first search through
    the graph, while keeping track of the path to the node.
 
    Cycles in the graph result would result in node being revisited while also
    being on its own path. In this case, take no action. This helps ensure we
    don't get stuck in a cycle.
 
    When assigning weight, the longer path (i.e. larger length) is preferred.
 
    We are only interested in the weights of packages that are in the
    requirement_keys.
    """
    path: Set[Optional[str]] = set()
    weights: Dict[Optional[str], int] = {}
 
    def visit(node: Optional[str]) -> None:
        if node in path:
            # We hit a cycle, so we'll break it here.
            return
 
        # Time to visit the children!
        path.add(node)
        for child in graph.iter_children(node):
            visit(child)
        path.remove(node)
 
        if node not in requirement_keys:
            return
 
        last_known_parent_count = weights.get(node, 0)
        weights[node] = max(last_known_parent_count, len(path))
 
    # Simplify the graph, pruning leaves that have no dependencies.
    # This is needed for large graphs (say over 200 packages) because the
    # `visit` function is exponentially slower then, taking minutes.
    # See https://github.com/pypa/pip/issues/10557
    # We will loop until we explicitly break the loop.
    while True:
        leaves = set()
        for key in graph:
            if key is None:
                continue
            for _child in graph.iter_children(key):
                # This means we have at least one child
                break
            else:
                # No child.
                leaves.add(key)
        if not leaves:
            # We are done simplifying.
            break
        # Calculate the weight for the leaves.
        weight = len(graph) - 1
        for leaf in leaves:
            if leaf not in requirement_keys:
                continue
            weights[leaf] = weight
        # Remove the leaves from the graph, making it simpler.
        for leaf in leaves:
            graph.remove(leaf)
 
    # Visit the remaining graph.
    # `None` is guaranteed to be the root node by resolvelib.
    visit(None)
 
    # Sanity check: all requirement keys should be in the weights,
    # and no other keys should be in the weights.
    difference = set(weights.keys()).difference(requirement_keys)
    assert not difference, difference
 
    return weights
 
 