depth_first_ordering

compas.topology.depth_first_ordering(adjacency, root)

Compute depth-first ordering of connected vertices.

Parameters

• adjacency (dict) – An adjacency dictionary. Each key represents a vertex and maps to a list of neighboring vertex keys.

• root (str) – The vertex from which to start the depth-first search.

Returns

list – A depth-first ordering of all vertices in the network.

Notes

Return all nodes of a connected component containing ‘root’ of a network represented by an adjacency dictionary.

This implementation uses a to visit stack. The principle of a stack is LIFO. In Python, a list is a stack.

Initially only the root element is on the stack. While there are still elements on the stack, the node on top of the stack is ‘popped off’ and if this node was not already visited, its neighbors are added to the stack if they hadn’t already been visited themselves.

Since the last element on top of the stack is always popped off, the algorithm goes deeper and deeper in the datastructure, until it reaches a node without (unvisited) neighbors and then backtracks. Once a new node with unvisited neighbors is found, there too it will go as deep as possible before backtracking again, and so on. Once there are no more nodes on the stack, the entire structure has been traversed.

Note that this returns a depth-first spanning tree of a connected component of the network.

Examples

>>>