int main() {

  time_t inicio, fim;

  cout.precision(3);
  char buffervert[33];
  char bufferlink[33];
  itoa (vertices,buffervert,10);
  itoa (links,bufferlink,10);

  do{
  cout<<"Enter number of nodes (n): ";
  cin >> vertices;
  }while(vertices<2);

  int matrizO[(vertices*(vertices-1))][3];

  do{
     cout<<"Enter number of links (l) (Between "<<(vertices-1)<<" and "<<((vertices*(vertices-1))/2)<<"): ";
     cin >> links;
  }while((links < (vertices -1)) || (links >((vertices*(vertices-1))/2)));


  char arq[100];
  sprintf(arq, "cb%d_%d.txt", vertices, links);

[b]  arquivo.open (arq);[/b]
   arquivo << "COMBINACOES: "<<endl<<endl;
   arquivo <<"Lista de <h>"<<endl<<endl;

   inicio=time(NULL);
   geracombinacao(links,matrizO);
   fim=time(NULL);

  arquivo<<"\nNumero de Nodos (n)  : "<<vertices<<endl;
  arquivo<<"\nNumero de Links (L)  : "<<links<<endl;
  arquivo<<"\nGrau Medio      ( )  : "<<graumedio<<endl;
  arquivo<<"\nTempo Processo  (t)  : "<<(fim-inicio)<<" Segundos"<<endl;

  delete(matrizO);

  [b]arquivo.close();[/b]  

  system("PAUSE");

  return 0;
}

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
#include<vector>
#include<string>
#include "combination.h"
#include <time.h>

int destino, origem, links, vertices=0;
long int cinvalidas=0;
int custo, *custos = NULL;
float graumedio=0;


ofstream arquivo;


void dijkstra(int *mediah, int vertices,int origem,int destino,int *custos, int *flagp)
{
   int i=0,v=0, cont = 0;
   int *ant, *tmp;  
   int *z;     /* vertices para os quais se conhece o caminho minimo */
   double min=0;
   double dist[vertices]; /* vetor com os custos dos caminhos, inicializa com o valor de vertices*/


   /* aloca as linhas da matriz */
   ant = new int[vertices];  //antecessor!.
   tmp = new int[vertices];
   if (ant == NULL) {
      cout<<"** Erro: Memoria Insuficiente **"<<endl;;
      system("PAUSE");
      //exit(-1);
   }

   z = new int[vertices];
   if (z == NULL) {
      cout<<"** Erro: Memoria Insuficiente **"<<endl;
      system("PAUSE");
      //exit(-1);
   }

   for (i = 0; i < vertices; i++) {
      if (custos[(origem - 1) * vertices + i] !=- 1) {
          ant[i] = origem - 1;
          dist[i] = custos[(origem-1)*vertices+i];
      } else {
         ant[i]= -1;
         dist[i] = INFINITY;
      }
      z[i]=0;
   }
   z[origem-1] = 1; // se conhece o caminho, fecha o vertice.
   dist[origem-1] = 0;


   /* Laco principal */
   do {

      /* Encontrando o vertice que deve entrar em z */
      min = INFINITY;
      for (i=0;i<vertices;i++)
         if (!z[i])
            if (dist[i]>=0 && dist[i]<min) {
               min=dist[i];v=i;
            }

      /* Calculando as distancias dos novos vizinhos de z */
      if (min != INFINITY && v != destino - 1) {
         z[v] = 1;
         for (i = 0; i < vertices; i++)
            if (!z[i]) {
               if (custos[v*vertices+i] != -1 && dist[v] + custos[v*vertices+i] < dist[i]) {
                     dist[i] = dist[v] + custos[v*vertices+i];
                  ant[i] =v;
                  }
              }
      }
   } while (v != destino - 1 && min != INFINITY);

   /* Mostra o Resultado da busca */
   if((min == INFINITY) && (origem!=destino)){
      cout<<"\tPROBLEMA"<<"\t";
      //arquivo<<"\tPROBLEMA"<<"\t";
   }else{
      cout<<"\tDe "<<origem<<" para "<<destino<<"\t";
      //arquivo <<"\tDe "<<origem<<" para "<<destino<<"\t";
   }



   if (min == INFINITY) {
         if((min == INFINITY) && (origem!=destino)){
         cout<<"GRAFO DESCONEXO";
         cout<<"\n\tSaltos: \t-"<<endl;
         *flagp=1; //indica que nao será exibido o <h>.
      }else{
         cout<<"Inexistente";
         //arquivo <<"Inexistente";
         cout<<"\n\tSaltos: \t-"<<endl;
         //arquivo<<"\n\tSaltos: \t-"<<endl;
      }

   }
   else {
      i = destino;
      i = ant[i-1];
      while (i != -1) {
           tmp[cont] = i+1;
         cont++;
         i = ant[i];
      }
      
      for (i = cont; i > 0 ; i--) {
           cout<<tmp[i-1]<<" -> ";
           //arquivo <<tmp[i-1]<<" -> ";
      }
      cout<< destino;
      //arquivo<<destino;
      
      cout <<"\n\tSaltos: "<<(int) dist[destino-1]<<endl;
      //arquivo<<"\n\tSaltos: "<<(int) dist[destino-1]<<endl;

      /* Calcula o total de hops na matriz h. Somente se existir caminho*/

         *mediah+=(int)dist[destino-1]; //guarda o num de hops

   }
}

