breadth_first_ordering

compas.topology.breadth_first_ordering(adjacency, root)

Return a breadth-first ordering of all vertices in an adjacency dictionary reachable from a chosen root vertex.

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

Returns

list – A breadth-first ordering of all vertices in the adjacency dict.

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.

Examples

>>>