bug/error in basis set path algorithm i can't figure out

Posted by Roy McAvoy on Stack Overflow See other posts from Stack Overflow or by Roy McAvoy
Published on 2010-03-25T01:30:52Z Indexed on 2010/03/25 1:33 UTC
Read the original article Hit count: 391

Filed under:

The following looks through a 2d array to find basis set paths. It is supposed to print out the individual paths but not repeat any and end when all paths are found. It however doesn't stop at the last path and has a bug in it somewhere in which the following happens: It goes halfway through the path and then goes to zero and ends the path for some reason.

For example the table is filled with the following: all 0s, except for

[1][2], [1][3], [2][4], [2][5], [3][5], [4][6], [5][6], [6][0]

which all have a 1 in them. The desired paths are P1: 1 2 4 6 0

P2: 1 3 5 6 0

P3: 1 2 5 6 0.

The output I get when i run the program is 12460

13560

1250

124

Any and all help on this is much appreciated, this is just the function that scans through the array looking for paths, I can add the entire program if that would be helpful. Thanks..

void find_path(int map[][MAX], int x){
 int path =0;
 int m=1;
 int blah=0;
 bool path_found = false;

 do
 {
  for(int n=0;n<(x+1);n++){
   if(map[m][n]==-1){
    blah=(n+1);
    if(blah<(x+1)){
     for(blah;blah<(x+1);blah++){
      if(map[m][blah]==1){
       map[m][blah]=-1;
       path=m;
       path_found = true;
       cout<<path;
       m=blah;
       n=0;
      }
     }
    }
    else{  
    path=m;
    path_found=false;
    cout<<path;
    m=n;
    if(m==0){
     path=0;
     cout<<path<<endl;
     m=1;
     path_found=false;
     }
    } 
   }
   else if(map[m][n]==1){
    map[m][n]=-1;
    path=m;
    path_found = true;
    cout<<path;
    m=n;
    if(m==0){
     path=0;
     cout<<path<<endl;
     m=1;
     path_found=false;
    }
   }

  }
 } 
 while(m<(x+1) && path_found);
}

© Stack Overflow or respective owner

Related posts about c++