depth_first_ordering

compas.topology.depth_first_ordering(adjacency, root)[source]

Compute a depth-first ordering of the nodes of a graph, starting from a root node.

Parameters

• adjacency (dict[hashable, dict[hashable, None]] | dict[hashable, sequence[hashable]]) – An adjacency dictionary representing the connectivity of the graph by mapping nodes identifiers to neighbour identifiers. Examples of valid adjacency dicts are

  • {0: [1, 2, 3, 4], 1: [0], 2: [0], 3: [0], 4: [0]}

  • {0: {1: None, 2: None, 3: None, 4: None}, 1: {0: None}, 2: {0: None}, 3: {0: None}, 4: {0: None}}

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

Returns

list[hashable] – A depth-first ordering of all nodes of the graph.

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.