[ create a new paste ] login | about

Link: http://codepad.org/E8oB9VCx    [ raw code | output | fork ]

maweaver - C, pasted on Nov 8:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTICES 250

#define ADJ(v1, v2) adjacent[(v1) * num_vertices + (v2)]

int num_test_cases;             //<! Number of test cases
int num_edges;                  //<! Number of edges
int num_vertices;               //<! Number of vertices
int weights[MAX_VERTICES];      //<! Vertex weights
int colors[MAX_VERTICES];       //<! Vertex colors
int adjacent[MAX_VERTICES * MAX_VERTICES - 1];      //<! Flattened adjacency matrix

int cur_clique[MAX_VERTICES];   //<! Current clique
int cur_clique_size;            //<! Size of the current clique
int cur_clique_weight;          //<! Weight of the current clique

int best_clique_weight;         //<! Weight of the best clique

/*!
 *  Expand each vertex of the given graph against the current clique.
 */
void expand(int *graph, int graph_size) {
	bool any_expanded = false;

	/* Loop through each vertex in the graph */
	for(int i = 0; i < graph_size; i++) {
		/* See if it is expandable -- if it is adjacent to all vertices in the clique */
		bool expandable = true;
		for(int j = 0; j < cur_clique_size; j++) {
			if(!ADJ(graph[i], cur_clique[j])) {
				expandable = false;
				break;
			}
		}
		if(expandable) {
			any_expanded = true;

			/* Add it to the current clique */
			cur_clique[cur_clique_size++] = graph[i];
			cur_clique_weight += weights[graph[i]];

			/* Build a new graph of all vertices in this graph adjacent to it */
			int *next_graph = malloc(graph_size * sizeof(int));
			int next_graph_size = 0;
			for(int j = 0; j < graph_size; j++) {
				if(j != i && ADJ(graph[i], graph[j])) {
					next_graph[next_graph_size++] = graph[j];
				}
			}

			/* Expand the next graph */
			expand(next_graph, next_graph_size);

			/* Destroy the temporary graph */
			free(next_graph);

			/* Remove it from the current clique */
			cur_clique_size--;
			cur_clique_weight -= weights[graph[i]];
		}
	}

	if(!any_expanded && cur_clique_weight > best_clique_weight) {
		best_clique_weight = cur_clique_weight;
	}
}

/*!
 *  Find the maximum clique
 */
void max_clique()
{
	/* Initialize */
	best_clique_weight  = 0;
	cur_clique_size     = 0; 
	cur_clique_weight   = 0;

	/* Expand the full graph */
	int * full_graph = malloc(num_vertices * sizeof(int));
	for(int i = 0; i < num_vertices; i++) {
		full_graph[i] = i;
	}
	expand(full_graph, num_vertices);
}

int main(int argc, char **argv) 
{
	scanf("%d", &num_test_cases);
	for(int i = 0; i < num_test_cases; i++) {

		/* Reset data */
		scanf("%d %d", &num_vertices, &num_edges);
		for(int j = 0; j < num_vertices * num_vertices - 1; j++) {
			adjacent[j] = 1;
		}
		memset(colors, 0, num_vertices);

		/* Read vertices */
		for(int j = 0; j < num_vertices; j++) {
			scanf("%d", &weights[j]);
		}
	
		/* Read edges */
		for(int j = 0; j < num_edges; j++) {
			int v1, v2;		
			scanf("%d %d", &v1, &v2);
			ADJ(v1 - 1, v2 - 1) = 0;
			ADJ(v2 - 1, v1 - 1) = 0;
		}

		/* Do the work */
		max_clique();

		/* Show the results */
		printf("%d\n", best_clique_weight);
	}
	
	return 0;
}


Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In function 'expand':
Line 30: error: 'for' loop initial declaration used outside C99 mode
Line 33: error: 'for' loop initial declaration used outside C99 mode
Line 49: error: 'for' loop initial declaration used outside C99 mode
In function 'max_clique':
Line 84: error: 'for' loop initial declaration used outside C99 mode
In function 'main':
Line 93: error: 'for' loop initial declaration used outside C99 mode
Line 97: error: 'for' loop initial declaration used outside C99 mode
Line 103: error: redefinition of 'j'
Line 97: error: previous definition of 'j' was here
Line 103: error: 'for' loop initial declaration used outside C99 mode
Line 108: error: redefinition of 'j'
Line 103: error: previous definition of 'j' was here
Line 108: error: 'for' loop initial declaration used outside C99 mode


Create a new paste based on this one


Comments: