Referência do Arquivo graph.h

Implementação de uma biblioteca para trabalhar com grafos. Mais...

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

Gráfico de dependência de inclusões para graph.h:

Este grafo mostra quais arquivos estão direta ou indiretamente relacionados com este arquivo:

Vá para o código-fonte deste arquivo.

Componentes

struct  struct_Graph
struct  struct_Vertex
struct  struct_VertexLinkedList
struct  struct_VertexNode
union  union_Util

Definições e Macros

#define ARCS   "arcs"
 Palavra-reservada do arquivo de definição para grafos para indicar um grafo DIRECIONADO.
#define ASCENDANT   0
 Ordenação ascendente.
#define DESCENDANT   1
 Ordenação descendente.
#define DIRECTED_GRAPH   1
 Constante para indicar um grafo direcionado.
#define IN_DEGREE   0
 Ordenação pelo grau de entrada.
#define LINK_DEGREE   2
 Ordenação pelo número de links.
#define LINKS   "links"
 Palavra-reservada do arquivo de definição para grafos para indicar um grafo NÃO DIRECIONADO.
#define NOT_DIRECTED_GRAPH   0
 Constante para indicar um grafo não direcionado.
#define OUT_DEGREE   1
 Ordenação pelo grau de saída.
#define VERTEX_ID   3
 Ordenação pelo id do vértice.
#define VERTEX_NAME_MAX_LENGTH   100
 Tamanho máximo do nome que identifica o vértice.

Definições de Tipos

typedef struct_Graph Graph
typedef union_Util util
typedef struct_Vertex Vertex
typedef struct_VertexLinkedList VertexLinkedList
typedef struct_VertexNode VertexNode

Funções

void addArc (Graph **refGraph, Vertex **refParent, Vertex **refChild)
 Define um arco, necessariamente direcional, entre dois vértices.
void addArcByIds (Graph **refGraph, int idParent, int idChild)
 Define um arco, necessariamente direcional, entre dois vértices.
void addLink (Graph **refGraph, Vertex **refVertexA, Vertex **refVertexB)
 Define um Link, necessariamente NÃO direcional, entre dois vértices.
void addLinkByIds (Graph **refGraph, int idVertexA, int idVertexB)
 Define um Link, necessariamente NÃO direcional, entre dois vértices.
int addVertex (Graph **refGraph, Vertex **refVertex)
 Adiciona um vértice ao grafo.
void appendVertexNode (VertexLinkedList **refList, Vertex *vertex)
 Acrescenta um VertexNode no final da lista ligada.
void appendVertexNodeSorted (VertexLinkedList **refList, Vertex *vertex, int field, int direction)
 Adiona um vertex no final da lista de maneira ordenada.
GraphbuildGraph (int type, char **vertices, int nVertices, int **links, int nLinks)
 Constrói um grafo a partir de um vetor de vértices e links.
VertexbuildVertex (int id, char *name)
 Constrói um novo vértice a partir da lista de argumentos.
void createGraphIndex (Graph **refGraph)
 Indexa a lista de vértices pelo id do vértice para acelerar a busca.
void destroyGraph (Graph **refGraph)
 Destrói o grafo e desaloca a memória alocada.
void destroyGraphIndex (Graph **refGraph)
 Desaloca e destrói o index de um grafo.
void destroyVertex (Vertex **refVertex)
 Destroy o vértice e desaloca a memória.
void destroyVertexLinkedList (VertexLinkedList **refList)
 Destroy uma lista ligada simples desaloca os nodes, mas sem desalocar o vértice armazenado no node.
void destroyVertexNode (VertexNode **refNode)
 Destrói um node da lista de vértices, mas não desaloca o vértice armazenado no node.
void dumpGraph (Graph *graph)
 Dump de um grafo para o stdout.
void dumpVertexLinkedList (VertexLinkedList *list)
 Dump de uma lista de vértices.
VertexgetVertex (Graph **refGraph, int n)
 Retorna o n-ésimo vértice do grafo com base na seqüência de ids.
VertexgetVertexById (Graph **refGraph, int id)
 Retorna o vértice identificado pelo id.
VertexLinkedListgetVertexChildren (Vertex *vertex)
 Obtem a lista ligada de vértices dos children do vértice.
