Python-сообщество

AnnaLischen
да, можно по очереди удалять те вершины и рёбра, которые соединены последовательно, но к циклу может быть привязан ещё какой-то “хвост” с другой стороны цикла

Не, вот там путь X2-X3, из-за вершины X8 он отрезается от всего графа. Зачем по нему вести поиск (во все стороны) для заданой в нём вершины, если он отрезан от циклов?

AnnaLischen
Почему лучше?

Потому что всё сводится к обработке маленького двумерного массива.

AnnaLischen
А вы можете сказать что-то по моему коду? Я бы очень хотела именно его отладить.

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

Сначала алгоритм надо описать словами от начала и до конца.
Потом по словесному описанию построить блок-схему и оптимизировать её.
Потом по блок-схеме записать псевдокод и оптимизировать его.
А потом уже по псевдокоду писать реальный код на выбранном языке.

kamisama
py.user.next говорит о матрице, но он это кажется неправильно говорит. Для матрицы алгоритм будет сложнее

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

kamisama
Ах да, путь. А по остальным вопросам?С путем такой же вопрос почти: другими словами надо найти путь между вершиной графа A и циклическим графом B, являющимся подграфом графа A, да? Если вершина находится в графе B, то путь будет равен нулю (пустому списку)?Или, как вы уже говорите, надо найти до любого ближайшего цикла?Граф же статически задается, что подразумевается под словом “соединить”?

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

AnnaLischen
Не, вот там путь X2-X3, из-за вершины X8 он отрезается от всего графа. Зачем по нему вести поиск (во все стороны) для заданой в нём вершины, если он отрезан от циклов?

Если бы у меня был один граф, такого вопроса бы не возникло, но там несколько тысяч. Это просто обобщённый случай.

kamisama
А твой код лучше выкинуть и забыть как страшный сон.

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

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

Но то как оптимизировать код писать его лучше, интересует меня никак не меньше. Если можете показать что-то конкретное, практическое, то будет совсем чудесно, потому что тогда будет понятнее.

kamisama
Нужна еще постановка задачи в строгом виде — что дано и что найти.

Я постралась ответить, как мне казалось. Но напишу ещё раз:
1) Есть большой граф А
2) В нём есть циклы, которые можно записать как отдельные графы
3) Есть разрешённые вершины

Что надо - получить новые графы, состоящие из циклов и разрешённых вершин, при условии, что последние связаны с циклами либо напрямую, либо через другие разрешённые вершины, либо сами входят в состав цикла. Результат: цикл + вершины/а, в случае вершины в цикле это будет просто вершина, в остальных - цикл и набор вершин (от 1 до n, но все должны быть разрешёнными, в противном случае, цепочка обрывается)

AnnaLischen
Если бы у меня был один граф, такого вопроса бы не возникло, но там несколько тысяч.

В итоге код впустую работает на множестве путей, которые сразу можно отрезать, ещё до поиска.
Если есть граф из сотни вершин, который представляет из себя прямую линию, то программа не должна в нём ничего искать. Она должна сделать операцию O(1) и вернуть пустоту.

Отредактировано py.user.next (Апрель 29, 2015 11:52:45)

AnnaLischen
Что надо - получить новые графы, состоящие из циклов и разрешённых вершин, при условии, что последние связаны с циклами либо напрямую, либо через другие разрешённые вершины, либо сами входят в состав цикла. Результат: цикл + вершины/а, в случае вершины в цикле это будет просто вершина, в остальных - цикл и набор вершин (от 1 до n, но все должны быть разрешёнными, в противном случае, цепочка обрывается)

Все равно не понятно полностью(
В вашу функцию подаются item и mainItemOfConnection. Item, вы говорите соединяет, т.е. вытаскивает подграф (один и с максимальной длиной пути или все возможные? И какое количество циклов ? От 2-х и более?) состаящий из этих циклов соедниенных разрешенными вершинами. А с mainItemOfConnection что делать?
Тут надо бы как в математике — формальное описание, типа “написать функцию принимающую на вход граф g, произвольные вершин item и mainitem принадлежащих графу g , спискок разрешенных вершин принадлежащих графу g, и возращающую подграф p, удовлетворяющий следующим условиям: …”.
Или, пожалуй будет проще привести примеры с частными случаями. Я покажу что хотел сказать, а вы потом уже сами обобщите, если что.

AnnaLischen
Я с этим не согласна совершенно. Опыт - сын ошибок трудных, все на чём-то учатся и разбор ошибок и их исправление тоже очень полезны для всего процесса.

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

Отредактировано kamisama (Апрель 29, 2015 18:06:58)

kamisama
И писать, наверное, было больно.

С одной стороны да, с другой - не знала/знаю как иначе, пока учусь, поэтому выжимала из себя то, что уже научилась понимать-соображать.

kamisama
item и mainItemOfConnection

На первом этапе совпадают, потом, когда я, например, соединяю вершину F с циклом A,B,C,E,D через вершины G и N (картинка), но затем, определив что следующая вершина - G - она в рекурсии встанет в item, mainItemOfConnection - const, то есть для этого примера всегда F.
Кстати, я нашла ещё одну проблему: граф ненаправленный (графов больших), как тот, который вы назвали А будет много (несколько тысяч), я не знаю, что там внутри, но надо как-то заставить программу писать граф-результат так: для G , для N и так далее, то есть чтобы поиск не уходил в сторону соседа F.
Математически надо подумать, чуть позже выложу графоматеманскую попытку, просто хочу написать, так чтобы было читаемо. Когда ты в задаче многое из того, что неясно другим, для тебя очевидно. Поэтому надо писать так, чтобы было понятно всем, даже тем, кто на задачу бросит лишь короткий взгляд.

AnnaLischen
постарайтесь плз)
“Список предыдущих предыдущих вершин”, “вершина с которой все началось”, “список циклов” это часть реализации вашего алгоритма. А нужны только главные параметры задачи. Мне кажется там будет только исходная вершина и список разрешенных вершин будет. А от нее уже там искать подграфы.
Еще про общепринятую терминологию не забывайте Например, “соединять”. Граф ведь похоже константный. Вершины уже все соединены (имеют связи).

AnnaLischen
Кстати, я нашла ещё одну проблему:
…
то есть чтобы поиск не уходил в сторону соседа F

Он должен туда сходить и, если там нет цикла, вернуть пустоту. А если вернулась пустота, то должен в другую сторону идти. (Могут же быть циклы не только с одной, но и с обеих сторон.)

Отредактировано py.user.next (Апрель 29, 2015 22:53:00)

py.user.next
Вам эта задача понятна?) Может это я только тут тугодумлю