On Thu, Aug 31, 2006 at 01:17:07AM +0400, Dmitry V. Levin wrote:
> On Thu, Aug 31, 2006 at 12:57:49AM +0400, Damir Shayhutdinov wrote:
> > > Далее, я знаю, как обнаруживать циклы.  Нужно сделать соединение ещё раз
> > > само на себя и проверить, не совпадают ли начальный и конечный элементы.
> > > Не понтяно правда, что потом делать с обнаруженными таким образом циклами.
> > Заменять на любой пакет из цикла - то есть, как говорил Сергей,
> > схлопывать циклы в одну вершину.
> 
> На любой пакет из цикла нельзя по двум причинам:
> 1. некоторые вершины есть виртуальные пакеты, их оставлять нехорошо;

Вроде бы на этом этапе виртуальных пакетов уже нет (по крайней мере, в
моём варианте они убирались раньше).

> 2. некоторые вершины могут принадлежать нескольким цепочкам, таким
> вершинам следует отдавать приоритет.

Если имелись в виду циклы, содержащие общие вершины - в этом случае в
одну вершину будут объединяться все вершины всех таких циклов, и с
точки зрения выбора минимального количества вершин никакой разницы
между такими объединёнными вершинами не будет.

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