int getVertexDegree (Vertex *vertex)
 O número ligações no vértice.
int getVertexInDegree (Vertex *vertex)
 Grau de entrada do vértice, isto é, número de arcos cujo destino é o vértice.
VertexgetVertexMaxId (Graph **refGraph)
 Retorna o maior ID entre os vértices, ou seja, o último elemento da lista de vértices.
VertexgetVertexMinId (Graph **refGraph)
 Retorna o menor ID entre os vértices, ou seja, o primeiro elemento da lista de vértices.
int getVertexOrder (Graph **refGraph, Vertex *vertex)
 Retorna a ordem do vértice de acordo com o id do mesmo.
int getVertexOutDegree (Vertex *vertex)
 Grau de saída do vértice, isto é, número de arcos cuja origem é o vértice.
VertexLinkedListgetVertexParents (Vertex *vertex)
 Obtem a lista ligada de vértices dos parents do vértice.
VertexLinkedListgetVertices (Graph *graph)
 Obtem a lista ligada de vértices do grafo.
int graphsize (Graph *graph)
 Retorna o número de vértices do grafo.
int isDirected (Graph *graph)
 Informa se o grafo é direcionado ou não, ou seja, se as ligações entre os vértices são direcionadas.
int length (VertexLinkedList *list)
 Retorna o tamanho da lista.
GraphloadGraph (char *filename)
 Interpreta arquivo com formato predefinido e constrói um grafo.
GraphnewGraph (int type)
 Cria um novo grafo, sem nome e sem vértices.
VertexLinkedListnewSortedVertexLinkedList (VertexLinkedList *list, int field, int direction)
 Cria uma nova lista ordenada com base em uma lista dada.
VertexnewVertex ()
 Cria um novo vértice, sem nome, com as listas vazias e com id = -1.
VertexLinkedListnewVertexLinkedList ()
 Cria uma nova lista ligada simples.
VertexNodenewVertexNode ()
 Cria um novo node da lista ligada de vértices.
void push (VertexLinkedList **refList, Vertex *vertex)
 Acrescenta um VertexNode no início da lista ligada.
VertexremoveFirst (VertexLinkedList **refList)
 Remove o primeiro elemento da lista.
VertexremoveLast (VertexLinkedList **refList)
 Remove o último elemento da lista.
int sizeGraph (Graph *graph)
 Retorna o número de vértices do grafo.
void sortVertexLinkedList (VertexLinkedList **refList, int field, int direction)
 Ordena uma lista de vértices por um campo definido na ordem definida.


Descrição Detalhada

Implementação de uma biblioteca para trabalhar com grafos.

Autor:
Ernesto Colla (ernesto@gmail.com)
Versão:
0.0.1
Data:
Fevereiro/2007
Implementação de uma biblioteca genérica de grafos direcionais e não direcionais. Grafos direcionais são compostos por vértices (nodes) e arcos (arcs). Grafos não direcionais são formados por vértices e links (links). O desenvolvedor deve invocar explicitamente apenas as funções para criar/destruir/inserir o próprio grafo e os vértices as funções que lidam com as estruturas internas como a lista ligada, os nodes da mesma e a indexação são gerenciados pela própria biblioteca e não devem ser invocados diretamente.

Definição no arquivo graph.h.


Definições dos tipos

typedef struct struct_Graph Graph

Grafo genérico

typedef union union_Util util

Tipos de dados que poderão ser armazenados nos campos de dados do vértice.

typedef struct struct_Vertex Vertex

Vértice (node) de um grafo

typedef struct struct_VertexLinkedList VertexLinkedList

Lista Ligada Simples (Single Linked List) de vértices de um grafo.

typedef struct struct_VertexNode VertexNode

Node da lista ligada simples de vértices de um grafo.


Funções

void addArc ( Graph **  refGraph,
Vertex **  refParent,
Vertex **  refChild 
)

Define um arco, necessariamente direcional, entre dois vértices.

Parâmetros:
[out] refGraph Referência Grafo no qual será adicionado o arco.
[out] refParent Referência para o vértice que é a origem do arco.
[out] refChild Referência para o vértice que é o destino do arco.

void addArcByIds ( Graph **  refGraph,
int  idParent,
int  idChild 
)

Define um arco, necessariamente direcional, entre dois vértices.

