void twocolor(graph *g) { int i; for (i = 1; i <= g->nvertices; i++) { color[i] = UNCOLORED; } bipartite = true; initialize_search(g); for (i = 1; i <= g->nvertices; i++) { if (discovered[i] == false) { color[i] = WHITE; bfs(g, i); } } } void process_edge(int x, int y) { if ((color[x] == color[y]) && (color[x] != UNCOLORED)) { bipartite = false; printf("Warning: not bipartite due to (%d, %d) \n", x, y); } color[y] = complement(color[x]);
} enum Color {UNCOLORED, WHITE, BLACK}; bool bipartite; Color color[MAXV + 1]; Color complement(Color color) { if (color == WHITE) return BLACK; if (color == BLACK) return WHITE; return UNCOLORED;
} void bfs(graph *g, int start) { std::queue <int> q;
int v; int y; edgenode *p;
q.push(start); discovered[start] = true;
while(!q.empty()) { v = q.front(); q.pop(); process_vertex_early(v); processed[v] = true; p = g->edges[v]; while (p != NULL) { y = p->y; if ((processed[y] == false) || g->directed) process_edge(v, y); if (discovered[y] == false) { q.push(y); discovered[y] = true; parent[y] = v; } p = p->next; } process_vertex_late(v); }
} |
Algorithms > Graph >