/
graph.h
56 lines (40 loc) · 1.54 KB
/
graph.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
#ifndef GRAPH_H
#define GRAPH_H
#include "util.h"
/* These data structures can represent both simple graphs and multigraphs */
typedef struct graph_matrix graph_matrix;
struct graph_matrix {
int n;
int *matrix; /* Convention : the (i,j) coefficient of the matrix
is matrix[i*n + j] */
};
/* gm = graph matrix */
graph_matrix* gm_alloc(int n);
graph_matrix* gm_init_zero(graph_matrix* g);
void gm_free(graph_matrix* g);
int gm_edge(const graph_matrix* g, int i, int j);
void gm_edge_add(graph_matrix* g, int i, int j);
void gm_edge_remove(graph_matrix* g, int i, int j);
void gm_multi_edge_add(graph_matrix* g, int i, int j);
void gm_multi_edge_remove(graph_matrix* g, int i, int j);
int gm_vertex_degree(const graph_matrix* g, int i);
typedef struct graph_list graph_list;
struct graph_list {
int n;
int_list** list_array;
};
/* gl = graph list */
graph_list* gl_alloc(int n);
void gl_free(graph_list* g);
int gl_edge(const graph_list* g, int i, int j);
void gl_edge_add(graph_list* g, int i, int j);
void gl_edge_remove(graph_list* g, int i, int j);
void gl_multi_edge_add(graph_list* g, int i, int j);
void gl_multi_edge_remove(graph_list* g, int i, int j);
int gl_vertex_degree(const graph_list* g, int i);
int gl_connected_components(const graph_list *g, int *result);
/* checks structural equality of the representation of the graph */
int gl_equal(const graph_list *g_a, const graph_list *g_b);
graph_list* graph_matrix_to_list(const graph_matrix *gm);
graph_matrix* graph_list_to_matrix(const graph_list *gl);
#endif