Network interface API

This page describes the common interfaces of a logic network data structure in mockturtle. Besides those listed below, more interfaces may be extended to a network by wrapping the network with views (see Views).

Warning

This part of the documentation makes use of a class called network. This class has been created solely for the purpose of creating this documentation and is not meant to be used in code. Custom network implementation do not have to derive from this class, but only need to ensure that, if they implement a function of the interface, it is implemented using the same signature.

Mandatory types and constants

The interaction with a logic network data structure is performed using four types for which no application details are assumed. The following four types must be defined within the network data structure. They can be implemented as nested types, or be exposed as type aliases.

class network

Public Types

using base_type = network

Type referring to itself.

The base_type is the network type itself. It is required, because views may extend networks, and this type provides a way to determine the underlying network type.

struct node

Type representing a node.

A node is a node in the logic network. It could be a constant, a primary input or a logic gate.

struct signal

Type representing a signal.

A signal can be seen as a pointer to a node, or an outgoing edge of a node towards its fanout. Depending on the kind of logic network, it may carry additional information such as a complement attribute.

struct storage

Type representing the storage.

A storage is some container that can contain all data necessary to store the logic network. It can be constructed outside of the logic network and passed as a reference to the constructor. It may be shared among several logic networks. A std::shared_ptr<T> is a convenient data structure to hold a storage in a logic network.

Further, a network must expose the following compile-time constants:

static constexpr uint32_t min_fanin_size;
static constexpr uint32_t max_fanin_size;

The struct is_network_type can be used to check at compile time whether a given type contains all required types and constants to implement a network type. It should be used in the beginning of an algorithm that expects a network type:

template<typename Ntk>
void algorithm( Ntk const& ntk )
{
  static_assert( is_network_type_v<Ntk>, "Ntk is not a network type" );
}

Constructors and copy assignment

class network

Public Functions

network()

Default constructor.

Constructs an empty network.

explicit network(storage s): Constructor taking a storage.

network &operator=(const network &other) = default

Default copy assignment operator.

Currently, most network implementations in mockturtle use std::shared_ptr<storage> to hold and share the storage. Thus, the default behavior of copy-assigning a network only copies the pointer, but not really duplicating the contents in the storage data structure. In other words, it makes a shallow copy by default.

Methods

The remainder lists methods that may be implemented by a network data structure. Algorithms can check whether a method method is implemented using the has_method struct. As an example to check whether the method get_constant is implemented, one of the following two static assertions can be added to the beginning of an algorithm:

// variant 1
static_assert( has_get_constant<Ntk>::value, "Ntk does not implement the get_constant method" );

// variant 2
static_assert( has_get_constant_v<Ntk>, "Ntk does not implement the get_constant method" );

Duplicate network

class network

Public Functions

network clone()

Explicitly duplicate a network.

Deep copy a network by duplicating the storage. Note that this method does not duplicate the network events.

Primary I/O and constants

class network

Public Functions

signal get_constant(bool value) const

Gets constant value represented by network.

A constant node is the only node that must be created when initializing the network. For this reason, this method has constant access and is not called create_constant.

Parameters:: value – Constant value

signal create_pi()

Creates a primary input in the network.

Each created primary input is stored in a node and contributes to the size of the network.

void create_po(signal const &s)

Creates a primary output in the network.

A primary output is not stored in terms of a node, and it also does not contribute to the size of the network. A primary output is created for a signal in the network and it is possible that multiple primary outputs point to the same signal.

Parameters:: s – Signal that drives the created primary output

bool is_constant(node const &n) const: Checks whether a node is a constant node.

bool is_pi(node const &n) const: Checks whether a node is a primary input.

bool is_ci(node const &n) const

Checks whether a node is a combinational input.

This method should be effectively the same as is_pi in a combinational network.

bool constant_value(node const &n) const

Gets the Boolean value of the constant node.

The method expects that n is a constant node.

Create unary functions

class network

Public Functions

signal create_buf(signal const &f)

Creates signal that computes f.

This method is not required to create a gate in the network. A network implementation can also just return f.

Parameters:: f – Child signal

signal create_not(signal const &f)

Creates a signal that inverts f.

This method is not required to create a gate in the network. If a network supports complemented attributes on signals, it can just return the complemented signal f.

Parameters:: f – Child signal

Create binary functions

class network

Public Functions

signal create_and(signal const &f, signal const &g): Creates a signal that computes the binary AND.

signal create_nand(signal const &f, signal const &g): Creates a signal that computes the binary NAND.

signal create_or(signal const &f, signal const &g): Creates a signal that computes the binary OR.

signal create_nor(signal const &f, signal const &g): Creates a signal that computes the binary NOR.

signal create_lt(signal const &f, signal const &g)

Creates a signal that computes the binary less-than.

