-
Notifications
You must be signed in to change notification settings - Fork 4
/
bipartite.c
96 lines (71 loc) · 1.71 KB
/
bipartite.c
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/* bipartite.c
* two color a bipartite graph
*
* by: steven Skiena
*
* 2015-05-02 23:57
* Altered by James Shi
*/
#include <stdio.h>
#include "bool.h"
#include "graph.h"
#include "queue.h"
extern bool processed[]; /* which vertices have been processed */
extern bool discovered[]; /* which vertices have been found */
extern int parent[]; /* discovery relation */
extern int entry_time[MAXV+1]; /* time of vertex entry */
extern int exit_time[MAXV+1]; /* time of vertex exit */
#define UNCOLORED 0 /* vertex not yet colored */
#define WHITE 1 /* white vertex */
#define BLACK 2 /* black vertex */
int color[MAXV+1]; /* assigned color of v */
bool bipartite; /* is the graph bipartite? */
void process_vertex_early(int v)
{
}
void process_vertex_late(int v)
{
}
void process_edge(int x, int y)
{
// y already has a color
if (color[x] == color[y]) {
bipartite = FALSE;
printf("Warning: graph not bipartite, due to (%d,%d)\n",x,y);
}
color[y] = complement(color[x]);
}
void complement(int color)
{
if (color == WHITE) return(BLACK);
if (color == BLACK) return(WHITE);
return(UNCOLORED);
}
void twocolor(graph *g)
{
int i; /* counter */
for (i=1; i<=(g->nvertices); i++)
color[i] = UNCOLORED;
bipartite = TRUE;
initialize_search(&g);
/* using for to dealing with unconnected graph */
for (i=1; i<=(g->nvertices); i++) {
if (discovered[i] == FALSE) {
color[i] = WHITE;
bfs(g,i);
}
}
}
int main()
{
graph g;
int i;
read_graph(&g,FALSE);
print_graph(&g);
twocolor(&g);
printf("the color of nodes\n");
for (i=1; i<=(g.nvertices); i++)
printf("%d: %d\n", i, color[i]);
printf("\n");
return 0;
}