edgegraph.traversal.breadthfirst.bft

edgegraph.traversal.breadthfirst.bft(uni, start, direction_sensitive=0, unknown_handling=2, ff_via=None, ff_result=None)

Perform a breadth-first traversal.

This function performs a breadth-first traversal within uni, starting at start, and returns the vertices visited in a list.

This algorithm is detailed in pseudocode in [CLRS09], figure 22.3, and [GoTa60], Algorithm 13.8.

Parameters:

• uni (Universe) – The universe to search in.

• start (Vertex) – The vertex to start searching at.

• direction_sensitive (int) –

  Directly passed through to neighbors(). This may be one of:

  • DIR_SENS_FORWARD (default), to follow edges only forward (when directed),

  • DIR_SENS_ANY, to follow edges regardless of their direction,

  • DIR_SENS_BACKWARD, to only follow edges backwards (when directed).

• unknown_handling (int) –

  Directly passed through to neighbors(). This may be one of:

  • LNK_UNKNOWN_ERROR (default), to throw an exception,

  • LNK_UNKNOWN_NEIGHBOR, to treat such edges as neighbors (and take the edge),

  • LNK_UNKNOWN_NONNEIGHBOR, to treat such edges as non-neighbors (do not take the edge).

• ff_via (Callable | None) –

  Directly passed through to neighbors() function’s filterfunc argument.

  edgegraph.traversal.breadthfirst.ff_via(e, v2)

  Determines 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 traversed (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.

• ff_result (Callable | None) –

  Callable used to filter the final output, after traversal has been completed.

  edgegraph.traversal.breadthfirst.ff_result(v)

  Determines if a vertex should be returned during the final output. This can be useful if you want to mask certain vertices in the result, but still traverse across them.

  Parameters:

  v – Vertex to be considered

  Returns:

  Whether or not v should be part of the output.

Returns:

The vertices visited during traversal.

Return type:

list[Vertex] | None