1 #ifndef R_GRAPH_H 2 #define R_GRAPH_H 3 4 #include <r_list.h> 5 6 #ifdef __cplusplus 7 extern "C" { 8 #endif 9 10 typedef struct r_graph_node_t { 11 unsigned int idx; 12 void *data; 13 RList *out_nodes; 14 RList *in_nodes; 15 RList *all_neighbours; 16 RListFree free; 17 } RGraphNode; 18 19 typedef struct r_graph_edge_t { 20 RGraphNode *from; 21 RGraphNode *to; 22 int nth; 23 } RGraphEdge; 24 25 typedef struct r_graph_t { 26 unsigned int n_nodes; 27 unsigned int n_edges; 28 int last_index; 29 RList *nodes; /* RGraphNode */ 30 } RGraph; 31 32 typedef struct r_graph_visitor_t { 33 void (*discover_node)(RGraphNode *n, struct r_graph_visitor_t *vis); 34 void (*finish_node)(RGraphNode *n, struct r_graph_visitor_t *vis); 35 void (*tree_edge)(const RGraphEdge *e, struct r_graph_visitor_t *vis); 36 void (*back_edge)(const RGraphEdge *e, struct r_graph_visitor_t *vis); 37 void (*fcross_edge)(const RGraphEdge *e, struct r_graph_visitor_t *vis); 38 void *data; 39 } RGraphVisitor; 40 typedef void (*RGraphNodeCallback)(RGraphNode *n, RGraphVisitor *vis); 41 typedef void (*RGraphEdgeCallback)(const RGraphEdge *e, RGraphVisitor *vis); 42 43 // Contrructs a new RGraph, returns heap-allocated graph. 44 R_API RGraph *r_graph_new(void); 45 // Destroys the graph and all nodes. 46 R_API void r_graph_free(RGraph* g); 47 // Gets the data of a node by index. 48 R_API RGraphNode *r_graph_get_node(const RGraph *g, unsigned int idx); 49 R_API RListIter *r_graph_node_iter(const RGraph *g, unsigned int idx); 50 R_API void r_graph_reset(RGraph *g); 51 R_API RGraphNode *r_graph_add_node(RGraph *g, void *data); 52 R_API RGraphNode *r_graph_add_nodef(RGraph *g, void *data, RListFree user_free); 53 // XXX 'n' is destroyed after calling this function. 54 R_API void r_graph_del_node(RGraph *g, RGraphNode *n); 55 R_API void r_graph_add_edge(RGraph *g, RGraphNode *from, RGraphNode *to); 56 R_API void r_graph_add_edge_at(RGraph *g, RGraphNode *from, RGraphNode *to, int nth); 57 R_API RGraphNode *r_graph_node_split_forward(RGraph *g, RGraphNode *split_me, void *data); 58 R_API void r_graph_del_edge(RGraph *g, RGraphNode *from, RGraphNode *to); 59 R_API const RList *r_graph_get_neighbours(const RGraph *g, const RGraphNode *n); 60 R_API RGraphNode *r_graph_nth_neighbour(const RGraph *g, const RGraphNode *n, int nth); 61 R_API const RList *r_graph_innodes(const RGraph *g, const RGraphNode *n); 62 R_API const RList *r_graph_all_neighbours(const RGraph *g, const RGraphNode *n); 63 R_API const RList *r_graph_get_nodes(const RGraph *g); 64 R_API bool r_graph_adjacent(const RGraph *g, const RGraphNode *from, const RGraphNode *to); 65 R_API void r_graph_dfs_node(RGraph *g, RGraphNode *n, RGraphVisitor *vis); 66 R_API void r_graph_dfs_node_reverse(RGraph *g, RGraphNode *n, RGraphVisitor *vis); 67 R_API void r_graph_dfs(RGraph *g, RGraphVisitor *vis); 68 69 #ifdef __cplusplus 70 } 71 #endif 72 73 #endif // R_GRAPH_H 74