Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void Graph::calculateNeighbors()
- {
- unsigned short numberOfNeighbors = NUMBER_OF_NEIGHBORS < numberOfNodes ? NUMBER_OF_NEIGHBORS : numberOfNodes;
- neighbors = std::vector< std::vector<unsigned short> >(numberOfNodes);
- for(unsigned int i = 0; i < numberOfNodes; ++i)
- {
- for(unsigned int j = 0; j < numberOfNodes; ++j)
- {
- if(i == j) //It should not be neighbor with it self
- continue;
- unsigned int dist = getDistance(i,j); //Distance between this node and another
- //If the neighbor list is not yet filled just insert it where it should be
- if(neighbors[i].size() < numberOfNeighbors)
- {
- bool found_place = false;
- //Insertion in correct position
- for(unsigned int k = 0; k < neighbors[i].size(); ++k)
- {
- //We found a place where the city is futher away than this
- if(dist < getDistance(i,neighbors[i][k]))
- {
- neighbors[i].insert(neighbors[i].begin() + k, j);
- found_place = true;
- break;
- }
- }
- //If the list only contains closer cities it should be in the end
- if(!found_place)
- neighbors[i].push_back(j);
- }
- else if(dist < getDistance(i, neighbors[i].back()))//The neighbor list is filled check if the last is futher away
- {
- //Search backwards to find where to place it
- for(unsigned int k = neighbors[i].size() -1 ; k >= 0; --k)
- {
- //We found a place where the city is futher away than this
- if(dist < getDistance(i,neighbors[i][k]))
- {
- neighbors[i].insert(neighbors[i].begin() + k, j);
- //The list now contains one element to much so remove the last
- neighbors[i].pop_back();
- break;
- }
- }
- }
- }
- }
- return;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement