Views

Views can modify the implementation of a network interface by

adding interface methods that are not supported by the implementation,
changing the implementation of interface methods, and
deleting interface methods.

Views implement the network interface and can be passed like a network to an algorithm. Several views are implemented in mockturtle.

topo_view: Ensure topological order

Header: mockturtle/views/topo_view.hpp

template<class Ntk, bool sorted = is_topologically_sorted_v<Ntk>> class topo_view

Ensures topological order for of all nodes reachable from the outputs.

Overrides the interface methods foreach_node, foreach_gate, size, num_gates.

This class computes on construction a topological order of the nodes which are reachable from the outputs. Constant nodes and primary inputs will also be considered even if they are not reachable from the outputs. Further, constant nodes and primary inputs will be visited first before any gate node is visited. Constant nodes precede primary inputs, and primary inputs are visited in the same order in which they were created.

Since the topological order is computed only once when creating an instance, this view disables changes to the network interface. Also, since only reachable nodes are traversed, not all network nodes may be called in foreach_node and foreach_gate.

Required network functions:

get_constant
foreach_pi
foreach_po
foreach_fanin
incr_trav_id
set_visited
trav_id
visited

Example

// create network somehow; aig may not be in topological order
aig_network aig = ...;

// create a topological view on the network
topo_view aig_topo{aig};

// call algorithm that requires topological order
cut_enumeration( aig_topo );

depth_view: Compute levels and depth

Header: mockturtle/views/depth_view.hpp

template<class Ntk, class NodeCostFn = unit_cost<Ntk>, bool has_depth_interface = has_depth_v<Ntk> && has_level_v<Ntk> && has_update_levels_v<Ntk>> class depth_view

Implements depth and level methods for networks.

This view computes the level of each node and also the depth of the network. It implements the network interface methods level and depth. The levels are computed at construction and can be recomputed by calling the update_levels method.

It also automatically updates levels, and depth when creating nodes or creating a PO on a depth_view, however, it does not update the information, when modifying or deleting nodes, neither will the critical paths be recalculated (due to efficiency reasons). In order to recalculate levels, depth, and critical paths, one can call update_levels instead.

Required network functions:

size
get_node
visited
set_visited
foreach_fanin
foreach_po

Example

// create network somehow
aig_network aig = ...;

// create a depth view on the network
depth_view aig_depth{aig};

// print depth
std::cout << "Depth: " << aig_depth.depth() << "\n";

Subclassed by mockturtle::rank_view< Ntk, false >, mockturtle::rank_view< Ntk, true >

rank_view: Order nodes within each level

Header: mockturtle/views/rank_view.hpp

template<class Ntk, bool has_rank_interface = has_rank_position_v<Ntk> && has_at_rank_position_v<Ntk> && has_swap_v<Ntk> && has_width_v<Ntk> && has_foreach_node_in_rank_v<Ntk> && has_foreach_gate_in_rank_v<Ntk>> class rank_view

Implements rank orders for a network.

This view assigns manipulable relative orders to the nodes of each level. A sequence of nodes in the same level is called a rank. The width of a rank is thereby defined as the number of nodes in the rank. The width of the network is equal to the width of the widest rank. This view implements functions to retrieve the assigned node position within a rank (rank_position) as well as to fetch the node in a certain rank at a certain position (at_rank_position). The ranks are assigned at construction and can be manipulated by calling the swap function.

This view also automatically inserts new nodes into their respective rank (at the end), however, it does not update the information, when modifying or deleting nodes.

Required network functions:

foreach_node
get_node
num_pis
is_ci
is_constant

Example

// create network somehow
aig_network aig = ...;

// create a rank view on the network
rank_view aig_rank{aig_depth};

// print width
std::cout << "Width: " << aig_rank.width() << "\n";

mapping_view: Add mapping interface methods

Header: mockturtle/views/mapping_view.hpp

template<typename Ntk, bool StoreFunction = false, bool has_mapping_interface = implements_mapping_interface_v<Ntk, StoreFunction>> class mapping_view

Adds mapping API methods to network.

This view adds methods of the mapping API methods to a network. It always adds the functions has_mapping, is_cell_root, clear_mapping, num_cells, add_to_mapping, remove_from_mapping, and foreach_cell_fanin. If the template argument StoreFunction is set to true, it also adds functions for cell_function and set_cell_function. For the latter case, this view requires more memory to also store the cells’ truth tables.

