graph

graph

BottomNode

Bases: LogicalCircuitNode

The bottom node representing False in the logic circuit.

Source code in cirkit/templates/logic/graph.py

class BottomNode(LogicalCircuitNode):
    """The bottom node representing False in the logic circuit."""

ConjunctionNode

Bases: LogicalCircuitNode

A conjunction in the logical circuit.

Source code in cirkit/templates/logic/graph.py

class ConjunctionNode(LogicalCircuitNode):
    """A conjunction in the logical circuit."""

DisjunctionNode

Bases: LogicalCircuitNode

A conjunction in the logical circuit.

Source code in cirkit/templates/logic/graph.py

class DisjunctionNode(LogicalCircuitNode):
    """A conjunction in the logical circuit."""

LiteralNode

Bases: LogicalInputNode

A literal in the logical circuit.

Source code in cirkit/templates/logic/graph.py

class LiteralNode(LogicalInputNode):
    """A literal in the logical circuit."""

LogicalCircuit

Bases: RootedDiAcyclicGraph[LogicalCircuitNode]

Source code in cirkit/templates/logic/graph.py

class LogicalCircuit(RootedDiAcyclicGraph[LogicalCircuitNode]):
    def __init__(
        self,
        nodes: Sequence[LogicalCircuitNode],
        in_nodes: dict[LogicalCircuitNode, Sequence[LogicalCircuitNode]],
        outputs: Sequence[LogicalCircuitNode],
    ) -> None:
        """A Logical circuit represented as a rooted acyclic graph.

        Args:
            nodes (Sequence[LogicalCircuitNode]): The list of nodes in the logic graph.
            in_nodes (dict[LogicalCircuitNode, Sequence[LogicalCircuitNode]]):
                A dictionary containing the list of inputs to each layer.
            outputs (Sequence[LogicalCircuitNode]):
                The output layers of the circuit.
        """
        if len(outputs) != 1:
            assert ValueError("A logic graphs can only have one output!")
        super().__init__(nodes, in_nodes, outputs)

    def prune(self):
        """Prune the current graph by applying unit propagation.

        Prune a graph in place by applying unit propagation to conjunction and disjunctions.
        See https://en.wikipedia.org/wiki/Unit_propagation.
        Nodes that are not used as input to other nodes and are not among the output nodes
        are removed too.
        """
        absorbing_element = lambda n: BottomNode if isinstance(n, ConjunctionNode) else TopNode
        null_element = lambda n: TopNode if isinstance(n, ConjunctionNode) else BottomNode

        def absorb_node(node):
            if isinstance(node, (ConjunctionNode, DisjunctionNode)):
                children = [absorb_node(c) for c in self.node_inputs(node)]

                # if the node contains the absorbing element, then it is replaced
                # altogether
                if any(isinstance(c, absorbing_element(node)) for c in children):
                    return absorbing_element(node)()

            return node

        # apply node absorbion and remove null elements from conjunctions and disjunctions
        in_nodes = {}
        for n, children in self._in_nodes.items():
            absorbed = absorb_node(n)

            if not isinstance(absorbed, (TopNode, BottomNode)):
                in_nodes[n] = [
                    c
                    for c in [absorb_node(c) for c in children]
                    if not isinstance(c, null_element(n))
                ]

        # remove nodes that are not used as input to any other node if they are not the output node
        out_nodes = graph_nodes_outgoings(self.nodes, lambda n: in_nodes.get(n, []))
        in_nodes = {
            n: children
            for n, children in in_nodes.items()
            if len(out_nodes.get(n, [])) > 0 or n in self._outputs
        }

        nodes = list(set(itertools.chain(*in_nodes.values())).union(in_nodes.keys()))

        # re initialize the graph
        self.__init__(nodes, in_nodes, list(self.outputs))

    @property
    def inputs(self) -> Iterator[LogicalCircuitNode]:
        return (cast(LogicalCircuitNode, node) for node in super().inputs)

    @property
    def outputs(self) -> Iterator[LogicalCircuitNode]:
        return (cast(LogicalCircuitNode, node) for node in super().outputs)

    @cached_property
    def num_variables(self) -> int:
        return len({i.literal for i in self.inputs if isinstance(i, LogicalInputNode)})

    def node_scope(self, node: LogicalCircuitNode) -> Scope:
        """Compute the scope of a node.

        Args:
            node (LogicalCircuitNode): The node for which the scope is computed.

        Returns:
            Scope: The scope of the node.
        """
        match node:
            case TopNode() | BottomNode():
                scope = Scope([])
            case LiteralNode() | NegatedLiteralNode():
                scope = Scope([node.literal])
            case DisjunctionNode() | ConjunctionNode():
                scope = Scope([])
                for i in self.node_inputs(node):
                    scope = scope.union(self.node_scope(i))
            case _:
                assert False, f"Unknown node type: {node.__class__}"

        return scope

    def smooth(self):
        """Convert the current graph to a smooth graph in place.
        see https://yoojungchoi.github.io/files/ProbCirc20.pdf and
        https://proceedings.neurips.cc/paper/2019/file/940392f5f32a7ade1cc201767cf83e31-Paper.pdf
        for more information.

        Returns:
            LogicalCircuit: A new logic graph that is smooth.
        """
        literal_map: dict[tuple[int, bool], LogicalCircuitNode] = {
            (node.literal, isinstance(node, LiteralNode)): node
            for node in self.nodes
            if isinstance(node, (LiteralNode, NegatedLiteralNode))
        }
        # smoothing map keeps track of the disjunctions created for smoothing purposes
        smoothing_map: dict[int, DisjunctionNode] = {}
        disjunctions = [n for n in self.nodes if isinstance(n, DisjunctionNode)]

        in_nodes = self._in_nodes
        for d in disjunctions:
            d_scope = self.node_scope(d)

            for input_to_d in self.node_inputs(d):
                to_add_for_smoothing: list[LogicalCircuitNode] = []
                missing_literals = d_scope.difference(self.node_scope(input_to_d))

                if len(missing_literals) > 0:
                    for ml in missing_literals:
                        if ml not in smoothing_map:
                            # construct a conjunction representing the literal ml
                            # for smoothing purposes
                            smooth_ml = DisjunctionNode()
                            in_nodes[smooth_ml] = [
                                literal_map.get((ml, True), LiteralNode(ml)),
                                literal_map.get((ml, False), NegatedLiteralNode(ml)),
                            ]
                            smoothing_map[ml] = smooth_ml

                        to_add_for_smoothing.append(smoothing_map[ml])

                    # if input to disjunction is a conjunction or a disjunction
                    # then directly add to its inputs else create an ad-hoc node
                    if input_to_d in in_nodes:
                        in_nodes[input_to_d].extend(to_add_for_smoothing)
                    else:
                        ad_hoc = ConjunctionNode()
                        in_nodes[ad_hoc] = to_add_for_smoothing
                        in_nodes[ad_hoc].append(input_to_d)

                        # replace input_to_d with the ad-hoc disjunction
                        in_nodes[d].remove(input_to_d)
                        # add to the top so that it does not get checked again
                        in_nodes[d].insert(0, ad_hoc)

        nodes = list(set(itertools.chain(*in_nodes.values())).union(in_nodes.keys()))
        self.__init__(nodes, in_nodes, self._outputs)

    def build_circuit(
        self,
        literal_input_factory: InputLayerFactory = None,
        negated_literal_input_factory: InputLayerFactory = None,
        weight_factory: ParameterFactory | None = None,
        num_channels: int = 1,
        enforce_smoothness: bool = True,
    ) -> Circuit:
        """Construct a symbolic circuit from a logic circuit graph.
        If input factories for literals and their negation are not provided the it
        falls back to a categorical input layer with two categories parametrized by
        the constant vector [0, 1] for a literal and [1, 0] for its negation.

        Args:
            literal_input_factory: A factory that builds an input layer for literals.
            negated_literal_input_factory:
                A factory that builds an input layer for negated literals.
            weight_factory: The factory to construct the weight of sum layers.
                It can be None, or a parameter factory, i.e., a map from a shape to
                a symbolic parameter.
                If None is used, the default weight factory uses non-trainable unitary
                parameters, which instantiate a regular boolean logic graph.
            num_channels: The number of channels for each variable.
            enforce_smoothness:
                Enforces smoothness of the circuit to support efficient marginalization.

        Returns:
            Circuit: A symbolic circuit.

        Raises:
            ValueError: If only one of literal_input_factory and
                negated_literal_input_factory are specified.
        """
        if enforce_smoothness:
            self.smooth()
        self.prune()

        in_layers: dict[Layer, Sequence[Layer]] = {}
        node_to_layer: dict[LogicalCircuitNode, Layer] = {}

        if (literal_input_factory is None) ^ (negated_literal_input_factory is None):
            raise ValueError(
                "Either both 'literal_input_factory' and 'negated_literal_input_factory' "
                "must be provided or none."
            )

        if literal_input_factory is None and negated_literal_input_factory is None:
            # default factory is locally imported when needed to avoid circular imports
            literal_input_factory = default_literal_input_factory(negated=False)
            negated_literal_input_factory = default_literal_input_factory(negated=True)

        if weight_factory is None:
            # default to unitary weights
            def weight_factory(n: tuple[int]) -> Parameter:
                # locally import numpy to avoid dependency on the whole file
                initializer = ConstantTensorInitializer(1.0)
                return Parameter.from_input(TensorParameter(*n, initializer=initializer))

        # map each input literal to a symbolic input layer
        for i in self.inputs:
            match i:
                case LiteralNode():
                    node_to_layer[i] = literal_input_factory(
                        Scope([i.literal]), num_units=1, num_channels=num_channels
                    )
                case NegatedLiteralNode():
                    node_to_layer[i] = negated_literal_input_factory(
                        Scope([i.literal]), num_units=1, num_channels=num_channels
                    )

        for node in self.topological_ordering():
            match node:
                case ConjunctionNode():
                    product_node = HadamardLayer(1, arity=len(self.node_inputs(node)))
                    in_layers[product_node] = [node_to_layer[i] for i in self.node_inputs(node)]
                    node_to_layer[node] = product_node
                case DisjunctionNode():
                    sum_node = SumLayer(
                        1,
                        1,
                        arity=len(self.node_inputs(node)),
                        weight_factory=weight_factory,
                    )
                    in_layers[sum_node] = [node_to_layer[i] for i in self.node_inputs(node)]
                    node_to_layer[node] = sum_node

        layers = list(set(itertools.chain(*in_layers.values())).union(in_layers.keys()))
        return Circuit(num_channels, layers, in_layers, [node_to_layer[self.output]])

