r"""
Cayley graph of a Boolean function
==================================
The ``boolean_cayley_graph`` module defines
a function that contructs the Cayley graph of a Boolean function.
AUTHORS:
- Paul Leopardi (2016-08-21): initial version
EXAMPLES:
::
sage: from boolean_cayley_graphs.boolean_cayley_graph import boolean_cayley_graph
sage: f = lambda n: (n // 2) % 2
sage: [f(i) for i in range(4)]
[0, 0, 1, 1]
sage: g = boolean_cayley_graph(2, f)
sage: g.adjacency_matrix()
[0 0 1 1]
[0 0 1 1]
[1 1 0 0]
[1 1 0 0]
REFERENCES:
Bernasconi and Codenotti [BC1999]_.
"""
from sage.graphs.graph import Graph
def boolean_cayley_graph(dim, f):
r"""
Construct the Cayley graph of a Boolean function.
Given the non-negative integer ``dim`` and the function ``f``,
a Boolean function that takes a non-negative integer argument,
the function ``Boolean_Cayley_graph`` constructs the Cayley graph of ``f``
as a Boolean function on :math:`\mathbb{F}_2^{dim}`,
with the lexicographica ordering.
The value ``f(0)`` is assumed to be ``0``, so the graph is always simple.
INPUT:
- ``dim`` -- integer. The Boolean dimension of the given function.
- ``f`` -- function. A Boolean function expressed as a Python function
taking non-negative integer arguments.
OUTPUT:
A ``Graph`` object representing the Cayley graph of ``f``.
.. SEEALSO:
:module:`sage.graphs.graph`
EXAMPLES:
The Cayley graph of the function ``f`` where :math:`f(n) = n \mod 2`.
::
sage: from boolean_cayley_graphs.boolean_cayley_graph import boolean_cayley_graph
sage: f = lambda n: n % 2
sage: g = boolean_cayley_graph(2, f)
sage: g.adjacency_matrix()
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
"""
return Graph([range(2 ** dim), lambda i, j: f(i ^ j)],
format="rule",
immutable=True)
