How to represent combinational circuits in code

Question

I'm writing a python program that does some operations on combinational circuits like comparing for equality to other circuits, merging gates, counting gates, counting connections, finding fanout gates,...

Right now im representing the combinational circuits in the following way:
(I also added the testing for equality)

class Circuit:
    def __init__(self):
        self.gates = {}  # key = the gates number, value = the gate

    def __eq__(self, other):
        if set(self.gates.keys()) != set(other.gates.keys()):
            return False
        for key in self.gates.keys():
            if self.gates[key] != other.gates[key]:
                return False
        return True


class Gate:
    def __init__(self, gate_type, number):
        self.gate_type = gate_type  # and, or, nand, nor, xor, xnor
        self.number = number
        self.incoming_gates = []
        self.outgoing_gates = []

    def __eq__(self, other):
        # i know this is not correct, but in my case correct enough
        return (
            self.gate_type == other.gate_type
            and self.number == other.number
            and len(self.incoming) == len(other.incoming)
            and len(self.outgoing) == len(other.outgoing)
        )

My representation in code seems very laborious to me, so I am looking for a better way to do this. I have searched for best practices on this but didn't find anything.

Answer 1

You're looking to implement a directed graph, with certain data stored in vertices. Wikipedia has a discussion of various ways to represent a graph and here's a stackoverflow talking about the more general problem.

For quickly modifying the topology of the graph, and for doing (merging gates, etc) an adjacency list like you have is often useful.

In general I think the test of an architecture is when you actually start to implement it--I'd suspect you'll become very familiar with the benefits and detriments of your design quickly once you get started using it, and be able to adjust or build helper functions as needed.

Answer 2

You could avoid redundancy in the Gate class by only storing the inbound gate references but that would make the rest of your code more complex to implement. I believe the tradeoff of redundancy vs ease of use should weigh in favour of ease of use.

I don't know how you implement the connections between the gates, but if you hold object references in self.incoming_gates / self.outgoing_gates, you can probably define them based only on incoming links and update the source's outgoing_gate list with self automatically (possibly in the constructor itself)