0
$\begingroup$

Suppose i want to check if my position is enclosed in a closed loop by following the connection of waypoints that surround it:

enter image description here

Now if i travel from node 0 to node 1. I'm at node 1 and i need to find the next connection of which as you can see i have multiple choices this time.

I can rule out where i came from quite easily, but that still leaves me with other options. How can I optimally pick which connection to follow next based on knowing that the connection from node 1 to node 2 is the only allowed option here anyway since as it's an enclosed loop you can consider them equivalent to being walls. I just am not sure how to check which is the most viable choice next logically speaking.

If node 1 to node 2 connection didn't exist, naturally the first logical choice would be to just go straight on ahead which is easy to tell visually just not so easy when thinking in code.

$\endgroup$

1 Answer 1

1
$\begingroup$

It seems that you are trying to construct a Eulerian circuit in your network. First, check that every node has an even number of incident edges, otherwise there will not be a Eulerian circuit. Then, use Hierholzer's algorithm to find the Eulerian circuit.

Roughly speaking, you don't need to check anything, you just pick any unused edge from the current node $v$, and sooner or later you will be forced to come back to $v$. However, this might leave out some edges of the network, so in case you want to cover them all, you have to start a new circuit from a node that you already reached and "paste it in" your old circuit.

$\endgroup$
1
  • $\begingroup$ I disagree with your second paragraph, imagine connections kinda like walls more than traversal paths. There's never a situation where I would need to be picking any edge and hope for the best. In the image travelling from 0 to 1,there is only on option any other direction is blocked by the 2 - > 1 connecting wall. So there must be a logical way to deudce that rather than traversal over many edges because the rest are immediately impossible to reach anyway. $\endgroup$
    – WDUK
    Jun 27, 2021 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.