-
Notifications
You must be signed in to change notification settings - Fork 1
/
grafo.h
108 lines (85 loc) · 2.62 KB
/
grafo.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*******************************************
* Implementação de biblioteca para grafos.
*
* Algoritmos em Grafos e Otimização
* Departamento de Informática - UFPR
* prof. Guilherme Derenievicz
*******************************************/
#ifndef _GRAFO_
#define _GRAFO_
#include "lista.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> // INT_MAX
#define ABERTO 1
#define PROCESSADO 2
#define FECHADO 3
typedef struct t_vertice *vertice;
typedef struct t_aresta *aresta;
typedef struct t_grafo *grafo;
typedef struct t_vertice {
int id;
char rotulo[10];
int particao; // para grafos multi-partidos
int custo; // para algoritmos de busca
int estado;
vertice pai;
lista fronteira_entrada;
lista fronteira_saida;
} t_vertice;
typedef struct t_aresta {
int id;
vertice u, v;
} t_aresta;
typedef struct t_grafo {
int id;
lista vertices;
lista arestas;
} t_grafo ;
//---------------------------------------------------------
// getters:
int vertice_id(vertice v);
char* vertice_rotulo(vertice v);
int vertice_particao(vertice v);
int custo(vertice v);
int estado(vertice v);
vertice pai(vertice v);
lista fronteira_entrada(vertice v);
lista fronteira_saida(vertice v);
int aresta_id(aresta e);
vertice vertice_u(aresta e);
vertice vertice_v(aresta e);
int grafo_id(grafo G);
lista vertices(grafo G);
lista arestas(grafo G);
//---------------------------------------------------------
// funcoes para construcao/desconstrucao do grafo:
// cria grafo vazio e o retorna
grafo cria_grafo(int id);
// destroi grafo G (desaloca toda a memoria)
void destroi_grafo(grafo G);
// cria novo vertice com id <id> rotulo <rotulo> e adiciona ao grafo G
void adiciona_vertice(int id, char *rotulo, int particao, grafo G);
// remove vertice com id <id> do grafo G e o destroi
// [deve remover e destruir tambem as arestas incidentes]
void remove_vertice(int id, grafo G);
// cria aresta com id <id>, rotulo <rotulo> e peso <peso>,
// incidente a vertices com ids <u_id> e <v_id> e adiciona ao grafo G
void adiciona_aresta(int id, int u_id, int v_id, grafo G);
// remove aresta com id <id> do grafo G e a destroi
void remove_aresta(int id, grafo G);
//---------------------------------------------------------
// funcoes para operacoes com o grafo pronto:
// calcula e devolve o grau do vertice v
int grau_entrada(vertice v);
int grau_saida(vertice v);
// imprime o grafo G
void imprime_grafo(grafo G);
// imprime o vertice v
void imprime_vertice(vertice v);
// imprime a aresta e
void imprime_aresta(aresta e);
// imprime apenas a estrutura da aresta e
void imprime_estrutura_aresta(aresta e);
#endif