Joachim Hansen Joachim Hansen - 1 year ago 88
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);
}
}

Answer Source

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