Breadth-First Topological View (bfs_topo_view)

Provides a breadth-first topological ordering for all nodes reachable from the outputs of a logic network. While Mockturtle’s topo_view implements a depth-first traversal, this view constructs the node order level by level using a queue-based breadth-first search (BFS).

All constant nodes and primary inputs are included in the traversal order, even if they are not directly reachable from the outputs. Constants always precede primary inputs, and primary inputs retain their creation order. This view is immutable and should only be used on static networks—modifications to the underlying network are not reflected once the order is constructed.

Typical use cases include:

  • Building rank or level-based data structures for planarization or visualization.

  • Constructing balanced rank views (e.g., for crossing minimization).

  • Performing topological analyses in breadth-first order rather than depth-first.

Header: fiction/networks/views/bfs_topo_view.hpp

template<class Ntk, bool sorted = mockturtle::is_topologically_sorted_v<Ntk>>
class bfs_topo_view

Computes a breadth-first topological order (whereas Mockturtle’s topo_view implements a depth-first search) for all nodes reachable from the outputs of a logic network.

Overrides the methods foreach_node, foreach_gate, size, and num_gates. The topological order is computed once upon construction and remains fixed for the lifetime of the view.

All constant nodes and primary inputs are included in the traversal, even if they are not reachable from the outputs. Constant nodes precede primary inputs, and primary inputs are ordered according to their creation order.

Modifications to the network are not allowed after construction, as the order is immutable. Only reachable nodes are included in foreach_node and foreach_gate, which may exclude some network nodes.

Required network functions:

  • get_constant

  • foreach_pi

  • foreach_fanin

  • incr_trav_id

  • set_visited

  • trav_id

  • visited

Template Parameters:

  • Ntk – Logic network type.

  • sorted – Internal tag to indicate if the network is already topologically sorted (default: false).