Разработка основных форматов данных

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

Главным объектом данных в программе является неориентированный граф, подлежащий раскраске. Для задания таких графов в математике обычно используют матрицы и списки. Наиболее просто представить граф матрицей смежности вершин. В такой матрице элемент, расположенный на пересечении строки i и столбца j, равен 1, если вершины i и j связаны ребром, и 0 в противном случае. Матрица смежности вершин обеспечивает высокую скорость выполнения основных операций над графами, но для графов большого размера не эффективна по затратам памяти, т.к. содержит большое число нулей. Однако в нашей задаче обработка таких графов не представляется возможной из-за довольно высокой трудоемкости алгоритма раскраски и сложности изображения графа с большим (более 20-25) числом вершин на форме, поэтому выбор матрицы смежности вполне оправдан. Представление графа в виде списка более эффективно по затратам памяти, но требует большего времени на выполнение типовых операций.

Итак, структура данных для представления исходного графа будет иметь следующий общий вид:

где , если вершины i и j связаны ребром, иначе.

Для представления в программе текущего варианта раскраски графа будем использовать вектор-столбец C, i-ый элемент которого (обозначаемый как ) содержит цвет, назначенный вершине i (неотрицательное целое число). Если вершине i не назначен цвет, в соответствующий элемент вектора C будем записывать –1. Такое представление обеспечит высокую скорость проверки цветов вершин в процессе раскраски и в то же время даст приемлемые затраты памяти.

Таким образом, структура данных для хранения цветов вершин будет представлена следующим образом:

где , если вершине i не назначен цвет, , если вершине i поставлен в соответствие цвет f.

Для хранения текущих значений «относительных» локальных степеней вершин графа в процессе раскраски введём вектор-строку L, i-ый элемент которой (обозначаемый через ) будет соответствовать i-ой вершине графа. Локальные степени будем рассчитывать без учёта уже окрашенных вершин, чего требует выбранный алгоритм раскраски.

Согласно сказанному, структура данных для хранения локальных степеней вершин будет определяться в виде:

где , если i-ая вершина не раскрашена, иначе.

Так как вектор L переупорядочивается по невозрастанию и соответствие между номерами вершин и его элементами нарушается, необходимо также хранить и вектор номеров вершин после переупорядочения. Этот вектор обозначим через O и определим в виде:

где – номер вершины, которой соответствует i-й элемент вектора L, до переупорядочения вектора L.

С целью задания в программе текущих координат вершин в области построения графа PaintBox введем вектор-столбец V следующего формата:

где , – декартовы координаты центра i-ой вершины в области построения графа.

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

Исходя из сказанного, информацию об отмененном действии можно представить следующей структурой данных:

где – порядковый номер вершины, – ее декартовы координаты ( ). Для удаленного ребра , , а – номера его концевых вершин. Для удаленной вершины – локальная степень, – ее порядковый номер до перенумерации, – ее декартовы координаты, а – соответственно номер до перенумерации и координаты j-ой вершины, смежной с удаленной ( ).

⇐ Предыдущая 123 4 Следующая ⇒