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