graph.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        graph.h
00031  * @author      Ernesto Colla (ernesto@gmail.com)
00032  * @version     0.0.1
00033  * @date        Fevereiro/2007
00034  * @brief       Implementação de uma biblioteca para trabalhar com grafos
00035  *
00036  * Implementação de uma biblioteca genérica de grafos direcionais e não direcionais. Grafos direcionais são compostos por vértices (\e nodes)
00037  * e arcos (\e arcs). Grafos não direcionais são formados por vértices e links (\e links).
00038  * O desenvolvedor deve invocar explicitamente apenas as funções para criar/destruir/inserir o próprio grafo e os vértices
00039  * as funções que lidam com as estruturas internas como a lista ligada, os \e nodes da mesma e a indexação são gerenciados pela própria
00040  * biblioteca e não devem ser invocados diretamente.
00041  *
00042  * @todo
00043  *      -# Melhorar a atribuição de \e ids para os vértices.
00044  *      -# Garantir a unicidade dos \e ids dos vértices. na veresão atual não há checagem da unicidade.
00045  *      -# Verificar que os \e ids são necessáriamente positivos
00046  */
00047 
00048 #ifndef GRAPH_H
00049 #define GRAPH_H
00050 
00051 /* Includes */
00052 
00053 #include <errno.h>
00054 #include <stdio.h>
00055 #include <stdlib.h>
00056 
00057 /* Defines */
00058 
00059 #define NOT_DIRECTED_GRAPH 0    //!< Constante para indicar um grafo não direcionado.
00060 #define DIRECTED_GRAPH 1                //!< Constante para indicar um grafo direcionado.
00061 
00062 #define ARCS "arcs"                             //!< Palavra-reservada do arquivo de definição para grafos para indicar um grafo DIRECIONADO.
00063 #define LINKS "links"                   //!< Palavra-reservada do arquivo de definição para grafos para indicar um grafo NÃO DIRECIONADO.
00064 
00065 /* Constantes para definir a forma de ordenação */
00066 
00067 #define IN_DEGREE 0             //!< Ordenação pelo grau de entrada.
00068 #define OUT_DEGREE 1    //!< Ordenação pelo grau de saída.
00069 #define LINK_DEGREE 2   //!< Ordenação pelo número de links.
00070 #define VERTEX_ID 3             //!< Ordenação pelo \e id do vértice.
00071 
00072 #define ASCENDANT 0             //!< Ordenação ascendente.
00073 #define DESCENDANT 1    //!< Ordenação descendente.
00074 
00075 #define VERTEX_NAME_MAX_LENGTH 100 //!< Tamanho máximo do nome que identifica o vértice.
00076 
00077 /* Definição dos tipos de dados */
00078 
00079 /*! Tipos de dados que poderão ser armazenados nos campos de dados do vértice. */
00080 typedef union union_Util {
00081         struct struct_Graph* G;                         //!< Ponteiro para um grafo.
00082         struct struct_Vertex* V;                        //!< Ponteiro para um vértice.
00083         struct struct_VertexLinkedList* L;      //!< Ponteiro para um lista de vértices.
00084         char* S;                                                        //!< Ponteiro para string.
00085         float* FP;                                                      //!< Ponteiro para float.
00086         int* IP;                                                        //!< Ponteiro para inteiros.
00087         char C;                                                         //!< Caracter.
00088         float F;                                                        //!< Número \e float.
00089         int I;                                                          //!< Número inteiro.
00090         void* data;                                                     //!< Ponteiro \e genérico
00091 } util;
00092 
00093 /*! Vértice (\e node) de um grafo */
00094 typedef struct struct_Vertex {
00095         int id;                                                                         //!< \e id único de um vértice no grafo. Não precisa ser sequencial e não há garantia que seja. É desejável que seja em função da forma como é feita a indexação. O valor \e id = -1 é reservado para vértices novos.
00096         char* name;                                                                     //!< Nome do \e node. O tamanho máximo é definido por VERTEX_NAME_MAX_LENGTH
00097         struct struct_Graph* graph;                                     //!< Ponteiro para o grado ao qual o \e node pertence.
00098         struct struct_VertexLinkedList* parents;        //!< Lista de \e nodes \e pais do \e node.
00099         struct struct_VertexLinkedList* children;       //!< Lista de \e nodes \e filhos do \e node.
00100         util user[4];                                                           //!< utility field para ser utilizado pelo usuário.
00101         util lib[4];                                                            //!< utility field para ser utilizado pela biblioteca.
00102 } Vertex;
00103 
00104 /*! Grafo genérico */
00105 typedef struct struct_Graph {
00106         int type;                                                                       //!< Indica o tipo do grafo: \e NOT_DIRECTED (não direcionado), \e DIRECTED (direcionado).
00107         char* name;                                                                     //!< Nome do grafo. Não obrigatório.
00108         int* order;                                                                     //!< \e Array que mapea um vértice à sua ordem considerando a seqüência de \e ids do grafo.
00109         struct struct_Vertex** index;                           //!< Index de vértices para acelerar a busca pelo \e id. Mapea o \e ao seu \e id. Tempo de busca constante.
00110         struct struct_VertexLinkedList* vertices;       //!< Lista Ligada Simples de vértices do grafo. Não á garantia de ordenação pelo \e id.
00111         util user[4];                                                           //!< \e Utility \e field para ser utilizado pelo usuário. Não são inicializados cabendo ao desenvolvedor alocar/desalocar. Recomenda-se sempre inicializá-lo antes de utilizá-lo.
00112         util lib[4];                                                            //!< \e Utility \e field para ser utilizado internamente por bibliotecas. Não são inicializados cabendo ao desenvolvedor alocar/desalocar. Recomenda-se sempre inicializá-lo antes de utilizá-lo.
00113 } Graph;
00114 
00115 /*! Node da lista ligada simples de vértices de um grafo. */
00116 typedef struct struct_VertexNode {
00117         struct struct_Vertex* vertex;   //!< Vértice do grafo.
00118         struct struct_VertexNode* next; //!< Ponteiro para o próximo elemento da lista.
00119 } VertexNode;
00120 
00121 /*! Lista Ligada Simples (\e Single \e Linked \e List) de vértices de um grafo.*/
00122 typedef struct struct_VertexLinkedList {
00123         int length;                                                     //!< Tamanho da lista (=número de vértices da lista).
00124         struct struct_VertexNode* first;        //!< Ponteiro para o primeiro vértice da lista.
00125         struct struct_VertexNode* last;         //!< Ponteiro para o último vértice da lista.
00126 } VertexLinkedList;
00127 
00128 
00129 /*!
00130  * @brief Cria um novo grafo, sem nome e sem vértices.
00131  *
00132  * Para desalocar a memória alocada utilizar a função destroyGraph.
00133  * @param[in] type Tipo de grafo não direcionado (\e NOT_DIRECTED) ou direcionado (\e DIRECTED).
00134  * @return Ponteiro para um grafo.
00135  */
00136 
00137 Graph* newGraph (int type);
00138 
00139 /*!
00140  * @brief Destrói o grafo e desaloca a memória alocada.
00141  * @param[out] refGraph Referência para o grafo que será destruído.
00142  */
00143 void destroyGraph (Graph** refGraph);
00144 
00145 /*!
00146  * @brief Cria um novo vértice, sem nome, com as listas vazias e com \e id = -1.
00147  *
00148  * O \e id do vértice pode ser alterado automaticamente ao inserir o vértice no grafo na função addVertex.
00149  * Para desalocar a memória alocada utilizar a função destroyVertex.
00150  * @return Ponteiro para um vétice.
00151  */
00152 
00153 Vertex* newVertex ();
00154 
00155 /*!
00156  * @brief Constrói um novo vértice a partir da lista de argumentos.
00157  *
00158  * O \e id do vértice deve ser único e não há garantia de que será seqüêncial. Em função da forma como é feita a indexação, para
00159  * para melhor performance e reduzir a memória necessária para indexar é desejável que os \e ids sejam seqüenciais e contínuos.
00160  * Para desalocar a memória alocada utilizar a função destroyVertex.
00161  * @param[in] id \e id do vértice.
00162  * @param[in] name Nome do vértice.
00163  * @return Vértice construido com os argumento fornecidos.
00164  */
00165 
00166 Vertex* buildVertex (int id, char* name);
00167 
00168 /*!
00169  * @brief Destroy o vértice e desaloca a memória.
00170  *
00171  * \e NÃO destrói (desaloca a memória) do conteúdo do vértice. Isto deve ser feito explicitamente no código.
00172  * @param[out] refVertex Referência para o vértice que será destruído.
00173  */
00174 
00175 void destroyVertex (Vertex** refVertex);
00176 
00177 /*!
00178  * @brief Adiciona um vértice ao grafo.
00179  *
00180  * Se o vértice estiver com o \e id = -1 acrescentará, \e sem verificar duplicidade, o \e id como a posição do vértice na lista.
00181  * @param[out] refGraph Referência para o grafo no qual o vértice será adicionado.
00182  * @param[out] refVertex Referência para o vértice a ser adicionado.
00183  * @return \e id do vértice inserido.
00184  */
00185 
00186 int addVertex(Graph** refGraph, Vertex** refVertex);
00187 
00188 /*!
00189  * @brief Retorna o número de vértices do grafo.
00190  * @param[in] graph Grafo do qual se deseja saber o número de nós.
00191  * @return Número de vértices do grafo.
00192  */
00193 
00194 int sizeGraph(Graph* graph);
00195 
00196 /*!
00197  * @brief Retorna o número de vértices do grafo.
00198  * @param[in] graph Grafo do qual se deseja saber o número de nós.
00199  * @return Número de vértices do grafo.
00200  */
00201 
00202 int graphsize(Graph* graph);
00203 
00204 /*!
00205  * @brief Indexa a lista de vértices pelo \e id do vértice para acelerar a busca.
00206  *
00207  * Após a indexação o tempo de busca do vértice é constante. A indexação é feita automaticamente internamente pela bilioteca sempre que necessário.
00208  * @param[out] refGraph Referência para o grafo que será indexado.
00209  */
00210 
00211 void createGraphIndex(Graph** refGraph);
00212 
00213 /*!
00214  * @brief Retorna o maior ID entre os vértices, ou seja, o último elemento da lista de vértices.
00215  * @param[out] refGraph Referência para o grafo do qual se deseja a informação.
00216  * @return Maior \e id da lista de vértices.
00217  */
00218 
00219 Vertex* getVertexMaxId(Graph** refGraph);
00220 
00221 /*!
00222  * @brief Retorna o menor ID entre os vértices, ou seja, o primeiro elemento da lista de vértices.
00223  * @param[out] refGraph Referência para o grafo do qual se deseja a informação.
00224  * @return Maior ID da lista de vértices.
00225  */
00226 
00227 Vertex* getVertexMinId(Graph** refGraph);
00228 
00229 /*!
00230  * @brief Desaloca e destrói o index de um grafo.
00231  * @param[out] refGraph Referência para o grafo do qual será desalocado o index.
00232  */
00233 
00234 void destroyGraphIndex(Graph** refGraph);
00235 
00236 /*!
00237  * @brief Retorna a ordem do vértice de acordo com o \e id do mesmo.
00238  * @param[out] refGraph Referência para o grafo do qual se deseja obter a ordem do vértice.
00239  * @param[in] vertex Vertex que se deseja saber a posição.
00240  * @return Posição do vértice.
00241  */
00242 
00243 int getVertexOrder(Graph** refGraph, Vertex* vertex);
00244 
00245 /*!
00246  * @brief Retorna o n-ésimo vértice do grafo com base na seqüência de \e ids.
00247  * @param[out] refGraph Referência para o grafo do qual se deseja obter o vértice.
00248  * @param[in] n Número do elemento que se deseja.
00249  * @return n-ésimo vétice ou null se não houver vértice.
00250  */
00251 
00252 Vertex* getVertex(Graph** refGraph, int n);
00253 
00254 /*!
00255  * @brief Retorna o vértice identificado pelo \e id.
00256  * @param[out] refGraph Referência para o grafo do qual se deseja obter o vértice.
00257  * @param[in] id \e id do elemento que se deseja.
00258  * @return vértice ou \e NULL se não houver vértice.
00259  */
00260 
00261 Vertex* getVertexById(Graph** refGraph, int id);
00262 
00263 /*!
00264  * @brief Define um arco, necessariamente direcional, entre dois vértices.
00265  * @param[out] refGraph  Referência Grafo no qual será adicionado o arco.
00266  * @param[out] refParent Referência para o vértice que é a origem do arco.
00267  * @param[out] refChild Referência para o vértice que é o destino do arco.
00268  */
00269 
00270 void addArc(Graph** refGraph, Vertex** refParent, Vertex** refChild);
00271 
00272 /*!
00273  * @brief Define um arco, necessariamente direcional, entre dois vértices.
00274  * @param[out] refGraph  Referência Grafo no qual será adicionado o arco.
00275  * @param[in] idParent \e id do vértice que é a origem do arco.
00276  * @param[in] idChild \e id do vértice que é o destino do arco.
00277  */
00278 
00279 void addArcByIds(Graph** refGraph, int idParent, int idChild);
00280 
00281 /*!
00282  * @brief Define um Link, necessariamente NÃO direcional, entre dois vértices.
00283  *
00284  * Um \e Link será formado por dois arcos direcionais com direções opostas.
00285  * @param[out] refGraph  Referência Grafo no qual será adicionado o arco.
00286  * @param[out] refVertexA Referência para o vértice na extremidade do link.
00287  * @param[out] refVertexB Referência para o vértice na extremidade do link.
00288  */
00289 
00290 void addLink(Graph** refGraph, Vertex** refVertexA, Vertex** refVertexB);
00291 
00292 /*!
00293  * @brief Define um Link, necessariamente NÃO direcional, entre dois vértices.
00294  *
00295  * Um \e Link será formado por dois arcos direcionais com direções opostas.
00296  * @param[out] refGraph  Referência Grafo no qual será adicionado o arco.
00297  * @param[in] idVertexA Id do vértice na extremidade do link.
00298  * @param[in] idVertexB Id do vértice na extremidade do link.
00299  */
00300 
00301 void addLinkByIds(Graph** refGraph, int idVertexA, int idVertexB);
00302 
00303 /*!
00304  * @brief Grau de saída do vértice, isto é, número de arcos cuja origem é o vértice.
00305  * @param[in] vertex Vértice do qual se deseja saber o grau de saída.
00306  * @return Grau de saída.
00307  */
00308 
00309 int getVertexOutDegree(Vertex* vertex);
00310 
00311 /*!
00312  * @brief Grau de entrada do vértice, isto é, número de arcos cujo destino é o vértice.
00313  * @param[in] vertex Vértice do qual se deseja saber o grau de entrada.
00314  * @return Grau de entrada.
00315  */
00316 
00317 int getVertexInDegree(Vertex* vertex);
00318 
00319 /*!
00320  * @brief O número ligações no vértice.
00321  *
00322  * Se o vértice está em um grafo direcionado o número de ligações é o resultado da soma do arcos que entram e saem (parents + children).
00323  * Se o grafo for não direcionado o número de ligações é o número de \e links.
00324  * @param[in] vertex Vértice do qual se deseja saber o grau de entrada.
00325  * @return Grau total o vértices
00326  */
00327 
00328 int getVertexDegree(Vertex* vertex);
00329 
00330 /*!
00331  * @brief Informa se o grafo é direcionado ou não, ou seja, se as ligações entre os vértices são direcionadas.
00332  * @param[in] graph Grafo do qual se deseja a informação.
00333  * @return NOT_DIRECTED_GRAPH se não for direcionado; (DIRECTED_GRAPH se for direcionado.
00334  */
00335 
00336 int isDirected(Graph *graph);
00337 
00338 /*!
00339  * @brief Interpreta arquivo com formato predefinido e constrói um grafo.
00340  * @param[in] filename Nome do arquivo com a definição do grafo.
00341  * @return Ponteiro para o grafo construído a partir dos dados do arquivo.
00342  */
00343 
00344 Graph* loadGraph(char* filename);
00345 
00346 /*!
00347  * @brief Constrói um grafo a partir de um vetor de vértices e links.
00348  * @param[in] type Tipo do grafo (Direcionado ou Não direcionado).
00349  * @param[in] vertices \e Array de vértices.
00350  * @param[in] nVertices Número de vértices.
00351  * @param[in] links \e Matriz n x 2 com as ligações (\e Arcs ou \e Links). Ordem: [parent, child].
00352  * @param[in] nLinks Número de ligações.
00353  * @return Ponteiro para o grafo construído a partir dos dados do arquivo.
00354  */
00355 
00356 Graph* buildGraph(int type, char** vertices, int nVertices, int** links, int nLinks);
00357 
00358 /*!
00359  * @brief Dump de um grafo para o \e stdout.
00360  * @param[in] graph Grafo do qual se deseja fazer o dump.
00361  */
00362 
00363 void dumpGraph(Graph* graph);
00364 
00365 /*!
00366  * @brief Obtem a lista ligada de vértices do grafo.
00367  * @param[in] graph Grafo do qual se deseja a lista de vértices.
00368  * @return Lista ligada (VertexLinkedList) com os vértices.
00369  */
00370 
00371 VertexLinkedList* getVertices(Graph* graph);
00372 
00373 /*!
00374  * @brief Obtem a lista ligada de vértices dos \e parents do vértice.
00375  * @param[in] vertex Vertex do qual se deseja a lista de vértices parents.
00376  * @return Lista ligada (VertexLinkedList) com os parents do vértice.
00377  */
00378 
00379 VertexLinkedList* getVertexParents(Vertex* vertex);
00380 
00381 /*!
00382  * @brief Obtem a lista ligada de vértices dos children do vértice.
00383  * @param[in] vertex Vertex do qual se deseja a lista de vértices children.
00384  * @return Lista ligada (VertexLinkedList) com os children do vértice.
00385  */
00386 
00387 VertexLinkedList* getVertexChildren(Vertex* vertex);
00388 
00389 // VertexLinkedList: Funções que lidam com a lista de vértices
00390 
00391 /*!
00392  * @brief Cria uma nova lista ligada simples.
00393  * @return Ponteiro para uma lista ligada simples com nodes para armazenar vértices.
00394  */
00395 
00396 VertexLinkedList* newVertexLinkedList ();
00397 
00398 /*!
00399  * @brief Cria uma nova lista ordenada com base em uma lista dada.
00400  * @param[in] list Lista de vértices a ser ordenada.
00401  * @param[in] field Campo utilizado na ordenação (LINK_DEGREE/IN_DEGREE/OUT_DEGREE).
00402  * @param[in] direction direção da ordenação (ASCENDANT/DESCENDANT).
00403  * @return Ponteiro para uma lista ligada ordenada
00404  */
00405 
00406 VertexLinkedList* newSortedVertexLinkedList (VertexLinkedList* list, int field, int direction);
00407 
00408 /*!
00409  * @brief Destroy uma lista ligada simples desaloca os \e nodes, mas sem desalocar o vértice armazenado no \e node.
00410  *
00411  * ATENÇÃO: Considerando que o Vertex pertence ao grafo e não à lista de vértice,
00412  * que é apenas uma estrutura auxiliar, a destruição a lista NÃO desaloca os,
00413  * vértices, os mesmos serão desalocados quando o grafo for destruído.
00414  * @param[out] refList Referência à lista que deve ser desalocada
00415  */
00416 
00417 void destroyVertexLinkedList (VertexLinkedList** refList);
00418 
00419 /*!
00420  * @brief Cria um novo node da lista ligada de vértices.
00421  * @return Ponteiro para um novo node da lista ligada de vértices.
00422 */
00423 
00424 VertexNode* newVertexNode ();
00425 
00426 /*!
00427  * @brief Destrói um node da lista de vértices, mas não desaloca o vértice armazenado no \e node.
00428  *
00429  * ATENÇÃO: Considerando que o Vertex pertence ao grafo e não à lista de vértice,
00430  * que é apenas uma estrutura auxiliar, a destruição a lista NÃO desaloca os
00431  * vértices, os mesmos serão desalocados quando o grafo for destruído.
00432  * @param[in] refNode Node da lista que deve ser destruído
00433  */
00434 
00435 void destroyVertexNode(VertexNode** refNode);
00436 
00437 /*!
00438  * @brief Retorna o tamanho da lista.
00439  * @return Tamanho da lista
00440  */
00441 
00442 int length(VertexLinkedList* list);
00443 
00444 /*!
00445  * @brief Acrescenta um VertexNode no início da lista ligada. 
00446  * @param[out] refList  Lista na qual deve ser acrescentado o \e node.
00447  * @param[in] vertex    VertexNode que dever ser acrescentado.
00448  */
00449 
00450 void push (VertexLinkedList** refList, Vertex* vertex);
00451 
00452 /*!
00453  * @brief Acrescenta um VertexNode no final da lista ligada. 
00454  * @param[out] refList  Lista na qual deve ser acrescentado o \e node.
00455  * @param[in] vertex    VertexNode que dever ser acrescentado.
00456 */
00457 
00458 void appendVertexNode(VertexLinkedList** refList, Vertex* vertex);
00459 
00460 /*!
00461  * @brief Adiona um vertex no final da lista de maneira ordenada.
00462  * @param[out] refList Referência a lista de vértices.
00463  * @param[in] vertex VertexNode que dever ser acrescentado.
00464  * @param[in] field Campo utilizado na ordenação (LINK_DEGREE/IN_DEGREE/OUT_DEGREE).
00465  * @param[in] direction direção da ordenação (ASCENDANT/DESCENDANT).
00466  */
00467 
00468 void appendVertexNodeSorted(VertexLinkedList** refList, Vertex* vertex, int field, int direction);
00469 
00470 /*!
00471  * @brief Remove o primeiro elemento da lista.
00472  * @param[out] refList Referência a lista de vértices.
00473  * @return Retorna o conteúdo que estava armazenado no VertexNode.
00474  */
00475 
00476 Vertex* removeFirst(VertexLinkedList** refList);
00477 
00478 /*!
00479  * @brief Remove o último elemento da lista.
00480  * @param[out] refList Referência a lista de vértices.
00481  * @return Retorna o conteúdo que estava armazenado no VertexNode.
00482  */
00483 
00484 Vertex* removeLast(VertexLinkedList** refList);
00485 
00486 /*!
00487  * @brief Ordena uma lista de vértices por um campo definido na ordem definida.
00488  * @param[out] refList Lista de vértices a ser ordenada
00489  * @param[in] field Campo utilizado na ordenação (LINK_DEGREE/IN_DEGREE/OUT_DEGREE)
00490  * @param[in] direction direção da ordenação (ASCENDANT/DESCENDANT)
00491  */
00492 
00493 void sortVertexLinkedList(VertexLinkedList** refList,int field, int direction);
00494 
00495 /*!
00496  * @brief Dump de uma lista de vértices.
00497  * @param[in] list Lista da qual se deseja o dump. 
00498  */
00499 
00500 void dumpVertexLinkedList(VertexLinkedList* list);
00501 
00502 #endif

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