inputs property

num_variables cached property

outputs property

__init__(nodes, in_nodes, outputs)

A Logical circuit represented as a rooted acyclic graph.

Parameters:

Name	Type	Description	Default
nodes	Sequence[LogicalCircuitNode]	The list of nodes in the logic graph.	required
in_nodes	dict[LogicalCircuitNode, Sequence[LogicalCircuitNode]]	A dictionary containing the list of inputs to each layer.	required
outputs	Sequence[LogicalCircuitNode]	The output layers of the circuit.	required

Source code in cirkit/templates/logic/graph.py

def __init__(
    self,
    nodes: Sequence[LogicalCircuitNode],
    in_nodes: dict[LogicalCircuitNode, Sequence[LogicalCircuitNode]],
    outputs: Sequence[LogicalCircuitNode],
) -> None:
    """A Logical circuit represented as a rooted acyclic graph.

    Args:
        nodes (Sequence[LogicalCircuitNode]): The list of nodes in the logic graph.
        in_nodes (dict[LogicalCircuitNode, Sequence[LogicalCircuitNode]]):
            A dictionary containing the list of inputs to each layer.
        outputs (Sequence[LogicalCircuitNode]):
            The output layers of the circuit.
    """
    if len(outputs) != 1:
        assert ValueError("A logic graphs can only have one output!")
    super().__init__(nodes, in_nodes, outputs)

