Приведен в run.sh, на вход подается путь к конфигурации в формате json из папки configs/config..) В данной конфигурации записываются необходимые параметры для каждого запроса.
python3 main.py "/path_to_config/configMooc.json"
эти запросы, которые выполняют поиск в ширину и поиск в глубину соответственно в заданном графе в базе данных. Оба метода принимают следующие параметры:
- tablename: Имя таблицы в базе данных, из которой будут извлекаться данные.
- startnode: Начальный узел (вершина) для выполнения обхода. Это узел, с которого начнется поиск.
- depth : Максимальная глубина обхода. Если уровень узла больше или меньше этого значения, он не будет обработан.
- fieldName : Имя поля в таблице, которое будет использоваться в условии фильтрации. Это поле будет проверяться на соответствие значению value.
- value : Значение, с которым будет сравниваться поле fieldName. Используется для фильтрации узлов, которые будут добавлены в стек для дальнейшего обхода.
- fromid : Имя поля, которое используется в запросе для определения связи между узлами. Это поле содержит идентификатор узла, от которого идет связь.
- toid : Имя поля, которое используется в запросе для получения идентификатора следующего узла. Это поле содержит идентификатор узла, к которому идет связь.
это метод, который выполняет простой запрос на фильтрацию в заданной коллекции в базе данных. Он принимает следующие параметры:
- tablename: Имя таблицы в базе данных, из которой будут извлекаться данные.
- id : Имя поля, которое содержит название узла в таблице.
- fieldname : Имя поля, по которому будет выполняться фильтрация.
- value: Значение, с которым будет сравниваться поле field_name. Используется для фильтрации записей в запросе. Записи, у которых значение field_name больше или равно value, будут извлечены из таблицы.
этот запрос, который выполняет более сложный запрос на фильтрацию в заданной коллекции в базе данных. Он подсчитывает количество рёбер для каждого узла и фильтрует узлы по количеству рёбер, возвращая только те, которые имеют количество рёбер, большее или равное заданному значению degree. Он принимает следующие параметры:
- tablename: Имя таблицы в базе данных, из которой будут извлекаться данные.
- result: Имя поля, которое будет использоваться для извлечения идентификаторов вершин (узлов) из таблицы.
- degree: Минимальное количество рёбер (связей), которое должно быть у узла, чтобы он был включён в результирующий список.
- fieldname: Имя поля, по которому будет выполняться фильтрация узлов. Записи будут извлекаться только в том случае, если значение этого поля соответствует заданному значению value
- value: Значение, с которым будет сравниваться поле field_name. Используется для фильтрации узлов в запросе.
Запрос фильтрует документы на основе определенного значения поля и вычисляет сумму другого поля для отфильтрованных документов. Затем он возвращает вершину и общую сумму.
- table_name: Название таблицы, из которой необходимо извлечь данные.
- collection: Название столбца, содержащего идентификатор вершины
- fieldName: Название атрибута, содержащего значение, которое нужно суммировать.
- sumValue: Не используется (планировалось использовать для фильрации итоговой суммы вершины)
- value: Значение, с которым будет сравниваться поле field_name. Используется для фильтрации узлов в запросе.
Запрос на нахождение кратчайшего пути. В рамках курсовой работы был реализован запрос на нахождение кратчайшего пenb между двумя вершинами в графе. Этот запрос позволяет найти наименьший по количеству шагов путь от одной вершины до другой, используя алгоритм поиска в ширину (BFS). Для выполнения запроса были заданы следующие параметры:
- graph: имя графа, который будет использоваться;
- table_name: имя таблицы, в которой хранятся связи между вершинами графа;
- fromVertex: идентификатор начальной вершины;
- value1: значение начальной вершины, от которой начинается поиск;
- toVertex: идентификатор конечной вершины;
- value2: значение конечной вершины до которой необходимо найти путь.
Для нахождения кратчайшего пути выполняется SQL-запрос, который извлекает все связи между вершинами в таблице.
На основе этих данных строится словарь смежности, в котором каждой вершине сопоставляется список всех ее соседей.
Дальше алгоритм BFS начинает с заданной начальной вершины (value1
) и проходит по графу, добавляя соседние вершины в очередь.
Каждую вершину он посещает только один раз, что предотвращает зацикливание. Когда достигается конечная вершина (value2
),
алгоритм завершает работу, возвращая найденный путь.
Запрос на нахождение «треугольников» в графе.
В данной реализации треугольники – это циклы длины три, то есть наборы вершин, где каждая вершина соединена с двумя другими.
Функция queryTriangles
принимает следующие параметры:
- graph: имя графа, который будет использоваться;
- table_name: имя таблицы, в которой хранятся ребра графа;
- fieldName: название атрибута в таблице, который представляет первую вершину (начальную точку ребра);
- filedName2: название атрибута в таблице, который представляет вторую вершину (конечную точку ребра).
Запрос работает следующим образом. Сначала выполняется запрос к базе данных, чтобы получить все ребра, соединяющие вершины
. Каждое ребро представляет собой связь между двумя вершинами (узлами) графа. Все полученные ребра охраняются в виде списка кортежей, где каждый кортеж содержит две связанные вершины. Также создается словарь смежности, в котором для каждой вершины хранится множество всех вершин, с которыми она
соединена ребром. Для каждой вершины а
алгоритм находит всех соседей b
и проверяет наличие общих соседей между a
и b
. Эти общие соседи образуют треугольники вместе с вершинами a
и b
. Найденные треугольники сохраняются в JSON-файл, чтобы результаты могли быть легко проанализированы позже.
-
Измерение времени:
- Время выполнения запроса измеряется с помощью модуля time.
- start_time = time.time(): Эта строка записывает текущее время в секундах перед началом выполнения запроса.
- end_time = time.time(): После выполнения запроса эта строка фиксирует время.
- Разница между end_time и start_time дает общее время выполнения запроса в секундах.
-
Измерение памяти:
- Используется модуль tracemalloc для отслеживания использования памяти.
- tracemalloc.start(): Это инициализирует отслеживание памяти перед началом выполнения запроса.
- snapshot = tracemalloc.take_snapshot(): После выполнения запроса эта строка делает снимок текущих распределений памяти.
- top_stats = snapshot.statistics('lineno'): Эта команда получает статистику об использовании памяти
-
Вывод результатов
- Метод getStats вызывается для отчета о измеренном времени выполнения и использовании памяти.
- Он принимает следующие параметры:
- graph: Тип обрабатываемого графа.
- nameQuery: Название запроса (в данном случае "queryFilterSum").
- execution_time: Общее время, затраченное на выполнение запроса (в секундах).
- memory_usage: Пиковое использование памяти во время выполнения (в килобайтах).
- В файл записываются название запроса, время выполнения (отформатированное до шести знаков после запятой) и пиковое использование памяти (также отформатированное до шести знаков после запятой).