These methods are used to represent a mapping that is annotated to a subject graph. The interface can, e.g., be used for LUT mapping or standard cell mapping. For a common terminology, we call a collection of nodes that belong to the same unit a cell, which has a single root. The mapped node is the cell root. A cell root, and therefore the cell it represents, may be assigned a function by means of a truth table.

Required network functions:

size
node_to_index

Example

// create network somehow
aig_network aig = ...;

// in order to apply mapping, wrap network in mapping view
mapping_view mapped_aig{aig};

// call LUT mapping algorithm
lut_mapping( mapped_aig );

// nodes of aig and mapped_aig are the same
aig.foreach_node( [&]( auto n ) {
  std::cout << n << " has mapping? " << mapped_aig.is_cell_root( n ) << "\n";
} );

cut_view: Network view on a single rooted cut

Header: mockturtle/views/cut_view.hpp

template<typename Ntk> class cut_view : public mockturtle::immutable_view<Ntk>

Implements an isolated view on a single cut in a network.

This view can create a network from a single cut in a largest network. This cut has a single output root and set of leaves. The view reimplements the methods size, num_pis, num_pos, foreach_pi, foreach_po, foreach_node, foreach_gate, is_pi, node_to_index, and index_to_node.

This view assumes that all nodes’ visited flags are set 0 before creating the view. The view guarantees that all the nodes in the view will have a 0 visited flag after the construction.

Required network functions:

set_visited
visited
get_node
get_constant
is_constant
make_signal

mffc_view: Network view on a (M)FFC

Header: mockturtle/views/mffc_view.hpp

template<typename Ntk> class mffc_view : public mockturtle::immutable_view<Ntk>

Implements an isolated view on the MFFC of a node.

The network is constructed from a given root node which is traversed towards the primary inputs. Nodes are collected as long they only fanout into nodes which are already among the visited nodes. Therefore the final view only has outgoing edges to nodes not in the view from the given root node or from the newly generated primary inputs.

The view reimplements the methods size, num_pis, num_pos, foreach_pi, foreach_po, foreach_node, foreach_gate, is_pi, node_to_index, and index_to_node.

The view requires that the nodes’ values contain their reference counts, i.e., they are assigned their fanout size. The values are restored by the view.

Required network functions:

get_node
decr_value
value
foreach_fanin
is_constant
node_to_index

immutable_view: Prevent network changes

Header: mockturtle/views/immutable_view.hpp

template<typename Ntk> class immutable_view : public Ntk 

Deletes all methods that can change the network.

This view deletes all methods that can change the network structure such as create_not, create_and, or create_node. This view is convenient to use as a base class for other views that make some computations based on the structure when being constructed. Then, changes to the structure invalidate these data.

Subclassed by mockturtle::cut_view< Ntk >, mockturtle::mapping_view< Ntk, StoreFunction, false >, mockturtle::mffc_view< Ntk >, mockturtle::topo_view< Ntk, false >, mockturtle::window_view< Ntk >

Public Functions

inline immutable_view(Ntk const &ntk)

Default constructor.

Constructs immutable view on another network.

fanout_view: Compute fanout

Header: mockturtle/views/fanout_view.hpp

template<typename Ntk, bool has_fanout_interface = has_foreach_fanout_v<Ntk>> class fanout_view

Implements foreach_fanout methods for networks.

This view computes the fanout of each node of the network. It implements the network interface method foreach_fanout. The fanout are computed at construction and can be recomputed by calling the update_fanout method.

Required network functions:

foreach_node
foreach_fanin

window_view: Network view on a window

Header: mockturtle/views/window_view.hpp

template<typename Ntk> class window_view : public mockturtle::immutable_view<Ntk>

Implements an isolated view on a window in a network.

This view creates a network from a window in a large network. The window is specified by three parameters: 1.) inputs are the common support of all window nodes, they do not overlap with gates (i.e., the intersection of inputs and gates is the empty set). 2.) gates are the nodes in the window, supported by the inputs (i.e., gates are in the transitive fanout of the inputs, 3.) outputs are signals (regular or complemented nodes) pointing to nodes in gates or inputs. Not all fanouts of an output node are already part of the window.

The second parameter gates has to be passed and is not automatically computed (for example in contrast to cut_view), because there are different strategies to construct a window from a support set. The outputs could be automatically computed.

The window_view implements three new API methods: 1.) belongs_to: takes a node (or a signal) and returns true if and only if the corresponding node belongs to the window 2.) foreach_internal_fanout: takes a node and invokes a predicate on all fanout nodes of the node that belong to the window 3.) foreach_external_fanout: takes a node and invokes a predicate on all fanouts of the node that do not belong to the window

