Project

General

Profile

Roadmap

Основная

open

Основная версия программы

100%

7 issues   (7 closed — 0 open)

План работы

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

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

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

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

Граф

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

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

, где

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

Графическое представление входных графов

cyclic graph

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

acyclic graph

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

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

В качестве дополнения (это не входило в основную задачу)

Возможность работы с нодами отдельно, т.е. в граф можно добавить ноду или набор нод отдельным запросом

Входной одиночный объект, описывающий ноду

{"name":"unique_node_name"}

Входной набор нод

[{"name":"unique_node_name"}, {"name":"unique_node_name"}, ...]

Возможность работы с рёбрами графа отдельно, т.е. в граф можно добавить ребро или набор рёбер отдельным запросом

Входной, одиночный объект описывающий ребро графа

{"nodeOne":"unique_node_one_name", "nodeTwo":"unique_node_one_name"}

Входной набор рёбер

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

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

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

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

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

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

При запросе к сервису можно получить следующие данные:

Граф целиком

{"nodes":[{"id":1, "name":"unique_name", "counter":0}, ...], "edges":[{"id":1, "nodeOne":"unique_node_name_one", "nodeOne":"unique_node_name_one"}, ...]}

Список вершин графа

[{"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 - ссылка на вторую ноду

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

db graph storage

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

SQL Schema (PostgreSQL notation)

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)
);

Виды ошибок

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

Модель данных ошибки:

error model

Выходные данные о возникшей ошибки в формате JSON

{
  "url": "request_link",
  "type": "APP_ERROR[,DATA_NOT_FOUND,DATA_ERROR,VALIDATION_ERROR, WRONG_REQUEST]",
  "place": "APP[,GRAPH,NODE,EDGE]",
  "messages": [
    "Any message 1",
    "Any message 2",
    ...
  ]
}

Виды сообщения об ошибках:

Обобщенные сообщения об ошибках

  • Argument must not be null - на вход вместо объекта был подан null
  • Collection must not be empty - на вход поступила пустая коллекция данных
  • Collection must not contain a null item - на вход поступила коллекция, в которой содержится null элемент
  • Collection must have more than one element - в определённых случаях требуется что бы коллекция состояла как минимум из двух элементов (например при работе с рёбрами графа, где требуется указать две вершины графа, которые нужно связать)
  • %s with ID = %d is not found - данные с указанным ID не обнаружены, где %s - может быть или NODE или EDGE, %d - номер id'шника.

Сообщения об ошибках, возникающие при работе с рёбрами графа

  • Edge for nodes [%s, %s] is not found - ребро для указанных вершин (нод) не найдено, [%s, %s] - уникальные имена пары вершин.
  • Edge for nodes ([%s, %s], [%s, %s]) already present in the graph - данное сообщение возникает при попытки добавить в граф уже существующее ребро. Где ([%s, %s], [%s, %s]) - подставляются уникальные имена вершин графа. Так как граф неориентированный, то например v1 и v2 <=> v2 и v1.
  • Edges for node %s is not found - данное сообщение возникает при попытки извлечь информацию по рёбрам графа для заданной вершины, %s - уникальное имя вершины графа.

Сообщения об ошибках, возникающие при работе с вершинами (нодами) графа

  • Node %s already present in the graph - данное сообщение возникает, при попытки добавить вершину, которая уже присутствует в графе.
  • Error while update node with id = - сообщение возникает при неудачной попытки обновить данные по вершине графа, где id - номер идентификатора вершины.
  • Node with NAME = %s is not found - сообщение возникает, при неудачном поиске вершины графа по её уникальному имени.
  • Node %s is not found - сообщение возникает, при неудачном поиске вершины графа в режиме поиска по заданному объекту.
  • Nodes %s and %s are not reachable to each other - сообщение возникает если один из узлов (вершин графа) не достижим до другого узла (т.е. имеются промежуточные узлы).
  • Node %s is fault - сообщение возникает в случае генерации сбоя в узле (в вершине графа), т.е. узел оказался недоступным во время обхода по узлам.

REST-запросы

В программе доступны следующие виды HTTP запросов: GET, POST, DELETE и OPTION
Могут возвращаться следующие коды статуса: 200, 201, 204, 422, 500

Ниже представлены примеры HTTP запросов

HTTP запросы при работе с графом

  • POST http://localhost:8080/rest/v1/graph - создаёт новый граф, при этом прежний граф полностью удаляется.
    • Тело запроса: {"nodes": [{"name":"unique_node_name"}, ...], "edges": [{"nodeOne":"unique_node_one_name", "nodeTwo":"unique_node_one_name"}, ...]}
    • Ответ: {"nodes":[{"id":1, "name":"unique_name", "counter":0}, ...], "edges":[{"id":1, "nodeOne":"unique_node_name_one", "nodeOne":"unique_node_name_one"}, ...]}
  • POST http://localhost:8080/rest/v1/graph/checkroute - проверка работоспособности заданной последовательности узлов.
    • Тело запроса вида: ["unique_node_name", "unique_node_name", ...]
    • Ответ вида: при корректном выполнении Route for nodes ["unique_node_name", "unique_node_name", ...] is found


  • DELETE http://localhost:8080/rest/v1/graph - удаляет граф с БД, т.е. полностью удаляется информация с БД по узлам и рёбрам графа.

HTTP запросы при отдельной работе с узлами графа

  • POST http://localhost:8080/rest/v1/graph/nodes - добавляет объект узла в граф
    • Тело запроса : {"name":"unique_node_name"}
    • Ответ : {"id":1, "name":"unique_name", "counter":0}
  • POST http://localhost:8080/rest/v1/graph/nodes/byBatch - добавление набора узлов в граф
    • Тело запроса : [{"name":"unique_node_name"}, {"name":"unique_node_name"}, ...]
    • Ответ : [{"id":1, "name":"unique_name", "counter":0}, {"id":2, "name":"unique_name", "counter":0}, ...]


HTTP запросы при отдельной работе с рёбрами графа

  • POST http://localhost:8080/rest/v1/graph/edges - добавляет объект ребра в граф
    • Тело запроса : {"nodeOne":"unique_node_one_name", "nodeTwo":"unique_node_one_name"}
    • Ответ : {"id":1, "nodeOne":"unique_node_name_one", "nodeOne":"unique_node_name_one"}
  • POST http://localhost:8080/rest/v1/graph/edges/byBatch - добавляет список рёбер графа
    • Тело запроса : [{"nodeOne":"unique_node_one_name", "nodeTwo":"unique_node_one_name"}, {"nodeOne":"unique_node_one_name", "nodeTwo":"unique_node_one_name"}, ...]
    • Ответ : [{"id":1, "nodeOne":"unique_node_name_one", "nodeOne":"unique_node_name_one"}, {"id":2, "nodeOne":"unique_node_name_one", "nodeOne":"unique_node_name_one"}, ...]


Go to top