Referência do Arquivo gibbs.h

Implementação da Heurística BEL/Gibbs para definir a ordem de eliminação. Mais...

#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.
BELTreebuildBELTree (Graph *graph, Vertex *vertex)
 Constrói a BEL associada a um grafo não deirecionado a partir de um vértice dado.
GraphbuildDissectionTree (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.
BELTreedoGibbsHeuristic (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.


Descrição Detalhada

Implementação da Heurística BEL/Gibbs para definir a ordem de eliminação.

Autor:
Ernesto Colla (ernesto@gmail.com)
Versão:
0.0.1
Data:
Março/2007

Definição no arquivo gibbs.h.


Definições dos tipos

typedef struct struct_BELTree BELTree

Árvore gerada pela Busca Em Largura (BEL)


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.

Parâmetros:
[in] beltree BEL tree da qual se deseja calcular o balanceamento.
Retorna:
Valor que indica 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.

Parâmetros:
[in] beltree BEL tree da qual se deseja calcular a variância.
Retorna:
Variância do número de vértices em cada nível da BEL

BELTree* buildBELTree ( Graph graph,
Vertex vertex 
)

Constrói a BEL associada a um grafo não deirecionado a partir de um vértice dado.

Parâmetros:
[in] graph Grafo, necessariamente não direcionadao, que será a base para se obter a BEL.
[in] vertex Vértice de origem da BEL.
Retorna:
BEL para o vértice e o grafo.

Graph* buildDissectionTree ( Graph moral,
BELTree beltree 
)

Contrói a árvore de dissecção (Dissection Tree)com os dados da BEL.

Parâmetros:
[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.
Retorna:
Árvore de dissecção.

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.

Parâmetros:
[in] dstree Árvore de dissecção.
[in] vertex Vértice do qual deve seguir a ordenação.
Retorna:
Array de inteiros com os ids dos vértices e pós-ordem.

int* defineEliminationOrder ( Graph moral  ) 

Determina a ordem de eliminação de um Grafo Moral.

Parâmetros:
[in] moral Grafo Moral do qual a ordem de eliminação deve ser determinada.
Retorna:
Array com os ids dos vértices na ordem que devem ser eliminados.

void destroyBELTree ( BELTree **  refBELTree  ) 

a BELTree e desaloca todos os recursos alocados.

Parâmetros:
[out] refBELTree Referencia para a BEL que deve ser destruida.

void destroyDissectionTree ( Graph **  refDSTree  ) 

Destrói a árvore de dissecção (Dissection Tree).

Parâmetros:
[out] refDSTree referência para a DSTree que deve ser destruida.

void dissection ( Graph **  refDSTree,
Vertex **  refRoot,
BELTree beltree,
int  begin,
int  end 
)

Dissecciona um range de vértices.

Parâmetros:
[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.

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.

Parâmetros:
[in] moral Grafo Moral do qual se deseja obter a BEL.
Retorna:
BEL para o nó escolhido quase periférico escolhido.

void dumpBELTree ( BELTree tree  ) 

Dump do conteúdo de uma BELTree.

Parâmetros:
[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).

Parâmetros:
[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.

Parâmetros:
[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.
Retorna:
Nível da BEL no qual deve ser feita a 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.

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.

Parâmetros:
[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.
Retorna:
Nível da BEL no qual deve ser feita a 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.

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.

Parâmetros:
[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.
Retorna:
Nível da BEL no qual deve ser feita a dicotomia.

void searchEliminationOrder ( int *  elmorder,
int *  n,
Vertex **  refVertex 
)

Monta a pós-ordem com base em uma árvore de dissecção.

Parâmetros:
[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.


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