TaPAS  0.2
ccl-graph.h
Go to the documentation of this file.
1 /*
2  * ccl-graph.h -- Generic graph
3  *
4  * This file is a part of the C Common Library (CCL) project.
5  *
6  * Copyright (C) 2010 CNRS UMR 5800 & Université Bordeaux I (see AUTHORS file).
7  *
8  * This program is free software; you can redistribute it and/or modify
9  * it under the terms of the AltaRica Public License that comes with this
10  * package.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
15  */
16 
22 #ifndef __CCL_GRAPH_H__
23 # define __CCL_GRAPH_H__
24 
25 # include <ccl/ccl-log.h>
26 # include <ccl/ccl-hash.h>
27 # include <ccl/ccl-list.h>
28 # include <ccl/ccl-tree.h>
29 
30 BEGIN_C_DECLS
31 
32 typedef struct ccl_graph_st ccl_graph;
33 
34 typedef struct ccl_vertex_st ccl_vertex;
35 typedef ccl_hash_methods ccl_vertex_data_methods;
36 typedef void ccl_vertex_map_proc (ccl_vertex *v, void *data);
37 typedef int ccl_vertex_search_func (ccl_vertex *v, void *data);
38 CCL_ITERATOR_TYPEDEF (ccl_vertex_iterator, ccl_vertex *);
39 
40 typedef struct ccl_edge_st ccl_edge;
41 typedef ccl_hash_methods ccl_edge_data_methods;
42 typedef void ccl_edge_map_proc (ccl_edge *v, void *data);
43 CCL_ITERATOR_TYPEDEF (ccl_edge_iterator, ccl_edge *);
44 
45 extern const ccl_vertex_data_methods *CCL_GRAPH_DEFAULT_VERTEX_METHODS;
46 extern const ccl_edge_data_methods *CCL_GRAPH_DEFAULT_EDGE_METHODS;
47 
48  /* --------------- */
49 
50 extern ccl_graph *
51 ccl_graph_create (const ccl_vertex_data_methods *vertex_methods,
52  const ccl_edge_data_methods *edge_methods);
53 
54 #define ccl_graph_create_default() \
55  (ccl_graph_create (CCL_GRAPH_DEFAULT_VERTEX_METHODS, \
56  CCL_GRAPH_DEFAULT_EDGE_METHODS))
57 
58 extern ccl_graph *
59 ccl_graph_add_reference (ccl_graph *G);
60 
61 extern void
62 ccl_graph_del_reference (ccl_graph *G);
63 
64 extern int
65 ccl_graph_get_number_of_vertices (const ccl_graph *G);
66 
67 extern void
68 ccl_graph_map_vertices (ccl_graph *G, ccl_vertex_map_proc *map, void *data);
69 
70 extern ccl_vertex_iterator *
71 ccl_graph_get_vertices (const ccl_graph *G);
72 
73 extern int
74 ccl_graph_get_number_of_edges (const ccl_graph *G);
75 
76 extern void
77 ccl_graph_map_edges (ccl_graph *G, ccl_edge_map_proc *map, void *data);
78 
79 extern ccl_edge_iterator *
80 ccl_graph_get_edges (const ccl_graph *G);
81 
82 extern void
83 ccl_graph_log_as_dot (ccl_log_type log, ccl_graph *G,
84  void (*graph_attributes) (ccl_log_type log,
85  ccl_graph *G,
86  void *cbdata),
87  void *graph_cb_data,
88  void (*dot_vertex_data)(ccl_log_type log,
89  ccl_vertex *v,
90  void *cbdata),
91  void *vertex_cb_data,
92  void (*dot_edge_data)(ccl_log_type log,
93  ccl_edge *e,
94  void *cbdata),
95  void *edge_cb_data);
96 
97 extern ccl_graph *
98 ccl_graph_dup (ccl_graph *G,
99  ccl_duplicate_func *dup_vertex_data,
100  ccl_duplicate_func *dup_edge_data);
101 
102  /* --------------- */
103 
104 extern ccl_vertex *
105 ccl_graph_find_or_add_vertex (ccl_graph *G, void *data);
106 
107 extern ccl_vertex *
108 ccl_graph_add_vertex (ccl_graph *G, void *data);
109 
110 extern void
111 ccl_graph_remove_vertex (ccl_graph *G, ccl_vertex *v, int merge_edges);
112 
113 extern ccl_vertex *
114 ccl_graph_get_vertex (const ccl_graph *G, void *data);
115 
116 extern void *
117 ccl_vertex_get_data (ccl_vertex *v);
118 
119 extern void
120 ccl_vertex_map_edges (ccl_vertex *v, ccl_edge_map_proc *map, void *data);
121 
122 extern ccl_edge_iterator *
123 ccl_vertex_get_edges (ccl_vertex *v);
124 
125 extern int
126 ccl_vertex_get_degree (ccl_vertex *v);
127 
128 extern void
129 ccl_vertex_map_in_edges (ccl_vertex *v, ccl_edge_map_proc *map, void *data);
130 
131 extern ccl_edge_iterator *
132 ccl_vertex_get_in_edges (ccl_vertex *v);
133 
134 extern int
135 ccl_vertex_get_in_degree (const ccl_vertex *v);
136 
137 extern void
138 ccl_vertex_map_out_edges (ccl_vertex *v, ccl_edge_map_proc *map, void *data);
139 
140 extern ccl_edge_iterator *
141 ccl_vertex_get_out_edges (ccl_vertex *v);
142 
143 extern int
144 ccl_vertex_get_out_degree (const ccl_vertex *v);
145 
146 extern int
147 ccl_vertex_has_successor (ccl_vertex *v, ccl_vertex *w);
148 
149 extern ccl_vertex_iterator *
150 ccl_vertex_get_successors (ccl_vertex *v);
151 
152 extern void
153 ccl_vertex_map_successors (ccl_vertex *v, ccl_vertex_map_proc *map,
154  void *data);
155 
156 extern int
157 ccl_vertex_has_predecessor (ccl_vertex *v, ccl_vertex *w);
158 
159 extern ccl_vertex_iterator *
160 ccl_vertex_get_predecessors (ccl_vertex *v);
161 
162 extern void
163 ccl_vertex_map_predecessors (ccl_vertex *v, ccl_vertex_map_proc *map,
164  void *data);
165 
166  /* --------------- */
167 
168 extern ccl_edge *
169 ccl_graph_add_edge (ccl_graph *G, ccl_vertex *src, ccl_vertex *dst, void *data);
170 
171 extern ccl_edge *
172 ccl_graph_add_data_edge (ccl_graph *G, void *sdata, void *ddata, void *data);
173 
174 extern void
175 ccl_graph_remove_edge (ccl_graph *G, ccl_edge *e);
176 
177 extern void *
178 ccl_edge_get_data (const ccl_edge *e);
179 
180 extern ccl_vertex *
181 ccl_edge_get_src (const ccl_edge *e);
182 
183 extern ccl_vertex *
184 ccl_edge_get_tgt (const ccl_edge *e);
185 
186  /* --------------- */
187 
188 extern void
189 ccl_graph_dfs (ccl_graph *G, ccl_vertex *root, int backward,
190  ccl_vertex_search_func *map, void *cbdata);
191 
192 extern void
193 ccl_graph_bfs (ccl_graph *G, ccl_vertex *root, int backward,
194  ccl_vertex_search_func *search, void *cbdata);
195 
196 extern void
197 ccl_graph_reverse_edges (ccl_graph *G);
198 
199 extern ccl_vertex_iterator *
200 ccl_graph_get_roots (ccl_graph *G);
201 
202 extern ccl_vertex_iterator *
203 ccl_graph_get_leaves (ccl_graph *G);
204 
205 extern int
206 ccl_graph_compute_scc (ccl_graph *G,
207  void (*attach)(ccl_graph *G, void *data, int comp,
208  void *cbdata),
209  void *cbdata);
210 
211 extern ccl_list *
212 ccl_graph_topological_order (ccl_graph *G);
213 
214 extern void
215 ccl_graph_map_reachables_from (ccl_graph *G, ccl_vertex *from,
216  ccl_vertex_search_func *search, void *cbdata);
217 
218 extern int
219 ccl_graph_is_reachable_from (ccl_graph *G, ccl_vertex *from, ccl_vertex *to);
220 
221 extern ccl_graph *
222 ccl_graph_compute_scc_graph (ccl_graph *G,
223  ccl_hash **p_v2comp,
224  void (*attach)(ccl_graph *G,
225  ccl_vertex *v,
226  ccl_vertex *sccv,
227  void *data),
228  void *cbdata);
229 
230 extern ccl_list *
231 ccl_graph_compute_modules (ccl_graph *G, int with_leaves);
232 
240 extern ccl_tree *
241 ccl_graph_compute_lsa_tree (ccl_graph *G, ccl_hash **p_v2t);
242 
243 END_C_DECLS
244 
245 #endif /* ! __CCL_GRAPH_H__ */
ccl_graph_compute_lsa_tree
ccl_tree * ccl_graph_compute_lsa_tree(ccl_graph *G, ccl_hash **p_v2t)
ccl-list.h
Generic simple linked list.
ccl_tree_st
Structure storing a node of a generic tree.
Definition: ccl-tree.h:40
CCL_ITERATOR_TYPEDEF
#define CCL_ITERATOR_TYPEDEF(_typename_, _eltype_)
Macro-function used to define and declare a new iterator type.
Definition: ccl-iterator.h:43
ccl_list
struct ccl_list_st ccl_list
Type of a generic list.
Definition: ccl-list.h:33
ccl-tree.h
Generic not ordered tree structure.
ccl_duplicate_func
void * ccl_duplicate_func(void *ptr)
Prototype of functions used to duplicate an object pointed by ptr.
Definition: ccl-protos.h:89
ccl_log_type
enum ccl_log_type_enum ccl_log_type
Enum that indicates which kind of message has to be displayed. Each kind of message can be displayed ...
Definition: ccl-log.h:50
ccl-hash.h
A dynamic association table implemented by hashing.
ccl_hash
struct ccl_hash_st ccl_hash
abstract type of an hash table.
Definition: ccl-hash.h:57
ccl-log.h
Message displayer.
Generated by   doxygen 1.8.5