План работы¶

Работа над тестовым заданием:

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

---

Структура данных.¶

Входные данные¶

Граф¶

Входными данными будет граф G(V,E), где V - множество вершин графа (ноды), E - множество рёбер, соединяющих вершины. Граф не ориентированный. Сама вершина (нода) представляет собой объект, состоящий из уникального имени. Ребро представляет собой объект состоящий из двух ссылок на вершины, которые это ребро соединяет, в данном случае под ссылками подразумевается уникальное имя ноды. В формате JSON это будет выглядеть так:

{[{"name":"unique_node_name"}, ...],[{"nodeOne":"unique_node_one_name", "nodeTwo":"unique_node_one_name"}, ...]}

, где

{"name":”unique_node_name"} - объект описывающий вершину графа (ноду)
{"nodeOne":"unique_node_one_name", "nodeTwo":"unique_node_one_name"} - объект описывающий ребро, соединяющее две вершины графа.

Примеры входных графов

Циклический граф

Ациклический граф

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

Вершины графа (Ноды)¶

Так же на вход будут подаваться списки вершин графа для проверки связности вершин. Представляет собой простой перечень уникальных имён вершин.
В представлении JSON будет выглядеть так:

["unique_node_name", "unique_node_name", ...]

, где unique_node_name - уникальное имя вершины.

Структура выходных данных¶

При запросе к сервису можно получить список вершин (нод) в следующем формате

[{"id":1, "name":"unique_name", "counter":0}, ...]

или объект отдельной вершины (информацию по отдельной вершине можно получить выполнив соответствующий запрос, либо по уникальному имени или по идентификатору вершины)

{"id":1, "name":"unique_name", "counter":0}

,где: id - уникальный идентификатор вершины, name - уникальное имя вершины, counter - счётчик посещения вершины.

Так же есть возможность получить информацию по рёбрам графа в следующем формате

Списком

[{"id":1, "nodeOne":"unique_node_name_one", "nodeOne":"unique_node_name_one"}, ...]

Отдельным объектом

{"id":1, "nodeOne":"unique_node_name_one", "nodeOne":"unique_node_name_one"}

,где: id - уникальный идентификатор ребра графа, nodeOne, nodeTwo - уникальное имя узла графа. Запись ребра графа хранит информацию о одной паре узлов.

Модель хранения данных¶

Класс Node - описывающий модель вершины графа (ноды). Класс состоит из следующих полей:

id - уникальный идентификатор (нужен для хранения в БД). Присваивается автоматически при записи в БД, его нельзя изменить из вне, данный параметр только на отдачу из базы.
name - уникальное имя узла (получаем из json).
counter - при каждом удачном проходе маршрута через ноду, счётчик ноды увеличивается автоматически, данный параметр только на отдачу из базы, его нельзя заменить из вне.

Класс Edge - описывающий модель ребра графа. Ребро графа способно хранить информацию только о одной паре паре узлов. Класс состоит из следующих полей:

id - уникальный идентификатор записи (нужен для хранения в БД). Присваивается автоматически при записи в БД, его нельзя изменить из вне, данный параметр только на отдачу из базы.
nodeOne - ссылка на первую ноду
nodeTwo - ссылка на вторую ноду

Модель хранения данных в БД¶

Связь один-к-одному Одна запись ребра графа хранит две ссылки на разные ноды

Предварительно скрипт создания таблиц будет выглядеть так

DROP TABLE IF EXISTS nodes CASCADE;
DROP TABLE IF EXISTS edges;
DROP SEQUENCE IF EXISTS global_seq CASCADE;

CREATE SEQUENCE global_seq START 5000;

CREATE TABLE nodes (
    id INTEGER PRIMARY KEY DEFAULT nextval('global_seq'),
    name VARCHAR NOT NULL,
    counter INTEGER DEFAULT 0 NOT NULL
);
CREATE UNIQUE INDEX nodes_unique_name_idx ON nodes(name);

CREATE TABLE edges (
    id INTEGER PRIMARY KEY DEFAULT nextval('global_seq'),
    nodeone INT NOT NULL,
    nodetwo INT NOT NULL,
    FOREIGN KEY (nodeone) REFERENCES nodes(id) ON DELETE CASCADE,
    FOREIGN KEY (nodetwo) REFERENCES nodes(id) ON DELETE CASCADE,
    CHECK (nodeone <> nodetwo),
    CONSTRAINT unique_edge UNIQUE (nodeone, nodetwo)
);