Проделана следующая работа на этапе проектирования
- Поиск инструмента работы с графами, попробую использовать следующую библиотеку JGrapT так же есть вариант самописного класса обхода вершин графа и поиск циклов в нём.
- Поиск способов хранения графов в БД, полезные ссылки Does it Make Sense to Map a Graph Data-structure into a Relational Database? , Storing data about undirected graph edges in a database
- Создание структуры данных
P.S. К сожалению выбиваюсь из поставленных сроков
Структура данных.¶
Входные данные¶
Граф¶
Входными данными будет граф G(V,E), где V - множество вершин графа (ноды), E - множество рёбер, соединяющих вершины. Граф не ориентированный. Сама вершина (нода) представляет собой объект, состоящий из уникального имени и числа с плавающей запятой в диапазоне от 0.0 до 1.0, описывающая вероятность отказы ноды. Ребро представляет собой объект состоящий из двух ссылок на вершины, которые это ребро соединяет, в данном случае под ссылками подразумевается уникальное имя ноды. В формате JSON это будет выглядеть так:
[[{”name”:”name_of_node_unique”, “probability”:0.5}, ...],[{”node1”:ref_to_node1, “node2”:ref_to_node2}, ...]]
, где
{”name”:”name_of_node_unique”, “probability”:0.5} - объект описывающий вершину графа (ноду)
{”node1”:ref_to_node1, “node2”:ref_to_node2} - объект описывающий ребро, соединяющее две вершины графа.
Примеры входных графов
Циклический граф
Ациклический граф
Входные графы могут содержать циклы, которые нужно исключить по условию задачи.
Вершины графа (Ноды)¶
Так же на вход будут подаваться списки вершин графа для проверки связности вершин. Представляет собой простой перечень вершин, можно указать или идентификатор вершины или уникальное имя.
В представлении JSON будет выглядеть так:
[node_id, node_id, ...]
,где node_id уникальный идентификатор вершины.
или так
[”node_name”, “node_name”, ...]
, где node_name - уникальное имя вершины.
Уникальный идентификатор или имя вершины извлекается запросом или из сервиса (возвращается в формате JSON) или из БД.
Структура выходных данных¶
При запросе к сервису можно получить список вершин (нод) в следующем формате
[{”id”:1, “name”:”unique_name”, “probability”:0.5, “counter”:0}, ...]
,где: id - уникальный идентификатор вершины, name - уникальное имя вершины, probability - вероятность отказа вершины, counter - счётчик посещения вершины.
Модель хранения данных¶
Класс Node - описывающий модель вершины графа (ноды). Класс состоит из следующих полей:
id - уникальный идентификатор.
name - уникальное имя узла (получаем из json).
probability - вероятность отказа узла (получаем из json).
counter - при каждом удачном проходе маршрута, через ноду, счётчик ноды увеличивается.
Класс Edge - описывающий модель ребра графа. Класс состоит из следующих полей:
node1 - ссылка на первую ноду
node2 - ссылка на вторую ноду
Модель хранения данных в БД¶
Предварительно скрипт создания таблиц будет выглядеть так
CREATE TABLE NODES(
ID INT NOT NULL AUTO_INCREMENT,
NAME VARCHAR(50) NOT NULL,
PROBABILITY FLOAT DEFAULT 0.5 NOT NULL,
COUNTER INT DEFAULT 0 NOT NULL,
PRIMARY KEY (ID)
);
CREATE TABLE EDGES(
NODE1_ID INT NOT NULL,
NODE2_ID INT NOT NULL,
FOREIGN KEY (NODE1_ID) REFERENCES NODE(ID),
FOREIGN KEY (NODE2_ID) REFERENCES NODE(ID),
CHECK (NODE1_ID <> NODE2_ID),
CONSTRAINT UNIQ_EDGE UNIQUE (NODE1_ID,NODE2_ID)
);
Обновлено