finiding min in array till satisfies condition explained in prbm stmnt

[tosh123]

hello.
i have a set of 50 points. (array of 50 objects (arrayOfNodes[]) having x, y locations and distance and nearest neighbor and neighbor table ). The points are given X-Y location randomly in a range of 300 X300. and there is a center point called BaseStaion (BS). For every point A, I have a neghbor table (array of int) where if the other point B is in range of 50mts then its a neighbor of A, so value in (arrayOfNodes[A].neighborTable) is set to distance of point B to BS for all other points value is set to 9999. From this neighbor table I want to find a nearest neighbor (any point that is neighbor of A and its distance from BS is minimum). So the code finds that fine. But there are some cases where 2 points are nearest neighbors of each other. I dont want that to happen. so I need to find the next neighbor wich can be closer to the BS amongst teh other points. I wrote a code to find the second min in array but at times even the point at second minimum are neighbore of each other. So i have to look into many neighbors to decide the next nearest one!. I am not able to figure that out.

I am attaching some part of code here. Sorry! my problem description can be weird. Please let me know if i can make myself more clear.

// set the vlaues in nebor table
  for (int i = 0; i < noOfNodes; i++)
    {
        for (int j =0; j<noOfNodes; j++)
        {
            if(i==j)
               arrayOfNodes[i].neighborTable[j] = 9999;       //self node   
            else  
               if (euclideanDistance(arrayOfNodes[i].xLocation, arrayOfNodes[j].xLocation, arrayOfNodes[i].yLocation,arrayOfNodes[j].yLocation) < txRange)
                  arrayOfNodes[i].neighborTable[j] = arrayOfNodes[j].distance;     
                                              // if neighbor node, save distance from BS
               else 
                  arrayOfNodes[i].neighborTable[j] = 9999;     // not neighbor  
        }//end of for j
    }//end of for i

    //find the neighbor closest to the BS and set it as nearestNeigborNode
  
    for (int i = 0; i < noOfNodes; i++)
    {

/* for some nodes wich are in range of 50 from BS, their nearest nebor is set to BS. Did that in some other part of code */

        if (arrayOfNodes[i].nearestNeighborNode != baseStation.nodeID) 
        {
          int minValue = arrayOfNodes[i].neighborTable[0];
          for (int j =1; j<noOfNodes; j++)
              {
                  if (arrayOfNodes[i].neighborTable[j] < minValue)
                    {
                     minValue = arrayOfNodes[i].neighborTable[j];
                     arrayOfNodes[i].nearestNeighborNode = j;
                     }
              }
    } //end of for i
                                                                                                                                                                                                                                                        
/* I am facing problem here here i want to keep looking recursively for other nebors of A till i find  B such that A and B are not nebors of each other. I did only to find second min, but i might have to look beyond second min. */

//for the case when 2 nodes are nearest neighbors of each other
     for (int i=0;i<noOfNodes;i++)
          for (int j =0 ; j<noOfNodes; j++)
          {
               if ((arrayOfNodes[i].nearestNeighborNode == j)&& (arrayOfNodes[j].nearestNeighborNode == i))
                {     arrayOfNodes[i].neighborTable[j] == 1000;
                                 
                      int minValue2 = arrayOfNodes[i].neighborTable[0];
                      for (int k =1; k<noOfNodes; k++)
                      {
                          if (arrayOfNodes[i].neighborTable[k] < minValue2)
                              {
                                   minValue2 = arrayOfNodes[i].neighborTable[k];
                                   arrayOfNodes[i].nearestNeighborNode = k;
                              }
                      } //end of for k
                      }//end of if
           } 
     }//end of if (arrayOfNodes[i].nearestNeighborNode = baseStation.nodeID     */
    } // end of i for nearest neighbor

[Lerner]

How about if you sort the neighbors by distance. Then search the array from closest to furthest looking for closest unique distance determined something like this:

WARNING: Following snippett not rigorously tested

type neighbors[capacity]
int size = number of neighbors
for(i = 0; i < size - 1; ++i)
{
  if(neighbors[i] == neighbors[i + 1])
    while((i < size - 1) && (neighbors[i] == neighbors[i + 1]))
        ++i;
  else
      indexOfClosestUniqueNeighbor = i;
      break;
}
if((i == size -1) && (neighbors[i] != neighbors[i - 1]))
   indexOfClosestUniqueNeighbor = i;
else
   cout << "no unique closest Neighbor"

[VernonDozier]

I'm trying to make sense of this. Can you post the Node struct and your declarations of the BaseStation variable and the arrayOfNodes array?

[tosh123]

I'm trying to make sense of this. Can you post the Node struct and your declarations of the BaseStation variable and the arrayOfNodes array?