binding_view: Add bindings from a technology library

Header: mockturtle/views/binding_view.hpp

template<class Ntk> class binding_view : public Ntk 

Adds bindings to a technology library and mapping API methods.

This view adds methods to create and manage a mapped network that implements gates contained in a technology library. This view is returned by the technology mapping command map. It can be used to report statistics about the network and write the network into a verilog file. It always adds the functions has_binding, remove_binding, add_binding, add_binding_with_check, get_binding, get_binding_index, get_library, compute_area, compute_worst_delay, report_stats, and report_gates_usage.

Required network functions:

size
foreach_node
foreach_fanin
is_constant
is_pi

Example

// create network somehow
aig_network aig = ...;

// read cell library in genlib format
std::vector<gate> gates;
lorina::read_genlib( "file.genlib", genlib_reader( gates ) )
tech_library tech_lib( gates );

// call technology mapping to obtain the view
binding_view<klut_network> res = map( aig, tech_lib );

// prints stats and gates usage
res.report_stats();
res.report_gates_usage();

// write the mapped network in verilog
write_verilog_with_binding( res, "file.v" );

cell_view: Add cell mappings from a technology library

Header: mockturtle/views/cell_view.hpp

template<class Ntk> class cell_view : public Ntk 

Adds cells to a technology library and mapping API methods.

This view adds methods to create and manage a mapped network that implements cells contained in a technology library. This view is returned by the technology mapping command emap. It can be used to report statistics about the network and write the network into a verilog file. It always adds the functions has_cell, remove_cell, add_cell, add_cell_with_check, get_cell, get_cell_index, get_library, compute_area, compute_worst_delay, report_stats, and report_cells_usage.

Required network functions:

size
foreach_node
foreach_fanin
is_constant
is_pi

Example

// create network somehow
aig_network aig = ...;

// read cell library in genlib format
std::vector<gate> gates;
lorina::read_genlib( "file.genlib", genlib_reader( gates ) )
tech_library tech_lib( gates );

// call technology mapping to obtain the view
cell_view<block_network> res = emap_block( aig, tech_lib );

// prints stats and cells usage
res.report_stats();
res.report_cells_usage();

names_view: Assign names to signals and outputs

Header: mockturtle/views/choice_view.hpp

template<typename Ntk, bool has_choice_interface = has_foreach_choice_v<Ntk>> class choice_view

Implements choices in network.

Overrides the interface methods substitute_node, incr_fanout_size, decr_fanout_size, fanout_size.

This class manages equivalent nodes keeping them saved as alternatives in the network. Each node belongs to an equivalence class in which a node is the class representative, by default the one with the lowest index. Equivalence classes are saved as linked lists. The _choice_repr vector associates each node to the next one in the linked list (the one closer to the representative). The representative is the tail and “points” at itself. The _choice_phase vector is used to save the polarity of each node in the class with respect to the representative. The representative uses its field to point to the head of the list.

This view is not compatible with fanout_view.

Required network functions:

get_node
size
node_to_index
index_to_node
is_complemented
make_signal

choice_view: Implements choices in networks

Header: mockturtle/views/names_view.hpp

template<class Ntk> class names_view : public Ntk 

Public Functions

inline signal create_pi(std::string const &name = {})

Creates a primary input and set its name.

Parameters:: name – Name of the created primary input

inline void create_po(signal const &s, std::string const &name = {})

Creates a primary output and set its name.

Parameters:

s – Signal that drives the created primary output
name – Name of the created primary output

template<typename StrType = const char*> inline void set_network_name(StrType name) noexcept

Sets network name.

Parameters:: name – Name of the network

inline std::string get_network_name() const noexcept

Gets network name.

Returns:: Network name

inline bool has_name(signal const &s) const

Checks if a signal has a name.

Note that complemented signals may have different names.

Parameters:: s – Signal to be checked
Returns:: Whether the signal has a name in record

inline void set_name(signal const &s, std::string const &name)

Sets the name for a signal.

Note that names are set separately for complemented signals.

Parameters:

s – Signal to be set a name
name – Name of the signal

inline std::string get_name(signal const &s) const

Gets signal name.

Note that complemented signals may have different names.

Parameters:: s – Signal to be queried
Returns:: Name of the signal

inline bool has_output_name(uint32_t index) const

Checks if a primary output has a name.

Parameters:: index – Index of the primary output to be checked
Returns:: Whether the primary output has a name in record

