Программа для построения графов C#

Представляем вашему вниманию программу для построения графов, написанную на языке C#. Внизу страницы вы можете скачать исходник этой программы, а в этой статье будут описаны функции программы и основные приемы, использовавшиеся при их кодировании.

Структура пользовательского интерфейса

Программа для построения графов C#

Рисунок 1. Пользовательский интерфейс программы

Пользовательский интерфейс программы изображен на рисунке 1. На нем цифрами обозначены элементы управления:

  1. Выбор вершины (при выборе какой-либо вершины, отображается ее степень).
  2. Создание вершины.
  3. Создание ребра.
  4. Удаление элемента.
  5. Удаление всего графа.
  6. Рабочее поле для построения графа.
  7. Построение матрицы смежности.
  8. Построение матрицы инцидентности.
  9. Поле для вывода информации о графе: степень выбранной вершины, матриц смежности и инцидентности, элементарных цепей и циклов.
  10. Вывод всех элементарных цепей.
  11. Вывод всех элементарных циклов.
  12. Информация о программе (окно представлено на рисунке 2).
  13. Сохранение изображения графа.

Если при построении ребра вы выбрали не ту вершину, то отменить выбор можно, нажав правой кнопкой мыши на выбранной вершине.

Программа для построения графов C#

Рисунок 2. Окно “О программе”

Описание структуры программы

Опишем ключевые моменты в программном коде.

При кодировании граф был представлен в виде списка (List<>) экземпляров класса Vertex (вершина):

где x и y – координаты центра вершины.

И списка (List<>) экземпляров класса Edge (ребро):

v1 и v2 – номера вершин, которые соединяет ребро.

Вот эти списки:

Когда происходит выбор вершины мышью, поиск нужной вершины из списка осуществляется посредством перебора всех вершин и проверки условия принадлежности точки, в месте щелчка мыши, окружности вершины с помощью уравнения окружности: (x – x0)2 + (y – y0)2 = R2.

где e.X, e.Y – координаты точки в месте щелчка мыши, а G.R – радиус окружности вершины.

Заполнение матрицы смежности:

numberV – количество вершин в графе. matrix имеет размер [numberV, numberV].

Заполнение матрицы инцидентности:

где numberV – количество вершин в графе. matrix имеет размер [numberV, E.Count].

Определение степени вершины происходит в результате суммирования элементов строки матрицы смежности с номером, равным номеру выбранной вершины.

Если нажата кнопка “удаление элемента”, то при щелчке мышью на рабочем поле происходит перебор всех элементов графа и поиск элемента, которому принадлежит координата в месте щелчка. При этом для ребер и петель поиск осуществляется с допуском в несколько пикселей, то есть, например, принадлежность точки, в месте щелка, конкретному ребру характеризуется принадлежностью точки области, границами которой выступают прямые, отстоящие вверх и вниз от исходной прямой на несколько пикселей.

Проиллюстрировать вышесказанное можно с помощью рисунка:

Области, рассматриваемые при поиске элемента графа для удаления

Рисунок 3. Области, рассматриваемые при поиске элемента графа для удаления

Красным цветом обозначен тот самый допуск в несколько пикселей при поиске элемента для удаления. Для вершины никакого допуска рассматривать не нужно.

Про поиск элементарных цепей и циклов мы уже рассказывали на vscode.ru. Почитать можно здесь:

Поиск элементарных цепей в графе

Поиск элементарных циклов в графе

Скачать исходник программы, написанной в Visual Studio, можно, нажав на кнопку ниже.

Скачать исходник

 

 

 

Программа для построения графов C#
4.38 (87.5%) 8 votes

Поделиться в соц. сетях:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">