Parâmetros:
[out] refGraph Referência Grafo no qual será adicionado o arco.
[in] idParent id do vértice que é a origem do arco.
[in] idChild id do vértice que é o destino do arco.

void addLink ( Graph **  refGraph,
Vertex **  refVertexA,
Vertex **  refVertexB 
)

Define um Link, necessariamente NÃO direcional, entre dois vértices.

Um Link será formado por dois arcos direcionais com direções opostas.

Parâmetros:
[out] refGraph Referência Grafo no qual será adicionado o arco.
[out] refVertexA Referência para o vértice na extremidade do link.
[out] refVertexB Referência para o vértice na extremidade do link.

void addLinkByIds ( Graph **  refGraph,
int  idVertexA,
int  idVertexB 
)

Define um Link, necessariamente NÃO direcional, entre dois vértices.

Um Link será formado por dois arcos direcionais com direções opostas.

Parâmetros:
[out] refGraph Referência Grafo no qual será adicionado o arco.
[in] idVertexA Id do vértice na extremidade do link.
[in] idVertexB Id do vértice na extremidade do link.

int addVertex ( Graph **  refGraph,
Vertex **  refVertex 
)

Adiciona um vértice ao grafo.

Se o vértice estiver com o id = -1 acrescentará, sem verificar duplicidade, o id como a posição do vértice na lista.

Parâmetros:
[out] refGraph Referência para o grafo no qual o vértice será adicionado.
[out] refVertex Referência para o vértice a ser adicionado.
Retorna:
id do vértice inserido.

void appendVertexNode ( VertexLinkedList **  refList,
Vertex vertex 
)

Acrescenta um VertexNode no final da lista ligada.

Parâmetros:
[out] refList Lista na qual deve ser acrescentado o node.
[in] vertex VertexNode que dever ser acrescentado.

void appendVertexNodeSorted ( VertexLinkedList **  refList,
Vertex vertex,
int  field,
int  direction 
)

Adiona um vertex no final da lista de maneira ordenada.

Parâmetros:
[out] refList Referência a lista de vértices.
[in] vertex VertexNode que dever ser acrescentado.
[in] field Campo utilizado na ordenação (LINK_DEGREE/IN_DEGREE/OUT_DEGREE).
[in] direction direção da ordenação (ASCENDANT/DESCENDANT).

Graph* buildGraph ( int  type,
char **  vertices,
int  nVertices,
int **  links,
int  nLinks 
)

Constrói um grafo a partir de um vetor de vértices e links.

Parâmetros:
[in] type Tipo do grafo (Direcionado ou Não direcionado).
[in] vertices Array de vértices.
[in] nVertices Número de vértices.
[in] links Matriz n x 2 com as ligações (Arcs ou Links). Ordem: [parent, child].
[in] nLinks Número de ligações.
Retorna:
Ponteiro para o grafo construído a partir dos dados do arquivo.

Vertex* buildVertex ( int  id,
char *  name 
)

Constrói um novo vértice a partir da lista de argumentos.

O 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 para melhor performance e reduzir a memória necessária para indexar é desejável que os ids sejam seqüenciais e contínuos. Para desalocar a memória alocada utilizar a função destroyVertex.

Parâmetros:
[in] id id do vértice.
[in] name Nome do vértice.
Retorna:
Vértice construido com os argumento fornecidos.

void createGraphIndex ( Graph **  refGraph  ) 

Indexa a lista de vértices pelo id do vértice para acelerar a busca.

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.

Parâmetros:
[out] refGraph Referência para o grafo que será indexado.

void destroyGraph ( Graph **  refGraph  ) 

Destrói o grafo e desaloca a memória alocada.

Parâmetros:
[out] refGraph Referência para o grafo que será destruído.

void destroyGraphIndex ( Graph **  refGraph  ) 

Desaloca e destrói o index de um grafo.

Parâmetros:
[out] refGraph Referência para o grafo do qual será desalocado o index.

void destroyVertex ( Vertex **  refVertex  ) 

Destroy o vértice e desaloca a memória.

NÃO destrói (desaloca a memória) do conteúdo do vértice. Isto deve ser feito explicitamente no código.

Parâmetros:
[out] refVertex Referência para o vértice que será destruído.

void destroyVertexLinkedList ( VertexLinkedList **  refList  ) 

Destroy uma lista ligada simples desaloca os nodes, mas sem desalocar o vértice armazenado no node.

ATENÇÃO: Considerando que o Vertex pertence ao grafo e não à lista de vértice, que é apenas uma estrutura auxiliar, a destruição a lista NÃO desaloca os, vértices, os mesmos serão desalocados quando o grafo for destruído.

Parâmetros:
[out] refList Referência à lista que deve ser desalocada

void destroyVertexNode ( VertexNode **  refNode  ) 

Destrói um node da lista de vértices, mas não desaloca o vértice armazenado no node.

ATENÇÃO: Considerando que o Vertex pertence ao grafo e não à lista de vértice, que é apenas uma estrutura auxiliar, a destruição a lista NÃO desaloca os vértices, os mesmos serão desalocados quando o grafo for destruído.

Parâmetros:
[in] refNode Node da lista que deve ser destruído

void dumpGraph ( Graph graph  ) 

Dump de um grafo para o stdout.

Parâmetros:
[in] graph Grafo do qual se deseja fazer o dump.

void dumpVertexLinkedList ( VertexLinkedList list  ) 

Dump de uma lista de vértices.

Parâmetros:
[in] list Lista da qual se deseja o dump.

Vertex* getVertex ( Graph **  refGraph,
int  n 
)

Retorna o n-ésimo vértice do grafo com base na seqüência de ids.

Parâmetros:
[out] refGraph Referência para o grafo do qual se deseja obter o vértice.
[in] n Número do elemento que se deseja.
Retorna:
n-ésimo vétice ou null se não houver vértice.

Vertex* getVertexById ( Graph **  refGraph,
int  id 
)

Retorna o vértice identificado pelo id.

Parâmetros:
[out] refGraph Referência para o grafo do qual se deseja obter o vértice.
[in] id id do elemento que se deseja.
Retorna:
vértice ou NULL se não houver vértice.

VertexLinkedList* getVertexChildren ( Vertex vertex  ) 

Obtem a lista ligada de vértices dos children do vértice.

Parâmetros:
[in] vertex Vertex do qual se deseja a lista de vértices children.
Retorna:
Lista ligada (VertexLinkedList) com os children do vértice.

int getVertexDegree ( Vertex vertex  ) 

O número ligações no vértice.

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). Se o grafo for não direcionado o número de ligações é o número de links.

Parâmetros:
[in] vertex Vértice do qual se deseja saber o grau de entrada.
Retorna:
Grau total o vértices

int getVertexInDegree ( Vertex vertex  ) 

Grau de entrada do vértice, isto é, número de arcos cujo destino é o vértice.

Parâmetros:
[in] vertex Vértice do qual se deseja saber o grau de entrada.
Retorna:
Grau de entrada.

Vertex* getVertexMaxId ( Graph **  refGraph  ) 

Retorna o maior ID entre os vértices, ou seja, o último elemento da lista de vértices.

Parâmetros:
[out] refGraph Referência para o grafo do qual se deseja a informação.
Retorna:
Maior id da lista de vértices.

Vertex* getVertexMinId ( Graph **  refGraph  ) 

Retorna o menor ID entre os vértices, ou seja, o primeiro elemento da lista de vértices.

Parâmetros:
[out] refGraph Referência para o grafo do qual se deseja a informação.
Retorna:
Maior ID da lista de vértices.

int getVertexOrder ( Graph **  refGraph,
Vertex vertex 
)

Retorna a ordem do vértice de acordo com o id do mesmo.

Parâmetros:
[out] refGraph Referência para o grafo do qual se deseja obter a ordem do vértice.
[in] vertex Vertex que se deseja saber a posição.
Retorna:
Posição do vértice.

int getVertexOutDegree ( Vertex vertex  ) 

Grau de saída do vértice, isto é, número de arcos cuja origem é o vértice.

Parâmetros:
[in] vertex Vértice do qual se deseja saber o grau de saída.
Retorna:
Grau de saída.

VertexLinkedList* getVertexParents ( Vertex vertex  ) 

Obtem a lista ligada de vértices dos parents do vértice.

Parâmetros:
[in] vertex Vertex do qual se deseja a lista de vértices parents.
Retorna:
Lista ligada (VertexLinkedList) com os parents do vértice.

