graphs.cpp

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include <vector>
#include<windows.h>
#include<iostream>
#include <Windows.h>
#include<fstream>
#include<string>
#include<math.h>

using namespace std;

class Graph
{
private:
	int A[30][30];
	int m;
	std::vector<int> longestPath;
public:
	Graph(char * filename)
	{
		FILE *fp;
		if ((fp = fopen(filename, "r")) == NULL)
		{
			printf("Error \n");
			exit(1);
		}
		fscanf(fp, "%i", &m);
		for (int i = 0; i < m; i++)
			for (int j = 0; j < m; j++)
				fscanf(fp, "%i", &A[i][j]);
	}

	void print()
	{
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < m; j++)
				printf("%4d", A[i][j]);
			printf("\n");
		}
	}

	void calcLongestPath()
	{
		std::vector<int> empty;
		longestPath = getLongestPath(empty, true);
	}

	void printLongestPath()
	{
		for (int i = 0; i < longestPath.size(); i++)
		{
			printf("%i-", longestPath[i]);
		}
		printf(" length=%i\n", getPathLength(longestPath));
	}

	int rebra()
	{
		int n = 0;
		for (int i = 0; i < 30 - 1; i++)
			for (int j = 0; j < 30 - 1; j++)
				if ((j > i) && (A[i][j] != 0)) n += 1;
		return n;
	}

	void drawLongestPath()
	{
		float *X;
		float *Y;
		float a;
		int r = 170, x_zero = 450, y_zero = 250;
		int i, j;
		char graf[3] = " ";
		X = new float[m];
		Y = new float[m];
		HDC hdc = GetDC(GetConsoleWindow());
		HPEN Pen = CreatePen(PS_SOLID, 1, RGB(0, 0, 255));
		SelectObject(hdc, Pen);
		for (int i = 0; i < m; i++)
		{
			X[i] = cos(i * 2 * 3.141592653589793238462643 / m)*r + x_zero;
			Y[i] = sin(i * 2 * 3.141592653589793238462643 / m)*r + y_zero;
			Ellipse(hdc, X[i] - 3, Y[i] + 3, X[i] + 3, Y[i] - 3);

			// Подписываем вершину:
			_itoa(i, graf, 10);
			TextOutA(hdc, X[i], Y[i], graf, strlen(graf));
		}


		for (i = 0; i < m; i++)
			for (j = 0; j < i; j++)
				if (A[i][j] != 0)
				{
					// Выбираем цвет в зависимости от есть ли эта пара в пути:
					if (isPairInPath(longestPath, i, j))
						Pen = CreatePen(PS_SOLID, 2, RGB(255, 0, 0));
					else
						Pen = CreatePen(PS_SOLID, 1, RGB(0, 0, 255));
					SelectObject(hdc, Pen);

					// Выводим линию этим цветом:
					MoveToEx(hdc, X[i], Y[i], NULL);
					LineTo(hdc, X[j], Y[j]);
					_itoa(A[i][j], graf, 10);

					// Подписываем длинну:
					TextOutA(hdc, (X[i] + X[j]) / 2, (Y[i] + Y[j]) / 2, graf, strlen(graf));
				}

		TextOutA(hdc, -100, -100, graf, strlen(graf));
	}

private:

	// Возвращает самый длинный путь в графе, который начинается на beginning
	std::vector<int> getLongestPath(std::vector<int> & beginning, bool printProgress = false)
	{
		if (beginning.size() == m)
		{
			return beginning;
		}
		std::vector<int> bestPath;
		int bestLength = -1;
		for (int i = 0; i < m; i++)
		{
			if (printProgress)
				printf("%f%%\n", (float)i / m * 100);
			if (std::find(beginning.begin(), beginning.end(), i) == beginning.end())
			{
				beginning.push_back(i);
				std::vector<int> path = getLongestPath(beginning);
				int length = getPathLength(path);
				if (length > bestLength)
				{
					bestPath = path;
					bestLength = length;
				}
				beginning.pop_back();
			}
		}
		return bestPath;
	}

	int getPathLength(std::vector<int> path)
	{
		int length = 0;
		for (int i = 0; i < path.size() - 1; i++)
		{
			int index1 = path[i];
			int index2 = path[i + 1];
			length += A[index1][index2];
		}
		return length;
	}

	// Проверяет есть ли указанная пара вершин в данном пути
	bool isPairInPath(std::vector<int> path, int a, int b)
	{
		for (size_t i = 0; i < path.size() - 1; i++)
		{
			if (path[i] == a & path[i + 1] == b)
				return true;
			if (path[i] == b & path[i + 1] == a)
				return true;
		}
		return false;
	}
};

int main()
{
	HDC hDC = GetDC(GetConsoleWindow());

	Graph g("graf.txt");

	g.calcLongestPath();
	g.printLongestPath();
	g.drawLongestPath();

	_getch();
	system("pause");

	return 0;
}