build_circuit(literal_input_factory=None, negated_literal_input_factory=None, weight_factory=None, num_channels=1, enforce_smoothness=True)

Construct a symbolic circuit from a logic circuit graph. If input factories for literals and their negation are not provided the it falls back to a categorical input layer with two categories parametrized by the constant vector [0, 1] for a literal and [1, 0] for its negation.

Parameters:

Name	Type	Description	Default
literal_input_factory	InputLayerFactory	A factory that builds an input layer for literals.	None
negated_literal_input_factory	InputLayerFactory	A factory that builds an input layer for negated literals.	None
weight_factory	ParameterFactory | None	The factory to construct the weight of sum layers. It can be None, or a parameter factory, i.e., a map from a shape to a symbolic parameter. If None is used, the default weight factory uses non-trainable unitary parameters, which instantiate a regular boolean logic graph.	None
num_channels	int	The number of channels for each variable.	1
enforce_smoothness	bool	Enforces smoothness of the circuit to support efficient marginalization.	True

Returns:

Name	Type	Description
Circuit	Circuit	A symbolic circuit.

Raises:

Type	Description
ValueError	If only one of literal_input_factory and negated_literal_input_factory are specified.

Source code in cirkit/templates/logic/graph.py

def build_circuit(
    self,
    literal_input_factory: InputLayerFactory = None,
    negated_literal_input_factory: InputLayerFactory = None,
    weight_factory: ParameterFactory | None = None,
    num_channels: int = 1,
    enforce_smoothness: bool = True,
) -> Circuit:
    """Construct a symbolic circuit from a logic circuit graph.
    If input factories for literals and their negation are not provided the it
    falls back to a categorical input layer with two categories parametrized by
    the constant vector [0, 1] for a literal and [1, 0] for its negation.

    Args:
        literal_input_factory: A factory that builds an input layer for literals.
        negated_literal_input_factory:
            A factory that builds an input layer for negated literals.
        weight_factory: The factory to construct the weight of sum layers.
            It can be None, or a parameter factory, i.e., a map from a shape to
            a symbolic parameter.
            If None is used, the default weight factory uses non-trainable unitary
            parameters, which instantiate a regular boolean logic graph.
        num_channels: The number of channels for each variable.
        enforce_smoothness:
            Enforces smoothness of the circuit to support efficient marginalization.

    Returns:
        Circuit: A symbolic circuit.

    Raises:
        ValueError: If only one of literal_input_factory and
            negated_literal_input_factory are specified.
    """
    if enforce_smoothness:
        self.smooth()
    self.prune()

    in_layers: dict[Layer, Sequence[Layer]] = {}
    node_to_layer: dict[LogicalCircuitNode, Layer] = {}

    if (literal_input_factory is None) ^ (negated_literal_input_factory is None):
        raise ValueError(
            "Either both 'literal_input_factory' and 'negated_literal_input_factory' "
            "must be provided or none."
        )

    if literal_input_factory is None and negated_literal_input_factory is None:
        # default factory is locally imported when needed to avoid circular imports
        literal_input_factory = default_literal_input_factory(negated=False)
        negated_literal_input_factory = default_literal_input_factory(negated=True)

    if weight_factory is None:
        # default to unitary weights
        def weight_factory(n: tuple[int]) -> Parameter:
            # locally import numpy to avoid dependency on the whole file
            initializer = ConstantTensorInitializer(1.0)
            return Parameter.from_input(TensorParameter(*n, initializer=initializer))

    # map each input literal to a symbolic input layer
    for i in self.inputs:
        match i:
            case LiteralNode():
                node_to_layer[i] = literal_input_factory(
                    Scope([i.literal]), num_units=1, num_channels=num_channels
                )
            case NegatedLiteralNode():
                node_to_layer[i] = negated_literal_input_factory(
                    Scope([i.literal]), num_units=1, num_channels=num_channels
                )

    for node in self.topological_ordering():
        match node:
            case ConjunctionNode():
                product_node = HadamardLayer(1, arity=len(self.node_inputs(node)))
                in_layers[product_node] = [node_to_layer[i] for i in self.node_inputs(node)]
                node_to_layer[node] = product_node
            case DisjunctionNode():
                sum_node = SumLayer(
                    1,
                    1,
                    arity=len(self.node_inputs(node)),
                    weight_factory=weight_factory,
                )
                in_layers[sum_node] = [node_to_layer[i] for i in self.node_inputs(node)]
                node_to_layer[node] = sum_node

    layers = list(set(itertools.chain(*in_layers.values())).union(in_layers.keys()))
    return Circuit(num_channels, layers, in_layers, [node_to_layer[self.output]])