class node {
public:
       int nodeID;
       int xLocation; //for the xy coordinates of the node
       int yLocation;
       float energyLevelOfNode; 
       int hopCount;
       float distance; // distance of node form the base station  
       int routeTable[][2];
       int nearestNeighborNode;
       int neighborTable [1000];  // saves the distance of neighbore node from BS. inorder to calc the nearest neighbor
      // int sendPacket();
       int neighborNode;

// initialization
node (){
     xLocation = 100;
     yLocation = 100; 
     hopCount = 0; 
     distance = 0.0;
     energyLevelOfNode = 1000.0;// this value is just for the Base station. will reset for all the other nodes
     nodeID = 1000; //this value for BS. will set for other nodes
     }
};  /*End of Class*/

 node arrayOfNodes[1000], baseStation;

[tosh123]

How about if you sort the neighbors by distance. Then search the array from closest to furthest looking for closest unique distance determined something like this:

WARNING: Following snippett not rigorously tested

type neighbors[capacity]
int size = number of neighbors
for(i = 0; i < size - 1; ++i)
{
  if(neighbors[i] == neighbors[i + 1])
    while((i < size - 1) && (neighbors[i] == neighbors[i + 1]))
        ++i;
  else
      indexOfClosestUniqueNeighbor = i;
      break;
}
if((i == size -1) && (neighbors[i] != neighbors[i - 1]))
   indexOfClosestUniqueNeighbor = i;
else
   cout << "no unique closest Neighbor"

Thanks a lot! I really appreaciate your efforts. But I have some dbts -
The index of the array neighborTable[] is important as it reflects the node. So in that case if have to sort this array then how do i retain the original indices? Do i keep make it a 2D array and store the index as well as distance? how do i sort in thsi case?

secondly- the distances are not same. So even if i sort the nebor table of node A and have the index also accordinglyl, when i find the next closest neighbor, i will have to again check if the nearest nebor of that node is not equal to A. i am trying to figure out a way to do that!

any suggestions or inputs are most welcome!
thanks a lot

[tosh123]

How about if you sort the neighbors by distance. Then search the array from closest to furthest looking for closest unique distance determined something like this:

WARNING: Following snippett not rigorously tested

type neighbors[capacity]
int size = number of neighbors
for(i = 0; i < size - 1; ++i)
{
  if(neighbors[i] == neighbors[i + 1])
    while((i < size - 1) && (neighbors[i] == neighbors[i + 1]))
        ++i;
  else
      indexOfClosestUniqueNeighbor = i;
      break;
}
if((i == size -1) && (neighbors[i] != neighbors[i - 1]))
   indexOfClosestUniqueNeighbor = i;
else
   cout << "no unique closest Neighbor"

I think i figured out someway to do this!
if i make nebortable as 2D array where
neighbortable[][1] = distance
neighbortable[][2] = nodeID
Assuming that this array is sorted by distance, i am really not concerned with actual distance value if array is sorted. i am only concerned with corresponding index/nodeID
then

for (int i =0;i<noOfNodes; i++)
for(int j=0;i<noOfNodes;j++)
if(arr.nearestNebor==j)&&(arr[j].nearestnebor==i)&&(i!=j)
{
int k=1;// (as i assume that arr.neborTable[0][2] == arr.nearestnebor==j)
while(arr[arr.neborTable[k][2]].nearestnebor == i)
{
k++;
}

arr.nearestnebor= arr.neborTable[k][2];

}

i hope this will work. not sure though. suggestions welcome
sorry for the complicated code.

[VernonDozier]

I guess this comment doesn't so much address your particular task, but more the design of your class. I think you have too much duplicate storage of distances between Nodes and the base station. In particular, I think having this array as a data member of Node is a bad idea:

int neighborTable [1000];  // saves the distance of neighbore node from BS. inorder to calc the nearest neighbor

This is an array of distances from other nodes to the base stateion. I think it would make sense if it was the distance between the node and some other node, but it isn't:

if the other point B is in range of 50mts then its a neighbor of A, so value in (arrayOfNodes[A].neighborTable) is set to distance of point B to BS for all other points value is set to 9999.

I think you should have each Node store its own distance to the base station. Don't store the distance from Node B to the base station in Node A. It's already stored in Node B:

float distance; // distance of node form the base station

What I think you SHOULD have in Node is a list of neighbor nodes. That could be a boolean array that is true if the Node in the corresponding arrayOfNodes index is a neighbor to this Node. Or it could a linked list of pointers to neighbor nodes. Or something. But somehow keep a list of neighbors so that you can reference a neighbor Node. Then reference that Node and get the "distance" data member from that neighbor Node. That's better than storing the same distances in a whole bunch of Nodes when it only needs to be stored once.

[tosh123]

I guess this comment doesn't so much address your particular task, but more the design of your class. I think you have too much duplicate storage of distances between Nodes and the base station. In particular, I think having this array as a data member of Node is a bad idea:

