Majority Logic Synthesis Based on Nauty Algorithm - Field-Coupled Nanocomputing: Paradigms, Progress, and Perspectives - page 114

(a) (b)

Fig. 8. (a) A graphical representation for graph G (b) A graphical representation for graph H

check if there exists a proper bijection that can make the graphs isomorphic. For a
moderately small graph with n = 100, n! is an unmanageably large number. A lot of
research has been done regarding isomorphism testing and many algorithms have been
proposed. Among them, Nauty is considered to be one of the fastest and the most
comprehensive isomorphism testing programs.

! ð 6 Þ

u : ¼

n1 n2 n3 n4 n5 n6

123456
abcdef

h : ¼

m1 m2 m3 m4 m5 m6

Nauty, first proposed by McKay, uses a set of transformations to reduce the
graphs, and test for the presence of isomorphism [ 19 ]. In this work, the details of
the algorithm will not be discussed and the emphasis is put on the use of the software.
The inputs to the software are two graphs and the output shows if they are isomorphic
or not. Additionally, if they are isomorphic, Nauty will also give the bijection between
them, which is a set of variable substitutions to make one graph to overlap over the
other. For further information on graph theory and Nauty algorithm, the interested
reader may refer to the material in Refs. [ 18 , 19 ].

3 Identifying Standard Functions with Nauty Algorithm

3.1 Primitives

The Boolean logic functions that can be represented by only one majority gate are
called primitives, which are the basic units to build all other majority expressions.
For four-variable functions, five types of primitives can be defined according to
the number of variables used as inputs to a majority gate. The first type has no
variable-inputs, which means this type includes two primitives, logic ''1'' and logic
''0''. The second type has a single variable-input like ''a'' o r '' ( c 0 )''. Since four-
variable Boolean functions are discussed here, there are 8 primitives that belong to
this type.
The third type of primitive has two variable-inputs. Any combination of two inputs
from ''a'' , '' b'' , '' c'' , '' d'' , '' ( a 0 )'', ''(b 0 )'', ''(c 0 )'' and ''(d 0 )'' are allowed except these
four pairs: ''(aa 0 )'', ''(bb 0 )'', ''(cc 0 )'' and ''(dd 0 )''. The number of possible