Detecting a loop in logic circuit simulator

Question

I'm trying to write a logic gates circuit simulator and everything is working so far except for one thing. My structure looks like this:

struct node
{
    int number;
    bool has_value;
    bool is_input;
    bool value;
    Gate operation;
    node* input1;
    node* input2;
};

The program calculates output value by using recursion, so any kind of loop inside the structure messes everything up. My question is: How do I detect something like this (see picture) , cause i can't come up with anything that works.

circuit

What I was doing, when I needed to detect loops in some structure, while recursing through it: pass additional `std::set` parameter to recursive function, and then, make that function write the unique identifier (can be anything) of item that is/was processed to said `std::set`, and then pass it down, recursively. If you detect that the item that you are about to process is already in a set, you can know, that it was already processed. — Algirdas Preidžius, Jan 22 '16 at 16:10
The thing is, the circuit you drew is perfectly valid. There are ways of handling this so the simulation still runs as expected - http://stackoverflow.com/questions/14299603/how-to-handle-loops-in-a-digital-logic-simulator — Andrew Williamson, Jan 22 '16 at 16:15
That's what I thought initially but wouldn't something like this also count as a loop with that solution? @AlgirdasPreidžius ![picture](http://oi64.tinypic.com/1zn7ecl.jpg) — fardragon, Jan 22 '16 at 16:19
@fardragon Well, I am not that familiar with logic circuits, so I can't definitively answer this question. What I can say - it all depends on how you choose to traverse a graph, and whether you choose to pass, said `std::set`, around, as a reference, or as a value. — Algirdas Preidžius, Jan 22 '16 at 16:26
@AndrewWilliamson That's interesting. Any idea what should i look for if i want to read more about such circuits? Anyway, I've got a feeling that to implement this I would've to modify a lot of code. I might consider doing it someday, but right now simply detecting such loop should be enough. — fardragon, Jan 22 '16 at 16:51
Sorry, I don't really have any more material than that. I just know of that post because I had to implement a logic simulator in my first year at University, and ran into the same problem :) — Andrew Williamson, Jan 22 '16 at 16:53
@JerryCoffin What if i need to visit single node multiple times, like here node 5 needs to be visited both from 2 and 4 ![example](http://oi64.tinypic.com/1zn7ecl.jpg) — fardragon, Jan 22 '16 at 17:12
@fardragon: What you've highlighted aren't really nodes--they're the arcs. A node is an actual gate. You visit each gate once per clock cycle. You read its current inputs, and update its output accordingly. Reading those inputs (which also the outputs of some other nodes) doesn't mean you visit the nodes that produce those outputs--it just means you read `input1->output` and `input2->output`. — Jerry Coffin, Jan 22 '16 at 17:24

score 1 · Accepted Answer · answered Jan 22 '16 at 17:16

The obvious way to deal with the problem is to include a bool in each node signifying whether that node has been visited yet in the current simulation step.

You'd want to set this to false initially, such as in the constructor.

Then a simulation step would consist of traversing the graph once to clear the flags. You'd do a recursion from a given node if and only if the flag was currently set.

Then you'd run the simulation step. This would proceed roughly the same way, but with the logic reversed. As you visit each node, you check its visited flag. If it's set, you can return immediately (and you've just detected a cycle in the graph). Otherwise, you set the flag, process the inputs for that node (etc.--your usual simulation "stuff"), then do recursive calls to do simulation on its child nodes. If any of them loops back to this one, that call will return immediately (because you've already set the flag), ending that "leg" of recursive calls.

Detecting a loop in logic circuit simulator

1 Answers1