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