ioftools / networkxMiCe / networkxmaster / 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() 