/*----------------------------------------------------------------------------*/
/* Gera as combinacoes pedidas por geracombinacoes() e imprime na tela */
template<class BidIt>

void display(BidIt begin,BidIt end, string *comb1)
{
//ponteiro para uma matriz.

int i=0;
  for (BidIt it=begin;it!=end;++it){
    comb1[i]=*it;   /* Grava uma combinacao na matriz combinacoes - geracombinacoes()*/
    i++;
  }
}
/*----------------------------------------------------------------------------*/


void add(float *ptrgrau, int links,int (*matadd)[3])
{
   if (!custos)
      delete(custos);

   custos = new int[vertices*vertices*vertices];

   for (int i = 0; i <= vertices * vertices; i++){
      custos[i] = -1;
   }

    float grau;

    for(int i=0;i<(links*2);i++){ //preenche a matriz de custos.
          custos[(matadd[i][0]-1) * vertices + matadd[i][1] - 1] = matadd[i][2];

          custos[(matadd[i][1]-1) * vertices + matadd[i][0] - 1] = matadd[i][2];  // para calcular um grafo nao dirigido.

           grau=(float)(i+1)/(vertices);
          *((float*)ptrgrau)=grau;
    }
}
/*----------------------------------------------------------------------------*/

void procurar()
{
   int i, j, hops=0,flag=0;
   float media=0.0;

   cout<<"Lista dos Menores Caminhos no Grafo: "<<endl<<endl;
      for (i = 1; i <= vertices; i++) {
        for (j = 1; j <= vertices; j++){
           dijkstra(&hops,vertices, i,j, custos, &flag);
        }
       cout<<endl;
      }
      if(flag==0){ //flag !=0 == grafo desconexo.
         media=(float)hops/(vertices*(vertices-1));
         cout<<"\nMedia Hops         <h> : "<<media<<endl;
         arquivo<<media<<endl;
      }else{
        cinvalidas++;
      }
}
/*----------------------------------------------------------------------------*/

/* Verifica se a matriz possui todos os nós interligados - retorna 1 se ok*/
int validaMatriz(int (*ptrmat)[3]){

int k=1;
string vet;
char bufferv[33];
   for(int i=0;i<vertices;i++){
      for(int j=0;j<2;j++){
         while(k <= vertices){
            if(ptrmat[i][j]==k){
             //cout<<"procurou "<<k<<" em "<<i<<"-"<<j<<" achou"<<endl;
                   /* entao k vai para o vetor se ainda nao estiver.*/
                if((vet.find((itoa (k,bufferv,10)),0)) == string::npos){
                   vet+=(itoa (k,bufferv,10));
                }
            }else{
               //cout<<"procurou "<<k<<" em "<<i<<"-"<<j<<" NAO achou"<<endl;
            }
            k++;
          }
          k=1;
         //cout<<"vetor : "<<vet<<endl;
      }
   }
   if(vet.size()==vertices){
      //cout<<"Rede valida : "<<vet<<endl;
      return 1;
   }else{
      //cout<<"Rede INvalida : "<<vet<<endl;
      return 0;
      }
}
/*----------------------------------------------------------------------------*/

