edgegraph.sorting.toposort.topological_ordering

edgegraph.sorting.toposort.topological_ordering#

edgegraph.sorting.toposort.topological_ordering(uni, *, direction_sensitive=0, unknown_handling=2, ff_via=None, method='kahn')#

Provide a topological ordering (sort) of a given universe’s vertices.

This function is a frontend for various implementations / algorithms for computing a topological ordering of a graph; that is, a linear ordering of a graph such that for every directed edge \((u, v)\), \(u\) comes before \(v\) in the ordered list.

Note that in many cases, multiple such ordering exist for a given graph. This function does not (currently) declare sorting stability; that is, it is only guaranteed to return a valid ordering, not necessarily the same ordering every time when called with the same arguments.

Topological sorts are not defined for graphs which contain cycles. If a graph provided here contains a cycle, GraphContainsCyclesError will be raised.

Parameters:

  • uni (Universe) – The universe whose vertices are to be ordered.

  • direction_sensitive (int) – Selector for direction-sensitivity. This is passed directly through to internal calls of neighbors(). Either forward or backward options are valid for all backends; certain backends MAY allow the ANY option, but there are typically severe restrictions in graph layout for this to work.

  • unknown_handling (int) – Selector for behavior when encountering an unknown link class. This is passed directly through to internal calls of neighbors().

  • ff_via (Callable | None) –

    Directly passed through to neighbors() function’s filterfunc argument. If not specified, the default option only requires that v2 is a member of the uni argument. If it is specified, the user-provided function is AND-gated with that same check (i.e., you cannot use this to escape the bounds of uni).

    edgegraph.sorting.toposort.ff_via(e, v2)

    Determins if an edge (e) from a given vertex to another (v2) should be followed. If not, that entire section of the graph will not be considered for ordering (assuming no other entries to that area).

    Parameters:

    • e – The edge connecting v1 to v2.

    • v2 – The vertex under consideration.

    Returns:

    Whether or not v2 should be considered a neighbor of v, when reached via e.

  • method –

    The backend algorithm to use. Options are:

    • "kahn": use Kahn’s algorithm. Worst case is approximately \(O(V+E)\), and does not use a recursive implementation.

    • "dfs": use a modified DFS algorithm. Worst case is approximately \(O(V)\), but this uses a recursive implementation.

Returns:

A list of Vertex objects, in a topological order.

Raises:

  • edgegraph.exceptions.GraphContainsCyclesError – if the graph given in uni contains cycles (cycles which are not followed, due to edge directionality, unknown-link options, or filter-function will not raise this exception).

  • ValueError – on an invalid argument. This may be delegated to individual method backends which implement different limitations.

Return type:

list[Vertex]