gibbs.h

Vá para a documentação deste arquivo.
00001 /*
00002 * Copyright 2007, 2008 Ernesto Coutinho Colla
00003 *
00004 * "BN Parallel Package" é um nome que identifica o conjunto de programas 
00005 * que forma uma biblioteca de rotinas que foram desenvolvidas como parte da 
00006 * dissertação de mestrado do autor em Ciências da Computação.
00007 *
00008 * O conjunto de programas foi integralmente desenvolvido pelo autor e está
00009 * disponível sob a licença GPL (GNU General Public License). O entendimento
00010 * integral dos termos da licença GPL é condição necessária para a utilização
00011 * parcial ou integral de qualquer parte deste conjunto de programas.
00012 *
00013 * This file is part of BN Parallel Package.
00014 * 
00015 * BN Parallel Package is free software: you can redistribute it and/or modify
00016 * it under the terms of the GNU General Public License as published by
00017 * the Free Software Foundation, either version 3 of the License.
00018 *
00019 * BN Parallel Package is distributed in the hope that it will be useful,
00020 * but WITHOUT ANY WARRANTY; without even the implied warranty of
00021 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00022 * GNU General Public License for more details.
00023 *
00024 * You should have received a copy of the GNU General Public License
00025 * along with BN Parallel Package. If not, see <http://www.gnu.org/licenses/>.
00026 */
00027 
00028 
00029 /*!
00030  * @file        gibbs.h
00031  * @author      Ernesto Colla (ernesto@gmail.com)
00032  * @version     0.0.1
00033  * @date        Março/2007
00034  * @brief       Implementação da Heurística BEL/Gibbs para definir a ordem de eliminação
00035  *
00036  */
00037 
00038 #ifndef DBGOUT
00039 #define DBGOUT stdout
00040 #endif
00041 
00042 #ifndef GIBBS_H
00043 #define GIBBS_H
00044 
00045 /* Includes */
00046 #include "graphtools.h"
00047 
00048 /* Defines */
00049 
00050 #define nextSeparator nextSeparator_SEPARADOR_PONDERADO //!< Define a estratégia de cálculo do separador com o qual foi compilado
00051 
00052 #define visited lib[0].I        //!< Redefine um campo da struct Graph utilizado para construir a árvore de dissecção, ajuda a identificar os separadores.
00053 #define list lib[1].L           //!< Redefine um campo da struct Graph para armazenar lista de vértices que compõe o vértices da árvore de dissecção.
00054 #define order lib[2].I          //!< Redefine um campo da struct Graph utilizado para montar a pós-ordem da árvore de dissecção.
00055 
00056 /* Definição dos tipos de dados */
00057 
00058 /*! Árvore gerada pela Busca Em Largura (BEL) */
00059 typedef struct struct_BELTree {
00060         int width;                                                                      //!< Largura da árvore BEL. 
00061         int depth;                                                                      //!< Profundidade da árvore BEL.
00062         int* sum;                                                                       //!< Soma dos vértices da árvore BEL até o \e i-ésimo nível. Utilizado para testar o balanceamento da árvore.
00063         struct struct_Graph* graph;                                     //!< Grafo para armazenar os vértices e a estrutura da árvore.
00064         struct struct_VertexLinkedList** vertices;      //!< Array de Lista ligadas de vértices correspondentes aos níveis da BEL.
00065 } BELTree;
00066 
00067 /* Funções */
00068 
00069 /*!
00070  * @brief Determina a ordem de eliminação de um Grafo Moral.
00071  * @param[in] moral Grafo Moral do qual a ordem de eliminação deve ser determinada.
00072  * @return Array com os \e ids dos vértices na ordem que devem ser eliminados.
00073  */
00074 
00075 int* defineEliminationOrder(Graph* moral);
00076 
00077 /*!
00078  * @brief Executa a heurística de gibbs para encontrar o nó quase periférico e retorna a BEL para o nó escolhido.
00079  * @param[in] moral Grafo Moral do qual se deseja obter a BEL.
00080  * @return BEL para o nó escolhido quase periférico escolhido.
00081  */
00082 
00083 BELTree* doGibbsHeuristic(Graph* moral);
00084 
00085 /*!
00086  * @brief Calcula o balanceamento da BEL, ou seja, a relação entre o número de vértices à direita e à esquerda.
00087  * @param[in] beltree BEL tree da qual se deseja calcular o balanceamento.
00088  * @return Valor que indica o balanceamento.
00089  */
00090 
00091 double BELBalance (BELTree* beltree);
00092 
00093 /*!
00094  * @brief Calcula a variância do número de vértices nos níveis da BEL, quando mais uniforme (menor a variância), melhor.
00095  * @param[in] beltree BEL tree da qual se deseja calcular a variância.
00096  * @return Variância do número de vértices em cada nível da BEL
00097  */
00098 
00099 double BELVariance (BELTree* beltree);
00100 
00101 /*!
00102  * @brief Constrói a BEL associada a um grafo não deirecionado a partir de um vértice dado.
00103  * @param[in] graph Grafo, necessariamente não direcionadao, que será a base para se obter a BEL.
00104  * @param[in] vertex Vértice de origem da BEL.
00105  * @return BEL para o vértice e o grafo.
00106  */
00107 
00108 // TODO: fazer o realloc para do número de níveis necessários ser superior ao alocado
00109 
00110 BELTree* buildBELTree(Graph* graph, Vertex* vertex);
00111 
00112 /*!
00113  * @brief a BELTree e desaloca todos os recursos alocados.
00114  * @param[out] refBELTree Referencia para a BEL que deve ser destruida.
00115  */
00116 
00117 void destroyBELTree (BELTree** refBELTree);
00118 
00119 /*!
00120  * @brief Dump do conteúdo de uma BELTree.
00121  * @param[in] tree BEL da qual se deseja fazer o dump.
00122  */
00123 
00124 void dumpBELTree (BELTree* tree);
00125 
00126 /*!
00127  * @brief Estratégia básica para determinação dos níveis que serão os separadores da BEL para o processo de dicotomia.
00128  *
00129  * Esta estratégia simplesmente calcula o nível central de um range de níveis. A estratégia a
00130  * ser adotada é definida na compilação de acordo com o valor definido para \e nextSeparator.
00131  * @param[in] beltree BELTree que será analisada.
00132  * @param[in] begin Indica o início do trecho que deve ser dividido.
00133  * @param[in] end indica o final do trecho que deve ser dividido.
00134  * @return Nível da BEL no qual deve ser feita a dicotomia.
00135  */
00136 
00137 int nextSeparator_BASICO(BELTree* beltree, int begin, int end);
00138 
00139 /*!
00140  * @brief Estratégia que pondera o número de vértices em cada nível para a determinação 
00141  * dos níveis que serão os separadores da BEL para o processo de dicotomia.
00142  *
00143  * Para determinar o separador considera-se o número de vértices que ficará de cada lado após a separação, 
00144  * procura-se divirdir igualmente, mas sem considerar a forma como os vértices estão conectados.
00145  * A estratégia a ser adotada é definida na compilação de acordo com o valor definido para \e nextSeparator.
00146  * @param[in] beltree BELTree que será analisada.
00147  * @param[in] begin Indica o início do trecho que deve ser dividido.
00148  * @param[in] end indica o final do trecho que deve ser dividido.
00149  * @return Nível da BEL no qual deve ser feita a dicotomia.
00150  */
00151 
00152 int nextSeparator_SEPARADOR_PONDERADO(BELTree* beltree, int begin, int end);
00153 
00154 /*!
00155  * @brief Estratégia que tenta obtar o separador com o menor número de vértices para determinação 
00156  * dos níveis que serão os separadores da BEL para o processo de dicotomia.
00157  *
00158  * Esta estratégia tenta obter dentre os possíveis candidatos para separador, aquele com o nenor número de vértices.
00159  * A estratégia a ser adotada é definida na compilação de acordo com o valor definido para \e nextSeparator.
00160  * @param[in] beltree BELTree que será analisada.
00161  * @param[in] begin Indica o início do trecho que deve ser dividido.
00162  * @param[in] end indica o final do trecho que deve ser dividido.
00163  * @return Nível da BEL no qual deve ser feita a dicotomia.
00164  */
00165 
00166 int nextSeparator_MENOR_SEPARADOR(BELTree* beltree, int begin, int end);
00167 
00168 /*!
00169  * @brief Dissecciona um range de vértices.
00170  * @param[out] refDSTree Referência para a árvore de dissecção (\e dstree) que está sendo construída.
00171  * @param[out] refRoot Referência para o vértice que será a raiz.
00172  * @param[in] beltree BELTree base para a árvore de dissecção.
00173  * @param[in] begin Indica o início do trecho que deve ser dividido.
00174  * @param[in] end Indica o final do trecho que deve ser dividido.
00175  */
00176 
00177 void dissection(Graph** refDSTree, Vertex** refRoot, BELTree* beltree, int begin, int end);
00178 
00179 /*!
00180  * @brief Contrói a árvore de dissecção (\e Dissection \e Tree)com os dados da BEL.
00181  * @param[in] moral Moral Graph do grafo de origem utilizado para se obter a BEL.
00182  * @param[in] beltree BELTree com base na qual será construída a árvore de dissecção.
00183  * @return Árvore de dissecção.
00184  */
00185 
00186 Graph* buildDissectionTree(Graph* moral, BELTree* beltree);
00187 
00188 /*!
00189  * @brief Destrói a árvore de dissecção (\e Dissection \e Tree).
00190  * @param[out] refDSTree referência para a DSTree que deve ser destruida.
00191  */
00192 
00193 void destroyDissectionTree (Graph** refDSTree);
00194 
00195 /*!
00196  * @brief Dump do conteúdo de uma árvore de dissecção (\e Dissection \e Tree).
00197  * @param[in] dstree Árvore de dissecção da qual se deseja fazer o dump.
00198  */
00199 
00200 void dumpDissectionTree (Graph* dstree);
00201 
00202 /*!
00203  * @brief Monta a ordem de eliminação com base na árvore de dissecção percorrendo recursivamente os vértices da árvore de dissecção. 
00204  * @param[in] dstree Árvore de dissecção.
00205  * @param[in] vertex Vértice do qual deve seguir a ordenação.
00206  * @return Array de inteiros com os \e ids dos vértices e pós-ordem.
00207  */
00208 
00209 int* buildEliminationOrder(Graph* dstree, Vertex* vertex);
00210 
00211 /*!
00212  * @brief Monta a pós-ordem com base em uma árvore de dissecção.
00213  * @param[in] elmorder Array que progressivamente armazena a ordem de eliminação.
00214  * @param[out] n Referência para um número inteiro que corresponde à posição atual no array \e elmorder.
00215  * @param[in] refVertex Referência para o vértice a ser visitado.
00216  */
00217 
00218 void searchEliminationOrder(int* elmorder, int *n, Vertex** refVertex);
00219 
00220 #endif

Gerado em Fri Feb 15 19:50:41 2008 para IME-Dissertação por  doxygen 1.5.1