Геометрические примитивы, Реализация алгоритма расположения вершин графа - Визуализация графа цитирования

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

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

Реализация алгоритма расположения вершин графа

Ориентированный граф цитирования хранится в списке смежности - структуре в которой каждой вершине сопоставляется множество смежных ей вершин. Такая структура в среднем требует меньше памяти и меньше ресурсов на изменение, чем более простой метод - матрица смежности. Список смежности реализован с помощью классов Set и Map из ES6.

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

Далее проводится симуляция физической системы. Один шаг симуляции обернут в метод tick(), возвращающий среднюю арифметическую скорость всех вершин. Это позволяет контролировать пользователю время остановки алгоритма, так как пользователь может перестать вызывать метод tick в любой момент и тем самым завершить алгоритм.

Похожие статьи




Геометрические примитивы, Реализация алгоритма расположения вершин графа - Визуализация графа цитирования

Предыдущая | Следующая