inline void set_output_name(uint32_t index, std::string const &name)

Sets the name for a primary output.

Note that even if two primary outputs are driven by the same signal, they may have different names.

Parameters:

index – Index of the primary output to set a name
name – Name of the primary output

inline std::string get_output_name(uint32_t index) const

Gets the name of a primary output.

Note that even if two primary outputs are driven by the same signal, they may have different names.

Parameters:: index – Index of the primary output to be queried
Returns:: Name of the primary output

dont_touch_view: Mark nodes as “don’t touch”

Header: mockturtle/views/dont_touch_view.hpp

template<class Ntk> class dont_touch_view : public Ntk 

Mark nodes as “don’t touch”.

This view adds methods to mark nodes as don’t touch. A don’t touch node will be skipped during logic optimization or mapping. It always adds the functions select_dont_touch, remove_dont_touch, is_dont_touch.

Required network functions:

size

Example

// create network somehow
klut_network klut = ...;
dont_touch_view klut_dont_touch{ klut };

// select dont touch nodes
klut_dont_touch.select_dont_touch( 20 );

// call technology mapping to map the rest of the network
binding_view<klut_network> res = emap( klut_dont_touch, tech_lib );

cnf_view: Creates a CNF while creating a network

Header: mockturtle/views/cnf_view.hpp

template<typename Ntk, bool AllowModify, bill::solvers Solver> class cnf_view : public mockturtle::detail::cnf_view_impl<cnf_view<Ntk, AllowModify, Solver>, Ntk, AllowModify, Solver>

A view to connect logic network creation to SAT solving.

When using this view to create a new network, it creates a CNF internally while nodes are added to the network. It also contains a SAT solver. The network can be solved by calling the solve method, which by default assumes that each output should compute true (an overload of the solve method can override this default behaviour and apply custom assumptions). Further, the methods model_value and pi_vmodel_alues can be used to access model values in case solving was satisfiable. Finally, methods var and lit can be used to access variable and literal information for nodes and signals, respectively, in order to add custom clauses with the add_clause methods.

The cnf_view can also be wrapped around an existing network by setting the AllowModify template parameter to true. Then it also updates the CNF when nodes are deleted or modified. This comes with an addition cost in variable and clause size.

Public Functions

inline bill::lit_type lit(node const &n) const: Returns the literal associated to a node.

template<typename _Ntk = Ntk, typename = std::enable_if_t<!std::is_same_v<typename _Ntk::signal, typename _Ntk::node>>> inline bill::lit_type lit(signal const &f) const: Returns the literal associated to a signal.

inline std::optional<bool> solve(bill::result::clause_type const &assumptions, uint32_t limit = 0)

Solves the network with a set of custom assumptions.

This function does not assert any primary output, unless specified explicitly through the assumptions.

The function returns nullopt, if no solution can be found (due to a conflict limit), or true in case of SAT, and false in case of UNSAT.

Parameters:

assumptions – Vector of literals to be assumped when solving
limit – Conflict limit (unlimited if 0)

inline std::optional<bool> solve(int limit = 0)

Solves the network by asserting all primary outputs to be true.

The function returns nullopt, if no solution can be found (due to a conflict limit), or true in case of SAT, and false in case of UNSAT.

Parameters:: limit – Conflict limit (unlimited if 0)

inline bool model_value(node const &n) const: Return model value for a node.

template<typename _Ntk = Ntk, typename = std::enable_if_t<!std::is_same_v<typename _Ntk::signal, typename _Ntk::node>>> inline bool model_value(signal const &f) const: Return model value for a node (takes complementation into account).

inline void block(): Blocks last model for primary input values.

inline uint32_t num_vars() const: Number of variables.

inline uint32_t num_clauses() const: Number of clauses.

inline void add_clause(bill::result::clause_type const &clause): Adds a clause to the solver.

inline void add_clause(std::vector<signal> const &clause): Adds a clause from signals to the solver.

template<typename ...Lit, typename = std::enable_if_t<std::disjunction_v<std::conjunction<std::is_same<Lit, bill::lit_type>...>, std::conjunction<std::is_same<Lit, signal>...>>>> inline void add_clause(Lit... lits)

Adds a clause to the solver.

Entries are either all literals or network signals.

color_view: Manages traversal IDs

Header: mockturtle/views/color_view.hpp

template<typename Ntk> class color_view : public Ntk 

Manager view for traversal IDs (in-place storage).