int neighborTable [1000];  // saves the distance of neighbore node from BS. inorder to calc the nearest neighbor

This is an array of distances from other nodes to the base stateion. I think it would make sense if it was the distance between the node and some other node, but it isn't:

I think you should have each Node store its own distance to the base station. Don't store the distance from Node B to the base station in Node A. It's already stored in Node B:

float distance; // distance of node form the base station

What I think you SHOULD have in Node is a list of neighbor nodes. That could be a boolean array that is true if the Node in the corresponding arrayOfNodes index is a neighbor to this Node. Or it could a linked list of pointers to neighbor nodes. Or something. But somehow keep a list of neighbors so that you can reference a neighbor Node. Then reference that Node and get the "distance" data member from that neighbor Node. That's better than storing the same distances in a whole bunch of Nodes when it only needs to be stored once.

I know i have plenty of duplicate storage. But i did not want to use pointers. And I wanted to maintain a nebor table of every node wherein in need to know the distance of that nebor from the BS so that i get a nebor nearest to BS called nearestNeighborNode. i am doing this by simply finding a min in the neborTable array. So i thot that storing this way wud make simpler with the downside of duplicate storage. Wat i basically want to find is how many nodes i need from a node A to reach the BS.

Thanks for your comments.

[VernonDozier]

I know i have plenty of duplicate storage. But i did not want to use pointers. And I wanted to maintain a nebor table of every node wherein in need to know the distance of that nebor from the BS so that i get a nebor nearest to BS called nearestNeighborNode. i am doing this by simply finding a min in the neborTable array. So i thot that storing this way wud make simpler with the downside of duplicate storage. Wat i basically want to find is how many nodes i need from a node A to reach the BS.

Thanks for your comments.

O.K. That's fine. It's doable without pointers. The extra storage won't kill you. I would make neighborTable type float though since "distance" in Node is type float.

You have an array of integers called neighborTable. One of them contains your the distance from your nearest neighbor to the base station. nearestNeighborNode is the index of the neighbor that is closest to the base station.

nearestNeighborNode = -1; // initialize to bogus value;
int shortestDistance = 10000; // initialize to bogus value;
for (int i = 0; i < numNodes; i++)
{
     // compare distance of node i to base
     // to shortestDistance.  If less than,
     // set shortestDistance to the distance to
     // base from node i and set
     // nearestNeighorNode to i
}
// nearestNeighborNode is now set.

[tosh123]

O.K. That's fine. It's doable without pointers. The extra storage won't kill you. I would make neighborTable type float though since "distance" in Node is type float.

You have an array of integers called neighborTable. One of them contains your the distance from your nearest neighbor to the base station. nearestNeighborNode is the index of the neighbor that is closest to the base station.

nearestNeighborNode = -1; // initialize to bogus value;
int shortestDistance = 10000; // initialize to bogus value;
for (int i = 0; i < numNodes; i++)
{
     // compare distance of node i to base
     // to shortestDistance.  If less than,
     // set shortestDistance to the distance to
     // base from node i and set
     // nearestNeighorNode to i
}
// nearestNeighborNode is now set.

thanks...now if u can refer to my earlier posts...inorder to solve my original Q, I might have to sort this neighbortable in ascending order based on distance. and also maintain the index(as it refers to the nodeID) . To do this now I will have to make neborTable as a 2 D array
neighbortable[][1] = distance
neighbortable[][2] = nodeID

how do i sort this array on distance?

[VernonDozier]

thanks...now if u can refer to my earlier posts...inorder to solve my original Q, I might have to sort this neighbortable in ascending order based on distance. and also maintain the index(as it refers to the nodeID) . To do this now I will have to make neborTable as a 2 D array
neighbortable[][1] = distance
neighbortable[][2] = nodeID

how do i sort this array on distance?

I think the above design would be an odd way of defining a 2-D array using this problem. In particular, if you change distance to a float to make it match your other distance declaration, the above declaration wouldn't work at all. Instead, two one-dimensional arrays would be better:

float distance[50];
int    nodeId[50];

Your choice of how to sort is independent of how you set this up. I can't picture it as a 2-D array, so I can't comment on that. If it was two one-dimensional arrays, you'd pick a sorting algorithm like Bubble Sort and use it on distance. Any swaps you might make with whatever algorithm you use, you would need to swap the elements in both node and distance vectors since distance and nodeId are paired data arrays. Thus I would prefer a struct. It gets rid of the potential for accidentally having the distance and nodeId array indexes no longer correspond to each other correctly

struct nodeDistance
{
     int nodeIndex;
     float distToBase;
};

Change neighborTable to a one dimensional array of type distToBase. Sort on distToBase. When you swap, don't swap distToBase. Swap the entire nodeDistance objects. Not sure what algorithm you are using to sort. BubbleSort is easiest.