node_scope(node)

Compute the scope of a node.

Parameters:

Name	Type	Description	Default
node	LogicalCircuitNode	The node for which the scope is computed.	required

Returns:

Name	Type	Description
Scope	Scope	The scope of the node.

Source code in cirkit/templates/logic/graph.py

def node_scope(self, node: LogicalCircuitNode) -> Scope:
    """Compute the scope of a node.

    Args:
        node (LogicalCircuitNode): The node for which the scope is computed.

    Returns:
        Scope: The scope of the node.
    """
    match node:
        case TopNode() | BottomNode():
            scope = Scope([])
        case LiteralNode() | NegatedLiteralNode():
            scope = Scope([node.literal])
        case DisjunctionNode() | ConjunctionNode():
            scope = Scope([])
            for i in self.node_inputs(node):
                scope = scope.union(self.node_scope(i))
        case _:
            assert False, f"Unknown node type: {node.__class__}"

    return scope

prune()

Prune the current graph by applying unit propagation.

Prune a graph in place by applying unit propagation to conjunction and disjunctions. See https://en.wikipedia.org/wiki/Unit_propagation. Nodes that are not used as input to other nodes and are not among the output nodes are removed too.

Source code in cirkit/templates/logic/graph.py

def prune(self):
    """Prune the current graph by applying unit propagation.

    Prune a graph in place by applying unit propagation to conjunction and disjunctions.
    See https://en.wikipedia.org/wiki/Unit_propagation.
    Nodes that are not used as input to other nodes and are not among the output nodes
    are removed too.
    """
    absorbing_element = lambda n: BottomNode if isinstance(n, ConjunctionNode) else TopNode
    null_element = lambda n: TopNode if isinstance(n, ConjunctionNode) else BottomNode

    def absorb_node(node):
        if isinstance(node, (ConjunctionNode, DisjunctionNode)):
            children = [absorb_node(c) for c in self.node_inputs(node)]

            # if the node contains the absorbing element, then it is replaced
            # altogether
            if any(isinstance(c, absorbing_element(node)) for c in children):
                return absorbing_element(node)()

        return node

    # apply node absorbion and remove null elements from conjunctions and disjunctions
    in_nodes = {}
    for n, children in self._in_nodes.items():
        absorbed = absorb_node(n)

        if not isinstance(absorbed, (TopNode, BottomNode)):
            in_nodes[n] = [
                c
                for c in [absorb_node(c) for c in children]
                if not isinstance(c, null_element(n))
            ]

    # remove nodes that are not used as input to any other node if they are not the output node
    out_nodes = graph_nodes_outgoings(self.nodes, lambda n: in_nodes.get(n, []))
    in_nodes = {
        n: children
        for n, children in in_nodes.items()
        if len(out_nodes.get(n, [])) > 0 or n in self._outputs
    }

    nodes = list(set(itertools.chain(*in_nodes.values())).union(in_nodes.keys()))

    # re initialize the graph
    self.__init__(nodes, in_nodes, list(self.outputs))

