Краткое описание пакета pd.imalyzer
====================================


Пакет предоставляет несколько утилит, предоставляющих возможность
работы с зависимостями: определять замкнутость зависимостей, определять
сегментацию графа завимостей 
### TODO Нужно посмотреть как называетя на самом деле
Все утилиты библиотеки используют специальные модули, которые могут
быть вызываны независимо, и требуют загрузки специального "драйвера
зависимостей", который для каждого узла дает список предоставляемых
возможностей и список требуемых зависимостей.

Возможность состоит из двух параметров: имя возможености и версия
возможности. Зависимость может требовать возможность с точным указанием
версии или с версией, попадающей в полуинтервал.

            
Список утилит
-------------

Утилита, определяющая замкнутость графа зависимостей
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Утилита, определяющая минимальный замкнутый подграф 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Утилит, определяющая графа зависимостей на два несвязных подграфа
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



Варианты использования
----------------------

Использование для анализа зависимостей в програмном пакете
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Необходимо ответить на следующие вопросы:
 
 1. Является ли пакет замкнутым,

 2. Можно ли разбить пакет на два и более независимых пакетов, если 
    нельзя - то какое множество зависимостей мешает это сделать (найти
    минимальный список),

 3. Осуществить подборку по условно-неограниченной базе пакетов тех
    из них, от которых зависит конкретный пакет,

 4. По списку пакетов найти те из них, удаление которых можно провести
    безболензнно (т.е. от них никто не зависит).

 5. Найти (учитывая номера версий) максимальное (по версиям) и минимальное
    (по версиям) подмножество пакетов.

Использование для анализа зависимостей в рассылке
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Зависимости в рассылке являются отражением того, что пользователи
вступают в переписку друг с другом. В этом случае отвечающий на письмо
зависит от автора этого письма. Анализ зависимостей, в таком случае,
в сущности анализ существущих социальных групп пользователей. Задача
осложняется тем, что зависимости могут быть заданы нечетко и неверно: т.е.
факт написания письма был ошибкой некоторого рода, поэтому, надо учитывать
"силу" зависимости, чтобы можно было выбрать те из них, которые можно
разорвать.


Утилиты пакета могут использоваться для достижения следующих целей:

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

 2. В данном круге поельзователей выделилть независимые круги пользователей,
    задача также может решатся как "наилучшая разбивка пользователей на 
    круги общения", отдельно можно выделить пользователей, служащих
    соединениями между кругами общения.

 3. По кругу пользовтелей можно выбрать тех из них, удаление которых 
    произойдет безболезненно - т.е. от них никто не зависит (тут есть
    некоторая вольность в постановке самого направленя зависимости,
    по этому возможно надо построить оба варианте, хотя, в случает 
    рассылки, зависимость проявляется именно в момент ответа на вопрос).

 4. Определить замкнутость круга общения - т.е. на все ли письма
    пользователей находится пользователь, который дает ответ.

 5. Попробовать классифицировать роли пользователей по их связям, 
    например: "ученик" - всегда спрашивает и не пишет ответов (первых),
    "учитель" - пишет только письма, в ответ. "Неприкаянные" - пишут 
    письма, в ответ на письма многих групп, "Бойкотируемые" - пользователм,
    письма которых остаются без ответов.

Использование для анализа зависимостей в вики
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Зависимости в вики - это перекрестные ссылки между текстовым контентом,
отсюда и анализ зависимостей сводится в первую очередь к рубрицированию
контента. Как и в случае с рассылкой, нужно обратить внимание на 
некоторую неоднозначность зависимостей: ссылка может быть поставлена
случайно, излишне или неправильно.

Таким образом, утилиты пакета могут использоватся для достижения следуюзщих
целей:

 1. Определить замкнутость множества контента по сссылкам;

 2. Найти возможность разбить множество контента на замкнутые поднможества
    (не обязательно не связаннные между собой);

 3. Упорядочить контент по ссылкам: выполнить т.н. "топологическую
    сортировку"

 4. Возможно (теоретически) разбить множество контента по дереву рубрик, в
    котором каждая рубрика содержит только материалы, связанные между
    собой, а вот материалы, которые служат предметом ссылок в разных
    рубриках вынести в корень дерева;


Драйвера зависимостей
---------------------

