govno.c

#include "functions.h"

#include <stdio.h>
#include <stdlib.h>

int dots = 0;
int edges = 0;
int minimal = INT_MAX;
int *minimal_path;
struct DOT *dotes;
int buff_b = 0, buff_end = 0, buff_w = 0;

void DoTravel(int nextstep, int min, int *path, int *flags, int it){
	int count = 0;
	path[it] = nextstep;
	flags[nextstep] = 1;
	for (int i = 0; i < dots; i++){
		if (flags[i] == 1)
			count++;
	}
	if (count == dots){
		//min += graph[path[count - 1]][0];
		int hook = 0;
		for (int i = 0; i < edges; i++){
			if (dotes[i].begin == path[dots - 1] && dotes[i].end == 0){
				min += dotes[i].weight;
				hook = 1;
			}
		}
		if (min < minimal && hook == 1){
			minimal = min;
			for (int i = 0; i < dots; i++){
				minimal_path[i] = path[i];
			}
		}
	}
	else{
		for (int i = 0; i < edges; i++){
			if (dotes[i].begin == nextstep && flags[dotes[i].end] != 1){
				int *_path = (int *)malloc(dots*sizeof(int));
				int *_flags = (int *)malloc(dots*sizeof(int));
				for (int i = 0; i < dots; i++){
					_path[i] = path[i];
					_flags[i] = flags[i];
				}
				DoTravel(dotes[i].end, min + dotes[i].weight, _path, _flags, it + 1);
				free(_flags);
				free(_path);
			}
		}
	}
}

void mainmenu(){
	printf("Choose\n");
	printf("Show graph [1] \n");
	printf("Start algo [2] \n");
	printf("Delete vertex [3] \n");
	printf("Delete edge [4] \n");
	printf("Add edge [5] \n");
	int choose = 0;
	scanf("%d", &choose);
	switch (choose){
	case(1) : {
				  showgraph();
				  mainmenu();
				  break;
	}
	case(2) : {
				  startalgo();
				  mainmenu();
				  break;
	}
	case(3) : {
				  deletever();
				  mainmenu();
				  break;

	}
	case(4) : {
				  deleteedge();
				  mainmenu();
				  break;
	}
	case(5) : {
				  addedge();
				  mainmenu();
				  break;
	}
	default:{
				printf("Bad choose! \n\n");
				mainmenu();
	}
	}
}

void startalgo(){
	minimal_path = (int *)malloc(dots *sizeof(int));
	int *path = (int *)malloc(dots*sizeof(int));
	int *flags = (int *)malloc(dots*sizeof(int));
	for (int i = 0; i < dots; i++){
		path[i] = 0;
		flags[i] = 0;
	}
	DoTravel(0, 0, path, flags, 0);

	//сохраняем в graphviz
	printf("\n");
	for (int i = 0; i < dots; i++){
		printf("%d->", minimal_path[i]);
	}
	printf("0");
	printf("    weight: %d", minimal);
	printf("\n");

	FILE *output = fopen("GRAPH.dot", "w");
	fprintf(output, "diagraph  {\n");
	for (int iw = 0; iw < dots; iw++){
		for (int jw = 0; jw < edges; jw++){
			if ((dotes[jw].begin == minimal_path[iw]) && (dotes[jw].end == minimal_path[iw + 1]))
				fprintf(output, "  %d -> %d [ label = \"%d\" ];\n", minimal_path[iw], minimal_path[iw + 1], dotes[jw].weight);
		}
	}
	for (int i = 0; i < edges; i++){
		if (dotes[i].begin == minimal_path[dots - 1] && dotes[i].end == 0){
			fprintf(output, "  %d -> %d [ label = \"%d\" ];\n", dotes[i].begin, 0, dotes[i].weight);
		}
	}

	fprintf(output, "}");
	fclose(output);
}

void showgraph(){
	for (int i = 0; i < edges; i++){
		printf("Edge [%d]: \t begin: %d   end: %d   weight %d \n", i, dotes[i].begin, dotes[i].end, dotes[i].weight);
	}
}

void deleteedge(){
	int edg = 0;
	printf("Input number of edge :  ");
	scanf("%d", &edg);
	if (edg < 0 && edg >= edges)
		printf("BAD!!!\n");
	else{
		for (int i = edg; i < edges - 1; i++){
			dotes[i].begin = dotes[i + 1].begin;
			dotes[i].end = dotes[i + 1].end;
			dotes[i].weight = dotes[i + 1].weight;
		}
		dotes = (struct DOT *)realloc((void *)dotes, (edges = edges - 1)*sizeof(struct DOT));
	}
}

