Brodal queue

[xtrm0]

Boas.

Alguem sabe como funciona uma Brodal queue?

[Warrior]

Já leste isto? http://en.wikipedia.org/wiki/Brodal_queue

Nunca usei uma Brodal Queue, mas o artigo que a descreve é um bom ponto de começo:

http://dl.acm.org/citation.cfm?id=313883

Já agora, ler artigos científicos quando procuramos algo técnico é um bom hábito, dá frutos a longo prazo.

Já agora, para que a queres usar?

[xtrm0]

A página da wikipedia e uma bela m****, já a tinha lido.

O artigo do acm custa 15$ (e estamos em crise ?). Não sabes algum site que descreva o algoritmo (de graça 😕 )?

Não quero usar a queue para nada, apenas me deparei com ela quando lia esta página (http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants) e como ja sabia usar duas destas estruturas(binary e pairing) achei estranho ser possível executar todas as operaoes em O(1) (excepto a remocao do minimo). E como conhecimento nunca é demais, pensei: "porque não apreder a implementá-la?".

[Warrior]

Desculpa lá, como estava dentro da rede da faculdade tenho acesso a esse tipo de coisas.

De qualquer modo, se pesquisasses no google scholar eras capaz de encontrar uma página qualquer a disponibilizar gratuitamente, já é um pouco antigo.

Fica aqui um link para o artigo: https://feupload.fe.up.pt/get/pIuEzirscu6vRhl

[xtrm0]

Obrigado.

[Pedro Ribeiro]

Tens também a tese (e os slides usados na defesa) do Brodal: http://cs.au.dk/~gerth/pub/ThesisBrodal.html

[xtrm0]

Obrigado. Já tenho algo para fazer fim-de-semana inteiro.

[xtrm0]

Boa noite.

Já comecei a programar a classe BQueue, no entanto ainda tenho um problema:

1-Não consigo implementar a função meld(q1, q2), e por isso nao consigo avancar mais na implementação da queue.

Estou a utilizar a estrutura de dados que o autor referenciou na página 47 (59 do pdf da tese). Decidi começar por esta, pois não consigo compreender como funciona a do capítulo VI (que tem complexidade O(1) para tudo excepto para remover o minimo).

Aqui fica o código que já tenho:

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

struct node{
      int minimo;
      int n;
      int rank;
      bool type; //1-true 2-false
      node* parent;
      node* leftmostchild;
      node* nextleft;
};

class BQueue{
     node pts[10000];
     int last; //diz qual foi o ultimo ponto a ser utilizado
     node * root;
public:
      BQueue(){ //done
          root = NULL;
          last=0;
      }
      node findMin(){ //done
          return *root;
      }
      int insert(int nv, int nm){ //é fazer um meld, agora só falta saber como, nm é o numero na array grafo

      }
      node delMin(){
          return *root;       
      }
      void decreaseKey(int e, int nv){
       return;
      }
      void meld(BQueue Q1, BQueue Q2) {
       return;
      }
};





//codigo que apenas tem a ver com o algoritmo de dijkstra, e que se encontra pouco optimizado
struct no{
 vector <int> filhos; //todos os nós para os quais o vertice no nó actual aponta
 vector <int> pesos;  //o peso de cada um dos vertices que liga o no pai
};
int main() {
   int N, A;//N-> numero de nos, A->Numero de arcos
   no grafo[10000];
   BQueue que;
   cin >> N >> A;
   for (int i=0; i<A; i++) { //o input vem com três casas por linha, no seguinte formato: "a b c\n"
   //a->ponto de partida do arco, //b-> ponto de chegada do arco, //c-> peso do arco
       int a,b,c;
       cin >> a >> b >> c;
       grafo[a].filhos.push_back(b);
       grafo[a].pesos.push_back(c);
   }
   //insere todos os elementos na queue, com distancia a no(0) infinita.
   que.insert(0,0); //o no(0) tem distancia 0 do no(0)
   for (int i=1; i<N; i++)
       que.insert(numeric_limits<int>::max(),i); //todos os outros nós têm distancia inf

   //pesquisa o caminho menos pesado, desde o no(0) ate ao no(N-1), utilizando o algoritmo de dijktra
   for (int i=1; i<N; i++) {
       node melhor = que.findMin();
       que.delMin();
       if (melhor.minimo == numeric_limits<int>::max()) break;
       //cajo nao consiga ir para mais nenhum vertice, ou haja algum problema com a queue
       if (melhor.n==N-1) {
           cout << melhor.minimo << endl;
           break;
       }//caso ja tenha chegado ao no pretendido

       for (int j=0; j<grafo[melhor.n].filhos.size(); j++) {
           que.decreaseKey(grafo[melhor.n].filhos[j], melhor.minimo + grafo[melhor.n].pesos[j]);
           //a funcao decrease key é que tem que verificar se o peso é menor ou nao.
       }
   }

   return 0;   
}

[Warrior]

xtrm0: nunca implementei uma Brodal queue, e não sei se vais arranjar alguém que tenha implementado uma.

Vai ser um trabalho bastante individual..