[tosh123]

I think the above design would be an odd way of defining a 2-D array using this problem. In particular, if you change distance to a float to make it match your other distance declaration, the above declaration wouldn't work at all. Instead, two one-dimensional arrays would be better:

float distance[50];
int    nodeId[50];

Your choice of how to sort is independent of how you set this up. I can't picture it as a 2-D array, so I can't comment on that. If it was two one-dimensional arrays, you'd pick a sorting algorithm like Bubble Sort and use it on distance. Any swaps you might make with whatever algorithm you use, you would need to swap the elements in both node and distance vectors since distance and nodeId are paired data arrays. Thus I would prefer a struct. It gets rid of the potential for accidentally having the distance and nodeId array indexes no longer correspond to each other correctly

struct nodeDistance
{
     int nodeIndex;
     float distToBase;
};

Change neighborTable to a one dimensional array of type distToBase. Sort on distToBase. When you swap, don't swap distToBase. Swap the entire nodeDistance objects. Not sure what algorithm you are using to sort. BubbleSort is easiest.

hey thanks!!
I have a dbt? how will i swap the nodeDistance Object?
i mean every Node will have one struct nodeDistance. and i want to sort the arr distToBase[] in that struct. and as i swap distance similarly i have to swap the nodeIndex also. so i think it will be again a problem of 2 single D arrays only that by putting it in struct we can have float n int arrays together. actually i earlier interpreted ur solution as making arrayOfStructnodeDistance[100] and swapping the array based on arrayOfStructnodeDistance[].distToBase[]. but i think thats not the case -

so will it look like ?

struct nodeDistance
{
int nodeIndex[1000];
float distToBase[1000];
};

correct me if i am wrong

[VernonDozier]

Please note a typo in my prior post.

struct nodeDistance
{
     int nodeIndex;
     float distToBase;
};

Change neighborTable to a one dimensional array of type distToBase. Sort on distToBase. When you swap, don't swap distToBase. Swap the entire nodeDistance objects. Not sure what algorithm you are using to sort. BubbleSort is easiest.

The word in red above should be nodeDistance, not distToBase.

[VernonDozier]

hey thanks!!
I have a dbt? how will i swap the nodeDistance Object?
i mean every Node will have one struct nodeDistance. and i want to sort the arr distToBase[] in that struct. and as i swap distance similarly i have to swap the nodeIndex also. so i think it will be again a problem of 2 single D arrays only that by putting it in struct we can have float n int arrays together. actually i earlier interpreted ur solution as making arrayOfStructnodeDistance[100] and swapping the array based on arrayOfStructnodeDistance[].distToBase[]. but i think thats not the case -

so will it look like ?

struct nodeDistance
{
int nodeIndex[1000];
float distToBase[1000];
};

correct me if i am wrong

No, it will not look like that. At the top of the file, above where you define your class, you'll have this:

struct nodeDistance
{
     int nodeIndex;
     float distToBase;
};

Within your Node class, you'll have this:

class node {
public:
       int nodeID;
       int xLocation; //for the xy coordinates of the node
       int yLocation;
       float energyLevelOfNode; 
       int hopCount;
       float distance; // distance of node form the base station  
       int routeTable[][2];
       int nearestNeighborNode;
       nodeDistance neighborTable [1000];  // saves the distance of neighbore node from BS. inorder to calc the nearest neighbor
      // int sendPacket();
       int neighborNode;

// initialization
node (){
     xLocation = 100;
     yLocation = 100; 
     hopCount = 0; 
     distance = 0.0;
     energyLevelOfNode = 1000.0;// this value is just for the Base station. will reset for all the other nodes
     nodeID = 1000; //this value for BS. will set for other nodes
     }
};  /*End of Class*/

 node arrayOfNodes[1000], baseStation;

Note line 11:

nodeDistance neighborTable [1000];

"nodeDistance" was "int" before this change.

So say you have five Nodes, not including the base station. The first number is the array index of neighborTable. Make the second number the index of arrayOfNodes that represents the Node, and the third number the distance from the base station. This is what is in the node 1's neighborTable array, which is an array of 5 elements of type nodeDistance with indexes of 0 to 4 (leftmost number).

0 0 100.00
1 1 150.00
2 2 40.00
3 3 25.00
4 4 60.00

Let's say the node in question is node 1 and that nodes 0, 3, and 4 are neighbors of node 1. Node 2 is not a neighbor of node 1. The above is the neighborTable array of node 1. It assigns 9999.0 to itself and all non-neighbors, as follows:

0 0 100.00
1 1 9999.00
2 2 9999.00
3 3 25.00
4 4 60.00

It then sorts this array by nodeDistance:

