Разрешение зависимостей элементов

[alexcrown]

Разрешение зависимостей элементов

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

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

С какй стороны подойти к решению?

 

[OZ]

Re: Разрешение зависимостей элементов

Автор оригинала: alexcrown
Есть следующая задача. Имеется набор элементов и для каждого элемента указан набор элементов, от которых он зависит. Нужно построить лес деревьев из этих элементов с учетом заисимостей.

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

С какй стороны подойти к решению?

С разработки алгоритма.

 

[alexcrown]

Это понятно, что с алгоритма. Просто я все время только читаю и иногда отвечаю в этом форуме. А тут захотелось чего-нибудь спросить
Сам алгоритм-то придумался быстро после вопроса. Сначала ищем элементы, которые ни от кого не зависят. Потом элементы, которые зависят только от эелементов, найденных на предыдущих шагах. И повторяем, пока ищется. Правда такой способ не выявляет циклические ссылки, он просто не включает их в результат.

OZ
А вот пользуясь случаем спрошу. Зачем при ответе цитировать все сообщение а не только вопрос, на который отвечаете? Читать же потом становится неудобно.

 

[OZ]

Автор оригинала: alexcrown
Это понятно, что с алгоритма. Просто я все время только читаю и иногда отвечаю в этом форуме. А тут захотелось чего-нибудь спросить
Сам алгоритм-то придумался быстро после вопроса. Сначала ищем элементы, которые ни от кого не зависят. Потом элементы, которые зависят только от эелементов, найденных на предыдущих шагах. И повторяем, пока ищется. Правда такой способ не выявляет циклические ссылки, он просто не включает их в результат.

OZ
А вот пользуясь случаем спрошу. Зачем при ответе цитировать все сообщение а не только вопрос, на который отвечаете? Читать же потом становится неудобно.

В какой строке кода ошибка?

Ответ цитировал на случай, если ты изменишь текст своего сообщения.

 

[phprus]

OZ
Брысь отсюда. Не надо вставлять свои бессмысленные реплики. ИМХО alexcrown не просит сделать за него что-либо, а просит совета, по его задаче.

В какой строке кода ошибка?

При чем тут код? Человек про алгоритм спрашивает, а ты все про какой то код.

alexcrown
В принципе для решения этой задачи можно привести граф зависимостей к ярусно-параллельной форме так как на ней сразу будет видно что от чего зависит, правда граф с циклами и граф в котором есть двунаправленные связи к такой форме привести невозможно. Но я не знаю, на сколько такое решение более оптимально чем ваш алгоритм.

Кстати если в графе зависимостей есть циклы или двунаправленные связи, то по вашему в каком порядке должны будут устанавливаться эти патчи?

 

[OZ]

phprus, иди [censored]. За такое "брысь" в реале получил бы по [censored].
Научись вежливо общаться с людьми, если хочешь уважения.
Я понимаю, что будет бан, и это замечательно.

-~{}~ 08.12.07 16:53:

кроме мании величия "старожил" на этом форуме больше ничего не обсуждается. Всего доброго.

 

[Фанат]

OZ
Ты действительно считаешь свои реплики в этом топике конструктивными?

 

[OZ]

Нет, но я считаю, что тема как минимум не в том разделе (о PHP здесь нет ни слова), а если по существу - труднее придумать алгоритм и способ его программирования, чем написать готовый код. Автор просит сделать за него именно то, что труднее. Такие темы раздражают.


P.S.: И снова всего доброго.

-~{}~ 08.12.07 17:26:

P.P.S.: *****, считаешь ли ты свои реплики в этой теме конструктивными? Или просто по привычке выпендрился?

 

[alexcrown]

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

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

В продолженние данной темы создал тему Управление изменениями структуры базы данных в проектах в рамках которой возникла данная задача.