The signal is true if and only if f is 0 and g is 1.

signal create_le(signal const &f, signal const &g)

Creates a signal that computes the binary less-than-or-equal.

The signal is true if and only if f is 0 or g is 1.

signal create_gt(signal const &f, signal const &g)

Creates a signal that computes the binary greater-than.

The signal is true if and only if f is 1 and g is 0.

signal create_ge(signal const &f, signal const &g)

Creates a signal that computes the binary greater-than-or-equal.

The signal is true if and only if f is 1 or g is 0.

signal create_xor(signal const &f, signal const &g): Creates a signal that computes the binary XOR.

signal create_xnor(signal const &f, signal const &g): Creates a signal that computes the binary XNOR.

Create ternary functions

class network

Public Functions

signal create_maj(signal const &f, signal const &g, signal const &h): Creates a signal that computes the majority-of-3.

signal create_ite(signal const &cond, signal const &f_then, signal const &f_else)

Creates a signal that computes the if-then-else operation.

Parameters:

cond – Condition for ITE operator
f_then – Then-case for ITE operator
f_else – Else-case for ITE operator

signal create_xor3(signal const &a, signal const &b, signal const &c): Creates a signal that computes the ternary XOR operation.

Create nary functions

class network

Public Functions

signal create_nary_and(std::vector<signal> const &fs)

Creates a signal that computes the n-ary AND.

If fs is empty, it returns constant-1.

signal create_nary_or(std::vector<signal> const &fs)

Creates a signal that computes the n-ary OR.

If fs is empty, it returns constant-0.

signal create_nary_xor(std::vector<signal> const &fs)

Creates a signal that computes the n-ary XOR.

If fs is empty, it returns constant-0.

Create arbitrary functions

class network

Public Functions

signal create_node(std::vector<signal> const &fanin, kitty::dynamic_truth_table const &function)

Creates node with arbitrary function.

The number of variables in function must match the number of fanin signals in fanin. fanin[0] will correspond to the least-significant variable in function.

Parameters:

fanin – Fan-in signals
function – Truth table for node function

signal clone_node(network const &other, node const &source, std::vector<signal> const &fanin)

Clones a node from another network of same type.

This method can clone a node from a different network other, which is from the same type. The node source is a node in the source network other, but the signals in fanin refer to signals in the target network, which are assumed to be in the same order as in the source network.

Parameters:

other – Other network of same type
source – Node in other
children – Fan-in signals from the current network

Returns:

New signal representing node in current network

Restructuring

class network

Public Functions

void substitute_node(node const &old_node, signal const &new_signal)

Replaces one node in a network by another signal.

This method causes all nodes that have old_node as fanin to have new_signal as fanin instead. In doing so, a possible polarity of new_signal is taken into account. Afterwards, the fan-out count of old_node is guaranteed to be 0.

It does not update custom values or visited flags of a node.

Parameters:

old_node – Node to replace
new_signal – Signal to replace old_node with

void substitute_nodes(std::list<std::pair<node, signal>> substitutions)

Perform multiple node-signal replacements in a network.

This method replaces all occurrences of a node with a signal for all pairs (node, signal) in the substitution list.

Parameters:: substitutions – A list of (node, signal) replacement pairs

std::optional<std::pair<node, signal>> replace_in_node(node const &n, node const &old_node, signal new_signal)

Replaces a child node by a new signal in a node.

If n has a child pointing to old_node, then it will be replaced by new_signal. If the replacement catches a trivial case, e.g., n becomes a constant, then this will be returned as an optional replacement candidate by the function.

The function updates the hash table. If no trivial case was found, it updates the hash table according to the new structure of n.

Parameters:

n – Node which may have old_node as a child
old_node – Child to be replaced
new_signal – Signel to replace old_node with

Returns:

May return new recursive replacement candidate

void replace_in_outputs(node const &old_node, signal const &new_signal)

Replaces a output driver by a new signal.

If old_node is drive to some output, then it will be replaced by new_signal.

Parameters:

old_node – Driver to be replaced
new_signal – Signal replace old_node with

void take_out_node(node const &n)

Removes a node (and potentially its fanins) from the hash table.

The node will be marked dead. This status can be checked with is_dead. Taking out a node does not change the indexes of other nodes. The node will be removed from the hash table. The reference counters of all fanin will be decremented and take_out_node will be recursively invoked on all fanins if their fanout count reach 0.

Parameters:: n – Node to be removed

bool is_dead(node const &n) const

Check if a node is dead.

A dead node is no longer visited in the foreach_node and foreach_gate methods. It still contributes to the overall size of the network, but num_gates does not take dead nodes into account.

Parameters:: n – Node to check
Returns:: Whether n is dead

Structural properties

class network

Public Functions

bool is_combinational() const: Checks whether the network is combinational.

