# And-Inverter Graphs (AIGs)

The central data structure for working with And-Inverter Graphs (AIGs) in aigverse is the [`Aig`](api/aigverse/networks/index.html.md#aigverse.networks.Aig) class.
It enables efficient representation and manipulation of logic circuits in a form that’s well-suited for optimization and verification tasks.

The following will demonstrate how to work with the [`Aig`](api/aigverse/networks/index.html.md#aigverse.networks.Aig) class in Python.

#### NOTE
AIGs (And-Inverter Graphs) are a compact representation of Boolean functions using only AND gates and inverters (NOT gates). They are widely used in formal verification, hardware design, and optimization tasks.

## Quickstart

The following code snippet demonstrates how to create a simple AIG representing basic logic operations.

```ipython3
from aigverse.networks import Aig

# Create a new AIG network
aig = Aig()

# Create primary inputs
x1 = aig.create_pi()
x2 = aig.create_pi()

# Create logic gates
f_and = aig.create_and(x1, x2)  # AND gate
f_or = aig.create_or(x1, x2)    # OR gate

# Create primary outputs
aig.create_po(f_and)
aig.create_po(f_or)

# Print the size of the AIG network
print(f"AIG Size: {aig.size}")
```

```myst-ansi
AIG Size: 5
```

#### NOTE
All primary inputs (PIs) must be created before any logic gates.

## Basic AIG Concepts

An AIG consists of nodes and signals:

- **Nodes** represent either primary inputs, constants, or logic gates
- **Signals** reference nodes, possibly with complementation (inversion)

```ipython3
# Create a new AIG
aig = Aig()

# Create a constant (false)
const0 = aig.get_constant(False)
print(f"Constant 0: {const0}")

# Create primary inputs
a = aig.create_pi()
b = aig.create_pi()
print(f"Input a: {a}")
print(f"Input b: {b}")

# Create an AND gate and its complement (NAND)
and_gate = aig.create_and(a, b)
nand_gate = aig.create_not(and_gate)
print(f"AND gate: {and_gate}")
print(f"NAND gate: {nand_gate}")

# Get the node from a signal
node = aig.get_node(and_gate)
print(f"Node of AND gate: {node}")

# Check if a signal is complemented
is_complemented = aig.is_complemented(nand_gate)
print(f"Is NAND complemented? {is_complemented}")
```

```myst-ansi
Constant 0: Signal(0)
Input a: Signal(1)
Input b: Signal(2)
AND gate: Signal(3)
NAND gate: Signal(!3)
Node of AND gate: 3
Is NAND complemented? True
```

### Exploring AIG Structure

You can iterate over all nodes in the AIG, or specific subsets like primary inputs or logic gates.

```ipython3
# Create a sample AIG
aig = Aig()
a = aig.create_pi()
b = aig.create_pi()
c = aig.create_pi()
f1 = aig.create_and(a, b)
f2 = aig.create_or(f1, c)
aig.create_po(f2)

# Iterate over all nodes in the AIG
print("All nodes:")
for node in aig.nodes():
    print(f"  Node: {node}")

# Iterate only over primary inputs
print("\nPrimary inputs:")
for pi in aig.pis():
    print(f"  PI: {pi}")

# Iterate only over logic gates
print("\nLogic gates:")
for gate in aig.gates():
    print(f"  Gate: {gate}")

# Iterate over the fanins of a node
print("\nFanins of the OR gate:")
or_node = aig.get_node(f2)
for fanin in aig.fanins(or_node):
    print(f"  Fanin: {fanin}")
```

```myst-ansi
All nodes:
  Node: 0
  Node: 1
  Node: 2
  Node: 3
  Node: 4
  Node: 5

Primary inputs:
  PI: 1
  PI: 2
  PI: 3

Logic gates:
  Gate: 4
  Gate: 5

Fanins of the OR gate:
  Fanin: Signal(!3)
  Fanin: Signal(!4)
```

### Building Complex Functions

AIGs support a variety of logic functions beyond just AND gates. Internally, those are decomposed into multiple nodes.

```ipython3
aig = Aig()
a = aig.create_pi()
b = aig.create_pi()
c = aig.create_pi()

# Create various logic functions
and_gate = aig.create_and(a, b)
or_gate = aig.create_or(a, b)
xor_gate = aig.create_xor(a, b)
maj_gate = aig.create_maj(a, b, c)  # Majority function (a&b | a&c | b&c)
ite_gate = aig.create_ite(a, b, c)  # If-then-else: a ? b : c

# Add outputs
aig.create_po(and_gate)
aig.create_po(or_gate)
aig.create_po(xor_gate)
aig.create_po(maj_gate)
aig.create_po(ite_gate)

# Print statistics
print(f"AIG Size: {aig.size}")
print(f"Number of gates: {aig.num_gates}")
print(f"Number of primary inputs: {aig.num_pis}")
print(f"Number of primary outputs: {aig.num_pos}")
```

```myst-ansi
AIG Size: 13
Number of gates: 9
Number of primary inputs: 3
Number of primary outputs: 5
```

## AIG Views

AIG views provide alternative representations of AIGs for specific tasks, such as depth computation or fanout analysis.
These views can be layered on top of the original AIG, allowing you to work with the same underlying structure while
adding additional functionality.

### Network and Signal Names

The [`NamedAig`](api/aigverse/networks/index.html.md#aigverse.networks.NamedAig) class extends the standard AIG with the ability to assign names to the network itself,
primary inputs, primary outputs, and internal signals. This is particularly useful for debugging, visualization, and
interfacing with external tools that rely on human-readable signal names.

```ipython3
from aigverse.networks import NamedAig

# Create a new named AIG (or construct from existing AIG)
named_aig = NamedAig()

# Set the network name
named_aig.set_network_name("full_adder")

# Create named primary inputs
a = named_aig.create_pi("a")
b = named_aig.create_pi("b")
cin = named_aig.create_pi("cin")

# Create full adder logic
sum = named_aig.create_xor3(a, b, cin)
carry = named_aig.create_maj(a, b, cin)

# Assign names to internal signals
named_aig.set_name(sum, "sum")
named_aig.set_name(carry, "carry")

# Create named primary outputs
named_aig.create_po(sum, "sum_output")
named_aig.create_po(carry, "carry_output")

# Retrieve names
print(f"Network name: {named_aig.get_network_name()}")
print(f"PI names: {[named_aig.get_name(named_aig.make_signal(pi)) for pi in named_aig.pis()]}")
print(f"Signal name (sum): {named_aig.get_name(sum)}")
print(f"Signal name (carry): {named_aig.get_name(carry)}")
print(f"PO name at index 0: {named_aig.get_output_name(0)}")
print(f"PO name at index 1: {named_aig.get_output_name(1)}")

# Check if a signal has a name
print(f"Has name: {named_aig.has_name(sum)}")
```

```myst-ansi
Network name: full_adder
PI names: ['a', 'b', 'cin']
Signal name (sum): sum
Signal name (carry): carry
PO name at index 0: sum_output
PO name at index 1: carry_output
Has name: True
```

Named AIGs are automatically created when reading from file formats that contain naming information, e.g., Verilog and
AIGER. See [File I/O]() for more details.

#### NOTE
Names are tied to the specific AIG structure. When you apply optimization algorithms or structural modifications
(such as [`cleanup_dangling()`](api/aigverse/algorithms/index.html.md#aigverse.algorithms.cleanup_dangling)), the names will be lost as the return type will be downcast to
[`Aig`](api/aigverse/networks/index.html.md#aigverse.networks.Aig). If preserving names is important, consider reapplying them after optimization.

### Depth and Level Computation

The depth of an AIG network represents the longest path from any input to any output, which corresponds to the critical
path delay in a circuit. You can compute the depth and level of each node using the [`DepthAig`](api/aigverse/networks/index.html.md#aigverse.networks.DepthAig)
class.

```ipython3
from aigverse.networks import DepthAig

# Create a sample AIG
aig = Aig()
a = aig.create_pi()
b = aig.create_pi()
c = aig.create_pi()
f1 = aig.create_and(a, b)
f2 = aig.create_and(f1, c)
aig.create_po(f2)

# Create a depth view of the AIG
depth_aig = DepthAig(aig)

# Get the depth of the AIG
print(f"Depth of AIG: {depth_aig.num_levels}")

# Print the level of each node
print("\nLevel of each node:")
for node in aig.nodes():
    print(f"  Node {node}: Level {depth_aig.level(node)}")

# Check which nodes are on the critical path
print("\nNodes on critical path:")
for node in aig.nodes():
    if depth_aig.is_on_critical_path(node):
        print(f"  Node {node}")
```

```myst-ansi
Depth of AIG: 2

Level of each node:
  Node 0: Level 0
  Node 1: Level 0
  Node 2: Level 0
  Node 3: Level 0
  Node 4: Level 1
  Node 5: Level 2

Nodes on critical path:
  Node 1
  Node 2
  Node 4
  Node 5
```

### AIGs with Fanout Information

Fanouts of AIG nodes can be collected using [`FanoutAig`](api/aigverse/networks/index.html.md#aigverse.networks.FanoutAig).

```ipython3
from aigverse.networks import FanoutAig

# Create a sample AIG
aig = Aig()
x1 = aig.create_pi()
x2 = aig.create_pi()
x3 = aig.create_pi()

# Create AND gates
n4 = aig.create_and(x1, x2)
n5 = aig.create_and(n4, x3)
n6 = aig.create_and(n4, n5)
# Create primary outputs
aig.create_po(n6)

fanout_aig = FanoutAig(aig)
print("\nFanout nodes of n4:")
for node in fanout_aig.fanouts(aig.get_node(n4)):
    print(f"  Node {node}")
```

```myst-ansi

Fanout nodes of n4:
  Node 5
  Node 6
```

### Cuts

The [`AigCut`](api/aigverse/networks/index.html.md#aigverse.networks.AigCut) class provides an isolated view on a single cut in a network. A cut has a single output (root) and a set of leaves (inputs). This is useful for analyzing subgraphs or extracting portions of a larger network.

```ipython3
from aigverse.networks import Aig, AigCut

# Create a sample AIG
aig = Aig()
x1 = aig.create_pi()
x2 = aig.create_pi()
x3 = aig.create_pi()

# Create logic
f1 = aig.create_and(x1, x2)
f2 = aig.create_and(f1, x3)
aig.create_po(f2)

# Create a small cut view with x1, x2 as leaves and f1 as root
# This is valid because f1 only depends on x1 and x2
cut = AigCut(aig, [x1, x2], f1)

print(f"Small cut has {cut.num_pis} PIs (leaves)")
print(f"Small cut has {cut.num_pos} POs (roots)")
print(f"Small cut has {cut.num_gates} gates")

# Iterate over leaves (PIs in the cut)
print("\nLeaf nodes in small cut:")
for leaf in cut.pis():
    print(f"  Leaf: {leaf}")

# Iterate over gates in the cut
print("\nGates in small cut:")
for gate in cut.gates():
    print(f"  Gate: {gate}")

# Create a larger cut with all PIs as leaves and f2 as root
# This cut includes both f1 and f2 gates
cut2 = AigCut(aig, [x1, x2, x3], f2)

print(f"\nLarger cut has {cut2.num_pis} PIs (leaves)")
print(f"Larger cut has {cut2.num_pos} POs (roots)")
print(f"Larger cut has {cut2.num_gates} gates")

# The gates include both f1 and f2
print("\nGates in larger cut:")
for gate in cut2.gates():
    print(f"  Gate: {gate}")
```

```myst-ansi
Small cut has 2 PIs (leaves)
Small cut has 1 POs (roots)
Small cut has 1 gates

Leaf nodes in small cut:
  Leaf: 1
  Leaf: 2

Gates in small cut:
  Gate: 4

Larger cut has 3 PIs (leaves)
Larger cut has 1 POs (roots)
Larger cut has 2 gates

Gates in larger cut:
  Gate: 4
  Gate: 5
```

#### NOTE
A cut is only valid if all dependencies of the root node are either included in the leaves or can be reached through nodes within the cut. The cut view clears all nodes’ visited flags before construction to ensure the cut is constructed correctly.

### Sequential AIGs

[`SequentialAig`](api/aigverse/networks/index.html.md#aigverse.networks.SequentialAig)s extend standard AIGs to include registers, which allow modeling sequential circuits
with memory elements.

```ipython3
from aigverse.networks import SequentialAig

# Create a sequential AIG
seq_aig = SequentialAig()

# Create a primary input and a register output
x = seq_aig.create_pi()       # Regular PI
r = seq_aig.create_ro()       # Register output (sequential PI)

# Create logic
f_and = seq_aig.create_and(x, r)   # AND gate

# Create a primary output and a register input
seq_aig.create_po(f_and)      # Regular PO
seq_aig.create_ri(f_and)      # Register input (sequential PO)

# Print information about the sequential AIG
print(f"Number of PIs: {seq_aig.num_pis}")
print(f"Number of POs: {seq_aig.num_pos}")
print(f"Number of registers: {seq_aig.num_registers}")

# Get the register associations (RI-RO pairs)
print("\nRegister associations:")
registers = seq_aig.registers()
for reg in registers:
    ri, ro = reg
    print(f"  RI: {ri} -> RO: {ro}")
```

```myst-ansi
Number of PIs: 1
Number of POs: 1
Number of registers: 1

Register associations:
  RI: Signal(3) -> RO: 2
```

#### NOTE
When creating sequential AIGs, follow these rules:

1. All register outputs (ROs) must be created after all primary inputs (PIs).
2. All register inputs (RIs) must be created after all primary outputs (POs).
3. As with regular AIGs, all PIs and ROs must be created before any logic gates.

## File I/O

AIGs can be read from and written to various file formats.

```ipython3
from aigverse.io import write_aiger, write_verilog, write_dot, read_aiger_into_aig, read_verilog_into_aig, read_pla_into_aig

# Create a sample AIG
aig = Aig()
a = aig.create_pi()
b = aig.create_pi()
f = aig.create_and(a, b)
aig.create_po(f)

# Write to AIGER format
write_aiger(aig, "example.aig")

# Write to Verilog format
write_verilog(aig, "example.v")

# Write to DOT format
write_dot(aig, "example.dot")

# Read from AIGER format
read_aig = read_aiger_into_aig("example.aig")

# Read from Verilog format
read_verilog_aig = read_verilog_into_aig("example.v")

# Read from PLA format
read_pla_aig = read_pla_into_aig("example.pla")

print(f"Original AIG size: {aig.size}")
print(f"Read AIGER AIG size: {read_aig.size}")
print(f"Read Verilog AIG size: {read_verilog_aig.size}")
print(f"Read PLA AIG size: {read_pla_aig.size}")
```

```myst-ansi
Original AIG size: 4
Read AIGER AIG size: 4
Read Verilog AIG size: 4
Read PLA AIG size: 9
```

#### NOTE
The gate-level Verilog file support constitutes a very small subset of the Verilog standard, similar
in extent to what ABC supports. For more information, see the
[`lorina` parser](https://lorina.readthedocs.io/en/latest/verilog.html) used by this project.

## Index Lists

Alternatively, index lists provide a compact, serialization-friendly representation of an AIG’s structure as a flat
list of integers. This is useful for ML pipelines, dataset generation, or exporting AIGs for use in environments where
fixed-size numeric arrays are required.

```ipython3
from aigverse.networks import AigIndexList

# Create a sample AIG
aig = Aig()
a = aig.create_pi()
b = aig.create_pi()
c = aig.create_pi()
d = aig.create_pi()
t0 = aig.create_and(a, b)
t1 = aig.create_and(~c, ~d)
t2 = aig.create_xor(t0, t1)
aig.create_po(t2)

# Convert an AIG to an index list
indices = aig.to_index_list()

# Convert an index list back to an AIG
aig2 = indices.to_aig()

# Convert to a Python list
indices = [int(i) for i in indices]
print(indices)
```

```myst-ansi
[4, 1, 5, 2, 4, 7, 9, 10, 13, 11, 12, 15, 17, 19]
```

The first three entries encode number of PIs, number of POs, and number of gates, respectively. In the example above,
those are `4`, `1`, and `5`. Successive pairs of indices refer to the fanins signals of nodes. Each fanin exists in two
polarities: negated = odd index, and non-negated = even index. In the example, `2` and `4` refer to the non-negated
signals originating from PIs `1` and `2`. These form the first AND gate. The subsequent `7` and `9` are odd, hence,
negated. If the first index is lower than the second, an AND gate is encoded. Otherwise, it is an XOR gate. The final
indices of the list refer to the PO signals. It must be ensured that they match the encoded number of POs.

For more information on the index list format, see
[`mockturtle`’s documentation](https://mockturtle.readthedocs.io/en/latest/utils/util_data_structures.html#index-list).

## Edge Lists

Edge lists provide a graph-based representation of an AIG’s structure as a flat collection of `(source, target, weight)` triples, one per structural connection. This is useful for feeding AIG structure directly into custom graph
algorithms, GNN frameworks, or other tooling that expects an edge-list-style graph, as a lighter-weight alternative to
the richer graph object produced by the [NetworkX adapter](machine_learning.html.md#networkx).

```ipython3
from aigverse.networks import AigEdgeList

# Create a sample AIG
aig = Aig()
a = aig.create_pi()
b = aig.create_pi()
f = aig.create_and(a, ~b)
aig.create_po(f)

# Convert the AIG to an edge list, using custom weights to mark regular/inverted connections
edges = aig.to_edge_list(regular_weight=0, inverted_weight=1)

for edge in edges:
    print(edge)
```

```myst-ansi
Edge(s:1,t:3,w:0)
Edge(s:2,t:3,w:1)
Edge(s:3,t:4,w:0)
```

Each `AigEdge` connects a `source` node to a `target` node, both identified by their integer node index, and carries a
`weight` set to `regular_weight` or `inverted_weight` depending on whether the connection is inverted. Constants,
primary inputs, and gates are numbered as usual; primary outputs are assigned synthetic target indices starting right
after the last node (i.e., at `aig.size`), so their edges point one index beyond the network’s regular nodes. For
sequential AIGs, additional edges connect each register input to its corresponding register output to represent the
feedback loop.

## `pickle` Support

AIGs support Python’s [`pickle`](https://docs.python.org/3/library/pickle.html) protocol, allowing you to serialize and
deserialize AIG objects for persistent storage. This is useful for saving intermediate results, sharing AIGs between
processes, quickly restoring previously computed networks, or integrating with Python-first data science and machine
learning workflows.

```ipython3
import pickle

# Save AIG to a file using pickle
with open("aig.pkl", "wb") as f:
    pickle.dump(aig, f)

# Load the AIG from the pickle file
with open("aig.pkl", "rb") as f:
    unpickled_aig = pickle.load(f)
```

You can also pickle and unpickle multiple AIGs at once by storing them in a tuple or list.

```ipython3
aig1 = Aig()
a1 = aig1.create_pi()
b1 = aig1.create_pi()
f1 = aig1.create_and(a1, b1)
aig1.create_po(f1)

aig2 = Aig()
a2 = aig2.create_pi()
b2 = aig2.create_pi()
f2 = aig2.create_or(a2, b2)
aig2.create_po(f2)

# Pickle both AIGs together
with open("aigs.pkl", "wb") as f:
    pickle.dump((aig1, aig2), f)

# Unpickle them
with open("aigs.pkl", "rb") as f:
    unpickled_aig1, unpickled_aig2 = pickle.load(f)
```