0 3 25.00
1 4 60.00
2 0 100.00
3 1 9999.00
4 2 9999.00

The closest neighbor of node 1 is in

arrayOfNodes[1].neighborTable[0]

, which is this:

0 3 25.00

So node 1's neighbor that is nearest the base station is this:

arrayOfNodes[1].neighborTable[0].nodeIndex

which is 3. The distance from node 3 to the base station is 25.00, which was the shortest distance of node 1's three neighbors.

Again, I don't think this is a good way to set up your class members, but since you have decided to stick with this neighborTable array storing distances from other nodes to the base station and have decided not to use pointers, that's what I had in mind to keep it close to what you intended.

Also keep this in mind. I am not sure, but all you may need to do is find the minimum. You may not have to sort this at all, just find the minimum, so there may be no need for any swaps at all. I don't know if this neighbor array is ever going to be used again or if it has to be in order or not. Sorting may actually be overkill, but sorting WILL also find the minimum distance too, as well as its corresponding index.

[tosh123]

No, it will not look like that. At the top of the file, above where you define your class, you'll have this:

struct nodeDistance
{
     int nodeIndex;
     float distToBase;
};

Within your Node class, you'll have this:

class node {
public:
       int nodeID;
       int xLocation; //for the xy coordinates of the node
       int yLocation;
       float energyLevelOfNode; 
       int hopCount;
       float distance; // distance of node form the base station  
       int routeTable[][2];
       int nearestNeighborNode;
       nodeDistance neighborTable [1000];  // saves the distance of neighbore node from BS. inorder to calc the nearest neighbor
      // int sendPacket();
       int neighborNode;

// initialization
node (){
     xLocation = 100;
     yLocation = 100; 
     hopCount = 0; 
     distance = 0.0;
     energyLevelOfNode = 1000.0;// this value is just for the Base station. will reset for all the other nodes
     nodeID = 1000; //this value for BS. will set for other nodes
     }
};  /*End of Class*/

 node arrayOfNodes[1000], baseStation;

Note line 11:

nodeDistance neighborTable [1000];

"nodeDistance" was "int" before this change.

So say you have five Nodes, not including the base station. The first number is the array index of neighborTable. Make the second number the index of arrayOfNodes that represents the Node, and the third number the distance from the base station. This is what is in the node 1's neighborTable array, which is an array of 5 elements of type nodeDistance with indexes of 0 to 4 (leftmost number).

0 0 100.00
1 1 150.00
2 2 40.00
3 3 25.00
4 4 60.00

Let's say the node in question is node 1 and that nodes 0, 3, and 4 are neighbors of node 1. Node 2 is not a neighbor of node 1. The above is the neighborTable array of node 1. It assigns 9999.0 to itself and all non-neighbors, as follows:

0 0 100.00
1 1 9999.00
2 2 9999.00
3 3 25.00
4 4 60.00

It then sorts this array by nodeDistance:

0 3 25.00
1 4 60.00
2 0 100.00
3 1 9999.00
4 2 9999.00

The closest neighbor of node 1 is in

arrayOfNodes[1].neighborTable[0]

, which is this:

0 3 25.00

So node 1's neighbor that is nearest the base station is this:

arrayOfNodes[1].neighborTable[0].nodeIndex

which is 3. The distance from node 3 to the base station is 25.00, which was the shortest distance of node 1's three neighbors.

Again, I don't think this is a good way to set up your class members, but since you have decided to stick with this neighborTable array storing distances from other nodes to the base station and have decided not to use pointers, that's what I had in mind to keep it close to what you intended.

Also keep this in mind. I am not sure, but all you may need to do is find the minimum. You may not have to sort this at all, just find the minimum, so there may be no need for any swaps at all. I don't know if this neighbor array is ever going to be used again or if it has to be in order or not. Sorting may actually be overkill, but sorting WILL also find the minimum distance too, as well as its corresponding index.

hey thanks for this!!
1. I actually had made the declaration like this - I defined the struct in the class declaration itself and then assiged that array

class node{
public:
       int nodeID;
       int xLocation; //for the xy coordinates of the node
       int yLocation;
       float energyLevelOfNode; 
       int hopCount;
       float distance; // distance of node form the base station  
       int routeTable[][2];
       int nearestNeighborNode;
     //  int neighborTable [1000];  // saves the distance of neighbore node from BS. inorder to calc the nearest neighbor
     
     struct neighbor {
            
            float distanceToBS;
            int nodeIndex;
            } neighborTable[1000];

