# When modeling a virtual circuit board, what is the best design pattern to check for cycles?

To make it simple assume you have only AND and OR gates. Each has two inputs and one output. The output of two inputs can be used as an input for the next gate For example:

A AND B -> E

C AND D -> F

E OR F -> G

Assuming an arbitrary number of gates, we want to check if the circuit ever connects back into itself at an earlier state? For example:

E AND F -> A

This should be illegal since it creates an endless cycle. What design pattern would best be able to check for these cycles?

-
The first time you model a flip-flop, you're going to discover why cycles in logic circuits are not only legal but important. – Blrfl Nov 2 '12 at 14:56

Looks like you are talking about building a directed graph and checking for cycles. This can be done in many ways. The most basic is a topological sort.

-

As @Blrfl pointed out, feedback in logic circuits is extremely useful. The way to deal with it in a model is to add a time component, essentially representing the propagation delay through the gate. For example:

``````A AND B -> B
``````

The way you deal with this is to consider `B` at time `0` and `B` at time `1` as two completely different signals, like:

``````A[0] AND B[0] -> B[1]
``````

This lets you do your calculations without entering an endless loop. Note that in this case you only have to do one iteration to determine the steady state (what it eventually settles down to). If `A` is `1`, `B` won't change from its initial value. If `A` is `0`, then `B` will also change to `0` and stay there.

-
Even on simple combinatorial circuits and using the propagation delay as your time increment, you have to iterate once for every gate between the inputs and the outputs before you come up with something "right." In the OP's case, line G won't be valid for two iterations. Some circuits never reach a stable state: loop the output of a NOR gate back into one input (or both inputs of a NAND) and the output will change state continuously. More complex circuits are clocked to regulate that behavior. – Blrfl Nov 2 '12 at 21:05