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