00001 #ifndef GRAPH_H
00002 #define GRAPH_H
00003
00004 typedef char *gGeneric;
00005
00006 typedef struct graph_struct {
00007 gGeneric user_data;
00008 } graph_t;
00009
00010 typedef struct vertex_struct {
00011 gGeneric user_data;
00012 } vertex_t;
00013
00014 typedef struct edge_struct {
00015 gGeneric user_data;
00016 } edge_t;
00017
00018 typedef void (*GRAPH_PFV)(gGeneric);
00019 typedef gGeneric (*GRAPH_PFG)(gGeneric);
00020
00021 EXTERN graph_t *g_alloc ARGS((void));
00022 EXTERN void g_free ARGS((graph_t *, void(*)(gGeneric), void(*)(gGeneric), void(*)(gGeneric)));
00023 EXTERN void g_check ARGS((graph_t *));
00024 EXTERN graph_t *g_dup ARGS((graph_t *, gGeneric(*)(gGeneric), gGeneric(*)(gGeneric), gGeneric(*)(gGeneric)));
00025
00026 EXTERN lsList g_get_vertices ARGS((graph_t *));
00027
00028 #define foreach_vertex(g, lgen, v) \
00029 for (lgen = lsStart(g_get_vertices(g)); \
00030 lsNext(lgen, &v, LS_NH) == LS_OK \
00031 || ((void) lsFinish(lgen), 0); )
00032
00033 #define foreach_edge(g, lgen, e) \
00034 for (lgen = lsStart(g_get_edges(g)); \
00035 lsNext(lgen, &e, LS_NH) == LS_OK \
00036 || ((void) lsFinish(lgen), 0); )
00037
00038 EXTERN vertex_t *g_add_vertex ARGS((graph_t *));
00039 EXTERN void g_delete_vertex ARGS((vertex_t *, void (*)(gGeneric), void (*)(gGeneric)));
00040 EXTERN graph_t *g_vertex_graph ARGS((vertex_t *));
00041
00042 EXTERN lsList g_get_edges ARGS((graph_t *));
00043 EXTERN lsList g_get_in_edges ARGS((vertex_t *));
00044 EXTERN lsList g_get_out_edges ARGS((vertex_t *));
00045
00046 #define foreach_in_edge(v, lgen, e) \
00047 for (lgen = lsStart(g_get_in_edges(v)); \
00048 lsNext(lgen, &e, LS_NH) == LS_OK \
00049 || ((void) lsFinish(lgen), 0); )
00050
00051 #define foreach_out_edge(v, lgen, e) \
00052 for (lgen = lsStart(g_get_out_edges(v)); \
00053 lsNext(lgen, &e, LS_NH) == LS_OK \
00054 || ((void) lsFinish(lgen), 0); )
00055
00056 EXTERN edge_t *g_add_edge ARGS((vertex_t *, vertex_t *));
00057 EXTERN void g_delete_edge ARGS((edge_t *, void (*)(gGeneric)));
00058 EXTERN graph_t *g_edge_graph ARGS((edge_t *));
00059 EXTERN vertex_t *g_e_source ARGS((edge_t *));
00060 EXTERN vertex_t *g_e_dest ARGS((edge_t *));
00061
00062 EXTERN array_t *g_dfs ARGS((graph_t *));
00063 EXTERN int g_is_acyclic ARGS((graph_t *));
00064 EXTERN array_t *g_graph_sort ARGS((graph_t *, int (*)(const void *, const void *)));
00065
00066 EXTERN st_table *g_reachable ARGS((graph_t *, st_table *));
00067 EXTERN st_table *g_EF ARGS((graph_t *, st_table *));
00068 EXTERN st_table *g_SCC ARGS((graph_t *, st_table *));
00069
00070 #endif
