PAA 2007.1 - Projeto 1 - Algoritmos para A.G.M.

Para maiores informações sobre o que é árvore geradora mínima (do inglês minimum spanning tree, também chamada de árvore de extensão mínima), clique aqui.

Parte 1: Algoritmo de Prim

O algoritmo de Prim acha a árvore geradora mínima de maneira gulosa: começa com um único vértice na árvore e, a cada passo, adiciona o vértice que se liga a árvore através da menor aresta até que todas os vértices do grafo tenham sido incluídos. A estratégia é gulosa já que a cada passo é adiciona a aresta de menor peso que liga um vértice que está na árvore a um vértice que não está. De maneira geral, podemos descrever o algoritmo de Prim segundo o seguinte pseudo-código:

MST-Prim(G, r): # acha a árvore geradora do grafo G começando do vértice r
    árvore resultado T = { r }
    enquanto T tiver menos que |V| vértices:
        encontrar o vértice x que ainda não está na árvore e que se liga
            a qualquer T pela menor aresta
        T = T U { x }

O problema é, então, manter uma estrutura que indique quais vértices estão (ou não) na árvore e que permita acessar facilmente, a cada passo, qual o vértice que não está na solução mais próximo da árvore sendo gerada. Podemos então refinar ainda mais o pseudo-código para o seguinte:

MST-Prim(G, r): # acha a árvore geradora do grafo G começando do vértice r
    MenorDistancia[1..|V|] = INFINITO
    MenorDistancia[r] = 0
    Arvore = { r }
    Enquanto Arvore tiver menos que |V| vértices:
        x = achar o vertice que nao esta em Arvore e que tem o menor
            valor de MenorDistancia
        Arvore = Arvore U { x }
        Para cada vizinho u de x:
            Se u não está em Arvore E a MenorDistancia[ u ] > peso(x,u), faça:
                MenorDistancia[ u ] = peso(x,u)

Análise de corretude

Uma excelente análise da corretude do algoritmo explicado acima encontra-se no livro "Introduction to Algorithms" de Cormen et. al, descrevemos a seguir uma versão resumida. O algoritmo de Prim começa com uma árvore contendo somente um único nó (logo mínima, porém ainda não geradora) e, a cada passo, mantém a invariante de que a árvore sendo criada é mínima, através do seguinte teorema (cuja prova encontra-se no livro mencionado acima):

