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. Astd::shared_ptr<T>
is a convenient data structure to hold a storage in a logic network.
-
using base_type = 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.
-
network()
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.
-
network clone()
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.
-
signal get_constant(bool value) const
Create unary functions
-
class network
Create binary functions
-
class network
Public Functions
-
signal create_nand(signal const &f, signal const &g)
Creates a signal that computes the binary NAND.
-
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 andg
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 org
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 andg
is 0.
-
signal create_nand(signal const &f, signal const &g)
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_maj(signal const &f, signal const &g, signal const &h)
Create nary functions
-
class network
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 infanin
.fanin[0]
will correspond to the least-significant variable infunction
.- 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 nodesource
is a node in the source networkother
, but the signals infanin
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
-
signal create_node(std::vector<signal> const &fanin, kitty::dynamic_truth_table const &function)
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 havenew_signal
as fanin instead. In doing so, a possible polarity ofnew_signal
is taken into account. Afterwards, the fan-out count ofold_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 toold_node
, then it will be replaced bynew_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 childold_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 bynew_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 andtake_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
andforeach_gate
methods. It still contributes to the overallsize
of the network, butnum_gates
does not take dead nodes into account.- Parameters:
n – Node to check
- Returns:
Whether
n
is dead
-
void substitute_node(node const &old_node, signal const &new_signal)
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.
-
bool is_combinational() const
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.
-
kitty::dynamic_truth_table node_function(node const &n) const
Nodes and signals
-
class network
Public Functions
-
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.
-
bool is_complemented(signal const &f) const
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. Iffn
returns abool
, then it can interrupt the iteration by returningfalse
.
-
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. Iffn
returns abool
, then it can interrupt the iteration by returningfalse
.
-
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 parameterfn
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. Iffn
returns abool
, then it can interrupt the iteration by returningfalse
.
-
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 parameterfn
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. Iffn
returns abool
, then it can interrupt the iteration by returningfalse
.
-
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. Iffn
returns abool
, then it can interrupt the iteration by returningfalse
.
-
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. Iffn
returns abool
, then it can interrupt the iteration by returningfalse
.For efficiency reasons, this interface is often not provided in the network implementations, but has to be extended by wrapping with
fanout_view
.
-
template<typename Fn>
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
andend
iterator point to values which are assumed to be assigned to the fanin of the node. Consequently, the distance frombegin
toend
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
-
template<typename Iterator>
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.
-
void clear_values() const
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.
-
void clear_visited() const
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.
-
network_events<base_type> &events() const