1 /*
2 graph.h
3 -------
4 
5 Graph stored as a compressed sparse row (CSR) matrix with no values.
6 
7 This is a specialization of sparse matrices suitable for cases
8 where we only need to know that two nodes are connected and will
9 typically be iterating row-by-row (get all edges for vertex v).
10 By default it stores bipartite graphs
11 
12 Essentially this can be viewed as a sparse matrix where all
13 of the non-zero values are 1.
14 
15 See sparse_matrix.h for more details.
16 
17 Currently we're not implementing edge types, graph traversal, etc.
18 */
19 
20 #ifndef GRAPH_H
21 #define GRAPH_H
22 
23 #include <stdlib.h>
24 #include <stdbool.h>
25 #include <stdint.h>
26 
27 #include "collections.h"
28 #include "file_utils.h"
29 #include "vector.h"
30 #include "vector_math.h"
31 
32 typedef enum {
33     GRAPH_DIRECTED,
34     GRAPH_UNDIRECTED,
35     GRAPH_BIPARTITE
36 } graph_type_t;
37 
38 typedef struct {
39     graph_type_t type;
40     uint32_t m;
41     uint32_t n;
42     bool fixed_rows;
43     uint32_array *indptr;
44     uint32_array *indices;
45 } graph_t;
46 
47 
48 graph_t *graph_new_dims(graph_type_t type, uint32_t m, uint32_t n, size_t nnz, bool fixed_rows);
49 graph_t *graph_new(graph_type_t type);
50 void graph_destroy(graph_t *self);
51 
52 void graph_set_size(graph_t *self);
53 
54 void graph_clear(graph_t *self);
55 
56 void graph_append_edge(graph_t *self, uint32_t col);
57 void graph_append_edges(graph_t *self, uint32_t *col, size_t n);
58 
59 void graph_finalize_vertex_no_sort(graph_t *self);
60 void graph_finalize_vertex(graph_t *self);
61 
62 bool graph_has_edge(graph_t *self, uint32_t i, uint32_t j);
63 
64 bool graph_write(graph_t *self, FILE *f);
65 bool graph_save(graph_t *self, char *path);
66 graph_t *graph_read(FILE *f);
67 graph_t *graph_load(char *path);
68 
69 #define graph_foreach_row(g, row_var, index_var, length_var, code) {            \
70     uint32_t _row_start = 0, _row_end = 0;                                      \
71     uint32_t *_indptr = g->indptr->a;                                           \
72     size_t _m = g->indptr->n - 1;                                               \
73                                                                                 \
74     for (uint32_t _i = 0; _i < _m; _i++) {                                      \
75         (row_var) = _i;                                                         \
76         _row_start = _indptr[_i];                                               \
77         _row_end = _indptr[_i + 1];                                             \
78         (index_var) = _row_start;                                               \
79         (length_var) = _row_end - _row_start;                                   \
80         code;                                                                   \
81     }                                                                           \
82 }
83 
84 #define graph_foreach(g, row_var, col_var, code) {                              \
85     uint32_t *_indices = g->indices->a;                                         \
86     uint32_t _index, _length;                                                   \
87     graph_foreach_row(g, row_var, _index, _length, {                            \
88         if (_length == 0) continue;                                             \
89         for (uint32_t _j = _index; _j < _index + _length; _j++) {               \
90             (col_var) = _indices[_j];                                           \
91             code;                                                               \
92         }                                                                       \
93     })                                                                          \
94 }
95 
96 #endif
97