Traversal IDs, called colors, are unsigned integers that can be assigned to nodes. The corresponding values are stored in-place in the flags of the underlying of the network.

Public Functions

inline uint32_t new_color() const: Returns a new color and increases the current color.

inline uint32_t current_color() const: Returns the current color.

inline void clear_colors(uint32_t color = 0) const: Assigns all nodes to color

inline auto color(node const &n) const: Returns the color of a node.

template<typename _Ntk = Ntk, typename = std::enable_if_t<!std::is_same_v<typename _Ntk::signal, typename _Ntk::node>>> inline auto color(signal const &n) const: Returns the color of a node.

inline void paint(node const &n) const: Assigns the current color to a node.

inline void paint(node const &n, uint32_t color) const: Assigns color to a node.

inline void paint(node const &n, node const &other) const: Copies the color from other to n

template<typename Pred> inline bool eval_color(node const &n, Pred &&pred) const: Evaluates a predicate on the color of a node.

template<typename Pred> inline bool eval_color(node const &a, node const &b, Pred &&pred) const: Evaluates a predicate on the colors of two nodes.

template<typename Pred> inline bool eval_fanins_color(node const &n, Pred &&pred) const: Evaluates a predicate on the colors of the fanins of a node.

template<typename Ntk> class out_of_place_color_view : public Ntk 

Manager view for traversal IDs (out-of-place storage).

Traversal IDs, called colors, are unsigned integers that can be assigned to nodes. The corresponding values are stored out-of-place in this view.

Public Functions

template<typename Pred> inline bool eval_color(node const &n, Pred &&pred) const: Evaluates a predicate on the color of a node.

template<typename Pred> inline bool eval_color(node const &a, node const &b, Pred &&pred) const: Evaluates a predicate on the colors of two nodes.

template<typename Pred> inline bool eval_fanins_color(node const &n, Pred &&pred) const: Evaluates a predicate on the colors of the fanins of a node.

cost_view: Manages global cost and maintains context

Header: mockturtle/views/cost_view.hpp

template<class Ntk, class RecCostFn> class cost_view : public Ntk 

Implements get_cost methods for networks.

This view computes the cost of the entire network, a subnetwork, and also fanin cone of a single node. It maintains the context of each node, which is the aggregated variables that affect the cost a node.

Required network functions:

size
get_node
visited
set_visited
foreach_fanin
foreach_po

Example

// create network somehow
xag_network xag = ...;

// create a cost view on the network, for example size cost
auto viewed = cost_view( xag, xag_size_cost_function<xag_network>() );

// print size
std::cout << "size: " << viewed.get_cost() << "\n";

Public Functions

inline context_t get_context(node const &n) const: Returns the context of node n.

inline void set_context(node const &n, context_t cost_val): Assigns the context of node n.

inline uint32_t get_cost() const: Returns the cost of the entire network.

inline uint32_t get_cost(node const &n): Returns the cost of node n’s fanin cone.

inline uint32_t get_cost(node const &n, std::vector<signal> const &divs): Returns the cost between node n and divs.

inline void update_cost(): Updates the context and cost of the entire network.

inline signal create_pi(context_t pi_cotext): Creates a PI with context assigned.

dont_care_view: Manages external don’t care information

Header: mockturtle/views/dont_care_view.hpp

template<class Ntk, bool hasEXCDC = true, bool hasEXODC = true> class dont_care_view

A view holding external don’t care information of a network.

This view helps storing and managing external don’t care information. There are two types of external don’t cares that may be given together or independently:

External controllability don’t cares (EXCDCs) are primary input patterns that will never happen or can be ignored. They are given as another network cdc_ntk having the same number of PIs as the main network and one PO. An input assignment making cdc_ntk output 1 is an EXCDC.

External observability don’t cares (EXODCs) are conditions for one or more primary outputs under which their values can be altered. EXODCs may be given for a PO as value combinations of other POs (for example, “the second PO is don’t care whenever the first PO is 1”). They may also be given as pairs of observably equivalent PO values (for example, “the output values 01 and 10 are considered equivalent and interchangable”).

By wrapping a network with this view and giving some external don’t care conditions, some algorithms supporting the consideration of external don’t cares can make use of them. Currently, only sim_resubstitution (which makes use of circuit_validator) and equivalence_checking_bill support external don’t cares.

Template Parameters:

hasEXCDC – Enables interfaces and data structure holding external controllability don’t cares (external don’t cares at the primary inputs)
hasEXODC – Enables interfaces and data structure holding external observability don’t cares (external dont cares at the primary outputs)