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  /* --------------- */
46 
47 extern ccl_graph *
48 ccl_graph_create (ccl_vertex_data_methods *vertex_methods,
49  ccl_edge_data_methods *edge_methods);
50 
51 extern ccl_graph *
52 ccl_graph_add_reference (ccl_graph *G);
53 
54 extern void
55 ccl_graph_del_reference (ccl_graph *G);
56 
57 extern int
58 ccl_graph_get_number_of_vertices (ccl_graph *G);
59 
60 extern void
61 ccl_graph_map_vertices (ccl_graph *G, ccl_vertex_map_proc *map, void *data);
62 
63 extern ccl_vertex_iterator *
64 ccl_graph_get_vertices (ccl_graph *G);
65 
66 extern int
67 ccl_graph_get_number_of_edges (ccl_graph *G);
68 
69 extern void
70 ccl_graph_map_edges (ccl_graph *G, ccl_edge_map_proc *map, void *data);
71 
72 extern ccl_edge_iterator *
73 ccl_graph_get_edges (ccl_graph *G);
74 
75 extern void
76 ccl_graph_log_as_dot (ccl_log_type log, ccl_graph *G,
77  void (*graph_attributes) (ccl_log_type log,
78  ccl_graph *G,
79  void *cbdata),
80  void *graph_cb_data,
81  void (*dot_vertex_data)(ccl_log_type log,
82  ccl_vertex *v,
83  void *cbdata),
84  void *vertex_cb_data,
85  void (*dot_edge_data)(ccl_log_type log,
86  ccl_edge *e,
87  void *cbdata),
88  void *edge_cb_data);
89 
90 extern ccl_graph *
91 ccl_graph_dup (ccl_graph *G,
92  ccl_duplicate_func *dup_vertex_data,
93  ccl_duplicate_func *dup_edge_data);
94 
95  /* --------------- */
96 
97 extern ccl_vertex *
98 ccl_graph_find_or_add_vertex (ccl_graph *G, void *data);
99 
100 extern ccl_vertex *
101 ccl_graph_add_vertex (ccl_graph *G, void *data);
102 
103 extern void
104 ccl_graph_remove_vertex (ccl_graph *G, ccl_vertex *v);
105 
106 extern ccl_vertex *
107 ccl_graph_get_vertex (const ccl_graph *G, void *data);
108 
109 extern void *
110 ccl_vertex_get_data (ccl_vertex *v);
111 
112 extern void
113 ccl_vertex_map_edges (ccl_vertex *v, ccl_edge_map_proc *map, void *data);
114 
115 extern ccl_edge_iterator *
116 ccl_vertex_get_edges (ccl_vertex *v);
117 
118 extern int
119 ccl_vertex_get_degree (ccl_vertex *v);
120 
121 extern void
122 ccl_vertex_map_in_edges (ccl_vertex *v, ccl_edge_map_proc *map, void *data);
123 
124 extern ccl_edge_iterator *
125 ccl_vertex_get_in_edges (ccl_vertex *v);
126 
127 extern int
128 ccl_vertex_get_in_degree (const ccl_vertex *v);
129 
130 extern void
131 ccl_vertex_map_out_edges (ccl_vertex *v, ccl_edge_map_proc *map, void *data);
132 
133 extern ccl_edge_iterator *
134 ccl_vertex_get_out_edges (ccl_vertex *v);
135 
136 extern int
137 ccl_vertex_get_out_degree (const ccl_vertex *v);
138 
139 extern int
140 ccl_vertex_has_successor (ccl_vertex *v, ccl_vertex *w);
141 
142 extern ccl_vertex_iterator *
143 ccl_vertex_get_successors (ccl_vertex *v);
144 
145 extern int
146 ccl_vertex_has_predecessor (ccl_vertex *v, ccl_vertex *w);
147 
148 extern ccl_vertex_iterator *
149 ccl_vertex_get_predecessors (ccl_vertex *v);
150 
151 
152  /* --------------- */
153 
154 extern ccl_edge *
155 ccl_graph_add_edge (ccl_graph *G, ccl_vertex *src, ccl_vertex *dst, void *data);
156 
157 extern ccl_edge *
158 ccl_graph_add_data_edge (ccl_graph *G, void *sdata, void *ddata, void *data);
159 
160 extern void
161 ccl_graph_remove_edge (ccl_graph *G, ccl_edge *e);
162 
163 extern void *
164 ccl_edge_get_data (const ccl_edge *e);
165 
166 extern ccl_vertex *
167 ccl_edge_get_src (const ccl_edge *e);
168 
169 extern ccl_vertex *
170 ccl_edge_get_tgt (const ccl_edge *e);
171 
172  /* --------------- */
173 
174 extern void
175 ccl_graph_dfs (ccl_graph *G, ccl_vertex *root, int backward,
176  ccl_vertex_search_func *map, void *cbdata);
177 
178 extern void
179 ccl_graph_bfs (ccl_graph *G, ccl_vertex *root, int backward,
180  ccl_vertex_search_func *search, void *cbdata);
181 
182 extern void
183 ccl_graph_reverse_edges (ccl_graph *G);
184 
185 extern ccl_vertex_iterator *
186 ccl_graph_get_roots (ccl_graph *G);
187 
188 extern ccl_vertex_iterator *
189 ccl_graph_get_leaves (ccl_graph *G);
190 
191 extern int
192 ccl_graph_compute_scc (ccl_graph *G,
193  void (*attach)(ccl_graph *G, void *data, int comp,
194  void *cbdata),
195  void *cbdata);
196 
197 extern ccl_list *
198 ccl_graph_topological_order (ccl_graph *G);
199 
200 extern int
201 ccl_graph_is_reachable_from (ccl_graph *G, ccl_vertex *from, ccl_vertex *to);
202 
203 extern ccl_graph *
204 ccl_graph_compute_scc_graph (ccl_graph *G, ccl_hash **p_v2comp);
205 
206 extern ccl_list *
207 ccl_graph_compute_modules (ccl_graph *G, int with_leaves);
208 
216 extern ccl_tree *
217 ccl_graph_compute_lsa_tree (ccl_graph *G, ccl_hash **p_v2t);
218 
219 END_C_DECLS
220 
221 #endif /* ! __CCL_GRAPH_H__ */
ccl_tree * ccl_graph_compute_lsa_tree(ccl_graph *G, ccl_hash **p_v2t)
Generic simple linked list.
Structure storing a node of a generic tree.
Definition: ccl-tree.h:40
#define CCL_ITERATOR_TYPEDEF(_typename_, _eltype_)
Macro-function used to define and declare a new iterator type.
Definition: ccl-iterator.h:43
struct ccl_list_st ccl_list
Type of a generic list.
Definition: ccl-list.h:33
Generic not ordered tree structure.
void * ccl_duplicate_func(void *ptr)
Prototype of functions used to duplicate an object pointed by ptr.
Definition: ccl-protos.h:84
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
A dynamic association table implemented by hashing.
struct ccl_hash_st ccl_hash
abstract type of an hash table.
Definition: ccl-hash.h:57
Message displayer.