Dependency graph

dependency_graph.ipynb

{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Построение графа зависимостей\n\n### Изначальные данные\n\nЕсть набор компонент, сами по себе они абстрактны и реализаций не содержат, поэтому в данной задаче нас интересуют только их идентификаторы, так что можно зафиксировать таблицу следующего вида:\n```sql\ncreate table component (\n    id int auto_increment primary key\n);\n```\n\nДалее у нас есть непосредственно реализации, а именно версии этих компонентов. Каждая версия нумеруется по системе semver четырьмя 4-байтовыми числами, то есть можно считать, что `hexname` — 16 байтовое число, для удобства отображения используем `varchar[32]`, так что версия `1.2.3.23425` записывается как `00000001000000020000000300005b81`, соответственно `hexname` можно сравнивать как строки в алфавитном порядке. Получаем следующее описание:\n```sql\ncreate table version (\n    id int auto_increment primary key,\n    component_id int foreign key references component (id),\n    hexname varchar(32)\n);\n```\n\nМежду компонентами существует механизм переиспользования, так что компоненты могут зависеть друг от друга. Зависимости могут меняться от версии к версии, так что будем привязывать их именно к версии. С другой стороны, зависимости прописываются как компонент + ограничения на версию, например, версия `1.0.0.0` компонента `B` зависит от компонента `A` версии от `1.0.0.0` до `2.0.0.0`, не включая `2.0.0.0`. В общем случае это полуинтервал между мажорными резизами, но возможны варианты по включению границ. Таким образом получаем следующую таблицу зависимостей:\n```sql\ncreate table dependency (\n    version_id int foreign key references version (id),\n    component_id int foreign key references component (id),\n    left_include boolean,  # Включается ли левая граница\n    left_hexname varchar(32),  # Непосредственно левая граница\n    right_include boolean,  # Включается ли правая граница\n    right_hexname varchar(32)  # Непосредственно правая граница\n);\n```\n\nНа этом исходные данные заканчиваются. Отдельно стоит сказать, что процесс добавления версии не обязан быть молниеносным, так что часть дальнейших расчётов можно вынести именно на этот шаг.\n\n### Постановка задачи\n\nКлиент выбирает определённые компоненты, после чего хочет получить итоговый набор версий, включающий необходимые зависимости или, если такой набор построить нельзя, то сообщение о несовместимости начального набора. Если конечных вариантов несколько, то выбрать с максимальными номерами версий."
    }
  ],
  "metadata": {
    "gist": {
      "id": "d42a37630d3898e305c3",
      "data": {
        "description": "Dependency graph",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/d42a37630d3898e305c3"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "latex_envs": {
      "eqNumInitial": 0,
      "bibliofile": "biblio.bib",
      "cite_by": "apalike",
      "current_citInitial": 1,
      "eqLabelWithNumbers": true
    },
    "language_info": {
      "name": "python",
      "version": "3.5.0",
      "pygments_lexer": "ipython3",
      "mimetype": "text/x-python",
      "nbconvert_exporter": "python",
      "file_extension": ".py",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}