smooth()

Convert the current graph to a smooth graph in place. see https://yoojungchoi.github.io/files/ProbCirc20.pdf and https://proceedings.neurips.cc/paper/2019/file/940392f5f32a7ade1cc201767cf83e31-Paper.pdf for more information.

Returns:

Name	Type	Description
LogicalCircuit		A new logic graph that is smooth.

Source code in cirkit/templates/logic/graph.py

def smooth(self):
    """Convert the current graph to a smooth graph in place.
    see https://yoojungchoi.github.io/files/ProbCirc20.pdf and
    https://proceedings.neurips.cc/paper/2019/file/940392f5f32a7ade1cc201767cf83e31-Paper.pdf
    for more information.

    Returns:
        LogicalCircuit: A new logic graph that is smooth.
    """
    literal_map: dict[tuple[int, bool], LogicalCircuitNode] = {
        (node.literal, isinstance(node, LiteralNode)): node
        for node in self.nodes
        if isinstance(node, (LiteralNode, NegatedLiteralNode))
    }
    # smoothing map keeps track of the disjunctions created for smoothing purposes
    smoothing_map: dict[int, DisjunctionNode] = {}
    disjunctions = [n for n in self.nodes if isinstance(n, DisjunctionNode)]

    in_nodes = self._in_nodes
    for d in disjunctions:
        d_scope = self.node_scope(d)

        for input_to_d in self.node_inputs(d):
            to_add_for_smoothing: list[LogicalCircuitNode] = []
            missing_literals = d_scope.difference(self.node_scope(input_to_d))

            if len(missing_literals) > 0:
                for ml in missing_literals:
                    if ml not in smoothing_map:
                        # construct a conjunction representing the literal ml
                        # for smoothing purposes
                        smooth_ml = DisjunctionNode()
                        in_nodes[smooth_ml] = [
                            literal_map.get((ml, True), LiteralNode(ml)),
                            literal_map.get((ml, False), NegatedLiteralNode(ml)),
                        ]
                        smoothing_map[ml] = smooth_ml

                    to_add_for_smoothing.append(smoothing_map[ml])

                # if input to disjunction is a conjunction or a disjunction
                # then directly add to its inputs else create an ad-hoc node
                if input_to_d in in_nodes:
                    in_nodes[input_to_d].extend(to_add_for_smoothing)
                else:
                    ad_hoc = ConjunctionNode()
                    in_nodes[ad_hoc] = to_add_for_smoothing
                    in_nodes[ad_hoc].append(input_to_d)

                    # replace input_to_d with the ad-hoc disjunction
                    in_nodes[d].remove(input_to_d)
                    # add to the top so that it does not get checked again
                    in_nodes[d].insert(0, ad_hoc)

    nodes = list(set(itertools.chain(*in_nodes.values())).union(in_nodes.keys()))
    self.__init__(nodes, in_nodes, self._outputs)

