breadth_first_ordering

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

Compute a breadth-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 breadth-first search.

Returns

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

Notes

This implementation uses a double-ended queue (deque) to keep track of nodes to visit. The principle of a queue is FIFO. In Python, a deque is ideal for removing elements from the beginning, i.e. from the ‘left’.

In a breadth-first search, all unvisited neighbors of a node are visited first. When a neighbor is visited, its univisited neighbors are added to the list of nodes to visit.

By appending the neighbors to the end of the list of nodes to visit, and by visiting the nodes at the start of the list first, the network is traversed in breadth-first order.