Dada uma árvore mínima $A=(S,E')$, subconjunto da árvore geradora mínima $T$, podemos adicionar ao conjunto $A$ a aresta leve $(u,v)$ e manter $A \subset T$. Uma aresta leve é a aresta de menor peso que liga um elemento $u \in S$ a um elemento $v \in (V-S)$.

Dessa maneira, adicionando-se a cada passo a aresta mínima que liga um elemento que está na árvore a um elemento que não está na árvore, ao adicionarmos $V-1$ arestas teremos somente uma única árvore geradora, que será mínima.

Análise de tempo

Analisando o pseudo-código acima, podemos caracterizar o custo do algoritmo MST-Prim como composto de três partes:

  1. A inicialização das estruturas, anterior ao laço
  2. A cada passo do laço, encontrar o vértice que está mais próximo da árvore
  3. A cada passo do laço, depois de escolher o vértice, atualizar as distâncias dos vizinhos daquele vértice à árvore.

Acelerar o algoritmo significa, então, encontrar estruturas de dados que permitam que essas três operações sejam feitas de maneira rápida. Neste projeto, será analisado o uso de uma Árvore Binária Balanceada (ABB) e de uma Leftist Heap. Todas as implementações seguiram um mesmo padrão: são utilizados dois vetores MinDist e InTree, de tamanho |V|, que armazenam para cada vértice, respectivamente, qual a menor distância atual dele até a solução sendo formada e se ele já se encontra ou não na solução; a estrutura de dados (ABB ou leftist heap) é utilizada para armazenar os nós que ainda não estão na solução (utilizando como chave suas distâncias até a solução atual).

Implementação com Árvore Binária Balanceada (ABB)

A utilização da estrutura de árvore balanceada foi feita da seguinte forma (as análises de complexidade são feitas em cima das complexidades descritas na questão anterior):

  1. Na inicialização, são inseridos todos os nós na árvore com distância infinita exceto o nó 1, que é inserido com distância zero (fazendo com que ele seja escolhido na primeira iteração). Esta fase tem custo $O(V \log V)$.
  2. A cada passo do laço, retira-se da árvore o nó que está ligado a árvore pela menor aresta. Esta fase tem custo $O(\log V)$ e, como é repetida |V| vezes, tem custo total $O(V \log V)$.
  3. A cada passo do laço, escolhido o vértice são atualizadas (caso tenham diminuido) as distâncias dos vértices que ainda não estão na solução. No total do algoritmo, todas as arestas encontradas podem diminuir a distância, fazendo com que a atualização possa ser feita, no pior caso, |E| vezes. Como cada atualização envolve a remoção ($O(\log n)$ e re-inserção ($O(\log n)$) de um nó na ABB (que possui no pior caso tamanho |V|), o custo total desse passo é $O(E \log V)$.

A partir da análise acima, podemos ver que o algoritmo tem complexidade total $O(V \log V + V \log V + E \log V) = O(E \log V)$. O código da implementação segue abaixo:

int PrimABB( vector< vector<int> > &adj, vector< vector<int> > &weight, int s ) {
    const int INFINITO = 1000000000;
 
    // custo total da arvore
    int treeCost = 0;
 
    // numero de nos que ja estao na arvore
    int treeSize = 0;
 
    // menor distancia da arvore ate cada no do grafo
    vector<int> minDist(adj.size(),INFINITO);
    minDist[s] = 0;
 
    // guarda as menores distancias de maneira ordenada
    set< pair<int,int> > conjunto; // pair< distancia, indice >
 
    // guarda um ponteiro para cada no na arvore
    vector< set< pair<int,int> >::iterator > ptr(adj.size()+1);
 
    // insere inicialmente todos os nos na arvore com distancia infinita
    for (int i=0;i<(int)adj.size();i++) {
        if (i != s)
            ptr[i] = (conjunto.insert( make_pair(INFINITO,i) )).first;
    }
    // insere o no inicial com distancia 0
    ptr[s] = conjunto.insert( make_pair(0,s) ).first;
 
    vector<bool> inTree(adj.size(),false);
    while (treeSize < (int)adj.size()-1) {
 
        // escolhe o no de menor distancia que ainda nao esta na arvore
        // complexidade total O(n log n)
        pair<int,int> node;
        node = *conjunto.begin();
        conjunto.erase(conjunto.begin());
 
        // coloca o no na arvore
        inTree[node.second] = true;
        treeCost += node.first;
        treeSize += 1;
 
        // atualiza os nos vizinhos
        vector<int>::iterator w = weight[node.second].begin();
        for (vector<int>::iterator i = adj[node.second].begin();
            i != adj[node.second].end(); i++) {
 
            if (inTree[*i] == false && *w < minDist[*i]) {
                conjunto.erase( ptr[*i] );
                minDist[*i] = *w;
                ptr[*i] = conjunto.insert( make_pair(*w,*i) ).first;
            }
            w++;
        }
    }
    return treeCost;
}

Implementação com leftist heaps sem operações lazy

As três fases do algoritmo foram estruturadas da seguinte maneira (novamente, as análises de complexidade dependem da estrutura, que foi descrita na questão anterior):

  1. Na inicialização, são inseridos todos os nós na árvore com distância infinita exceto o nó 1, que é inserido com distância zero (fazendo com que ele seja escolhido na primeira iteração). Esta fase tem custo $O(V \log V)$.
  2. A cada passo do laço, retira-se da heap o nó que está ligado a árvore pela menor aresta. Esta fase tem custo $O(\log V)$ e, como é repetida |V| vezes, tem custo total $O(V \log V)$.
  3. A cada passo do laço, escolhido o vértice são atualizadas (caso tenham diminuido) as distâncias dos vértices que ainda não estão na solução. No total do algoritmo, todas as arestas encontradas podem diminuir a distância, fazendo com que a atualização possa ser feita, no pior caso, |E| vezes. Como cada atualização envolve a remoção ($O(\log n)$ e re-inserção ($O(\log n)$) de um nó na leftist heap (que possui no pior caso tamanho |V|), o custo total desse passo é $O(E \log V)$.

A complexidade total do algoritmo, de maneira semelhante ao algoritmo anterior, é $O(E \log V)$. A implementação está extremamente semelhante à implementação com ABBs:

int PrimHeap(vector< vector<int> > &adj, vector< vector<int> > &weight, int s) {
    const int INFINITO = 1000000000;
 
    // custo total da arvore
    int treeCost = 0;
 
    // numero de nos que ja estao na arvore
    int treeSize = 0;
 
    // menor distancia da arvore ate cada no do grafo
    vector<int> minDist(adj.size(),INFINITO);
    minDist[s] = 0;
 
    // guarda as menores distancias de maneira ordenada
    LeftistHeap< pair<int,int> > conjunto; // pair< distancia, indice >
 
    // guarda um ponteiro para cada no na arvore
    vector< LeftistHeapNode< pair<int,int> >* > ptr(adj.size()+1);
 
    // insere inicialmente todos os nos na arvore com distancia infinita
    for (int i=0;i<(int)adj.size();i++) {
        if (i != s)
            ptr[i] = conjunto.insert( make_pair(INFINITO,i) );
    }
    // insere o no inicial com distancia 0
    ptr[s] = conjunto.insert( make_pair(0,s) );
 
    vector<bool> inTree(adj.size(),false);
    while (treeSize < (int)adj.size()-1) {
 
        // escolhe o no de menor distancia que ainda nao esta na arvore
        // complexidade total O(n log n)
        pair<int,int> node;
        node = conjunto.top();
        conjunto.pop();
 
        // coloca o no na arvore
        inTree[node.second] = true;
        treeCost += node.first;
        treeSize += 1;
 
        // atualiza os nos vizinhos
        vector<int>::iterator w = weight[node.second].begin();
        for (vector<int>::iterator i = adj[node.second].begin();
            i != adj[node.second].end(); i++) {
 
            if (inTree[*i] == false && *w < minDist[*i]) {
                conjunto.erase( ptr[*i] );
                minDist[*i] = *w;
                ptr[*i] = conjunto.insert( make_pair(*w,*i) );
            }
            w++;
        }
    }
    return treeCost;
}

Implementação com leftist heaps com operações lazy

Para que as operações lazy fossem mais efetivas, foram feitas pequenas modificações na idéia dos algoritmos anteriores. A idéia é, ainda, que o algoritmo mantenha sempre uma estrutura geral que forneca qual o nó que está ligado a solução pela menor aresta. Neste passo, entretanto, a estrutura geral é um pouco alterada: é utilizada uma estrutura de Union-Find para realizar a deleção implícita das arestas que ligam nós que já estão na mesma árvore. A análise de tempo do algoritmo fica, então, bastante complicada.

  1. Na inicialização, é criada uma lazy leftist heap contendo as arestas que parte do nó 1, usando como chave da heap o peso das arestas. O nó 1 é então considerado já dentro da árvore. Esta fase tem custo $O(V)$, pois o nó 1 tem no máximo V vizinhos e a operação de criar uma heap custa tempo linear. É criado também uma estrutura de union-find, que será utilizada para a deleção implícita de arestas do heap.
  2. A cada passo do laço, retira-se do heap o nó que está ligado a árvore pela menor aresta. A operação de remoção do topo é feita de maneira lazy, e as arestas são marcadas como deletadas de maneira implícita: o método recebe como parâmetro a estrutura de union-find, o que permite que ele faça checagens para descobrir se dois vértices ligados por uma aresta estão já no mesmo componente, marcando assim a aresta como removida. Um limite superior para o custo deste passo é $O(E \log V + E)$ já que, no global do algoritmo, serão unidas ao todo $E$ arestas, com um custo de união de $O(\log V)$ a cada união.
  3. A cada passo do laço, escolhido o vértice que vai entrar na solução são atualizadas (caso tenham diminuido) as distâncias dos vértices que ainda não estão na solução. Esse passo é feito criando-se uma lazy leftist heap com as arestas que levam do nó escolhido até nós que ainda não estejam na árvore e então fazendo um lazy merge desta heap com o conjunto que é mantido pelo algoritmo. Como a soma do tamanho das heaps criadas é, na execução toda do algoritmo, no máximo $O(E)$ e cada junção lazy custa $O(1)$, o custo total desta parte do algoritmo é $O(E)$.

A complexidade total do algoritmo é $O(E \log V)$. O código é semelhante ao da heap sem lazy, com as modificações descritas acima:

int PrimLazyHeap(vector< vector<int> > &adj, vector< vector<int> > &weight, int s) {
    const int INFINITO = 1000000000;
 
    // total cost of the tree
    int treeCost = 0;
 
    // number of vertices that are already at the tree
    // we begin with the s vertex already in the tree
    int treeSize = 1;
 
    // minimum distance from the tree to each graph node
    vector<int> minDist(adj.size(),INFINITO);
    minDist[s] = 0;
 
    // creates the union find structure
    UnionFind uf((int)adj.size()+1);
 
    // stores a pointer to each tree node
    vector< LeftistHeapNode< pair< int, pair<int,int> > >* > ptr;
 
    // creates the heap with the edges of s
    vector< pair< int, pair<int,int> > > d;
    for (int i=0;i<(int)adj[s].size();i++) {
        d.push_back( make_pair( weight[s][i], make_pair(s,adj[s][i]) ) );
    }
 
    // stores the minimum distances in non-decrescent order
    LazyLeftistHeap conjunto(d,ptr); // pair< distancia, indice >
 
    // data structure that tells wich nodes are already in the tree
    vector<bool> inTree(adj.size(),false);
    // adds s to the tree
    inTree[s] = true;
 
    while (treeSize < (int)adj.size()-1) {
 
        // chooses the closest node that's not already in the tree
        // total complexity O(n log n)
        pair< int, pair<int,int> > node;
        node = conjunto.lazyTop(uf);
        conjunto.lazyPop();
 
        // puts the node in the tree
        inTree[node.second.second] = true;
        treeCost += node.first;
        treeSize += 1;
        // puts the new node in the tree
        uf.unionClass(uf.getClass(s),uf.getClass(node.second.second));
 
        // creates a heap with the edges of the chosen node
        vector< pair< int, pair<int,int> > > d;
        vector< LeftistHeapNode< pair< int, pair<int,int> > >* > vPtr;
        for (int i=0;i<(int)adj[node.second.second].size();i++) {
            if (inTree[ adj[node.second.second][i] ] == false)
                d.push_back( make_pair( weight[node.second.second][i],
                    make_pair(node.second.second,adj[node.second.second][i]) )
                            );
        }
        // if the neighbor heap is not empty
        if (d.empty() == false) {
            // creates a new heap and merges it
            LazyLeftistHeap *l = new LazyLeftistHeap(d,vPtr);
            conjunto.lazyMerge(l);
        }
    }
    return treeCost;
}

Parte 2: Algoritmo Round-Robin

O algoritmo Round-Robin, proposto originalmente por Cheriton e Tarjan, acha uma árvore geradora mínima através da união sucessiva de árvores em uma floresta de custo mínimo. O algoritmo começa com uma floresta composta por $|V|$ árvores, uma para cada nó do grafo. Essas árvores são colocadas em uma fila e, a cada iteração do algoritmo, é retirada uma árvore da fila, é escolhida a menor aresta que sai desta árvore e chega em uma árvore diferente e estas duas árvores são unidas. Depois de unidas, são colocadas novamente na fila, e o algoritmo executa até chegarmos somente a uma única árvore. O pseudo-código abaixo é baseado no código apresentado no livro de Tarjan:

MST-RR( G=(V,E) ): # acha a árvore geradora mínima do grafo G
    T = { } # lista de arestas da árvore
    fila = [ ]
    para cada vértice v em V, faça:
        heap[ v ] = criar um heap com as arestas incidentes a v
        fila = fila & [ v ]

    enquanto |fila| > 1, faça:
        # encontra a menor aresta incidente a árvore que
        # está na primeira posição da fila
        {v,w} = encontrarMinimo( heap[ fila[0] ] ) 

        T = T U {v,w}
        remover da fila as árvores que contém os elementos v e w
        juntar as árvores que contém os elementos v e w
            (juntando inclusive as heaps)
        fila = fila & [ representante da nova árvore de v e w ]

    retornar T

Algumas decisões devem ser tomadas para implementar o algoritmo acima: precisamos de uma estrutura de heap que permita a união entre dois heaps rapidamente; precisamos de uma estrutura que permita associar os diversos nós de uma mesma árvore um "representante" comum; precisamos que a fila seja implementada de maneira que o acesso ao primeiro elemento e a remoção de nós seja feita rapidamente; o método "encontrarMínimo" deve ter o cuidado de não retornar arestas que ligam dois nós que já estão na mesma árvore.

Os três primeiros problemas são resolvidos sem dificuldades, respectivamente, pelas estruturas de leftist heap (que permite união de heaps em tempo $O(\log n)$), pela estrutura de union-find (que permite a representação de conjuntos disjuntos com baixa complexidade assintótica) e por uma estrutura de lista duplamente encadeada (que permite remoção em tempo constante). Já o quarto problema é resolvido de forma elegante pelas lazy leftist heaps, como será visto adiante.

Análise de corretude

Uma excelente análise da corretude do algoritmo explicado acima encontra-se no livro "Data Structures and Network Algorithms" de Robert Tarjan, descrevemos a seguir uma versão resumida. Pode-se definir a construção de uma árvore geradora mínima como uma coloração das arestas do grafo em duas cores: azul e vermelha. Existem duas regras para a coloração das arestas (para a prova das regras, ver o livro acima):

Regra azul
Selecione um corte pelo qual não passam arestas azuis. Entre as arestas que não tem cor que cruzam o corte, escolher a de menor peso e pintar de azul.
Regra vermelha
Selecione um ciclo simples que não contém arestas vermelhas. Entre as arestas do ciclo, escolher a de maior custo e pintar de vermelho.

Ao aplicar sucessivamente essas regras até que todas as arestas estejam coloridas, teremos uma árvore geradora mínima formada pelas arestas azuis (novamente, a prova deste teorema pode ser encontrada no livro citado acima). A aplicação das regras não é determinística, pode-se aplicá-las em qualquer ordem. O algoritmo Round-Robin acima funciona aplicando-se sucessivamente a regra azul. No primeiro passo, criam-se $V$ árvores azuis, compostas somente pelos nós do grafo. A cada passo, escolhe-se uma árvore azul e liga-se a outra árvore azul através da menor aresta que liga elementos das árvores (aplicação da regra azul). No fim do algoritmo, temos somente uma única árvore azul.

Análise de tempo

De maneira semelhante à análise de tempo feita com o algoritmo de Prim na questão anterior, o custo do algoritmo Round-Robin pode ser subdividido nas seguintes partes:

  1. Inicialização das heaps no começo do algoritmo
  2. Encontrar a menor aresta incidente à árvore que está no começo da fila, garantindo que essa aresta não liga elementos que já estão na mesma árvore
  3. Remover da fila as duas árvores
  4. Juntar as heaps das duas árvores
  5. Manter uma estrutura que diga, para cada nó, qual a árvore a qual ele pertence

O tempo de execução total do algoritmo dependerá, então, da estrutura escolhida para armazenar as heaps.

Implementação com leftist heaps sem operações lazy

Para a implementação com leftist heaps sem lazy, o algoritmo segue os seguintes passos:

  1. As heaps são inicializadas gerando uma heap para cada nó. O custo total desse passo é $O(E)$, pois são criadas heaps cuja soma dos tamanhos é $E$.
  2. Nesse passo, como não é feita a deleção implícita das arestas, pode ser necessário retirar várias arestas de uma só vez do heap, até encontrar uma aresta que ligue dois elementos em árvores distintas. O custo total desse passo é $O(E \log V)$, pois podem ser retiradas $E$ arestas a um custo $O(\log E)$ cada uma.
  3. A fila é implementada como uma lista duplamente encadeada, permitindo remoção em tempo constante. O custo total desse passo é $O(V)$.
  4. Juntar as heaps das duas árvores $V$ vezes, tem custo total $O(V \log V)$.
  5. Para manter a estrutura informando a árvore de cada vértice do grafo, é utilizada a estrutura de union-find descrita na questão anterior, que permite operações em tempo praticamente constante.

A complexidade total do algoritmo é $O(E) + O(E \log V) + O(V \log V) = O(E \log V)$. O código-fonte segue abaixo:

int RRHeap(vector< vector<int> > &adj, vector< vector<int> > &weight, int s) {
 
    // creates the union find structure
    UnionFind uf((int)adj.size()+1);
 
    // creates the queue structure and the reverse array
    list<int> q;
    vector< list<int>::iterator > rev(adj.size()+1);
 
    // creates the array of leftist heaps
    // vector of leftist heaps
    // each heap node is a pair with the edge weight and the edge itself
    vector< LeftistHeap< pair< int, pair<int,int> > >* > listaHeaps(adj.size()+1);
 
    // initialization step, time O(M)
    for (int i=1;i<(int)adj.size();i++) {
        // for each vertice:
 
        // 1. puts it in the queue and store its location in the reverse array
        rev[i] = q.insert( q.end(), i );
 
        // 2. creates a heap with the edges adjacent to it
        vector< pair< int, pair<int,int> > > d;
        vector< LeftistHeapNode< pair< int, pair<int,int> > >* > vPtr;
        vector<int>::iterator j = adj[i].begin();
        vector<int>::iterator w = weight[i].begin();
        while (j != adj[i].end()) {
            // puts a pair with the edge weight and the edge itself
            d.push_back( make_pair(*w, make_pair(i,*j)) );
            j++; w++;
        }
        listaHeaps[i] = new LeftistHeap< pair< int, pair<int,int> > >(d,vPtr);
    }
 
    int treeCost = 0;
    int treeSize = 0;
 
    // while |queue| > 1
    while (treeSize < (int)adj.size()-2) {
 
        // {v,w} = findmin( h( queue(1) ) )
        // there's a possibility we have to take out a lot of edges from
        // the heap, since we can take out an edge between two already connected
        // trees
        pair< int, pair<int,int> > edge;
        do {
            edge = listaHeaps[ q.front() ]->top();
            listaHeaps[ q.front() ]->pop();
        } while (uf.sameClass( edge.second.first, edge.second.second ));
 
        int u = edge.second.first, v = edge.second.second;
        int w = edge.first;
 
        // counts the edge in the tree
        treeCost += w;
        treeSize += 1;
 
        // removes them both from the queue
        // queue = queue - {find(u),find(v)}
        q.erase( rev[ uf.getClass(u) ] );
        q.erase( rev[ uf.getClass(v) ] );
 
        // joins the two heaps
        listaHeaps[ uf.getClass(u) ]->merge( listaHeaps[ uf.getClass(v) ] );
 
        // connects the two trees
        // link( find(u), find(v) )
        uf.unionClass( u, v );
 
        // puts the result back into the queue
        rev[ uf.getClass(u) ] = q.insert( q.end(), uf.getClass(u) );
    }
    return treeCost;
}

Implementação com leftist heaps com operações lazy

A análise de tempo da implementação com leftist heaps é um pouco mais complicada, pois a operação lazyTop() tem um custo que depende das operações realizadas anteriormente, o que pode variar de instância para instância. O livro "Data Structures and Network Algorithms" de Robert Tarjan apresenta uma excelente análise do tempo do algoritmo. Abaixo, um resumo da análise de tempo do algoritmo Round-Robin com leftist heaps e operações lazy:

  1. As heaps são inicializadas gerando uma heap para cada nó. O custo total desse passo é $O(E)$, pois são criadas heaps cuja soma dos tamanhos é $E$.
  2. No segundo passo a estrutura de union-find é utilizada para realizar a deleção implícita das arestas: não é necessário marcar explicitamente cada aresta que liga dois nós da mesma árvore como deletada - a estrutura de union-find é capaz de identificar as arestas que ainda são válidas. Dessa maneira, o método para retornar a melhor aresta recebe como parâmetro a estrutura de union-find e consegue identificar quais as arestas ainda válidas - não precisamos, como no algoritmo anterior, nos preocupar em retirar várias arestas do heap, sabemos que a aresta retornada será válida. A complexidade deste passo pode ser dividida entre a complexidade de fazer "pequenas" operações de top() (operações em que existe menos que $\frac{x}{{\log n}^2}$ arestas removidas implicitamente, onde $x$ é o número total de arestas na árvore) e fazer "grandes" operações de top(). O custo de todas os "pequenos" top() é $O(m)$ e o custo de todos os "grandes" top() é $O(m \log \log n)$, tornando o custo total do passo $O(m \log \log n)$.
  3. A fila é implementada como uma lista duplamente encadeada, permitindo remoção em tempo constante. O custo total desse passo é $O(V)$.
  4. Juntar as heaps das duas árvores $V$ vezes, tem custo total $O(V)$ pois as junções são feitas usando operações lazy.
  5. Para manter a estrutura informando a árvore de cada vértice do grafo, é utilizada a estrutura de union-find descrita na questão anterior, que permite operações em tempo praticamente constante.

A complexidade total do algoritmo é dominada pelo passo de remover o mínimo das heaps, de custo total $O(m \log \log n)$. Esse é o algoritmo assintoticamente mais rápido de todos os algoritmos estudados no trabalho.

int RRLazyHeap(vector< vector<int> > &adj, vector< vector<int> > &weight, int s) {
    // creates the union find structure
    UnionFind uf((int)adj.size()+1);
 
    // creates the queue structure and the reverse array
    list<int> q;
    vector< list<int>::iterator > rev(adj.size()+1);
 
    // creates the array of leftist heaps
    // vector of leftist heaps
    // each heap node is a pair with the edge weight and the edge itself
    vector< LazyLeftistHeap* > listaHeaps(adj.size()+1);
 
    // initialization step, time O(M)
    for (int i=1;i<(int)adj.size();i++) {
        // for each vertice:
 
        // 1. puts it in the queue and store its location in the reverse array
        rev[i] = q.insert( q.end(), i );
 
        // 3. creates a heap with the edges adjacent to it
        vector< pair< int, pair<int,int> > > d;
        vector< LeftistHeapNode< pair< int, pair<int,int> > >* > vPtr;
        vector<int>::iterator j = adj[i].begin();
        vector<int>::iterator w = weight[i].begin();
        while (j != adj[i].end()) {
            // puts a pair with the edge weight and the edge itself
            d.push_back( make_pair(*w, make_pair(i,*j)) );
            j++; w++;
        }
        listaHeaps[i] = new LazyLeftistHeap(d,vPtr);
    }
 
    int treeCost = 0;
    int treeSize = 0;
 
    // while |queue| > 1
    while (treeSize < (int)adj.size()-2) {
 
        // {v,w} = findmin( h( queue(1) ) )
        pair< int, pair<int,int> > edge;
        edge = listaHeaps[ q.front() ]->lazyTop(uf);
        listaHeaps[ q.front() ]->lazyPop();
 
        int u = edge.second.first, v = edge.second.second;
        int w = edge.first;
 
        // counts the edge in the tree
        treeCost += w;
        treeSize += 1;
 
        // removes them both from the queue
        // queue = queue - {find(u),find(v)}
        q.erase( rev[ uf.getClass(u) ] );
        q.erase( rev[ uf.getClass(v) ] );
 
        int oldU = uf.getClass(u), oldV = uf.getClass(v);
        // connects the two trees
        // link( find(u), find(v) )
        uf.unionClass( u, v );
 
        // find their new class
        int newClass = uf.getClass(u);
        // joins the two heaps
        listaHeaps[ newClass ]->lazyMerge( listaHeaps[ (newClass == oldU ?
                oldV : oldU) ] );
 
        // puts the result back into the queue
        q.push_back( newClass );
        rev[ newClass ] = --(q.end());
    }
    return treeCost;
}

Resultados

Instâncias de teste

Foram utilizadas para testar os algoritmos três famílias de instâncias do problema da Árvore de Steiner: as instâncias DMXA, ALUT e ALUE. A tabela abaixo mostra as informações de cada instância, onde as instâncias estao ordenadas crescentemente por número de arestas. Foi utilizado também um algoritmo, denominado "VectorPrim", para calcular o valor das árvores geradoras mínimas em cada instância - é uma implementação do algoritmo de Prim que utiliza vetor como estrutura de dados, simplificando assim a implementação e servindo como "controle" para os resultados dos outros algoritmos. Além disso, o algoritmo "VectorPrim" mostra a performance de um algoritmo de complexidade $O(V^2)$, que seria ideal para grafos densos.

Instância Vértices (|V|) Arestas (|E|) Custo da AGM
dmxa0628.stp 169 280 944
dmxa0296.stp 233 386 1424
dmxa1304.stp 298 503 1781
dmxa1109.stp 343 559 2078
alut2764.stp 387 626 1970
dmxa0848.stp 499 861 2938
dmxa0903.stp 632 1087 3723
dmxa0734.stp 663 1154 3742
dmxa1516.stp 720 1269 4051
dmxa1200.stp 770 1383 4381
alue7229.stp 940 1474 5527
alut0805.stp 966 1666 5065
dmxa1721.stp 1005 1731 5932
alue2105.stp 1220 1858 7551
alue2087.stp 1244 1971 7415
alut0787.stp 1160 2089 6043
dmxa0454.stp 1848 3286 10339
dmxa0368.stp 2050 3676 11037
dmxa1801.stp 2333 4137 12572
alue6951.stp 2818 4419 17653
alue6179.stp 3372 5213 21439
alue5067.stp 3524 5560 21775
alut1181.stp 3041 5693 16352
alue3146.stp 3626 5869 22693
alue6457.stp 3932 6137 25327
alue6735.stp 4119 6696 25638
alue5623.stp 4472 6938 28563
dmxa1010.stp 3983 7108 22478
alue5345.stp 5179 8165 32010
alut2566.stp 5021 9055 27596
alue7066.stp 6405 10454 39772
alut2010.stp 6104 11011 33723
alut2288.stp 9070 16595 49737
alue5901.stp 11543 18429 71150
alue7065.stp 34046 54841 211817
alue7080.stp 34479 55494 215158
alut2610.stp 33901 62816 184956
alut2625.stp 36711 68117 200270

Uma análise das instâncias acima mostra que, em sua maioria, eles representam grafos pouco densos: a maioria das instâncias tem $E \approx V$. O conjunto de instâncias é bastante desbalanceado, havendo pouco equilíbrio entre instâncias densas e esparsas. É uma indicação que o algoritmo "VectorPrim" não terá bons resultados em comparação aos outros algoritmos implementados.

Resultados do algoritmo de Prim

O gráfico abaixo (em escala logarítmica de tempo, para realçar melhor as diferenças) mostra uma comparação do desempenho das três versões do algoritmo de Prim. Pelo gráfico, fica claro que a versão utilizando árvore balanceada é mais rápida que as demais. A segunda mais rápida é a versão com leftist heap sem utilização de operações lazy, enquanto a mais lenta é a lazy leftist heap.

prim.png

Pelo gráfico podemos perceber que, como esperado, o tempo de execução dos algoritmo parece depender diretamente do número de arestas na instância. Infelizmente o tamanho das instâncias não cresce uniformemente, então ficam alguns "pulos" no gráfico. O fato mais interessante é que todos as três linhas que representam os tempos de execução tem o mesmo formato, com os valores diferindo somente por um produto constante a cada ponto - indicando que, embora os três algoritmos tenham a mesma complexidade teórica (e, consequentemente as três linhas tenham o mesmo formato), as constantes ocultadas na notação Big-Oh são até certo ponto significativas: o algoritmo com árvore balançeada é, no geral, duas vezes mais rápido que o algoritmo com lazy leftist heap.

Resultados do algoritmo Round-Robin

A análise dos resultados do algoritmo Round-Robin não é tão óbvia quanto a do algoritmo Prim. Neste caso, os algoritmos tem complexidades assintóticas diferentes, o que gera duas curvas de performance diferentes.

roundrobin.png

No gráfico acima, vemos que o algoritmo Round-Robin que utiliza lazy leftist heaps, apesar de assintoticamente mais rápido que o algoritmo sem operações lazy têm uma performance pior em praticamente todas as instâncias. Isso se deve principalmente as altas constantes ocultas pela notação Big-Oh do algoritmo - toda chamada do método top() envolve manipulação de listas e algumas buscas recursivas que acabam consumindo um tempo considerável. As constantes ocultas no algoritmo são grandes o suficiente para deixá-lo tão lento quanto o algoritmo sem lazy. Talvez o uso de uma base de testes com instâncias de tamanho maior pudesse esclarecer este fato.

Resultados finais

A tabela a seguir mostra para cada instância os resultados de cada um dos 5 algoritmos descritos acima, além do resultado de um algoritmo "controle".

Instância |V| |E| Prim + Vector Prim + ABB Prim + Lazy Prim + NonLazy RR + Lazy RR + NonLazy
dmxa0628.stp 169 280 0,0007 0,0002 0,0007 0,0003 0,0011 0,0009
dmxa0296.stp 233 386 0,0014 0,0003 0,0010 0,0004 0,0015 0,0012
dmxa1304.stp 298 503 0,0023 0,0004 0,0014 0,0006 0,0019 0,0016
dmxa1109.stp 343 559 0,0030 0,0004 0,0015 0,0006 0,0021 0,0018
alut2764.stp 387 626 0,0038 0,0005 0,0016 0,0006 0,0024 0,0020
dmxa0848.stp 499 861 0,0061 0,0006 0,0022 0,0009 0,0033 0,0027
dmxa0903.stp 632 1087 0,0100 0,0009 0,0028 0,0012 0,0042 0,0035
dmxa0734.stp 663 1154 0,0109 0,0009 0,0030 0,0012 0,0045 0,0038
dmxa1516.stp 720 1269 0,0128 0,0010 0,0034 0,0013 0,0049 0,0041
dmxa1200.stp 770 1383 0,0147 0,0010 0,0036 0,0015 0,0053 0,0045
alue7229.stp 940 1474 0,0218 0,0013 0,0039 0,0017 0,0058 0,0051
alut0805.stp 966 1666 0,0228 0,0013 0,0043 0,0018 0,0065 0,0059
dmxa1721.stp 1005 1731 0,0251 0,0014 0,0048 0,0019 0,0069 0,0060
alue2105.stp 1220 1858 0,0363 0,0016 0,0050 0,0021 0,0074 0,0067
alue2087.stp 1244 1971 0,0382 0,0017 0,0053 0,0022 0,0078 0,0075
alut0787.stp 1160 2089 0,0336 0,0017 0,0054 0,0022 0,0080 0,0073
dmxa0454.stp 1848 3286 0,0841 0,0028 0,0087 0,0036 0,0130 0,0121
dmxa0368.stp 2050 3676 0,1036 0,0031 0,0097 0,0040 0,0148 0,0134
dmxa1801.stp 2333 4137 0,1340 0,0033 0,0109 0,0046 0,0168 0,0157
alue6951.stp 2818 4419 0,1953 0,0042 0,0118 0,0053 0,0191 0,0172
alue6179.stp 3372 5213 0,2795 0,0054 0,0143 0,0066 0,0222 0,0210
alue5067.stp 3524 5560 0,3033 0,0055 0,0151 0,0068 0,0238 0,0235
alut1181.stp 3041 5693 0,2287 0,0052 0,0150 0,0064 0,0229 0,0233
alue3146.stp 3626 5869 0,3232 0,0056 0,0160 0,0075 0,0252 0,0229
alue6457.stp 3932 6137 0,3783 0,0058 0,0168 0,0080 0,0429 0,0273
alue6735.stp 4119 6696 0,4193 0,0070 0,0182 0,0081 0,0292 0,0272
alue5623.stp 4472 6938 0,5000 0,0073 0,0192 0,0084 0,0488 0,0321
dmxa1010.stp 3983 7108 0,3882 0,0068 0,0186 0,0083 0,0493 0,0306
alue5345.stp 5179 8165 0,6543 0,0078 0,0263 0,0100 0,0555 0,0322
alut2566.stp 5021 9055 0,6250 0,0081 0,0239 0,0105 0,0601 0,0397
alue7066.stp 6405 10454 1,0094 0,0102 0,0463 0,0129 0,0704 0,0466
alut2010.stp 6104 11011 0,9141 0,0110 0,0467 0,0132 0,0700 0,0490
alut2288.stp 9070 16595 2,0156 0,0172 0,0667 0,0342 0,1006 0,0789
alue5901.stp 11543 18429 3,2656 0,0209 0,0727 0,0426 0,1128 0,0940
alue7065.stp 34046 54841 28,4219 0,0685 0,1847 0,1125 0,2730 0,2448
alue7080.stp 34479 55494 29,2344 0,0734 0,1825 0,1090 0,2786 0,2485
alut2610.stp 33901 62816 28,0469 0,0703 0,1983 0,1158 0,2943 0,2706
alut2625.stp 36711 68117 33,0938 0,0760 0,2142 0,1250 0,3213 0,2996

Quando é feita uma comparação entre os cinco algoritmos descritos, o algoritmo Prim com a utilização de árvore balanceada desponta como o mais rápido em todas as instâncias. O algoritmo possui boa complexidade assintótica ($O(E \log V)$, adequada para grafos esparsos) e constantes baixas - boa parte devido a utilização de estruturas da biblioteca padrão da linguagem, que em teoria são mais rápidas que estruturas codificadas individualmente. Os algoritmos Round-Robin são sempre mais lentos que os algoritmos Prim.

todos.png

Uma primeira observação é que todas as curvas de tempo dos algoritmos tem um formato semelhante, um sinal de que suas complexidades assintóticas são semelhantes. Outra observação relevante é em relação ao algoritmo Round-Robin com utilização de lazy leftist heaps que, embora tenha a melhor complexidade assintótica dos algoritmos testados, têm a pior performance de todos. É interessante fazer algumas contas para mostrar como o fator $\log \log V$ do algoritmo (que é melhor assintoticamente do que o fator $\log V$ do restante) se perde nas constantes ocultas na notação Big-Oh. Vamos analisar a maior instância, que possui o maior número de nós: 68117. Nesse caso, o algoritmo Round-Robin com lazy tem complexidade de pior caso em torno de $E \log \log 68117 \approx 4 E$, enquanto os outros quatro algoritmos tem complexidade $E \log 68117 \approx 16 E$, ou seja, o algoritmo com lazy deveria ser 4 vezes mais rápido que os outros algoritmos. É interessante aprofundar um pouco mais a análise do algoritmo para entender o que leva a uma performance tão ruim na prática.

O cerne da execução do algoritmo Round-Robin com lazy leftist heap está nas execuções do método lazyTop(), que faz a "limpeza" da estrutura de dados, removendo os nós que representam arestas que não podem ser incluídas na solução. O método se utiliza de outro método purgeDeleted() para encontrar as sub-árvores válidas do heap e coloca-las em uma fila para que possam ser, posteriormente, transformadas novamente em um único heap. Na análise de tempo do algoritmo, foi dito que o custo de uma operação lazyTop() custa $O(1)$ caso o heap contenha somente 1 elemento a ser removido. Entretanto, esse custo $O(1)$ mascara constantes grandes: vários métodos tem de ser chamados e alocações dinâmicas são feitas. Isso faz com que o custo da função lazyTop() seja grande, mesmo com poucos elementos. O grande problema da implementação em C++ apresentada parece ser o uso de elementos da biblioteca padrão, que realizam muitas operações de alocação/desalocação de elementos da memória, deixando as constantes do algoritmo bastante altas. Com constantes tão altas, o fator $\log \log n$ do algoritmo Round-Robin não consegue nunca ser melhor que o fator $\log n$ do algoritmo de Prim - especialmente o algoritmo que utiliza a árvore balanceada da biblioteca padrão, que possui uma implementação bastante rápida. Dessa maneira, é compreensível a baixa performance do algoritmo Round-Robin com lazy.

O algoritmo de Prim, ao contrário, possui constantes muito baixas para cada um de seus passos: as operações realizadas pela estrutura de dados subjacente são bastante simples e uma implementação eficiente (como a da árvore balanceada da biblioteca padrão do C++) gera resultados excelentes na prática.

Os resultados obtidos são exatamente semelhantes aos resultados do trabalho de "An Empirical Analysis of Algorithms for Constructing a Minimum Spanning Tree", de Moret e Shapiro[1], que mostra que apesar da análise assintótica mostre o contrário, os algoritmos mais rápidos para a árvore geradora mínima são os algoritmos que utilizam como base o algoritmo de Prim.

Referências
1. "An Empirical Analysis of Algorithms for Constructing a Minimum Spanning Tree", B. M. E. Moret and H. D. Shapiro; Lecture Notes in Computer Science v. 519, 1991. http://citeseer.ist.psu.edu/moret91empirical.html
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.