uint32_t size() const: Returns the number of nodes (incl. constants and PIs and dead nodes).

uint32_t num_pis() const: Returns the number of primary inputs.

uint32_t num_pos() const: Returns the number of primary outputs.

uint32_t num_cis() const

Returns the number of combinational inputs.

This method should be effectively the same as num_pis` in a combinational network.

uint32_t num_cos() const

Returns the number of combinational outputs.

This method should be effectively the same as num_pos` in a combinational network.

uint32_t num_gates() const: Returns the number of gates (without dead nodes)

uint32_t fanin_size(node const &n) const: Returns the fanin size of a node.

uint32_t fanout_size(node const &n) const: Returns the fanout size of a node.

uint32_t incr_fanout_size(node const &n) const

Increments fanout size and returns old value.

This is useful for ref-counting based algorithm. The user of this function should make sure to bring the value back to a consistent state.

uint32_t decr_fanout_size(node const &n) const

Decrements fanout size and returns new value.

This is useful for ref-counting based algorithm. The user of this function should make sure to bring the value back to a consistent state.

uint32_t depth() const

Returns the length of the critical path.

For efficiency reasons, this interface is often not provided in the network implementations, but has to be extended by wrapping with depth_view.

uint32_t level(node const &n) const

Returns the level of a node.

For efficiency reasons, this interface is often not provided in the network implementations, but has to be extended by wrapping with depth_view.

bool is_and(node const &n) const: Returns true if node is a 2-input AND gate.

bool is_or(node const &n) const: Returns true if node is a 2-input OR gate.

bool is_xor(node const &n) const: Returns true if node is a 2-input XOR gate.

bool is_maj(node const &n) const: Returns true if node is a majority-of-3 gate.

bool is_ite(node const &n) const: Returns true if node is a if-then-else gate.

bool is_xor3(node const &n) const: Returns true if node is a 3-input XOR gate.

bool is_nary_and(node const &n) const: Returns true if node is a primitive n-ary AND gate.

bool is_nary_or(node const &n) const: Returns true if node is a primitive n-ary OR gate.

bool is_nary_xor(node const &n) const: Returns true if node is a primitive n-ary XOR gate.

bool is_function(node const &n) const: Returns true if node is a general function node.

Functional properties

class network

Public Functions

kitty::dynamic_truth_table node_function(node const &n) const

Returns the gate function of a node.

Note that this function returns the gate function represented by a node in terms of the intended gate. For example, in an AIG, all gate functions are AND, complemented edges are not taken into account. Also, in an MIG, all gate functions are MAJ, independently of complemented edges and possible constant inputs.

In order to retrieve a function with respect to complemented edges one can use the compute function with a truth table as simulation value.

Nodes and signals

class network

Public Functions

node get_node(signal const &f) const: Get the node a signal is pointing to.

signal make_signal(node const &n) const: Create a signal from a node (without edge attributes).

bool is_complemented(signal const &f) const

Check whether a signal is complemented.

This method may also be provided by network implementations that do not have complemented edges. In this case, the method simply returns false for each node.

uint32_t node_to_index(node const &n) const

Returns the index of a node.

The index of a node must be a unique for each node and must be between 0 (inclusive) and the size of a network (exclusive, value returned by size()).

node index_to_node(uint32_t index) const

Returns the node for an index.

This is the inverse function to node_to_index.

Parameters:: index – A value between 0 (inclusive) and the size of the network (exclusive)

node pi_at(uint32_t index) const

Returns the primary input node for an index.

Parameters:: index – A value between 0 (inclusive) and the number of primary inputs (exclusive).

signal po_at(uint32_t index) const

Returns the primary output signal for an index.

Parameters:: index – A value between 0 (inclusive) and the number of primary outputs (exclusive).

node ci_at(uint32_t index) const

Returns the combinational input node for an index.

Parameters:: index – A value between 0 (inclusive) and the number of combinational inputs (exclusive).

signal co_at(uint32_t index) const

Returns the combinational output signal for an index.

Parameters:: index – A value between 0 (inclusive) and the number of combinational outputs (exclusive).

uint32_t pi_index(node const &n) const

Returns the index of a primary input node.

Parameters:: n – A primary input node.
Returns:: A value between 0 and num_pis()-1.

uint32_t po_index(signal const &n) const

Returns the index of a primary output signal.

Parameters:: n – A primary output signal.
Returns:: A value between 0 and num_pos()-1.

uint32_t ci_index(node const &n) const

Returns the index of a combinational input node.

Parameters:: n – A combinational input node.
Returns:: A value between 0 and num_cis()-1.

uint32_t co_index(signal const &n) const

Returns the index of a combinational output signal.

Parameters:: n – A combinational output signal.
Returns:: A value between 0 and num_cos()-1.

Node and signal iterators

class network

Public Functions

