Joachim Hansen - 1 year ago 100
C++ Question

# Can't spot the reason behind infinite loop

I am currently working on a program, that can read a set of coordinates from a file forming a contour and then fill it out using the flood fill algorithm.

It seems that the code below runs in an infinite loop, but i can't seem to spot why.

Help or advice is much appreciated :-)

``````    /* Flood fill */
TargetColour = 0.0;
NewColour = 2.0;
starting_point = 0+slice;

//Create queue
queue < int > MyQue;
//Insert first point into the queue
MyQue.push(starting_point);

//While loop for iterating over the nodes.
while (!MyQue.empty()){
//Take out the front element
Node = MyQue.front();
MyQue.pop();
tmpSlice[Node] = NewColour;

//Define the Node directions
WestNode = Node-1;
EastNode = Node+1;
NorthNode = Node-sizes[1];
SouthNode = Node+sizes[2];

//East Node
if (slab[EastNode] == TargetColour && floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1]) == floor((EastNode-sizes[1]*sizes[2]*floor(EastNode/(sizes[1]*sizes[2])))/sizes[1])){
MyQue.push(EastNode);
}
//West Node
if (slab[WestNode] == TargetColour && floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1]) == floor((WestNode-sizes[1]*sizes[2]*floor(WestNode/(sizes[1]*sizes[2])))/sizes[1])){
MyQue.push(WestNode);
}
//North Node
if (slab[NorthNode] == TargetColour && floor(Node / (sizes[1]*sizes[2])) == floor(NorthNode / (sizes[1]*sizes[2]))){
MyQue.push(NorthNode);
}
//South Node
if (slab[SouthNode] == TargetColour && floor(Node / (sizes[1]*sizes[2])) == floor(SouthNode / (sizes[1]*sizes[2]))){
MyQue.push(SouthNode);
}
}
``````

I'm partly sure that your algorithm is actually terminating, but only after a very long time (assuming there is enough memory for the queue). I'd need more details on the values of `sizes` to be completely sure.

Lets play a little 3x3 example field and assume that the whole `floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1])` is just a boundary check (what is it?).

Field (numbers are the position names):

``````1 2 3
4 5 6
7 8 9
``````

Assume `starting_point = 1`

1. MyQue = { 1 }
• visit 1, add 2 and 4 to MyQue
2. MyQue = { 2, 4 }
• visit 2, add 3 and 5 to MyQue
3. MyQue = { 4, 3, 5 }
• visit 4, add 5 and 7 to MyQue
4. MyQue = { 3, 5, 5, 7 }
• visit 3, add 6 to MyQue
5. MyQue = { 5, 5, 7, 6 }
• visit 5, add 6 and 8 to MyQue
6. MyQue = { 5, 7, 6, 6, 8 }
• visit 5, add 6 and 8 to MyQue
7. MyQue = { 7, 6, 6, 8, 6, 8 }
• visit 7, add 8 to MyQue
8. MyQue = { 6, 6, 8, 6, 8, 8 }
• visit 6, add 9 to MyQue
9. MyQue = { 6, 8, 6, 8, 8, 9 }
• visit 6, add 9 to MyQue
10. MyQue = { 8, 6, 8, 8, 9, 9 }
• visit 8, add 9 to MyQue
11. MyQue = { 6, 8, 8, 9, 9, 9 }
• visit 6, add 9 to MyQue
12. MyQue = { 8, 8, 9, 9, 9, 9 }
• visit 8, add 9 to MyQue
13. MyQue = { 8, 9, 9, 9, 9, 9 }
• visit 8, add 9 to MyQue
14. MyQue = { 9, 9, 9, 9, 9, 9 }
• visit 9
15. MyQue = { 9, 9, 9, 9, 9 }
• visit 9
16. MyQue = { 9, 9, 9, 9 }
• visit 9
17. MyQue = { 9, 9, 9 }
• visit 9
18. MyQue = { 9, 9 }
• visit 9
19. MyQue = { 9 }
• visit 9

I hope this illustrates how the algorithm is going to repeat the same thing very often even for a small field - this effect will increase for bigger field sizes.

So what you can do is ensure that each node is only queued once. I think the evaluation order doesn't really matter, so instead of a `queue` you can use a `set` to store the working set. This will ensure that each number is only queued once at the same time.

You can also combine queue and set so you keep evaluation order.

``````set < int > marker;
queue < int > MyQue;

// ... replace later in code
// MyQue.push(SomeNode);
// by
if (marker.insert(SomeNode).second) {
MyQue.push(SomeNode);
}
``````

Edit: changed the if condition a bit. `marker.insert(SomeNode).second` will be `true` if `SomeNode` was inserted and `false` if `SomeNode` was already part of the set.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download