maxcut.cpp

#include "../main.h"
#include <stdlib.h>
#include <assert.h>
#include <cstring>

using std::pair;

const int VERSION = 1;
const bool ALLOW_MISTAKES = 1;

struct Nd {
	vector<pair<Nd *, int>> edges; // target node, weight
	bool color = false;
};


void calc_maxcut_naive(Nd * nd, int nd_size)
{
	fo(i, nd_size) nd[i].color = false;
	bool change = true;
	while(change)
	{
		change = false;
		fo(i, nd_size)
		{
			int count = 0;
			int wrong = 0;
			for(auto [target, weight] : nd[i].edges)
			{
				if(nd[i].color == target->color)
					wrong += weight;
				count += weight;
			}
			if(wrong > count - wrong)
			{
				nd[i].color = !nd[i].color;
				change = true;
			}
		}
	}
}

void calc_maxcut_gw(Nd * nd, int nd_size)
{
	auto [p_stdin, p_stdout] = lib::dualpopen("julia");
	{
		vector<vector<int>> matrix(nd_size, vector<int>(nd_size, 0));
		fo(i, nd_size)
			for(auto [target, weight] : nd[i].edges)
				matrix[i][target-nd] += weight;

		fprintf(p_stdin,
				"include(\"MaxCut.jl/src/MaxCut.jl\");\
				using Random;\
				Random.seed!(3);\
				MaxCut.maxcut([");
		fo(i,nd_size)
		{
			fo(j, nd_size) fprintf(p_stdin, " %d", matrix[i][j]);
			fprintf(p_stdin, ";");
			//fo(j, nd_size) fprintf(stderr, " %d", matrix[i][j]);
			//fprintf(stderr, ";\n");
		}
		fprintf(p_stdin, "])[2][1]\n");
	}
	fflush(p_stdin);

	char * line;
	int elements;
	assert(fscanf(p_stdout, "%d%m[^\n]", &elements, &line)==2);
	assert(!strcmp(line, "-element Vector{Int64}:"));
	delete [] line;

	fo(i, nd_size) nd[i].color = false;
	fo(i, elements)
	{
		int val;
		assert(fscanf(p_stdout, "%d", &val)==1);
		val--;
		//fprintf(stderr, "-> %d\n", val);
		nd[val].color = true;
	}
	fclose(p_stdin);
	fclose(p_stdout);
}

void calc_maxcut(Nd * nd, int nd_size, const char * algorithm)
{
	if(!strcmp("naive", algorithm)) calc_maxcut_naive(nd, nd_size);
	else
	if(!strcmp("gw", algorithm)) calc_maxcut_gw(nd, nd_size);
	else assert(false);
}

vector<bool> solve(int n, vector<int> input,
		int argc, char const* const* argv)
{
	assert(argc==2);
	int cars_per_vertex = atoi(argv[0]);
	assert(cars_per_vertex>0);
	const char * maxcut_algorithm = argv[1];
	vector<int> other = lib::gen_arr_other_car_of_type(n, input);
	vector<bool> out(2*n);
	int nd_size = (2*n -1)/cars_per_vertex + 1;
		// ceil(2n / cars_per_vertex)
	Nd * nd = new Nd[nd_size];
	fo(i, 2*n)
	{
		int a = i/cars_per_vertex;
		int b = other[i]/cars_per_vertex;
		if(a != b)
			nd[a].edges.push_back({nd + b, 1});
	}

	calc_maxcut(nd, nd_size, maxcut_algorithm);

	fo(i, 2*n)
		out[i] = nd[i/cars_per_vertex].color;

	return out;
}