#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. | |
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. | |
Vertex * | buildVertex (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. | |
Vertex * | getVertex (Graph **refGraph, int n) |
Retorna o n-ésimo vértice do grafo com base na seqüência de ids. | |
Vertex * | getVertexById (Graph **refGraph, int id) |
Retorna o vértice identificado pelo id. | |
VertexLinkedList * | getVertexChildren (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. | |
Vertex * | getVertexMaxId (Graph **refGraph) |
Retorna o maior ID entre os vértices, ou seja, o último elemento 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. | |
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. | |
VertexLinkedList * | getVertexParents (Vertex *vertex) |
Obtem a lista ligada de vértices dos parents do vértice. | |
VertexLinkedList * | getVertices (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. | |
Graph * | loadGraph (char *filename) |
Interpreta arquivo com formato predefinido e constrói um grafo. | |
Graph * | newGraph (int type) |
Cria um novo grafo, sem nome e sem vértices. | |
VertexLinkedList * | newSortedVertexLinkedList (VertexLinkedList *list, int field, int direction) |
Cria uma nova lista ordenada com base em uma lista dada. | |
Vertex * | newVertex () |
Cria um novo vértice, sem nome, com as listas vazias e com id = -1. | |
VertexLinkedList * | newVertexLinkedList () |
Cria uma nova lista ligada simples. | |
VertexNode * | newVertexNode () |
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. | |
Vertex * | removeFirst (VertexLinkedList **refList) |
Remove o primeiro elemento da lista. | |
Vertex * | removeLast (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. |
Definição no arquivo graph.h.
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.
Define um arco, necessariamente direcional, entre dois vértices.
[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.
[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. |
Define um Link, necessariamente NÃO direcional, entre dois vértices.
Um Link será formado por dois arcos direcionais com direções opostas.
[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.
[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. |
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.
[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. |
void appendVertexNode | ( | VertexLinkedList ** | refList, | |
Vertex * | vertex | |||
) |
Acrescenta um VertexNode no final da lista ligada.
[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.
[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.
[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. |
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.
[in] | id | id do vértice. |
[in] | name | Nome do vértice. |
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.
[out] | refGraph | Referência para o grafo que será indexado. |
void destroyGraph | ( | Graph ** | refGraph | ) |
Destrói o grafo e desaloca a memória alocada.
[out] | refGraph | Referência para o grafo que será destruído. |
void destroyGraphIndex | ( | Graph ** | refGraph | ) |
Desaloca e destrói o index de um grafo.
[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.
[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.
[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.
[in] | refNode | Node da lista que deve ser destruído |
void dumpGraph | ( | Graph * | graph | ) |
Dump de um grafo para o stdout.
[in] | graph | Grafo do qual se deseja fazer o dump. |
void dumpVertexLinkedList | ( | VertexLinkedList * | list | ) |
Dump de uma lista de vértices.
[in] | list | Lista da qual se deseja o dump. |
Retorna o n-ésimo vértice do grafo com base na seqüência de ids.
[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 o vértice identificado pelo id.
[out] | refGraph | Referência para o grafo do qual se deseja obter o vértice. |
[in] | id | id do elemento que se deseja. |
VertexLinkedList* getVertexChildren | ( | Vertex * | vertex | ) |
Obtem a lista ligada de vértices dos children do vértice.
[in] | vertex | Vertex do qual se deseja a lista de vértices children. |
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.
[in] | vertex | Vértice do qual se deseja saber o grau de entrada. |
int getVertexInDegree | ( | Vertex * | vertex | ) |
Grau de entrada do vértice, isto é, número de arcos cujo destino é o vértice.
[in] | vertex | Vértice do qual se deseja saber o grau de entrada. |
Retorna o maior ID entre os vértices, ou seja, o último elemento da lista de vértices.
[out] | refGraph | Referência para o grafo do qual se deseja a informação. |
Retorna o menor ID entre os vértices, ou seja, o primeiro elemento da lista de vértices.
[out] | refGraph | Referência para o grafo do qual se deseja a informação. |
Retorna a ordem do vértice de acordo com o id do mesmo.
[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. |
int getVertexOutDegree | ( | Vertex * | vertex | ) |
Grau de saída do vértice, isto é, número de arcos cuja origem é o vértice.
[in] | vertex | Vértice do qual se deseja saber o grau de saída. |
VertexLinkedList* getVertexParents | ( | Vertex * | vertex | ) |
Obtem a lista ligada de vértices dos parents do vértice.
[in] | vertex | Vertex do qual se deseja a lista de vértices parents. |
VertexLinkedList* getVertices | ( | Graph * | graph | ) |
Obtem a lista ligada de vértices do grafo.
[in] | graph | Grafo do qual se deseja a lista de vértices. |
int graphsize | ( | Graph * | graph | ) |
Retorna o número de vértices do grafo.
[in] | graph | Grafo do qual se deseja saber o número de nós. |
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.
[in] | graph | Grafo do qual se deseja a informação. |
int length | ( | VertexLinkedList * | list | ) |
Retorna o tamanho da lista.
Graph* loadGraph | ( | char * | filename | ) |
Interpreta arquivo com formato predefinido e constrói um grafo.
[in] | filename | Nome do arquivo com a definição do grafo. |
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.
[in] | type | Tipo de grafo não direcionado (NOT_DIRECTED) ou direcionado (DIRECTED). |
VertexLinkedList* newSortedVertexLinkedList | ( | VertexLinkedList * | list, | |
int | field, | |||
int | direction | |||
) |
Cria uma nova lista ordenada com base em uma lista dada.
[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). |
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.
VertexLinkedList* newVertexLinkedList | ( | ) |
Cria uma nova lista ligada simples.
VertexNode* newVertexNode | ( | ) |
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.
[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.
[out] | refList | Referência a lista de vértices. |
Vertex* removeLast | ( | VertexLinkedList ** | refList | ) |
Remove o último elemento da lista.
[out] | refList | Referência a lista de vértices. |
int sizeGraph | ( | Graph * | graph | ) |
Retorna o número de vértices do grafo.
[in] | graph | Grafo do qual se deseja saber o número de nós. |
void sortVertexLinkedList | ( | VertexLinkedList ** | refList, | |
int | field, | |||
int | direction | |||
) |
Ordena uma lista de vértices por um campo definido na ordem definida.
[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) |