Для задания графа G=(V,E) предложен компактный способ, занимающий O(|E|+n) памяти, где n=|V|: текстовый файл из n строк, i-я строка которого содержит список тех вершин, смежных вершине v_i и номера которых больше i; i=0, 1, …, n-1. Если все вершины, смежные вершине v_i, имеют номера, меньшие чем i, то i-я строка содержит единственный символ “-“. Признаком орграфа является замена в последней строке знака “-“ на знак “+”, элементами остальных строк, отличных от “-“, могут быть как положительные, так и отрицательные числа. Присутствие числа j в i-й строке (abs(j)>i) служит: при j>0 – признаком дуги (i,j), при j<0 – признаком дуги (abs(j),i). 

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

Свойства проекта: 1) предоставляется выбор координат вершин: чтение из файла или генерация программным путем; 2) конфигурация рисунка графа может быть изменена пользователем путем визуального перетаскивания вершин графа с помощью мышки; 3) предусмотрено как масштабирование рисунка в целом, так и масштабирование элементов рисунка – радиуса вершин, размера шрифта надписей, размеров стрелок дуг и толщины линий – с сохранением координат вершин; 4) использование предыстории и пост-истории (при визуальном перетаскивании вершин создается стек изменений, сохраняющий последовательность изменений практически неограниченной глубины); 5) все изменения при этом заносятся в протокол и отображаются в текстовом редакторе; 6) благодаря .rtf-формату, наряду с буквенно-цифровой информацией в текстовый редактор разрешается помещать и рисунки графа с последующим сохранением.

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

На страницу проекта