      // int sendPacket();
      ...........

IS this also not the correct way to do this?
Secondly,
for all the nodes first I just find the min value of distance and assign the respective nodeIndex as nearest neighbor.

for (int i = 0; i < noOfNodes; i++)
    {
        if (arrayOfNodes[i].nearestNeighborNode != baseStation.nodeID)
        {
          float minValue = arrayOfNodes[i].neighborTable[0].distanceToBS;
          for (int j =1; j<noOfNodes; j++)
              {
                  if (arrayOfNodes[i].neighborTable[j].distanceToBS < minValue)
                    {
                     minValue = arrayOfNodes[i].neighborTable[j].distanceToBS;
                     arrayOfNodes[i].nearestNeighborNode = j; 
                      //j= arrayOfNodes[i].neighborTable[j].nodeIndex 
                     }
              }
    } //end of for i

This saves me from teh overhead of sorting all the neighborTable arrays.
But there are cases when 2 nodes will refer each others as nearestNebors. This cauese infinte loop in the recursive loop which i have later. So i dont want that to happen.
So i would sort the neborTable array only for such 'special cases.' Earlier i was taking the index of second min as my nearestNebor B, but at times both A and B still are mutual nearestNebor so i need to look for another nearestNebor....there for i will walk thru the sorted array till i find the needed nearestNebor

for (int i=0;i<noOfNodes;i++)
   for (int j =0 ; j<noOfNodes; j++)
   {
   if((arrayOfNodes[i].nearestNeighborNode == j)&& (arrayOfNodes[j].nearestNeighborNode == i)&&(i!=j))
{
                     
 // FIRST SORT THE NEIGHBOR TABLE  based on the distance  that code goes here. i used bubble sort     
           
int temp;             // holding variable
int arrayLength = arrayOfNodes[i].neighborTable[j].length(); 
for(int m = 1; (m <= arrayLength) ; m++)
     for (int n=0; n < (arrayLength -1); n++)
        if (arrayOfNodes[m].neighborTable[n+1].distanceToBS < arrayOfNodes[m].neighborTable[n].distanceToBS)          
 { 
          temp = arrayOfNodes[m].neighborTable[n];             // swap elements
          arrayOfNodes[m].neighborTable[n] = arrayOfNodes[m].neighborTable[n+1];
          arrayOfNodes[m].neighborTable[n+1] = temp;
   }                                              
     
// used arr instead of arrayOfNodes :)
int k=1;// (as i assume that arr[i].neborTable[k==0].nodeIndex == arr[i].nearestnebor==j)  
while(arr[arr[i].neborTable[k].nodeIndex].nearestnebor == i) 
{
k++;
}
arr[i].nearestnebor= arr[i].neborTable[k].nodeIndex;

}

in this while loop it will increment k till the nebors dont refer each other. I havent yet compiled my code yet so not sure if this works really! but the logic looks straight atleast to me!! comments welcome!!

And thanks for all your posts. I really appreciate your efforts!

[VernonDozier]

I think you'll need to post your entire code for people to get a feel for it. For example, you've defined a struct called "neighbor", but do you ever use it? If so, I don't see it anywhere, so I can't give an opinion on whether it's a good setup.

As far as ties for nearest neighbor, that shouldn't be a problem. If two neighbor nodes are the same distance from the base station, pick one of them or the other and assign it as the nearest neighbor. It seems to me that you need to do this (in this order):

1. Figure out how many nodes you have, set up your arrayOfNodes array for that many nodes. Also, pick a base station. Decide whether that base station is also in arrayOfNodes.

2. For all nodes, fill in their (x, y) coordinates and fill in that node's xCoordinate and yCoordinate data member values with those numbers.

3. For all nodes, calculate their distance from the base station and put that in distance.

4. You've decided to, within each node in arrayOfNodes, keep an array of all of the distances between every node and the base station. Create this array and fill in that distance array for every node by referring to the numbers calculated in step 3.

5. For every node in arrayOfNodes, go through the above array from step 4. For each node in that array, decide whether that node is a neighbor. If so, keep the distance for that node the same as it was before. If not, change the distance to 9999.00. Also, check if that node is yourself. If so, change it to 9999.0

6. With the above array from step 5, sort it by distance to base station. If you don't want to sort, just find the minimum distance. Figure out the array index that goes along with that minimum distance. Put that array index into the data attribute within node called nearestNeighborNode. If there are any ties, just pick one of the nodes with the minimum distance as the nearest neighbor.

Not sure what you want to do with all of this, but by the end of the above process, every node will have an accurate nearestNeighborNode stored in it, from the way you have defined nearest neighbor. Looks like you are trying to calculate the shortest path from each node to the base station, hopping from node to node to node to get there and want to use nearestNeighborNode to help you do that.

There are numerous ways of setting the above up, but regardless, from the way you've described things and the way you've described how you want to approach it, I think the six steps above should be your game plan. The important thing is to think of a way that is consistent and can do all of the above.

Again, can't comment on the code since I can't get my hands around it without seeing the whole program.

[tosh123]

I think you'll need to post your entire code for people to get a feel for it. For example, you've defined a struct called "neighbor", but do you ever use it? If so, I don't see it anywhere, so I can't give an opinion on whether it's a good setup.

As far as ties for nearest neighbor, that shouldn't be a problem. If two neighbor nodes are the same distance from the base station, pick one of them or the other and assign it as the nearest neighbor. It seems to me that you need to do this (in this order):

1. Figure out how many nodes you have, set up your arrayOfNodes array for that many nodes. Also, pick a base station. Decide whether that base station is also in arrayOfNodes.

2. For all nodes, fill in their (x, y) coordinates and fill in that node's xCoordinate and yCoordinate data member values with those numbers.

3. For all nodes, calculate their distance from the base station and put that in distance.

4. You've decided to, within each node in arrayOfNodes, keep an array of all of the distances between every node and the base station. Create this array and fill in that distance array for every node by referring to the numbers calculated in step 3.

5. For every node in arrayOfNodes, go through the above array from step 4. For each node in that array, decide whether that node is a neighbor. If so, keep the distance for that node the same as it was before. If not, change the distance to 9999.00. Also, check if that node is yourself. If so, change it to 9999.0

6. With the above array from step 5, sort it by distance to base station. If you don't want to sort, just find the minimum distance. Figure out the array index that goes along with that minimum distance. Put that array index into the data attribute within node called nearestNeighborNode. If there are any ties, just pick one of the nodes with the minimum distance as the nearest neighbor.

Not sure what you want to do with all of this, but by the end of the above process, every node will have an accurate nearestNeighborNode stored in it, from the way you have defined nearest neighbor. Looks like you are trying to calculate the shortest path from each node to the base station, hopping from node to node to node to get there and want to use nearestNeighborNode to help you do that.

There are numerous ways of setting the above up, but regardless, from the way you've described things and the way you've described how you want to approach it, I think the six steps above should be your game plan. The important thing is to think of a way that is consistent and can do all of the above.

Again, can't comment on the code since I can't get my hands around it without seeing the whole program.

hey WOW!
you have written down the entire algo for my code.
This is my exact game plan!!! and theres much more to it. which i am still building.

and the struct neighbor is actually the struct nodeDistance form ur code and i have neighborTable as array of struct neighbor/nodeDistance which i use later to find the nearest neighbor. and abt the ties in case of nearestneighbors, they are not ties based of distance.
ties based on nodes referring each other as there nearest nebors. So for that just finding the min value dosent help. i need to sort. atleast thats wat i feel.

thanks for all your help. and sorry i will not be able to post the entire code here. its part of some project. and you might see me here now on with some more dbts with another part of my code. :)

[VernonDozier]

hey WOW!
you have written down the entire algo for my code.
This is my exact game plan!!! and theres much more to it. which i am still building.

and the struct neighbor is actually the struct nodeDistance form ur code and i have neighborTable as array of struct neighbor/nodeDistance which i use later to find the nearest neighbor. and abt the ties in case of nearestneighbors, they are not ties based of distance.
ties based on nodes referring each other as there nearest nebors. So for that just finding the min value dosent help. i need to sort. atleast thats wat i feel.

thanks for all your help. and sorry i will not be able to post the entire code here. its part of some project. and you might see me here now on with some more dbts with another part of my code. :)

Ah, OK, I see the issue with the ties a little better now. You're calculating routes to the base station and you are concerned about two neighbors continually going back and forth to each other in the hopes of getting closer to the base station, but they'll never get there because each thinks the other is closer and so they just keeping going back and forth.

It might be worth checking out this link and the links that IT links to. Might give you some ideas on organization beyond the six steps I listed. In your case, a "path" exists between any two nodes that are neighbors. The "cost" of taking that path will have to do with the distance between those two nodes, I imagine. Anyway, these algorithms may be useful to you. Good luck.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

[tosh123]

Ah, OK, I see the issue with the ties a little better now. You're calculating routes to the base station and you are concerned about two neighbors continually going back and forth to each other in the hopes of getting closer to the base station, but they'll never get there because each thinks the other is closer and so they just keeping going back and forth.

It might be worth checking out this link and the links that IT links to. Might give you some ideas on organization beyond the six steps I listed. In your case, a "path" exists between any two nodes that are neighbors. The "cost" of taking that path will have to do with the distance between those two nodes, I imagine. Anyway, these algorithms may be useful to you. Good luck.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

yes....thats wat i am trying to do finding kindof shortest path to BS. By using the code, above i am able to solve the problem locally of not have loops like A and B referring to each other. But when i saw the output more clearly i found that somewhere down the line teh problem still exists. like
A-B-C-D-E-A

so in this case also the recusion fails.
so i think i will have to use some of the std. routing algos now. but i do not want to use any of them

i think i will use
Floyd's All Pairs Shortest Path Algorithm
http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5119//

yet to figure out how this works? never worked much with pointers...

[tosh123]

yes....thats wat i am trying to do finding kindof shortest path to BS. By using the code, above i am able to solve the problem locally of not have loops like A and B referring to each other. But when i saw the output more clearly i found that somewhere down the line teh problem still exists. like
A-B-C-D-E-A

so in this case also the recusion fails.
so i think i will have to use some of the std. routing algos now. but i do not want to use any of them

i think i will use
Floyd's All Pairs Shortest Path Algorithm
http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5119//

yet to figure out how this works? never worked much with pointers...

Can u shed some light on how they use the pointers in the code in the above link.
I am not really able to guess what is this declaration?

int *C=new int[n*n];

also
if ( *(C+i*n+j) == 0)

thanks

[VernonDozier]

Can u shed some light on how they use the pointers in the code in the above link.
I am not really able to guess what is this declaration?

int *C=new int[n*n];

also
if ( *(C+i*n+j) == 0)

thanks

There are lots of tutorials on pointers out there and a whole lot of people who know the subject better and can explain it far better than I can. Here is one such person:

http://www.daweidesigns.com/cgi-bin/pointers.php

Here are some others:

http://www.softwareacademy.de/cpplernen/?cpp=Arrays,+Pointers+and+References&ziel=Pointer+Arithmetic
http://www.cprogramming.com/tutorial/lesson6.html

I'm guessing I can't explain it as well as the people who wrote these links can or some of the other people on this forum can. Basically in this line:

int *C=new int[n*n];

1. n * n is simply multiplying n times itself, so * is the multiplication operator here.
2. int[n * n] would be int[100] if n = 10. So you're talking about an array of 100 integers.
3. The word "new" is telling the compiler to set aside space for 100 integers.
4. int* C means that C "points to" the address of the first element of the array of 100 integers.

I'm hoping I didn't say anything that was technically untrue in number 4 above. DaWei, the person who wrote the first link, makes a distinction between a pointer and an array that is worth reading.

if ( *(C+i*n+j) == 0)

i * n + j is an "offset" from the address C and is a type of "pointer arithmetic". See the links above and others for tutorials on pointer arithmetic. The first * in:

*(C + i * n + j)

is the "dereferencing operator". The second * is the multiplication operator.

Check out those links and many others out there. If those lines don't make sense afterwards, it might be worth starting a new thread on Daniweb on that topic.

[tosh123]

There are lots of tutorials on pointers out there and a whole lot of people who know the subject better and can explain it far better than I can. Here is one such person:

http://www.daweidesigns.com/cgi-bin/pointers.php

Here are some others:

http://www.softwareacademy.de/cpplernen/?cpp=Arrays,+Pointers+and+References&ziel=Pointer+Arithmetic
http://www.cprogramming.com/tutorial/lesson6.html

I'm guessing I can't explain it as well as the people who wrote these links can or some of the other people on this forum can. Basically in this line:

int *C=new int[n*n];

1. n * n is simply multiplying n times itself, so * is the multiplication operator here.
2. int[n * n] would be int[100] if n = 10. So you're talking about an array of 100 integers.
3. The word "new" is telling the compiler to set aside space for 100 integers.
4. int* C means that C "points to" the address of the first element of the array of 100 integers.

I'm hoping I didn't say anything that was technically untrue in number 4 above. DaWei, the person who wrote the first link, makes a distinction between a pointer and an array that is worth reading.

if ( *(C+i*n+j) == 0)

i * n + j is an "offset" from the address C and is a type of "pointer arithmetic". See the links above and others for tutorials on pointer arithmetic. The first * in:

*(C + i * n + j)

is the "dereferencing operator". The second * is the multiplication operator.

Check out those links and many others out there. If those lines don't make sense afterwards, it might be worth starting a new thread on Daniweb on that topic.

hey thanks..
i was not much aware of pointer arithmetics till now..
the links u gave helped..
i pretty much understood the Floyds algo.
but it is supposed to give the shortest path between all the pairs of points
but when i run the same code for my 50 points, the output which i am getting is like

path from 1to 2is 16,2
path from 1to 3is
path from 1to 4is 39,6,34,4
path from 1to 5is
path from 1to 6is 39,6
path from 1to 7is
path from 1to 8is 8
path from 1to 9is
path from 1to 10is
path from 1to 11is
path from 1to 12is 12
path from 1to 13is
path from 1to 14is 12,14
path from 1to 15is
path from 1to 16is 16
path from 1to 17is 17
path from 1to 18is 16,18
path from 1to 19is 39,6,34,4,40,48,19
path from 1to 20is
path from 1to 21is
path from 1to 22is
path from 1to 23is

and so on.

I am not sure why some of the paths are not mentioned there?
any idea?