template<typename Fn> void foreach_node(Fn &&fn) const

Calls fn on every node in network.

The order of nodes depends on the implementation and must not guarantee topological order. The parameter fn is any callable that must have one of the following four signatures.

void(node const&)
void(node const&, uint32_t)
bool(node const&)
bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn> void foreach_gate(Fn &&fn) const

Calls fn on every gate node in the network.

Calls each node that is not constant and not a combinational input. The parameter fn is any callable that must have one of the following four signatures.

void(node const&)
void(node const&, uint32_t)
bool(node const&)
bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn> void foreach_pi(Fn &&fn) const

Calls fn on every primary input node in the network.

The order is in the same order as primary inputs have been created with create_pi. The parameter fn is any callable that must have one of the following four signatures.

void(node const&)
void(node const&, uint32_t)
bool(node const&)
bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn> void foreach_po(Fn &&fn) const

Calls fn on every primary output signal in the network.

The order is in the same order as primary outputs have been created with create_po. The function is called on the signal that is driving the output and may occur more than once in the iteration, if it drives more than one output. The parameter fn is any callable that must have one of the following four signatures.

void(signal const&)
void(signal const&, uint32_t)
bool(signal const&)
bool(signal const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn> void foreach_ci(Fn &&fn) const

Calls fn on every combinational input node in the network.

This method should be effectively the same as foreach_pi in a combinational network.

template<typename Fn> void foreach_co(Fn &&fn) const

Calls fn on every combinational output signal in the network.

This method should be effectively the same as foreach_po in a combinational network.

template<typename Fn> void foreach_fanin(node const &n, Fn &&fn) const

Calls fn on every fanin of a node.

The order of the fanins is in the same order that was used to create the node. The parameter fn is any callable that must have one of the following four signatures.

void(signal const&)
void(signal const&, uint32_t)
bool(signal const&)
bool(signal const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn> void foreach_fanout(node const &n, Fn &&fn) const

Calls fn on every fanout of a node.

The method gives no guarantee on the order of the fanout. The parameter fn is any callable that must have one of the following signatures.

void(node const&)
void(node const&, uint32_t)
bool(node const&)
bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

For efficiency reasons, this interface is often not provided in the network implementations, but has to be extended by wrapping with fanout_view.

Simulate values

class network

Public Functions

template<typename Iterator> iterates_over_t<Iterator, T> compute(node const &n, Iterator begin, Iterator end) const

Simulates arbitrary value on a node.

This is a generic simulation method that can be implemented multiple times for a network interface for different types. One only needs to change the implementation and change the value for the type parameter T, which indicates the element type of the iterators.

Examples for simulation types are bool, kitty::dynamic_truth_table, bit masks, or BDDs.

The begin and end iterator point to values which are assumed to be assigned to the fanin of the node. Consequently, the distance from begin to end must equal the fanin size of the node.

Parameters:

n – Node to simulate (used to retrieve the node function)
begin – Begin iterator to simulation values of fanin
end – End iterator to simulation values of fanin

Returns:

Returns computed simulation value of type T

Custom node values

Each node can be assigned a value, which is a 32-bit unsigned integer. The default value is 0. Note that all value-functions are constant, because a change to the values is considered transparent to the network. If a caller passes a constant network to an algorithm, the algorithm may change the values but cannot change the structure of the network or any other visible property.

Warning

Values are meant to use internally in the implementation of an algorithm. Users of these utility function should make sure not to call other algorithms that may overwrite the values. Exclusive access to temporary storage can only be guaranteed by using custom containers.

class network

Public Functions

void clear_values() const: Reset all values to 0.

uint32_t value(node const &n) const: Returns value of a node.

void set_value(node const &n, uint32_t value) const: Sets value of a node.

uint32_t incr_value(node const &n) const: Increments value of a node and returns previous value.

uint32_t decr_value(node const &n) const: Decrements value of a node and returns new value.

Visited flags

Visited flags are similar to custom node values, but are used for the specific purpose of checking whether a node was visited in traversing algorithms. Again, all visited-functions are constant, because a change to the visited flags is considered transparent to the network. If a caller passes a constant network to an algorithm, the algorithm may change the visited flags but cannot change the structure of the network or any other visible property. The use of traversal ids helps to use unique visited flags in multiple depending contexts.

class network

Public Functions

void clear_visited() const: Reset all visited values to 0.

uint32_t visited(node const &n) const: Returns the visited value of a node.

void set_visited(node const &n, uint32_t v) const: Sets the visited value of a node.

uint32_t trav_id() const: Returns the current traversal id.

void incr_trav_id() const: Increment the current traversal id.

General methods

class network

Public Functions

network_events<base_type> &events() const

Returns network events object.

Clients can register callbacks for network events to this object. Events include adding nodes, modifying nodes, and deleting nodes.