#include "graphtools.h"
Gráfico de dependência de inclusões para gibbs.h:
Vá para o código-fonte deste arquivo.
Componentes | |
struct | struct_BELTree |
Definições e Macros | |
#define | DBGOUT stdout |
#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. | |
#define | nextSeparator nextSeparator_SEPARADOR_PONDERADO |
Define a estratégia de cálculo do separador com o qual foi compilado. | |
#define | order lib[2].I |
Redefine um campo da struct Graph utilizado para montar a pós-ordem da árvore de dissecção. | |
#define | visited lib[0].I |
Redefine um campo da struct Graph utilizado para construir a árvore de dissecção, ajuda a identificar os separadores. | |
Definições de Tipos | |
typedef struct_BELTree | BELTree |
Funções | |
double | BELBalance (BELTree *beltree) |
Calcula o balanceamento da BEL, ou seja, a relação entre o número de vértices à direita e à esquerda. | |
double | BELVariance (BELTree *beltree) |
Calcula a variância do número de vértices nos níveis da BEL, quando mais uniforme (menor a variância), melhor. | |
BELTree * | buildBELTree (Graph *graph, Vertex *vertex) |
Constrói a BEL associada a um grafo não deirecionado a partir de um vértice dado. | |
Graph * | buildDissectionTree (Graph *moral, BELTree *beltree) |
Contrói a árvore de dissecção (Dissection Tree)com os dados da BEL. | |
int * | buildEliminationOrder (Graph *dstree, Vertex *vertex) |
Monta a ordem de eliminação com base na árvore de dissecção percorrendo recursivamente os vértices da árvore de dissecção. | |
int * | defineEliminationOrder (Graph *moral) |
Determina a ordem de eliminação de um Grafo Moral. | |
void | destroyBELTree (BELTree **refBELTree) |
a BELTree e desaloca todos os recursos alocados. | |
void | destroyDissectionTree (Graph **refDSTree) |
Destrói a árvore de dissecção (Dissection Tree). | |
void | dissection (Graph **refDSTree, Vertex **refRoot, BELTree *beltree, int begin, int end) |
Dissecciona um range de vértices. | |
BELTree * | doGibbsHeuristic (Graph *moral) |
Executa a heurística de gibbs para encontrar o nó quase periférico e retorna a BEL para o nó escolhido. | |
void | dumpBELTree (BELTree *tree) |
Dump do conteúdo de uma BELTree. | |
void | dumpDissectionTree (Graph *dstree) |
Dump do conteúdo de uma árvore de dissecção (Dissection Tree). | |
int | nextSeparator_BASICO (BELTree *beltree, int begin, int end) |
Estratégia básica para determinação dos níveis que serão os separadores da BEL para o processo de dicotomia. | |
int | nextSeparator_MENOR_SEPARADOR (BELTree *beltree, int begin, int end) |
Estratégia que tenta obtar o separador com o menor número de vértices para determinação dos níveis que serão os separadores da BEL para o processo de dicotomia. | |
int | nextSeparator_SEPARADOR_PONDERADO (BELTree *beltree, int begin, int end) |
Estratégia que pondera o número de vértices em cada nível para a determinação dos níveis que serão os separadores da BEL para o processo de dicotomia. | |
void | searchEliminationOrder (int *elmorder, int *n, Vertex **refVertex) |
Monta a pós-ordem com base em uma árvore de dissecção. |
Definição no arquivo gibbs.h.
typedef struct struct_BELTree BELTree |
Árvore gerada pela Busca Em Largura (BEL)
double BELBalance | ( | BELTree * | beltree | ) |
Calcula o balanceamento da BEL, ou seja, a relação entre o número de vértices à direita e à esquerda.
[in] | beltree | BEL tree da qual se deseja calcular o balanceamento. |
double BELVariance | ( | BELTree * | beltree | ) |
Calcula a variância do número de vértices nos níveis da BEL, quando mais uniforme (menor a variância), melhor.
[in] | beltree | BEL tree da qual se deseja calcular a variância. |
Constrói a BEL associada a um grafo não deirecionado a partir de um vértice dado.
[in] | graph | Grafo, necessariamente não direcionadao, que será a base para se obter a BEL. |
[in] | vertex | Vértice de origem da BEL. |
Contrói a árvore de dissecção (Dissection Tree)com os dados da BEL.
[in] | moral | Moral Graph do grafo de origem utilizado para se obter a BEL. |
[in] | beltree | BELTree com base na qual será construída a árvore de dissecção. |
Monta a ordem de eliminação com base na árvore de dissecção percorrendo recursivamente os vértices da árvore de dissecção.
[in] | dstree | Árvore de dissecção. |
[in] | vertex | Vértice do qual deve seguir a ordenação. |
int* defineEliminationOrder | ( | Graph * | moral | ) |
Determina a ordem de eliminação de um Grafo Moral.
[in] | moral | Grafo Moral do qual a ordem de eliminação deve ser determinada. |
void destroyBELTree | ( | BELTree ** | refBELTree | ) |
a BELTree e desaloca todos os recursos alocados.
[out] | refBELTree | Referencia para a BEL que deve ser destruida. |
void destroyDissectionTree | ( | Graph ** | refDSTree | ) |
Destrói a árvore de dissecção (Dissection Tree).
[out] | refDSTree | referência para a DSTree que deve ser destruida. |
Dissecciona um range de vértices.
[out] | refDSTree | Referência para a árvore de dissecção (dstree) que está sendo construída. |
[out] | refRoot | Referência para o vértice que será a raiz. |
[in] | beltree | BELTree base para a árvore de dissecção. |
[in] | begin | Indica o início do trecho que deve ser dividido. |
[in] | end | Indica o final do trecho que deve ser dividido. |
Executa a heurística de gibbs para encontrar o nó quase periférico e retorna a BEL para o nó escolhido.
[in] | moral | Grafo Moral do qual se deseja obter a BEL. |
void dumpBELTree | ( | BELTree * | tree | ) |
Dump do conteúdo de uma BELTree.
[in] | tree | BEL da qual se deseja fazer o dump. |
void dumpDissectionTree | ( | Graph * | dstree | ) |
Dump do conteúdo de uma árvore de dissecção (Dissection Tree).
[in] | dstree | Árvore de dissecção da qual se deseja fazer o dump. |
int nextSeparator_BASICO | ( | BELTree * | beltree, | |
int | begin, | |||
int | end | |||
) |
Estratégia básica para determinação dos níveis que serão os separadores da BEL para o processo de dicotomia.
Esta estratégia simplesmente calcula o nível central de um range de níveis. A estratégia a ser adotada é definida na compilação de acordo com o valor definido para nextSeparator.
[in] | beltree | BELTree que será analisada. |
[in] | begin | Indica o início do trecho que deve ser dividido. |
[in] | end | indica o final do trecho que deve ser dividido. |
int nextSeparator_MENOR_SEPARADOR | ( | BELTree * | beltree, | |
int | begin, | |||
int | end | |||
) |
Estratégia que tenta obtar o separador com o menor número de vértices para determinação dos níveis que serão os separadores da BEL para o processo de dicotomia.
Esta estratégia tenta obter dentre os possíveis candidatos para separador, aquele com o nenor número de vértices. A estratégia a ser adotada é definida na compilação de acordo com o valor definido para nextSeparator.
[in] | beltree | BELTree que será analisada. |
[in] | begin | Indica o início do trecho que deve ser dividido. |
[in] | end | indica o final do trecho que deve ser dividido. |
int nextSeparator_SEPARADOR_PONDERADO | ( | BELTree * | beltree, | |
int | begin, | |||
int | end | |||
) |
Estratégia que pondera o número de vértices em cada nível para a determinação dos níveis que serão os separadores da BEL para o processo de dicotomia.
Para determinar o separador considera-se o número de vértices que ficará de cada lado após a separação, procura-se divirdir igualmente, mas sem considerar a forma como os vértices estão conectados. A estratégia a ser adotada é definida na compilação de acordo com o valor definido para nextSeparator.
[in] | beltree | BELTree que será analisada. |
[in] | begin | Indica o início do trecho que deve ser dividido. |
[in] | end | indica o final do trecho que deve ser dividido. |
void searchEliminationOrder | ( | int * | elmorder, | |
int * | n, | |||
Vertex ** | refVertex | |||
) |
Monta a pós-ordem com base em uma árvore de dissecção.
[in] | elmorder | Array que progressivamente armazena a ordem de eliminação. |
[out] | n | Referência para um número inteiro que corresponde à posição atual no array elmorder. |
[in] | refVertex | Referência para o vértice a ser visitado. |