void deletever(){
	int ver = 0;
	printf("Input number of edge :  ");
	scanf("%d", &ver);
	if (ver < 0 && ver >= dots)
		printf("BAD!!!\n");
	else{
		for (int i = 0; i < edges; i++){
			for (int s = 0; s < edges; s++){
				if (dotes[i].begin == ver || dotes[i].end == ver){
					for (int j = i; j < edges - 1; j++){
						dotes[j].begin = dotes[j + 1].begin;
						dotes[j].end = dotes[j + 1].end;
						dotes[j].weight = dotes[j + 1].weight;
					}
					dotes = (struct DOT *)realloc((void *)dotes, (edges = edges - 1)*sizeof(struct DOT));
				}
			}
		}
		for (int p = 0; p < edges; p++){
			if (dotes[p].begin>ver)
				dotes[p].begin -= 1;
			if (dotes[p].end > ver)
				dotes[p].end -= 1;
		}
		dots = dots - 1;
	}
}

void addedge(){
	int tempb = 0;
	int tempe = 0;
	int tempw = 0;
	printf("Input BEGIN and END and WEIGHT: ");
	scanf("%d %d %d", &tempb, &tempe, &tempw);
	if ((tempb < 0 && tempb >= dots) || (tempe < 0 && tempe >= dots) || tempb == tempe)
	{
		printf("BAD\n");
		mainmenu();
	}
	else{
		int target = 0;
		for (int i = 0; i < edges; i++){
			if (tempb == dotes[i].begin && tempe == dotes[i].end)
				target = 1;
		}
		if (target == 1){
			printf("BAD\n");
			mainmenu();
		}
		else{
			dotes = (struct DOT *)realloc((void *)dotes, (edges = edges + 1)*sizeof(struct DOT));
			dotes[edges - 1].begin = tempb;
			dotes[edges - 1].end = tempe;
			dotes[edges - 1].weight = tempw;
		}
	}
}

int parse_string(char *s) {
	int i = 0;
	int j;
	while (s[i] >= '0' && s[i] <= '9')
		++i;
	if (i == 0 || s[i] == '\0')
		return 0;
	char *buffer = (char*)malloc(i + 1);
	for (j = 0; j < i; j++)
		buffer[j] = s[j];
	buffer[i] = '\0';
	buff_b = atoi(buffer);
	free(buffer);

	while ((s[i] < '0' || s[i] > '9') && s[i] != '\0')
		++i;
	if (s[i] == '\0')
		return 0;
	int snd_begin = i;
	while (s[i] >= '0' && s[i] <= '9')
		++i;
	if (s[i] == '\0')
		return 0;
	buffer = (char*)malloc(i - snd_begin + 1);
	for (j = snd_begin; j < i; j++)
		buffer[j - snd_begin] = s[j];
	buffer[i - snd_begin] = '\0';
	buff_end = atoi(buffer);
	free(buffer);

	while ((s[i] < '0' || s[i] > '9') && s[i] != '\0')
		++i;
	if (s[i] == '\0')
		return 0;
	snd_begin = i;
	while (s[i] >= '0' && s[i] <= '9')
		++i;
	if (s[i] == '\0')
		return 0;
	buffer = (char*)malloc(i - snd_begin + 1);
	for (j = snd_begin; j < i; j++)
		buffer[j - snd_begin] = s[j];
	buffer[i - snd_begin] = '\0';
	buff_w = atoi(buffer);
	free(buffer);
	return 1;
}

void loadit(){
	FILE *input = fopen("graph.txt", "r+");
	if (input == NULL){
		printf("CANNOT OPEN THIS \n");
	}
	else{
		char s[1024];
		//dotes = (DOT *)malloc(edges * sizeof(DOT)); // массив структур
		dotes = (struct DOT *)realloc((void *)dotes, (edges)*sizeof(struct DOT));
		while (!feof(input)){
			fgets(s, 1024, input);
			if (parse_string(s)) {
				dotes = (struct DOT *)realloc((void *)dotes, (edges = edges + 1)*sizeof(struct DOT));
				dotes[edges - 1].begin = buff_b;
				dotes[edges - 1].end = buff_end;
				dotes[edges - 1].weight = buff_w;
				if (dotes[edges - 1].begin + 1 >= dots)
					dots = dotes[edges - 1].begin + 1;
				if (dotes[edges - 1].end + 1 >= dots)
					dots = dotes[edges - 1].end + 1;
			}
		}
		fclose(input);
	}
}