ВОСПРОИЗВЕДЕНИЕ И ИНТЕРАКТИВНОЕ РЕДАКТИРОВАНИЕ ГРАФА В ПРОЕКТЕ VISUAL C#

Магомедов А.М.

Доктор физико-математических наук, профессор, Дагестанский государственный университет

ВОСПРОИЗВЕДЕНИЕ И ИНТЕРАКТИВНОЕ РЕДАКТИРОВАНИЕ ГРАФА В ПРОЕКТЕ VISUAL C#

Аннотация

Предложен компактный формат исходных данных для построения графа. Предлагаемый в статье способ воспроизведения и интерактивного редактирования ориентированных и неориентированных графов способствует достижению хорошего полиграфического качества рисунков графов, сопровождающих статьи и учебные пособия по теории графов. Изложенный метод включает визуальное изменение координат вершин на рисунке графа с применением стека изменений практически неограниченной глубины, масштабирование всего рисунка и отдельных его элементов (размеров изображения вершин, толщины линий и стрелок с сохранением координат вершин), ведение протокола изменений в rtf-формате.

Результаты находят применение в создании полиграфических документов с рисунками графов.

Ключевые слова: рисунок, двойная буферизация, граф, список связности, компактное представление.

Magomedov A.M.

PhD in Physics and Mathematics, Professor, Dagestan State University

PLAYBACK AND INTERACTIVE EDIT OF THE CURVE IN VISUAL C # PROJECT

Abstract

The article presents a compact format of the initial data for graph construction. The paper contains the analysis and interactive analysis of oriented and unoriented graphs, which allow achieving good polygraph quality of graphs figures, accompanying articles and textbooks on graph theory and is offered in the game form. The presented method includes visual change of the vertex coordinates in the figure with actual correction of changes and unlimited depth, scaling of the whole figure and its individual elements (keeping the protocol of changes in rtf-format).

The results can be applied in the creation of polygraphic documents with graphs.

Keywords: figure, double buffering, graph, connectivity list, compact representation.

1. Введение

Вопросы визуального представления графов востребованы как в учебных занятиях по дискретной математике и компьютерной графике, так и для создания полиграфических документов (статей, учебных пособий) с пояснительными рисунками по тематике теории графов.

В разделе 2 предложены компактная структура представления исходных данных и способ повышения устойчивости к ошибкам набора данных, в разделе 3 изложен способ визуального редактирования графа.

Работа выполнена при поддержке Отдела математики и информатики ДНЦ РАН

2. Компактная структура исходного файла

Для текстового файла с информацией о неориентированном графе  – множество из n вершин, E – множество ребер, предлагается следующая структура: в i-й строке файла с n строками (i=0, 1, …, n-1) располагается список тех вершин, смежных вершине v_i, номера которых больше i; если номера всех вершин, смежных вершине v_i, меньше i, то i-я строка содержит единственный символ “-“.

Текстовому файлу, приведенному на рис. 1 (слева), соответствует неориентированный граф из семи вершин (см. на рис. 1 справа). Очевидно, что последняя строка файла всегда содержит знак минуса.

Рис. 1 – Пример представления неориентированного графа

 

Признаком ориентированного графа является замена в последней строке файла знака “-“ на знак “+”; при этом строка, состоящая из единственного знака “-“, имеет смысл, аналогичный приведенному выше; элементами каждой i-й строки, отличной от “-“ и “+“, могут быть как положительные, так и отрицательные числа j,  > i : j>0 – признак дуги (i,j), j<0 – признак дуги (j,i). Текстовому файлу, приведенному на рис. 2 (слева), соответствует ориентированный граф из семи вершин (см. на рис. 2 справа).

Рис. 2 – Пример представления ориентированного графа

 

Не вдаваясь в подробное изложение вопросов распределения памяти, отметим, что объем требуемой памяти при описанном способе задания графа «приближенно» равен , тогда как, например, все описанные в [1, С. 203] способы потребуют (для неориентированных графов) «приближенно» 2  памяти.

Набор исходных файлов, используемых в нашем C#-проекте: 1) текстовый файл “name.txt” со структурой описанного выше типа; 2) файл “name.bmp” с растровым рисунком для изображения вершин; 3) необязательный файл “coo.txt”, содержащий координаты вершин в последовательных строках. Если файл “coo.txt” существует, то координаты вершин загружаются из него, в противном случае координаты вершин графа генерируются автоматически, после чего вызывается функция (обозначим ее Dr) рисования графа.

Распространенной ошибкой при наборе чисел с разделительным знаком «запятая» является вставка избыточного знака пробела после запятой. Покажем, как средствами языка C# достигается устойчивость к ошибкам такого рода (предполагается, что строковый массив t, массив p с элементами класса Point и двумерный «зубчатый» целочисленный массив a, соответствующий описанной выше структуре входного текстового файла, уже объявлены ранее):

