File: graph.h

package info (click to toggle)
cliquer 1.21-1
  • links: PTS, VCS
  • area: main
  • in suites: jessie, jessie-kfreebsd, stretch, wheezy
  • size: 484 kB
  • sloc: ansic: 5,394; makefile: 180
file content (73 lines) | stat: -rw-r--r-- 2,028 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#ifndef CLIQUER_GRAPH_H
#define CLIQUER_GRAPH_H

#include "set.h"

typedef struct _graph_t graph_t;
struct _graph_t {
	int n;             /* Vertices numbered 0...n-1 */
	set_t *edges;      /* A list of n sets (the edges). */
	int *weights;      /* A list of n vertex weights. */
};


#define GRAPH_IS_EDGE_FAST(g,i,j)  (SET_CONTAINS_FAST((g)->edges[(i)],(j)))
#define GRAPH_IS_EDGE(g,i,j) (((i)<((g)->n))?SET_CONTAINS((g)->edges[(i)], \
							  (j)):FALSE)
#define GRAPH_ADD_EDGE(g,i,j) do {            \
	SET_ADD_ELEMENT((g)->edges[(i)],(j)); \
	SET_ADD_ELEMENT((g)->edges[(j)],(i)); \
} while (FALSE)
#define GRAPH_DEL_EDGE(g,i,j) do {            \
	SET_DEL_ELEMENT((g)->edges[(i)],(j)); \
	SET_DEL_ELEMENT((g)->edges[(j)],(i)); \
} while (FALSE)


PUBLIC graph_t *graph_new(int n);
PUBLIC void graph_free(graph_t *g);
PUBLIC void graph_resize(graph_t *g, int size);
PUBLIC void graph_crop(graph_t *g);

PUBLIC boolean graph_weighted(graph_t *g);
PUBLIC int graph_edge_count(graph_t *g);

PUBLIC graph_t *graph_read_dimacs(FILE *fp);
PUBLIC graph_t *graph_read_dimacs_file(char *file);
PUBLIC boolean graph_write_dimacs_ascii(graph_t *g, char *comment,FILE *fp);
PUBLIC boolean graph_write_dimacs_ascii_file(graph_t *g,char *comment,
					     char *file);
PUBLIC boolean graph_write_dimacs_binary(graph_t *g, char *comment,FILE *fp);
PUBLIC boolean graph_write_dimacs_binary_file(graph_t *g, char *comment,
					      char *file);

PUBLIC void graph_print(graph_t *g);
PUBLIC boolean graph_test(graph_t *g, FILE *output);
PUBLIC int graph_test_regular(graph_t *g);

UNUSED_FUNCTION INLINE
static int graph_subgraph_weight(graph_t *g,set_t s) {
	int i,j;
	int count=0;
	setelement e;

	for (i=0; i<SET_ARRAY_LENGTH(s); i++) {
		if (s[i]) {
			e=s[i];
			for (j=0; j<ELEMENTSIZE; j++) {
				if (e&1)
					count+=g->weights[i*ELEMENTSIZE+j];
				e = e>>1;
			}
		}
	}
	return count;
}

UNUSED_FUNCTION INLINE
static int graph_vertex_degree(graph_t *g, int v) {
	return set_size(g->edges[v]);
}

#endif /* !CLIQUER_GRAPH_H */