/graph_recognizer

Primary LanguagePython

Intelligent Graph Recognizer

Постановка задачи

Задача

Требуется разработать “Intelligent Graph Recognizer”, который принимает на вход изображение планарного графа, и выдаёт на выход его список смежности.

Требования к данным

  • Цветные изображения, белый фон, одно изображение -- один связный граф.
  • Формат .png, так как .jpg использует сжатие с потерями.
  • Размер не менее 60x60 и не более 800x800.
  • Графы планарные неориентированные и невзвешенные, допускается до 50 вершин включительно.
  • Граф и граница изображения разнесены хотя бы на 5 пикселей (присутствует зазор).
  • Визуальные особенности изображений графов:
    • каждая вершина изображается окружностью зеленого цвета с меткой синего цвета по центру;
    • метка представляет из себя два символа синего цвета, первый -- заглавная буква латинского алфавита(A-Z), второй -- цифра(0-9). Например, валидная метка -- A7;
    • Шрифт для меток -- Tahoma, не жирный;
    • Метка не выходит за пределы окружности, а по размеру шрифта сопоставима с ней (баундбокс метки и окружность вершины отличаются по площади не более чем на 35%);
    • Ребра невзвешенные двух видов -- обозначаемые одним отрезком черного цвета и обозначаемые двумя параллельными отрезками красного цвета.
  • Входные изображения -- выход утилиты graphviz для отрисовки графов, не фотографии и не изображения от руки.
  • При разработке ориентация будет на указанные требования к входным данным, однако нарушение некоторых из них, например, превышение допустимого количества вершин или наличие шума вокруг границ графа, подобного шуму на .jpg, планируется тоже учесть в разработанном алгоритме.

API

  • “Intelligent Graph Recognizer” оформлен в виде python-библиотеки intelligent_graph_recognizer_lib.

  • Библиотека поставляется каталогом intelligent_graph_recognizer_lib с файлом intelligent_graph_recognizer.py, содержащим функцию - точку входа def recognize_graph(<path_to_png_jpg_image_on_local_computer>).

  • Точка входа возвращает dict[str: dict[str: dict[str: Union[str, int]]]] - словарь, где ключом является строковая меткой вершины, а значением – словарём, в котором каждой смежной вершине сопоставлен словарь с ключами для веса и типа ребра. Если граф не взвешенный, вес всех рёбер равен “1”. Существует отображение из типов ребер в числовые метки.

    Например, {'a': {'b': {'weight': '1', 'type': 0}}, ...}.

  • Для улучшения восприятия работы алгоритма вместе со словарем будет опционально возврщаться изображение графа, построенное по распознанному списку смежности.

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

С примерами входных данных можно ознакомиться по ссылке.