public int VertexCount { get; private set; }
//матрица смежности графа
private readonly bool[,] adjacencyMatrix;
//конструктор. создает матрицу графа и проверяет, что количество вершин положительно
public Graph(int vertexCount)
{
if (vertexCount <= 0)
throw new UserException("Количество вершин в графе должно быть положительным числом. Значение {0} неприемлемо.", vertexCount);
VertexCount = vertexCount;
adjacencyMatrix = new bool[vertexCount, vertexCount];
}
//Добавить ребро
public void AddEdge(int v1, int v2)
{
adjacencyMatrix[v1, v2] = true;
}
//Удалить ребро
public void DeleteEdge(int v1, int v2)
{
adjacencyMatrix[v1, v2] = false;
}
//Узнать есть ли ребро
public bool HasEdge(int v1, int v2)
{
return adjacencyMatrix[v1, v2];
}
}
}
using System.IO;
using System.Linq;
using System.Threading;
using ColoringGraphProblem.Exceptions;
namespace ColoringGraphProblem.WorkWithFiles
{
public class GraphReader
{
//Прочитать граф из файла по пути filePath
public static Graph Read(string filePath, int maxGraphSize)
{
string[] text = File.ReadAllLines(filePath).ToArray();
if (text.Length == 0)throw new UserException("Ожидается, что файл не пустой");
int vertexAmount = int.Parse(text[0]);
if (vertexAmount > maxGraphSize)
throw new UserException("Ожидается, что количество вершин в графе будет не больше, чем {0}. Значение {1} неприемлемо.", maxGraphSize, vertexAmount);
var result = new Graph(vertexAmount);
for (int i = 1; i <= vertexAmount; i++)
{
var args = text[i].Split(' ').Where(str => !string.IsNullOrEmpty(str));
foreach(var arg in args)
{
int val = int.Parse(arg);
if (val < 1 || val > vertexAmount) throw new UserException("Номера вершин должны быть от 1 до {0}", vertexAmount);
if (val == i) throw new UserException("В графе не должно быть петель");
if (result.HasEdge(i-1, val-1)) throw new UserException("В графе не должно быть мультиребер.");
result.AddEdge(i-1, val-1);
}
}
return result;
}
}
}
using System.Collections.Generic;
using System.IO;
using System.Text;
namespace ColoringGraphProblem.WorkWithFiles
{
public class GraphWriter
{
//записывает граф graph в файл по пути filePath
public static void Write(string filePath, Graph graph)
{
var sb = new StringBuilder();
sb.AppendLine(string.Format("{0}", graph.VertexCount));
for (int i = 0; i < graph.VertexCount; i++)
{
for (int j = 0; j < graph.VertexCount; j++)
if (graph.HasEdge(i, j))
sb.Append(string.Format("{0} ", j+1));
sb.AppendLine();
}
File.WriteAllText(filePath, sb.ToString());
}
}
}
using System;
namespace ColoringGraphProblem.Exceptions
{
public class InnerException : Exception
{
public InnerException(string text, params object[] args)
: base(string.Format(text, args))
{
}
}
}
using System;
namespace ColoringGraphProblem.Exceptions
{
public class UserException : Exception
{
public UserException(string text, params object[] args)
: base(string.Format(text, args))
{
}
}
}
using System.Drawing;
using System.Windows.Forms;
namespace ColoringGraphProblem.Drawing
{
//Полотно на котором мы будем рисовать
//
// Вся отрисовка идет на PictureBox
// Вся отрисовка идет на Graphics - это то, на чем у PictureBox-а рисуют
public class Canvas
{
public Canvas(PictureBox pictureBox)
: this(pictureBox.CreateGraphics(), pictureBox.Height, pictureBox.Width)
{
}
public Canvas(PictureBox pictureBox, Graphics graphics)
: this(graphics, pictureBox.Height, pictureBox.Width)
{
}
public Canvas(Graphics graphics, int height, int width)
{
Graphics = graphics;
Height = height;
Width = width;
}
//Привести точку из квадрата от 0 до 1 в пиксельные координаты
public Point NormalizePoint(Point point)
{
double xScale = Width;
double yScale = Height;
return new Point(xScale * point.X, yScale * point.Y);
}
public Graphics Graphics { get; private set; }
public int Height { get; private set; }
public int Width { get; private set; }
}
}
using System;
using System.Drawing;
namespace ColoringGraphProblem.Drawing
{
//Класс для перевода раскраски алгоритма в случайные цвета Windows
public class Colorer
{
//readonly - можем присваивать значение только в конструкторе
private readonly Color[] color;
//neededColors - количество случайных цветов Windows которые нам нужны для раскраски
public Colorer(int neededColors)
{
var random = new Random(146);
color = new Color[neededColors];
for (int i = 0; i < neededColors; i++)
color[i] = Color.FromArgb(random.Next(256), random.Next(256), random.Next(256));
}
public Color[] CreateColoring(int[] coloring)
{
var result = new Color[coloring.Length];
for (int i = 0; i < coloring.Length; i++)
result[i] = color[coloring[i]-1];
return result;
}
}
}
using System;
using System.Drawing;
using System.Windows.Forms;
namespace ColoringGraphProblem.Drawing
{
//Класс, который отлавливает событие клика по графу и что-то отмечает
public class GraphClicker
{
//максимальное расстояние от центра вершины графа при котором считается, что мы кликнули по ней
private const double MaximalClickableDist = 20;
public PictureBox PictureBox { get; private set; }
private readonly GraphDrawer drawer;
public GraphClicker(PictureBox pictureBox)
{
PictureBox = pictureBox;
drawer = new GraphDrawer();
//подписываемся на событие клика PictureBox.Click
PictureBox.Click += MouseLeftButtonClick;
}
public Graph Graph { get; private set; }
public bool[] clicked;
//Отрисовка графа с выделением кликнутой вершины
public void Draw(Canvas canvas)
{
//Подготовили массив системных цветов для отрисовки графа
var coloring = new Color[Graph.VertexCount];
for (int i = 0; i < Graph.VertexCount; i++)
if (clicked[i])
coloring[i] = GraphDrawingConstants.GraphSelectedVertexBrushColor;
else
coloring[i] = GraphDrawingConstants.GraphVertexBrushColor;
drawer.Draw(canvas, Graph, coloring);
}
private void ClickOnVertex(Canvas canvas, int vertexId)
{
//Если вершина уже была выделена, то снимаем выделение
if (clicked[vertexId])
clicked[vertexId] = false;
//Если вершина не была выделена, то
else
{
//пытаемся найти уже выделенную вершину
int vertex1 = -1;
for (int i = 0; i < clicked.Length; i++)
if (clicked[i])
vertex1 = i;
//если уже была выделенная вершина
if (vertex1 != -1)
{
int vertex2 = vertexId;
if (Graph.HasEdge(vertex1, vertex2))
Graph.DeleteEdge(vertex1, vertex2);
else
Graph.AddEdge(vertex1, vertex2);
clicked[vertex1] = false;
}
else
clicked[vertexId] = true;
}
//перерисовываем граф
Draw(canvas);
}
//Координаты центра вершины vertexId из vertexCount в пикселях
private static Point GetVertexCenterInPixels(Canvas canvas, int vertexId, int vertexCount)
{
return canvas.NormalizePoint(GraphDrawer.GetVertexCenter(vertexId, vertexCount));
}
private void ProcessClick(int x, int y)
{
//если нет графа, то ничего не делаем
if (Graph == null) return;
var canvas = new Canvas(PictureBox);
var cur = new Point(x, y);
//находим самый близкий к cur центр вершины
var bestDist = cur.Dist(GetVertexCenterInPixels(canvas, 0, Graph.VertexCount)); ;
int bestVertexId = 0;
for (int i = 1; i < Graph.VertexCount; i++)
if (bestDist > cur.Dist(GetVertexCenterInPixels(canvas, i, Graph.VertexCount)))
{
bestDist = cur.Dist(GetVertexCenterInPixels(canvas, i, Graph.VertexCount));
bestVertexId = i;
}
//Если расстояние меньше либо равно, чем MaximalClickableDist
if (bestDist <= MaximalClickableDist)
ClickOnVertex(canvas, bestVertexId);
}
//метод, который вызовется по клику мыши
private void MouseLeftButtonClick(object sender, EventArgs e)
{
//если событие для мыши
if (e is MouseEventArgs)
{
var me = (MouseEventArgs)e;
//если событие клика левой кнопки мыши
if (me.Button == MouseButtons.Left)
{
ProcessClick(me.X, me.Y);
}
}
}
public bool HasGraph()
{
return Graph != null;
}
public void SetGraph(Graph graph)
{
Graph = graph;
clicked = new bool[Graph.VertexCount];
}
}
using System;
using System.Drawing;
using ColoringGraphProblem.Exceptions;
namespace ColoringGraphProblem.Drawing
{
//рисует граф
public class GraphDrawer
{
//радиус круга графа
private const double graphRadius = 0.4;
//радиус вершины
private const double vertexRaduis = 0.02;
private readonly PrimitiveDrawer primitiveDrawer;
public GraphDrawer()
{
primitiveDrawer = new PrimitiveDrawer();
}
//нарисовать граф c цветами вершин по умолчанию
public void Draw(Canvas canvas, Graph graph)
{
var coloring = new Color[graph.VertexCount];
for (int i = 0; i < coloring.Length; i++)
coloring[i] = GraphDrawingConstants.GraphVertexBrushColor;
Draw(canvas, graph, coloring);
}
//нарисовать граф с цветами вершин coloring
public void Draw(Canvas canvas, Graph graph, Color[] coloring)
{
if (coloring.Length != graph.VertexCount)
throw new InnerException("Размерность {0} окраски не соотвествует количеству {1} вершин графа.", coloring.Length, graph.VertexCount);
primitiveDrawer.ClearCanvas(canvas);
for (int i = 0; i < graph.VertexCount; i++)
for (int j = 0; j < graph.VertexCount; j++)
if (graph.HasEdge(i, j)) DrawEdge(canvas, i, j, graph.VertexCount);
for (int i = 0; i < graph.VertexCount; i++)
{
DrawVertex(canvas, coloring[i], i, graph.VertexCount);
}
}
//Нарисовать ребро из вершины с номером v1 в вершину с номером v2 из vertexCount
private void DrawEdge(Canvas canvas, int v1, int v2, int vertexCount)
{
primitiveDrawer.DrawLine(canvas, GraphDrawingConstants.GraphVertexPen, GetVertexCenter(v1, vertexCount), GetVertexCenter(v2, vertexCount), vertexRaduis);
}
//Нарисовать вершину с номером id из vertexCount
private void DrawVertex(Canvas canvas, Color color, int id, int vertexCount)
{
primitiveDrawer.DrawCircle(canvas, GraphDrawingConstants.GraphVertexPen, new SolidBrush(color), GetVertexCenter(id, vertexCount), vertexRaduis);
primitiveDrawer.DrawText(canvas, new SolidBrush(GraphDrawingConstants.GraphVertexPenColor), GetVertexCenter(id, vertexCount), (id + 1).ToString(), GraphDrawingConstants.Font);
}
//Центр вершины с номером id из vertexCount в квадрате [0,0,1,1]
public static Point GetVertexCenter(int id, int vertexCount)
{
double angle = (Math.PI*2.0/vertexCount) * id;
return new Point(Math.Cos(angle) * graphRadius + 0.5, Math.Sin(angle) * graphRadius + 0.5);
}
}
}
using System.Drawing;
namespace ColoringGraphProblem.Drawing
{
public static class GraphDrawingConstants
{
//цвет внутренности вершины
public static Color GraphVertexBrushColor = Color.AliceBlue;
//кисть внутренности вершины
public static Brush GraphVertexBrush = new SolidBrush(GraphVertexBrushColor);
//цвет внутренности выделенной вершины
public static Color GraphSelectedVertexBrushColor = Color.Yellow;
//кисть внутренности выделенной вершины
public static Brush GraphSelectedVertexBrush = new SolidBrush(GraphSelectedVertexBrushColor);
//цвет границы вершины
public static Color GraphVertexPenColor = Color.Black;
//ручка границы вершины
public static Pen GraphVertexPen = new Pen(GraphVertexPenColor, 2);
//фоновый цвет
public static Color BackgroundColor = Color.AliceBlue;
//фоновая кисть
public static Brush BackgroundColorBrush = new SolidBrush(BackgroundColor);
//шрифт
public static Font Font = new Font(new FontFamily("Times New Roman"), 12);
}
}
using System;
namespace ColoringGraphProblem.Drawing
{
//Точка
public class Point
{
public Point(double x, double y)
{
X = x;
Y = y;
}
//Расстояние до другой точки
public double Dist(Point p)
{
return Math.Sqrt((X - p.X) * (X - p.X) + (Y - p.Y) * (Y - p.Y));
}
public double X{ get; private set;}
public double Y{ get; private set;}
}
}
using System;
using System.Drawing;
namespace ColoringGraphProblem.Drawing
{
public class PrimitiveDrawer
{
//очистить полотно
public void ClearCanvas(Canvas canvas)
{
canvas.Graphics.FillRectangle(GraphDrawingConstants.BackgroundColorBrush, 0, 0, canvas.Width, canvas.Height);
}
public void DrawText(Canvas canvas, Brush brush, Point center, string text, Font font)
{
Point realCenter = canvas.NormalizePoint(center);
var rect = canvas.Graphics.MeasureString(text, font);
canvas.Graphics.DrawString(text, font, brush, new PointF{X = (float)realCenter.X-rect.Width/2, Y = (float)realCenter.Y-rect.Height/2});
}
//нарисовать круг
public void DrawCircle(Canvas canvas, Pen border, Brush brush, Point center, double radius)
{
double xScale = canvas.Width;
double yScale = canvas.Height;
Point realCenter = canvas.NormalizePoint(center);
double realRadius = radius * Math.Min(xScale, yScale);
canvas.Graphics.FillEllipse(brush,
(int)(realCenter.X - realRadius),
(int)(realCenter.Y - realRadius),
(int)(2.0 * realRadius),
(int)(2.0 * realRadius));
canvas.Graphics.DrawEllipse(border,
(int)(realCenter.X - realRadius),
(int)(realCenter.Y - realRadius),
(int)(2.0 * realRadius),
(int)(2.0 * realRadius));
}
//нарисовать линию
public void DrawLine(Canvas canvas, Pen border, Point p1, Point p2, double radius)
{
const double angle30 = 0.52359877559829887307710723054658;
double xScale = canvas.Width;
double yScale = canvas.Height;