Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / examples / applications / plot_circuits.py @ 5cef0f13

History | View | Annotate | Download (3.39 KB)

1
#!/usr/bin/env python
2
# circuits.py - convert a Boolean circuit to an equivalent Boolean formula
3
#
4
# Copyright 2016 Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>.
5
#
6
# This file is part of NetworkX.
7
#
8
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
9
# information.
10
"""
11
========
12
Circuits
13
========
14

15
Convert a Boolean circuit to an equivalent Boolean formula.
16

17
A Boolean circuit can be exponentially more expressive than an
18
equivalent formula in the worst case, since the circuit can reuse
19
subcircuits multiple times, whereas a formula cannot reuse subformulas
20
more than once. Thus creating a Boolean formula from a Boolean circuit
21
in this way may be infeasible if the circuit is large.
22

23
"""
24
from networkx import dag_to_branching
25
from networkx import DiGraph
26
from networkx.utils import arbitrary_element
27

    
28

    
29
def circuit_to_formula(circuit):
30
    # Convert the circuit to an equivalent formula.
31
    formula = dag_to_branching(circuit)
32
    # Transfer the operator or variable labels for each node from the
33
    # circuit to the formula.
34
    for v in formula:
35
        source = formula.node[v]['source']
36
        formula.node[v]['label'] = circuit.node[source]['label']
37
    return formula
38

    
39

    
40
def formula_to_string(formula):
41

    
42
    def _to_string(formula, root):
43
        # If there are no children, this is a variable node.
44
        label = formula.node[root]['label']
45
        if not formula[root]:
46
            return label
47
        # Otherwise, this is an operator.
48
        children = formula[root]
49
        # If one child, the label must be a NOT operator.
50
        if len(children) == 1:
51
            child = arbitrary_element(children)
52
            return '{}({})'.format(label, _to_string(formula, child))
53
        # NB "left" and "right" here are a little misleading: there is
54
        # no order on the children of a node. That's okay because the
55
        # Boolean AND and OR operators are symmetric. It just means that
56
        # the order of the operands cannot be predicted and hence the
57
        # function does not necessarily behave the same way on every
58
        # invocation.
59
        left, right = formula[root]
60
        left_subformula = _to_string(formula, left)
61
        right_subformula = _to_string(formula, right)
62
        return '({} {} {})'.format(left_subformula, label, right_subformula)
63

    
64
    root = next(v for v, d in formula.in_degree() if d == 0)
65
    return _to_string(formula, root)
66

    
67

    
68
def main():
69
    # Create an example Boolean circuit.
70
    #
71
    # This circuit has a ∧ at the output and two ∨s at the next layer.
72
    # The third layer has a variable x that appears in the left ∨, a
73
    # variable y that appears in both the left and right ∨s, and a
74
    # negation for the variable z that appears as the sole node in the
75
    # fourth layer.
76
    circuit = DiGraph()
77
    # Layer 0
78
    circuit.add_node(0, label='')
79
    # Layer 1
80
    circuit.add_node(1, label='')
81
    circuit.add_node(2, label='')
82
    circuit.add_edge(0, 1)
83
    circuit.add_edge(0, 2)
84
    # Layer 2
85
    circuit.add_node(3, label='x')
86
    circuit.add_node(4, label='y')
87
    circuit.add_node(5, label='¬')
88
    circuit.add_edge(1, 3)
89
    circuit.add_edge(1, 4)
90
    circuit.add_edge(2, 4)
91
    circuit.add_edge(2, 5)
92
    # Layer 3
93
    circuit.add_node(6, label='z')
94
    circuit.add_edge(5, 6)
95
    # Convert the circuit to an equivalent formula.
96
    formula = circuit_to_formula(circuit)
97
    print(formula_to_string(formula))
98

    
99
if __name__ == '__main__':
100
    main()