graph

graph.cpp

#define MAXV 1000

bool processed[MAXV+1];
bool discovered[MAXV+1];
int parent[MAXV+1];

struct edgenode {
	int y;
	int weight;
	edgenode *next;
	edgenode(int _y) : y(_y) {}
};

struct graph {
	edgenode *edges[MAXV+1];
	int degree[MAXV+1]; // outdegree of each vertex
	int nvertices;
	int nedges;
	bool directed;
};

void init_graph(graph *g, bool directed) {
	g->nvertices = 0;
	g->nedges = 0;
	n->directed = directed;
	for(int i=1; i<=MAXV; i++) {
		g->degree[i] = 0;
		g->edges[i] = NULL;
	}
}

void insert_edge(graph *g, int x, int y, bool directed) {
	edgenode *p = new edgenode(y);
	p->weight = 0;
	p->next = g->edges[x];
	g->edges[x] = p;
	g->degree[x]++;
	if(directed == false)
		insert_edge(g, y, x, true);
	else
		g->nedges++;
}

void read_graph(graph *g, bool directed) {
	init_graph(g, directed);
	int n; // num of edges
	int x, y; // vertices in edge (x, y)
	scanf("%d %d", &(g->nvertices), &n);
	for(int i=1; i<=n; i++) {
		scanf("%d %d", &x, &y);
		insert_edge(g, x, y, directed);
	}
}

// =============================================
void init_search(graph *g) {
	for(int i=1; i<=g->nvertices; i++) {
		processed[i] = discovered[i] = false;
		parent[i] = -1;
	}
}

void process_vertex_late(int v) {
	// do nothing for now
}

void process_vertex_early(int v) {
	printf("processed vertex %d\n", v);
}

void process_edge(int x, int y) {
	printf("processed edge (%d, %d)\n", x, y);
}

void bfs(graph *g, int start) {
	queue q;
	init_queue(&q);
	enqueue(&q, start);
	discovered[start] = true;

	while(empty_queue(&q) == false) {
		int v = dequeue(&q);
		process_vertex_early(v);
		processed[v] = true;

		edgenode *p = g->edges[v];
		while(p != NULL) {
			int y = p->y;
			if(processed[y] == false || g->directed)
				process_edge(v, y);
			if(discovered[y] == false) {
				enqueue(&q, y);
				discovered[y] = true;
				parent[y] = v;
			}
			p = p->next;
		}
		process_vertex_late(v);
	}
}

// =============================================
// find path from start to end
void find_path(int start, int end, int parents[]) {
	if(start == end || end == -1)
		printf("\n%d", start);
	else {
		find_path(start, parents[end], parents);
		printf(" %d", end);
	}
}

// =============================================
// return num of connected components
int connected_components(graph *g) {
	int count = 0;
	init_search(g);
	for(int i=1; i<=g->nvertices; i++) {
		if(discovered[i] == false) {
			count++;
			printf("Component %d:", count);
			bfs(g, i);
			printf("\n");
		}
	}
	return count;
}

// =============================================
#define UNCOLORED 0
#define WHITE 1
#define BLACK 2
int color[MAXV+1];
bool bipartite;

void two_color(graph *g) {
	for(int i=1; i<=g->nvertices; i++)
		color[i] = UNCOLORED;
	bipartite = true;
	init_search(g);
	for(int 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]) {
		bipartite = false;
		printf("Warning: not bipartite due to (%d, %d)\n", x, y);
	}
	color[y] = complement(color[x]);
}

int complement(int col) {
	if(col == WHITE) return BLACK;
	if(col == BLACK) return WHITE;
}

// =============================================
int time = 0;
bool finished = false;
int entry_time[MAXV];
int exit_time[MAXV];

void dfs(graph *g, int v) {
	if(finished) return;
	discovered[v] = true;
	time = time+1;
	entry_time[v] = time;

	process_vertex_early(v);
	edgenode *p = g->edges[v];
	while(p) {
		int y = p->y;
		if(discovered[y] == false) {
			parent[y] = v;
			process_edge(v, y);
			dfs(g, y);
		} else if(!processed[y] || g->directed)
			process_edge(v, y);
		if(finished) return;
		p = p->next;
	}
	process_vertex_late(v);
	time = time+1;
	exit_time[v] = time;

	processed[v] = true;
}