An example of an 8-input butterfly network is illustrated in
Figure 1. The nodes in this graph represent
switches, and the edges represent wires. Each node in the network has
a distinct label 
, where r is the row, and l is the level.
In a butterfly with N inputs, the row is a 
-bit binary
number and the level is an integer between 0 and 
. The
nodes on level 0 and 
are called the inputs and
outputs, respectively. For 
, a node labeled 
is
connected to nodes 
and 
, where 
denotes r
with bit l complemented (bit 0 is the most significant, bit 
the least).
In a butterfly, messages are typically sent from the switches on level
0, called the inputs, to those on level 
, called the
outputs. In a one-to-one routing problem, each input is
the origin of at most one message, and each output is the destination
of a most one message. One-to-one routing is also called
permutation routing.
Figure 1: An 8-input butterfly network.