Драйвер зависимостей, это утилита либо предоставляющая интерфейс для
последовательного получения списка зависимостей, либо, напротив,
предоставляющую интерфейс обращения к элемантам и получения списка
зависимостей и возможностий.


Драйвер пакетов RPM
~~~~~~~~~~~~~~~~~~~

Достаточно интересным и, в тоже время, простым в реализации является драйвер
базы RPM-пакетов (в т.ч. установленных в системе), так как позволяет решить
насущные проблемы управления базой пакетов, склонной к замусориванию.


Драйвер хранилища APT
~~~~~~~~~~~~~~~~~~~~~

Позволяет оптимизировать коллекцию пакетов, лежащих в репозитории: например,
оптимальным образом разбить ее по дискам.


Драйвер установленных модулей Python
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Позволяет проанализировать установленное множество пакетов, чтобы
оптимизировать зависимости между  ними (например, чтобы вынести
возможность из сложного пакета, чтобы избежать его обязательной установки).

Может быть использован для автоматической генерации модулей зависимостей 
межде пакетами.


Драйвер PyPI
~~~~~~~~~~~~

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

Драйвер вики
~~~~~~~~~~~~

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

Драйвер вики работает либо с множеством статей лежащих на диске,
либо встроен в вики-интерфейс.


Утилиты, которые уже получились
-------------------------------
Чисто в экспериментальном порядке, что бы побаловаться с прототипом, было
кое-что написано (оно может быть сильно ускорено, если придумать правильные
алгоритмы, ну и в аналогичных случаях). В настоящее время это просто
прототип программы сегментации графа зависимостей, написанный без строгих
доказательств.

kernel.py
    Утилита, раздевающая по слоям граф, что бы добратся до нераздеваемого
    ядра;

cluster.py
    Утилита, разбивающая граф зависимостей на независимые кластеры. Получает на
    вход список вершин подграфа;

subtree.py
    Утилита, которая перечислит вершины, которые могли быть установлены
    только ради того, чтобы поставить указанный пакет;

suborphan.py
    Неверная утилита, аналог subtree.py, возможно надо стереть;

subtrees.py
    Утилита, составляющая по списку вершин список их поддеревьев.
    Учитывается возможность пересечения деревьем. разбивающая граф на список
    поддеревъев.


### Че делать:
###  В процессе построениея деревьев ведем статистику прекращения роста

###   1. Рост прекратился "в нигде" - самостоятельное дерево

###   2. Рост прекратился "в дерево" (одно-единственное, свободных вершин
###   нет) - становится поддеревом

###   3. Рост прекратился "в дерево" (единственное, есть свободные вершины)
###   - по первости самостоятельное дерево, далее пытаемся вырезать из
###   дерева, в которое вросли, подграф, зависящий от данного.

###   4. Рост прекратился "в множество деревьев" - по первости
###   самостоятельное дерево, далее пытаемся вырезать из дерева, в которое
###   вросли, подграф, зависящий от данного.
         
###


imalyzer.py
    Сводная утилита, выполняющая всю работу по расщеплению графа
    зависимостей различными способами.

Конечным результатом является, на сегодняшний день, программа kernel,
которая, выполнив сложную работу, дает упорядоченный по слоям список вершин
оболочки и ядро графа (состоящее, возможно, из нескольких компонент
связности). Ее доработка сводится к реализации следующего алгоритма:

 1. Классификация вершин, раздетых из слоев, по поддеревьям - перечисляем
    все вершины, разбивая слои на деревья (в очень сильно изменнном смысле). 
    Фактически используем наработки утилиты subtrees, при построении каждого
    дерева, касание уже существующего поддерева приводит либо к "сращиванию"
    (если существующее поддерево полностью зависит от текущего), либо к
    "отщеплению по линии касания" ( если есть вершины, от которых не зависит
    единственное поддерево), либо к постройке полностью независимого дерева.
    
 2. Переделка cluster так, что бы она могла распиливать любое множество
    перечисленных вершин (сейчас это сделано за счет отрицания, надо
    натягивать адаптер на драйвер).
    
Результат такой разработки, массивной, видимо утилита imalyzer, которая на
выходе дает кучу трассировки, соответствующей в настоящий момент утилите
cluster, а далее выдает список подграфов, найденных в п. (1,2), нумерует их
и перечисляет отношения зависимостей между ними.

[name:недописано]

