portage.util.digraph module

class portage.util.digraph.digraph

Bases: object

A directed graph object.

add(node, parent, priority=0)

Adds the specified node with the specified parent.

If the dep is a soft-dep and the node already has a hard relationship to the parent, the relationship is left as hard.

addnode(node, parent, priority=0)

Adds the specified node with the specified parent.

If the dep is a soft-dep and the node already has a hard relationship to the parent, the relationship is left as hard.

all_nodes()

Return a list of all nodes in the graph

allnodes()

Return a list of all nodes in the graph

allzeros(ignore_priority=None)

Return all nodes that have no children

If ignore_soft_deps is True, soft deps are not counted as children in calculations.

bfs(start, ignore_priority=None)

child_nodes(node, ignore_priority=None)

Return all children of the specified node

clear()

Remove all nodes and edges.

clone()

contains(node)

Checks if the digraph contains mynode

copy()

debug_print()

delnode(node)

difference_update(t)

Remove all given nodes from node_set. This is more efficient than multiple calls to the remove() method.

discard(node)

Like remove(), except it doesn’t raises KeyError if the node doesn’t exist.

empty()

Checks if the digraph is empty

firstzero()

get(key, default=None)

get_cycles(ignore_priority=None, max_length=None)

Returns all cycles that have at most length ‘max_length’. If ‘max_length’ is ‘None’, all cycles are returned.

has_edge(child, parent)

Return True if the given edge exists.

hasallzeros(ignore_priority=None)

hasnode(node)

Checks if the digraph contains mynode

is_empty()

Checks if the digraph is empty

leaf_nodes(ignore_priority=None)

Return all nodes that have no children

If ignore_soft_deps is True, soft deps are not counted as children in calculations.

parent_nodes(node, ignore_priority=None)

Return all parents of the specified node

remove(node)

Removes the specified node from the digraph, also removing and ties to other nodes in the digraph. Raises KeyError if the node doesn’t exist.

remove_edge(child, parent)

Remove edge in the direction from child to parent. Note that it is possible for a remaining edge to exist in the opposite direction. Any endpoint vertices that become isolated will remain in the graph.

root_nodes(ignore_priority=None)

Return all nodes that have no parents.

If ignore_soft_deps is True, soft deps are not counted as parents in calculations.

shortest_path(start, end, ignore_priority=None)

update(other)

Add all nodes and edges from another digraph instance.