grasp p-median non random

#include <iostream>
#include <vector>
#include <time.h>
#include <utility>
#include <stdlib.h>
#include <list>
#include <string.h>
#include <map>
#include <limits.h>


#define LIMIT_CONSTRUCTION_VALUE 2100 //limite que poda a matriz de adjacencia
#define LIMIT_NEIGHBORHOOD_FAILURE 5 // limite de falhas na melhoria externa da movimentação de vizinhança
#define INITIAL_MATRIX_CEIL_VALUE 999999 //valores randomicos da matriz vão ser gerados de 1 até este valor
#define GRASP_MAX_ITER 50 // numero de iterações do grasp
#define GRASP_ALPHA_VALUE 0.5 //porcentagem de aleatoriedade do grasp

using namespace std;

typedef vector<vector<int> > vv;
typedef vector<list<pair<int, int> > > vlp; // <node, cost>

//Auxiliar functions:
void print_matrix(vv);
void print_list(vlp);
void print_global_solution(pair<int, vector<int> >);
void print_vec(vector<int> vec);
bool not_in(int, vector<int>);

//algorithm functions:
void fill_matrix(vv &adj, int size){ // preenche a matrix com valores aleatórios, grafo completo e undirected

    srand(time(NULL));
    vector<int> aux(size);
    adj.reserve(size);

    for (int i = 0; i<size; i++) {

        for (int j = i; j<size; j++)
            if (i == j)
                aux[j] = 0;
            else
                aux[j] = rand() % INITIAL_MATRIX_CEIL_VALUE + 1; // valores entre 1 e 50

        adj.push_back(aux);
    }

    for (int i = 0; i < size; i++) {  //espelha o triangulo superior (grafo undirected)
        for (int j = 0; j < size; j++) {
            adj[j][i] = adj[i][j];
        }
    }
}

std::vector< std::vector<int> > readInput()
{
    int route = 0,
        numberInput = 0;

    std::cin >> route;

    std::vector< std::vector<int> > mDistance;

  for (int i = 0; i < route; i++)
  {
      std::vector<int> vTemp;
      for (int j = 0; j < route; j++)
      {
           std::cin >>  numberInput;
           vTemp.push_back ( numberInput );
      }
      mDistance.push_back( vTemp );
  }

 std::cout << "\n \t *************** \n" << std::endl;
  // Print out the elements
   for(unsigned int i = 0; i< mDistance.size(); i++)
   {
      for (unsigned int j = 0; j < mDistance[i].size(); j++)
          std::cout << "\t" <<  mDistance[i][j] << " ";

      std::cout << std::endl;
   }

   return mDistance;

}

vlp construction(vv &adj, int limit){ // converte a matriz numa lista, setando valores de distancia acima do parametro como intratáveis
    int size = adj.size();
    vlp adj_list(size);

    for(int i=0; i<size; i++)
        for(int j=0; j<size; j++)
            if(i!=j)
                if(adj[i][j] <= limit)
                    adj_list[i].push_back(make_pair(j, adj[i][j]));


    return adj_list;
}

vector<int> grasp_solution(vlp adj, int P, float alpha){

    multimap<float, int> medias;
    vector<int> random_set;
    vector<int> solution;
    float media, alpha_part;
    int size_list = adj.size(), total_part, random, cont=0, random_set_size;

    print_list(adj);

    for(int i=0; i<size_list; i++){
        media = 0;
        for(list<pair<int, int> >::iterator it = adj[i].begin(); it!=adj[i].end(); it++){
            media += it->second;
        }
        media /= adj[i].size();
        medias.insert(make_pair(media, i));
    }

    cout << "Medias ordenadas (media, nó): " << endl;
    for(multimap<float, int>::iterator it = medias.begin(); it!=medias.end(); it++){
        cout << "( " << it->first << " , " << it->second << " )" << endl;
    }

    alpha_part = P * alpha;
    total_part = P + alpha_part;
    cout << "P: " << P << endl;
    cout << "alpha part: " << alpha_part << endl;
    cout << "total part: " << total_part << endl;

    for(int i=0; i<P; i++){
        random_set_size = random_set.size();
        do{
            random = rand() % (total_part+1);
            if(not_in(random, random_set)){
                cout << "random: " << random << endl;
                random_set.push_back(random);
            }
        }while(random_set_size==random_set.size());
    }

    multimap<float, int>::iterator map_iter = medias.begin();

    for(int i=0; i<P; i++){
        map_iter = medias.begin();
        for(int j=0; j<random_set[i]; j++)
            map_iter++;
        solution.push_back(map_iter->second);
    }

    cout << "solucao:" << endl;
    print_vec(solution);

    return solution;
}

// soma local com LISTA
int local_sum(vlp adj, vector<int> solution){
    int size_list = adj.size(), size_sol = solution.size(), min, sum=0;
    bool pass;

    for(int i=0; i<size_list; i++){

        min = INT_MAX;
        pass = true;
        for(int g=0; g<size_sol; g++)
            if(i==solution[g])
                pass = false;

        if(pass){
            for(list<pair<int, int> >::iterator it = adj[i].begin(); it != adj[i].end(); it++)
                for(int g=0; g<size_sol; g++)
                    if(it->first == solution[g])
                        if(it->second < min)
                            min = it->second;


            if(min != INT_MAX){
                sum += min; // soma os mínimos para cada nó
            }
        }
    }
    return sum; // retorna a soma
}