Отметим здесь же, что на стадии инициализации рисунок из файла “name.bmp” вводится в объект b класса Bitmap, затем масштабируется (величина d, указанная ниже, может быть изменена интерактивным способом), его краям придается свойство прозрачности:

3. Редактирование рисунка графа

Как правило, следствием автоматической генерации координат вершин графа p[i] – объектов класса Point (i=0, …, n-1) является рисунок, не вполне соответствующий целям автора. Поэтому в проекте необходимо предусмотреть визуальное перемещение вершин графа с помощью мышки:

1. В обработчике события

вычисляется индекс I вершины, ближайшей к точке (e.X, e.Y) нажатия кнопки мыши и устанавливается флажок нажатия – некоторой глобальной логической переменной присваивается значение True (опускание флажка выполняется в обработчике события pictureBox1_MouseUp);

2. В обработчике события перемещения мыши:

проверяется факт установки флажка нажатия и, если флажок установлен, точка p[I] воссоздается с текущими координатами курсора мыши: p[I] = new Point(e.X, e.Y), после чего вызывается функция Dr для прорисовки графа.

Отметим две коллизии, возникающие при этом. Если фрагменты рисунка выводятся непосредственно на «холст» видимого окна (в нашем случае – окна графического контейнера pictureBox1), то в промежутках между выводом этих фрагментов экран успевает обновиться, вследствие чего рисунок претерпевает искажения. Искажения такого рода в компьютерной терминологии называются артефактами. Для исключения появления артефактов рекомендуется использовать метод двойной буферизации [2, С. 264]. Для этих целей на стадии инициализации нашего проекта создается объект b0 класса Bitmap, размеры которого совпадают с размерами графического контейнера pictureBox1:

Bitmap b0= new Bitmap (pictureBox1.Width, pictureBox1.Height);

затем создаются два «холста» – объекты класса Graphics – g0 и g1, соответствующие объектам b0 и pictureBox1:

g0 = Graphics.FromImage(b0);

g1 = pictureBox1.CreateGraphics().

В упомянутой выше функции Dr процесс вывода всех частей рисунка выполняется прежде всего на холст g0 объекта b0, выполняющего роль второго буфера:

сначала вывод линий – со стрелками или без них, затем вывод изображения b в точках расположения вершин и, наконец, вывод номеров вершин (такая последовательность существенна).

В конце функции Dr, после завершения формирования рисунка графа на холсте g0 объекта b0, выполняется вывод b0 на холст g1 графического контейнера pictureBox1. Как известно, здесь возможны два варианта: 1) вызов метода DrawImage:

g1.DrawImage(b0, 0,0)

холста g1 графического контейнера pictureBox1

или 2) присвоение b0 свойству Image этого контейнера:

pictureBox1.Image = b0.

Мы рекомендуем второй вариант. Практика показывает неустойчивость вывода при первом варианте. Причины этой коллизии автору неизвестны.

Замечание. Специальные классы C#, предназначенные для реализации метода двойной буферизации, подробно рассмотрены в статье [3].

На рис. 3: слева – граф с вершинами, координаты которых сгенерированы программой (при отсутствии файла “coo.txt”), справа – граф, преобразованный пользователем в интерактивном режиме; сохранение преобразованных координат вершин с целью выбора их из файла при очередном запуске программы не представляет труда.

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

 

Замечание. Масштабирование рисунка в целом или отдельных его элементов – радиуса фигуры, изображающей вершину, толщину линий (ребер, дуг), надписей (с сохранением координат вершин) – достигается привязкой параметров этих элементов к свойству Value визуальной компоненты trackBar. На рис. 4 показан результат использования такой привязки.

Рис. 4 – Визуальные элементы графа, изображенного слева, масштабированы за исключением координат вершин (результат см. справа)

 

4. Заключение

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

Список литературы / References

1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2000. – 304 с.
2. Порев В.Н. Компьютерная графика. – СПб.: БХВ-Петербург, 2004. – 432с.
3. Гуков Д. Детали реализации двойной буферизации в Windows Forms: [Электронный ресурс]. URL: https://habrahabr.ru/post/144294/ (дата обращения: 11.05.2017).

 Список литературы на английском языке / References in English

1. Novikov F.A. Diskretnaja matematika dlja programmistov [Discrete mathematics for programmers]. – SPb.: Piter, 2000. – 304 P. [in Russian]
2. Porev V.N. Komp'juternaja grafika [Computer graphics]. – SPb.: BHV-Peterburg, 2004. – 432 P. [in Russian]
3. Gukov D. Detali realizacii dvojnoj buferizacii v Windows Forms [The implementation details of double buffering in Windows Forms]: [Electronic resource]. URL: https://habrahabr.ru/post/144294/ (accessed: 11.05.2017). [in Russian]