prefix_graph

Implements directed graphs to sort and manipulate packages within a prefix.

Object inheritance:

Classes

PrefixGraph	A directed graph structure used for sorting packages (prefix_records) in prefixes and
GeneralGraph	Compared with PrefixGraph, this class takes in more than one record of a given name,

class PrefixGraph(records, specs=())

A directed graph structure used for sorting packages (prefix_records) in prefixes and manipulating packages within prefixes (e.g. removing and pruning).

The terminology used for edge direction is "parents" and "children" rather than "successors" and "predecessors". The parent nodes of a record are those records in the graph that match the record's "depends" field. E.g. NodeA depends on NodeB, then NodeA is a child of NodeB, and NodeB is a parent of NodeA. Nodes can have zero parents, or more than two parents.

Most public methods mutate the graph.

property records

remove_spec(spec)

Remove all matching nodes, and any associated child nodes.

Parameters

spec (MatchSpec) --

Returns

The removed nodes.

Return type

tuple[PrefixRecord]

remove_youngest_descendant_nodes_with_specs()

A specialized method used to determine only dependencies of requested specs.

Returns

The removed nodes.

Return type

tuple[PrefixRecord]

prune()

Prune back all packages until all child nodes are anchored by a spec.

Returns

The pruned nodes.

Return type

tuple[PrefixRecord]

get_node_by_name(name)

all_descendants(node)

all_ancestors(node)

_remove_node(node)

Removes this node and all edges referencing it.

_toposort()

classmethod _toposort_raise_on_cycles(graph)

classmethod _topo_sort_handle_cycles(graph)

static _toposort_pop_key(graph)

Pop an item from the graph that has the fewest parents. In the case of a tie, use the node with the alphabetically-first package name.

static _toposort_prepare_graph(graph)

class GeneralGraph(records, specs=())

Bases: PrefixGraph

Compared with PrefixGraph, this class takes in more than one record of a given name, and operates on that graph from the higher view across any matching dependencies. It is not a Prefix thing, but more like a "graph of all possible candidates" thing, and is used for unsatisfiability analysis

breadth_first_search_by_name(root_spec, target_spec)

Return shorted path from root_spec to spec_name