LogicalCircuitNode

Bases: ABC

The abstract base class for nodes in logic circuits.

Source code in cirkit/templates/logic/graph.py

class LogicalCircuitNode(ABC):
    """The abstract base class for nodes in logic circuits."""

LogicalInputNode

Bases: LogicalCircuitNode

The abstract base class for input nodes in logic circuits.

Source code in cirkit/templates/logic/graph.py

class LogicalInputNode(LogicalCircuitNode):
    """The abstract base class for input nodes in logic circuits."""

    def __init__(self, literal: int) -> None:
        """Init class.

        Args:
            literal (int): The literal of this node.
        """
        super().__init__()
        self._literal = literal

    @property
    def literal(self) -> int:
        """The literal of this input.

        Returns:
            str: The int representation of the literal.
        """
        return self._literal

    def __repr__(self) -> str:
        """Generate the repr string of the node.

        Returns:
            str: The str representation of the node.
        """
        return f"{type(self).__name__}@0x{id(self):x}({self.literal})"

_literal = literal instance-attribute

literal property

The literal of this input.

Returns:

Name	Type	Description
str	int	The int representation of the literal.

__init__(literal)

Init class.

Parameters:

Name	Type	Description	Default
literal	int	The literal of this node.	required

Source code in cirkit/templates/logic/graph.py

def __init__(self, literal: int) -> None:
    """Init class.

    Args:
        literal (int): The literal of this node.
    """
    super().__init__()
    self._literal = literal

__repr__()

Generate the repr string of the node.

Returns:

Name	Type	Description
str	str	The str representation of the node.

Source code in cirkit/templates/logic/graph.py

def __repr__(self) -> str:
    """Generate the repr string of the node.

    Returns:
        str: The str representation of the node.
    """
    return f"{type(self).__name__}@0x{id(self):x}({self.literal})"

NegatedLiteralNode

Bases: LogicalInputNode

A negated literal in the logical circuit.

Source code in cirkit/templates/logic/graph.py

class NegatedLiteralNode(LogicalInputNode):
    """A negated literal in the logical circuit."""

TopNode

Bases: LogicalCircuitNode

The top node representing True in the logic circuit.

Source code in cirkit/templates/logic/graph.py

class TopNode(LogicalCircuitNode):
    """The top node representing True in the logic circuit."""