vector<int> random_permutation(vlp adj_list, vector<int> partial_solution){

    int adj_size = adj_list.size(), partial_size = partial_solution.size(), random[2];

    random[0] = rand() % partial_size;

    do{
        random[1] = rand() % adj_size;
    }while(!not_in(random[1], partial_solution));

    partial_solution[random[0]] = random[1];

    return partial_solution;
}

pair<int, vector<int> > neighborhood_moviments(vlp adj_list, vector<int> initial_solution){ // essa função vai fazer as permutações e calcular as somas

    int best_local_sum = INT_MAX, init_size = initial_solution.size(), partial_sum, not_improve = 0;
    vector<int> best_local_solution, partial_solution = initial_solution;
    bool improve=true;

    best_local_sum = local_sum(adj_list, partial_solution); // solução inicial
    best_local_solution = partial_solution;
    cout << "initial sum: " << best_local_sum << endl;
    cout << "initial solution: ";
    print_vec(best_local_solution);
    cout << endl;

    while(improve){

        initial_solution = partial_solution;

        if(not_improve>=LIMIT_NEIGHBORHOOD_FAILURE){
            cout << "not_improve >= " << LIMIT_NEIGHBORHOOD_FAILURE << "... interrompendo movimentação" << endl;
            break;
        }

        improve = false;

        for(int i=0; i<init_size; i++){
            for(list<pair<int, int> >::iterator it = adj_list[initial_solution[i]].begin(); it != adj_list[initial_solution[i]].end(); it++){


                if(not_in(it->first, partial_solution)){
                    cout << "antes da troca: ";
                    print_vec(partial_solution);
                    partial_solution[i] = it->first;
                }else
                    continue;
                cout << "depois da troca: ";
                print_vec(partial_solution);
                cout << "soma pos troca: ";
                partial_sum = local_sum(adj_list, partial_solution);
                cout << partial_sum;
                cout << endl;

                if(partial_sum<best_local_sum){
                    cout << "essa solução foi a melhor até agora" << endl;
                    best_local_sum = partial_sum;
                    best_local_solution = partial_solution;
                    improve = true;
                }

            }

            partial_solution[i] = initial_solution[i];
        }

        cout << "antes da permutação randomica:";
        print_vec(partial_solution);
        partial_solution = random_permutation(adj_list, partial_solution);
        cout << "depois da permutação randomica: ";
        print_vec(partial_solution);

        if(!improve){
            not_improve++;
            cout << "não melhorou... not_improve: " << not_improve << endl;
            improve = true;
        }

    }

    return make_pair(best_local_sum, best_local_solution);
}

int main()
{
    vv adj_matrix = readInput();
    vlp adj_list, original_list, heuristic_list;
    int P, V;
    vector<int> initial_solution;
    pair<int, vector<int> > global_solution, local_solution;
    global_solution.first = INT_MAX;

    /*cout << "Defina tamanho do grafo ( V ):";
    cin >> V;*/

    //fill_matrix(adj_matrix, V);
    original_list = construction(adj_matrix, INITIAL_MATRIX_CEIL_VALUE);
    heuristic_list = construction(adj_matrix, LIMIT_CONSTRUCTION_VALUE);

    do{
        cout << "defina P ( P < V and P > 0):";
        cin >> P;
    }while(P>=V && P<=0);

    for(int i=0; i<GRASP_MAX_ITER; i++){
        //formando clusters (heuristica de construção utilizando um parâmetro que define oque é perto e o que é longe)
        adj_list = heuristic_list; // (matrix, limit_value)

        //seleção gulosa de medianas
        initial_solution = grasp_solution(adj_list, P, GRASP_ALPHA_VALUE);

        //essa linha retorna a lista pra o estado original da matrix
        adj_list = original_list;

        //busca local (retorna a soma das distanticas dos clientes a sua facilidade mais próxima para uma dada seleção de medianas), insere o par <soma, solução> no multimap de soluções locais
        local_solution = neighborhood_moviments(adj_list, initial_solution);

        //fica só com a melhor
        global_solution = local_solution.first<global_solution.first?local_solution:global_solution;
    }
    print_global_solution(global_solution);

    return 0;
}


//implementação de funções auxiliares
void print_matrix(vv adj) {

    int size = adj.size();
    cout << "Matrix:" << endl;

    for (int i = 0; i<size; i++) {
        for (int j = 0; j<size; j++)
            cout << adj[i][j] << " ";

        cout << endl;
    }
}

void print_list(vlp adj_list){

    int len = adj_list.size();
    typename list<pair<int, int> >::iterator it;

    cout << "List(node, cost):" << endl;

    for(int i=0; i<len; i++){

        cout << "[" << i << "] -> ";

        for(it=adj_list[i].begin(); it!=adj_list[i].end(); it++)
                cout << "(" << it->first << " , " << it->second << ") -> ";

        cout << endl;
    }
}

void print_global_solution(pair<int, vector<int> > result){

    int size = result.second.size();
    cout << "Melhor resultado da heuristica: " << endl;
    cout << "( " << result.first << " , [,";
    for(int i=0; i<size; i++)
        cout << result.second[i] << ",";
    cout << "] )" << endl;
}

void print_vec(vector<int> vec){
    int size = vec.size();

    for(int i=0; i<size; i++)
        cout << vec[i] << ",";
    cout << endl;
}

bool not_in(int test, vector<int> vec){
    int size = vec.size();
    for(int i=0; i<size; i++)
        if(test==vec[i])
            return false;
    return true;
}