void geracombinacao(int l, int (*mat)[3]){

cout.precision(3);

vector<string> str;  /* vetor das combinacoes, todas as possibilidades, L1*/
vector<string> str1; /* vetor com numero de links que se quer*/


/* ---> prenche o vetor str. com os links possiveis, na diagonal superior
        para o numero de nós passado. (D1) ex. n=5, gera 20 linhas ---*/

cout<<"Para o numero de vertices informado: "<<vertices<<endl;
for(int i=1;i<=vertices;i++){
   for(int j=1;j<=vertices;j++){
     if(j>i){
      /* transforma o i e j em string para concatenar.*/
      char bufferi[33];
      char bufferj[33];
      itoa (i,bufferi,10);
      itoa (j,bufferj,10);

      std::string ori=bufferi; /* ori = origem */
      std::string dst=bufferj; /* dst = destino */
      std::string conc;
      std::string concinv; /* conc = concatenado inverso*/
      conc = ori + ':' + dst;  /* preenche conc com 1:2, 1:3...*/
         str.push_back (conc); /* Adiciona a string concatenada no final do vetor str */
      cout<<conc<<endl;
     }
   }
}
cout<<"Estas sao as arestas DUPLEX possiveis "<<endl;
system("PAUSE");
/*----------------------------------------------------------------------------*/

/* ---> Preenche o vetor str1 com o numero de linhas a combinar*/

cout<<"De acordo com o pedido por links: "<<l<<endl;
/* preenche o vetor str1*/
   for(int i=0;i<(l);i++){
      str1.push_back (str[i]);
      cout<<str[i]<<endl;
   }
/*----------------------------------------------------------------------------*/


/* Reserva memória para a matriz das combinacoes (uma combinacao)*/

string combinacoes[(l*2)]; /* guarda as combinacoes geradas */

/* gera todas as combinações com  l */

long int count=0;
float *ptrptrgrau; /* ponteiro que aponta para grau de add*/

  do
  {
    display(str1.begin(),str1.end(),combinacoes);
    //somador de combinacoes.
    count++;

    /* Mostra uma combinacao*/
    string source, destination;
    int sourceint, destint, position;
    for(int i=0;i<(l*2);i++){

       if(combinacoes[i]!=""){
          cout<<"Link :  "<<combinacoes[i]<<endl;;
          //arquivo << "Link: " <<combinacoes[i]<<endl;
       }

       /* separa o string e converte em inteiros.*/
       position=combinacoes[i].find(":",0);
       source=combinacoes[i].substr(0,position);
       destination=combinacoes[i].substr(position+1);
       sscanf(source.c_str(), "%d", &sourceint);
       sscanf(destination.c_str(), "%d", &destint);

       /* grava os dados na matrizO*/
       mat[i][0]=sourceint; /* origem */
       mat[i][1]=destint; /* destino */
       mat[i][2]=1; /* valor default para o peso*/
    }
    cout<<endl;


        if(validaMatriz(mat)!=0){
              //cout<<"ESTA MATRIZ EH VALIDA"<<endl;
              add(&graumedio,l,mat);
              procurar(); //funcao dijskstra procura caminhos e <h>
        }else{
          cinvalidas++;
        }


  }
  while(next_combination(str.begin (),str.end (),str1.begin (),str1.end()));


  cout<<"Combinacoes validas: "<<count-cinvalidas<<endl;
  cout<<"Invalidas: "<<cinvalidas<<endl;
  cout<<"Total: " <<count<<endl;

  arquivo<<"\nCombinacoes     ( )  : "<<count-cinvalidas<<endl; /* Grava no arquivo*/

}
/*----------------------------------------------------------------------------*/


int main() {

  time_t inicio, fim;

  cout.precision(3);
  char buffervert[33];
  char bufferlink[33];
  itoa (vertices,buffervert,10);
  itoa (links,bufferlink,10);

  do{
  cout<<"Informe o numero de nos (n) (minimo 2): ";
  cin >> vertices;
  }while(vertices<2);

  int matrizO[(vertices*(vertices-1))][3];  /* matriz com as combinacoes geradas*/

  do{
     cout<<"Informe o numero de links (l) (entre "<<(vertices-1)<<" e "<<((vertices*(vertices-1))/2)<<"): ";
     cin >> links;
  }while((links < (vertices -1)) || (links >((vertices*(vertices-1))/2)));


  char arq[100];
  sprintf(arq, "cb%d_%d.txt", vertices, links);
  arquivo.open (arq);


   arquivo << "COMBINACOES: "<<endl<<endl;
   arquivo <<"Lista de <h>"<<endl<<endl;

   inicio=time(NULL); /* guarda o tempo inicial */
    /* gera as combinacoes e imprime na tela.*/
  geracombinacao(links,matrizO); /* numero de links que se quer aplicar.*/
   fim=time(NULL); /* guarda o tempo final */

  cout<<"\nNumero de Nodos (n)  : "<<vertices<<endl;
  cout<<"\nNumero de Links (L)  : "<<((vertices*graumedio)/2)<<endl;
  cout<<"\nGrau Medio      ( )  : "<<graumedio<<endl;
  cout<<"\nTempo Processo  (t)  : "<<(fim-inicio)<<" Segundos"<<endl;

  arquivo<<"\nNumero de Nodos (n)  : "<<vertices<<endl;
  arquivo<<"\nNumero de Links (L)  : "<<links<<endl;
  arquivo<<"\nGrau Medio      ( )  : "<<graumedio<<endl;
  arquivo<<"\nTempo Processo  (t)  : "<<(fim-inicio)<<" Segundos"<<endl;


  delete(matrizO); //liberar da memória o cont de matrizO.

  arquivo.close();
  system("PAUSE");

  return 0;
}

        for (j = 1; j <= vertices; j++){
           //dijkstra(&hops,vertices, i,j, custos, &flag);
        }

        if(validaMatriz(mat)!=0){
              //cout<<"ESTA MATRIZ EH VALIDA"<<endl;
              add(&graumedio,l,mat);
              //procurar(); //funcao dijskstra procura caminhos e <h>
        }else{
          cinvalidas++;
        }