1
2 #ifndef CLIQUER_GRAPH_H
3 #define CLIQUER_GRAPH_H
4
5 #include "cliquer/set.h"
6
7 typedef struct _graph_t graph_t;
8 struct _graph_t {
9 int n; /* Vertices numbered 0...n-1 */
10 set_t *edges; /* A list of n sets (the edges). */
11 int *weights; /* A list of n vertex weights. */
12 };
13
14
15 #define GRAPH_IS_EDGE_FAST(g,i,j) (SET_CONTAINS_FAST((g)->edges[(i)],(j)))
16 #define GRAPH_IS_EDGE(g,i,j) (((i)<((g)->n))?SET_CONTAINS((g)->edges[(i)], \
17 (j)):FALSE)
18 #define GRAPH_ADD_EDGE(g,i,j) do { \
19 SET_ADD_ELEMENT((g)->edges[(i)],(j)); \
20 SET_ADD_ELEMENT((g)->edges[(j)],(i)); \
21 } while (FALSE)
22 #define GRAPH_DEL_EDGE(g,i,j) do { \
23 SET_DEL_ELEMENT((g)->edges[(i)],(j)); \
24 SET_DEL_ELEMENT((g)->edges[(j)],(i)); \
25 } while (FALSE)
26
27
28 extern graph_t *graph_new(int n);
29 extern void graph_free(graph_t *g);
30 extern void graph_resize(graph_t *g, int size);
31 extern void graph_crop(graph_t *g);
32
33 extern boolean graph_weighted(graph_t *g);
34 extern int graph_edge_count(graph_t *g);
35
36 extern graph_t *graph_read_dimacs(FILE *fp);
37 extern graph_t *graph_read_dimacs_file(char *file);
38 extern boolean graph_write_dimacs_ascii(graph_t *g, char *comment,FILE *fp);
39 extern boolean graph_write_dimacs_ascii_file(graph_t *g,char *comment,
40 char *file);
41 extern boolean graph_write_dimacs_binary(graph_t *g, char *comment,FILE *fp);
42 extern boolean graph_write_dimacs_binary_file(graph_t *g, char *comment,
43 char *file);
44
45 extern void graph_print(graph_t *g);
46 extern boolean graph_test(graph_t *g, FILE *output);
47 extern int graph_test_regular(graph_t *g);
48
49 UNUSED_FUNCTION INLINE
graph_subgraph_weight(graph_t * g,set_t s)50 static int graph_subgraph_weight(graph_t *g,set_t s) {
51 int i,j;
52 int count=0;
53 setelement e;
54
55 for (i=0; i<SET_ARRAY_LENGTH(s); i++) {
56 if (s[i]) {
57 e=s[i];
58 for (j=0; j<ELEMENTSIZE; j++) {
59 if (e&1)
60 count+=g->weights[i*ELEMENTSIZE+j];
61 e = e>>1;
62 }
63 }
64 }
65 return count;
66 }
67
68 UNUSED_FUNCTION INLINE
graph_vertex_degree(graph_t * g,int v)69 static int graph_vertex_degree(graph_t *g, int v) {
70 return set_size(g->edges[v]);
71 }
72
73 #endif /* !CLIQUER_GRAPH_H */
74