VertexLinkedList* getVertices ( Graph graph  ) 

Obtem a lista ligada de vértices do grafo.

Parâmetros:
[in] graph Grafo do qual se deseja a lista de vértices.
Retorna:
Lista ligada (VertexLinkedList) com os vértices.

int graphsize ( Graph graph  ) 

Retorna o número de vértices do grafo.

Parâmetros:
[in] graph Grafo do qual se deseja saber o número de nós.
Retorna:
Número de vértices do grafo.

int isDirected ( Graph graph  ) 

Informa se o grafo é direcionado ou não, ou seja, se as ligações entre os vértices são direcionadas.

Parâmetros:
[in] graph Grafo do qual se deseja a informação.
Retorna:
NOT_DIRECTED_GRAPH se não for direcionado; (DIRECTED_GRAPH se for direcionado.

int length ( VertexLinkedList list  ) 

Retorna o tamanho da lista.

Retorna:
Tamanho da lista

Graph* loadGraph ( char *  filename  ) 

Interpreta arquivo com formato predefinido e constrói um grafo.

Parâmetros:
[in] filename Nome do arquivo com a definição do grafo.
Retorna:
Ponteiro para o grafo construído a partir dos dados do arquivo.

Graph* newGraph ( int  type  ) 

Cria um novo grafo, sem nome e sem vértices.

Para desalocar a memória alocada utilizar a função destroyGraph.

Parâmetros:
[in] type Tipo de grafo não direcionado (NOT_DIRECTED) ou direcionado (DIRECTED).
Retorna:
Ponteiro para um grafo.

VertexLinkedList* newSortedVertexLinkedList ( VertexLinkedList list,
int  field,
int  direction 
)

Cria uma nova lista ordenada com base em uma lista dada.

Parâmetros:
[in] list Lista de vértices a ser ordenada.
[in] field Campo utilizado na ordenação (LINK_DEGREE/IN_DEGREE/OUT_DEGREE).
[in] direction direção da ordenação (ASCENDANT/DESCENDANT).
Retorna:
Ponteiro para uma lista ligada ordenada

Vertex* newVertex (  ) 

Cria um novo vértice, sem nome, com as listas vazias e com id = -1.

O id do vértice pode ser alterado automaticamente ao inserir o vértice no grafo na função addVertex. Para desalocar a memória alocada utilizar a função destroyVertex.

Retorna:
Ponteiro para um vétice.

VertexLinkedList* newVertexLinkedList (  ) 

Cria uma nova lista ligada simples.

Retorna:
Ponteiro para uma lista ligada simples com nodes para armazenar vértices.

VertexNode* newVertexNode (  ) 

Cria um novo node da lista ligada de vértices.

Retorna:
Ponteiro para um novo node da lista ligada de vértices.

void push ( VertexLinkedList **  refList,
Vertex vertex 
)

Acrescenta um VertexNode no início da lista ligada.

Parâmetros:
[out] refList Lista na qual deve ser acrescentado o node.
[in] vertex VertexNode que dever ser acrescentado.

Vertex* removeFirst ( VertexLinkedList **  refList  ) 

Remove o primeiro elemento da lista.

Parâmetros:
[out] refList Referência a lista de vértices.
Retorna:
Retorna o conteúdo que estava armazenado no VertexNode.

Vertex* removeLast ( VertexLinkedList **  refList  ) 

Remove o último elemento da lista.

Parâmetros:
[out] refList Referência a lista de vértices.
Retorna:
Retorna o conteúdo que estava armazenado no VertexNode.

int sizeGraph ( Graph graph  ) 

Retorna o número de vértices do grafo.

Parâmetros:
[in] graph Grafo do qual se deseja saber o número de nós.
Retorna:
Número de vértices do grafo.

void sortVertexLinkedList ( VertexLinkedList **  refList,
int  field,
int  direction 
)

Ordena uma lista de vértices por um campo definido na ordem definida.

Parâmetros:
[out] refList Lista de vértices a ser ordenada
[in] field Campo utilizado na ordenação (LINK_DEGREE/IN_DEGREE/OUT_DEGREE)
[in] direction direção da ordenação (ASCENDANT/DESCENDANT)


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