Project

General

Profile

Actions

Надо сделать #127

closed

Выполнение задания

Added by Александр Александров almost 6 years ago. Updated over 5 years ago.

Status:
Отклонена
Priority:
Нормальный
Category:
Разработка
Target version:
Start date:
03/08/2019
Due date:
04/30/2019
% Done:

40%

Estimated time:
48:00 h
Spent time:
Issue closed :
09/01/2019

Description

  1. Схематично отразить работу программы, рассмотреть несколько вариантов работы, где должно быть отражено успех программы или неуспех. Это наглядно покажет как должна работать программа.
  2. Создать структуру хранения данных исходя из условия задачи. В БД должны быть как минимум 2 таблицы - таблица с узлами, таблица графа построенного из входных узлов (таблица связи узлов в графе).
  3. Создать структуру веб-приложения работающего как REST-сервис.
  4. Создание основной бизнес логики.
  5. Покрытие тестами.

Checklist

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

Related issues

Follows Linkchecker (тестовое задание) - Надо сделать #126: Закрыть пробелы в знаниях, которые необходимы для выполнения поставленной задачиЗакрытаАлександр Александров03/04/201903/07/2019

Actions
Actions #1

Updated by Александр Александров almost 6 years ago

  • Due date set to 03/08/2019
  • Start date changed from 03/04/2019 to 03/08/2019
  • Follows Надо сделать #126: Закрыть пробелы в знаниях, которые необходимы для выполнения поставленной задачи added
Actions #2

Updated by Александр Александров almost 6 years ago

  • Due date changed from 03/08/2019 to 03/15/2019
Actions #3

Updated by Александр Александров over 5 years ago

  • Status changed from Новая to В работе
Actions #4

Updated by Александр Александров over 5 years ago

Проделана следующая работа на этапе проектирования

  1. Поиск инструмента работы с графами, попробую использовать следующую библиотеку JGrapT так же есть вариант самописного класса обхода вершин графа и поиск циклов в нём.
  2. Поиск способов хранения графов в БД, полезные ссылки Does it Make Sense to Map a Graph Data-structure into a Relational Database? , Storing data about undirected graph edges in a database
  3. Создание структуры данных

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} - объект описывающий ребро, соединяющее две вершины графа.

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

cyclic graph

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

acyclic graph

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

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

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

Так же на вход будут подаваться списки вершин графа для проверки связности вершин. Представляет собой простой перечень вершин, можно указать или идентификатор вершины или уникальное имя.
В представлении 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 - при каждом удачном проходе маршрута, через ноду, счётчик ноды увеличивается.

class node

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

class edge

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

db graph storage

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

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)
);
Actions #5

Updated by Александр Александров over 5 years ago

Создал git репозиторий, завёл ветку v1 - первый вариант программы на основе упрощённого шаблона spring mvc.

https://gitlab.resprojects.ru/mrresident/linkchecker/tree/v1

Сначала хотел взять в качестве каркаса приложения с topjava, но показалось что он для каркаса не совсем подходит, нашёл более подходящий, в упрощённой форме. Для примера работоспособности этого шаблона, была создана простенькая модель Book и показана работа с ней.

В качестве БД было решено всё таки взять postgresql.

Actions #6

Updated by Александр Александров over 5 years ago

Всё таки попробовал воспользоваться карксом приложения из topjava. Сроки и количество потраченного времени надо пересматривать.

Actions #7

Updated by Александр Александров over 5 years ago

  • Due date changed from 03/15/2019 to 03/31/2019
Actions #8

Updated by Александр Александров over 5 years ago

  • Estimated time changed from 24:00 h to 48:00 h
Actions #9

Updated by Александр Александров over 5 years ago

Определился с форматом входных данных по графу. В качестве примера приведён граф, состоящий из 5 вершин и 4 рёбер.

{
  "nodes":[
    {"name":"v1","probability":0.1},
    {"name":"v2","probability":0.3},
    {"name":"v3","probability":0.15},
    {"name":"v4","probability":0.65},
    {"name":"v5","probability":0.23}
  ],
  "edges":[
    {"node1":"v1","node2":"v2"},
    {"node1":"v1","node2":"v3"},
    {"node1":"v1","node2":"v5"},
    {"node1":"v3","node2":"v4"}
  ]
}
Actions #10

Updated by Александр Александров over 5 years ago

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

Actions #11

Updated by Александр Александров over 5 years ago

  • Due date changed from 03/31/2019 to 04/30/2019
Actions #12

Updated by Александр Александров over 5 years ago

Решил немного модифицировать поставленную задачу :) Подробности позже.

Actions #13

Updated by Александр Александров over 5 years ago

Закрываю эту задачу. Решил делать всё с начала.

Actions #14

Updated by Александр Александров over 5 years ago

  • Status changed from В работе to Закрыта
Actions #15

Updated by Александр Александров over 5 years ago

  • Status changed from Закрыта to Отклонена
Actions

Also available in: Atom PDF

Go to top