Обход графа

← →
Kerk © (2013-03-04 16:09) [0]

Столкнулся тут с проблемой. Прошу громко не смеяться, у всех свои слабости.

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

Допустим, их миллион. Т.е. в какой-то момент у меня получится список из 900000 элементов и, попадая в очередную вершину (их, напомню, осталось еще сотни тысяч), по этому списку я буду запускать поиск. Как-то дофига поисков получается по большому списку. Причем списку несортированному. Как вариант, можно сортировать список после каждой вставки, тогда поиск будет работать быстрее. Но сортировка после каждой вставки - это очень много сортировок большого списка. Шило на мыло.

Можно исхитрится и организовать список таким образом, чтобы новая вставка была сразу в нужное место. Таким образом и вставка и поиск будут относительно быстрыми. Вроде вполне себе компромисс?

И пока я не стал реализовывать этот компромисс, спрошу у общественности. Может быть, я чего-то упускаю?

← →
Дмитрий С © (2013-03-04 16:16) [1]

А у элементов графа нельзя выделить битик (уже обошел/еще не обошел) ?

> Можно исхитрится

Можно не исхитряться. Берешь TStringList и смотришь как он устроен.

← →
Ega23 © (2013-03-04 16:20) [2]

Список - сортировать. Искать дихотомией.

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

Именно так.

← →
Kerk © (2013-03-04 16:21) [3]

> Дмитрий С © (04.03.13 16:16) [1]
> А у элементов графа нельзя выделить битик (уже обошел/еще
> не обошел) ?

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

← →
Дмитрий С © (2013-03-04 16:22) [4]

К тому же если массив вершин (веток) графа пронумерован, можно использовать отдельный массив флагов обошел/не обошел.

← →
Ega23 © (2013-03-04 16:25) [5]

Тут правда всякого дополнительного наворочено. Но можешь основное выдрать, убрать всякие Union и Intersect.
Ну и inline-ов добавить, где надо.
TSortedIntList = class(TObject) private FItems: PIntegerArray; FCount: Integer; FCapacity: Integer; procedure Grow; function GetItemIndex(Value: Integer): Integer; procedure Insert(Index, Value: Integer); function GetItem(Index: Integer): Integer; procedure SetCapacity(const Value: Integer); procedure SetCount(const Value: Integer); protected property Memory: PIntegerArray read FItems; public destructor Destroy; override; function Add(Value: Integer): Integer; procedure Assign(Source: TSortedIntList); procedure Intersect(Source: TSortedIntList); procedure Union(Source: TSortedIntList); overload; procedure Union(Memory: Pointer; Count: Integer); overload; procedure Delete(Index: Integer); procedure Remove(Value: Integer); procedure Clear; function IndexOf(Value: Integer): Integer; procedure ToList(List: TList); function Equal(Source: TSortedIntList): Boolean; procedure LoadFromStream(Stream: TStream); procedure SaveToStream(Stream: TStream); property Count: Integer read FCount write SetCount; property Capacity: Integer read FCapacity write SetCapacity; property Items[Index: Integer]: Integer read GetItem; default; end; { TSortedIntList } function TSortedIntList.Add(Value: Integer): Integer; begin if FCount = 0 then begin Insert(0, Value); Exit(0); end; Result := GetItemIndex(Value); if Result < FCount then begin if FItems^[Result] <> Value then Insert(Result, Value); end else Insert(Result, Value); end; procedure TSortedIntList.Assign(Source: TSortedIntList); begin SetCount(Source.Count); System.Move(Source.FItems^[0], FItems^[0], FCount * c_IntSize); end; procedure TSortedIntList.Clear; begin SetCount(0); SetCapacity(0); end; procedure TSortedIntList.Delete(Index: Integer); begin if (Index < 0) or (Index >= FCount) then raise Exception.CreateFmt("TSortedIntList.Delete Index out of bounds (%d)", [Index]); Dec(FCount); if Index < FCount then System.Move(FItems^[Index + 1], FItems^[Index], (FCount - Index) * c_IntSize); end; destructor TSortedIntList.Destroy; begin Clear; inherited; end; function TSortedIntList.Equal(Source: TSortedIntList): Boolean; begin Result := Source.Count = Count; if Result then Result := CompareMem(Memory, Source.Memory, Count * SizeOf(Integer)); end; function TSortedIntList.GetItem(Index: Integer): Integer; begin Result := FItems^[Index]; end; function TSortedIntList.GetItemIndex(Value: Integer): Integer; var FC, FL, FR: Cardinal; begin FL := 0; FR := FCount - 1; if (FItems^[FL] > Value) then Exit(0); if (FItems^[FR] < Value) then Exit(FR + 1); FC := (FL + FR) shr 1; repeat if (FItems^[FC] = Value) then Exit(FC); if (FItems^[FC] < Value) then FL := FC else FR := FC; FC := (FR + FL) shr 1; until FL = FC; if (FItems^[FC] < Value) then Inc(FC); Result := FC; end; procedure TSortedIntList.Grow; var Delta: Integer; begin if FCapacity > 64 then Delta := FCapacity div 4 else if FCapacity > 8 then Delta := 16 else Delta := 4; SetCapacity(FCapacity + Delta); end; function TSortedIntList.IndexOf(Value: Integer): Integer; begin if FCount = 0 then Exit(-1); Result := GetItemIndex(Value); if FItems^[Result] <> Value then Result := -1; end; procedure TSortedIntList.Insert(Index, Value: Integer); begin if FCount = FCapacity then Grow; if Index < FCount then System.Move(FItems^[Index], FItems^[Index + 1], (FCount - Index) * c_IntSize); FItems^[Index] := Value; Inc(FCount); end; procedure TSortedIntList.Intersect(Source: TSortedIntList); var i: Integer; begin for i := FCount - 1 downto 0 do if Source.IndexOf(FItems^[i]) = -1 then Delete(i); end; procedure TSortedIntList.LoadFromStream(Stream: TStream); var cnt: Integer; begin Stream.ReadBuffer(cnt, c_IntSize); SetCount(cnt); Stream.ReadBuffer(FItems^[0], cnt * c_IntSize); end; procedure TSortedIntList.Remove(Value: Integer); var index: Integer; begin if FCount > 0 then begin index := GetItemIndex(Value); if index < FCount then if FItems^[index] = Value then Delete(index); end; end; procedure TSortedIntList.SaveToStream(Stream: TStream); begin Stream.WriteBuffer(FCount, c_IntSize); Stream.WriteBuffer(FItems^[0], c_IntSize * FCount); end; procedure TSortedIntList.SetCapacity(const Value: Integer); begin if FCapacity <> Value then begin ReallocMem(FItems, Value * c_IntSize); FCapacity := Value; end; end; procedure TSortedIntList.SetCount(const Value: Integer); begin if Value > FCount then SetCapacity(Value); FCount := Value; end; procedure TSortedIntList.ToList(List: TList); begin List.Count := FCount; System.Move(FItems^[0], List.List^[0], FCount * SizeOf(Pointer)); end; procedure TSortedIntList.Union(Memory: Pointer; Count: Integer); var i: Integer; Cursor: PInteger; begin Cursor := Memory; for i := 0 to Count - 1 do begin Add(Cursor^); Inc(Cursor); end; end; procedure TSortedIntList.Union(Source: TSortedIntList); var i: Integer; begin for i := 0 to Source.FCount - 1 do Add(Source.FItems^[i]); end;

← →
Дмитрий С © (2013-03-04 16:27) [6]

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

← →
Дмитрий С © (2013-03-04 16:32) [7]

> Ega23 ©

Object-тов не хватает :(

← →
Ega23 © (2013-03-04 16:34) [8]

> Object-тов не хватает :(

Ээээ... А зачем?

← →
Ega23 © (2013-03-04 16:38) [9]

Либо list.Add(Node.ID)
Либо list.Add(Integer(Node))
Либо допилить, переделав на PPointerArray

← →
Inovet © (2013-03-04 16:38) [10]

> [3] Kerk © (04.03.13 16:21)
> Мне список посещенных вершин (вершины, до которых можно
> дойти из заданной точки) нужен как конечный результат.

Так таких может быть больше одного и с пересечениями. Можно идти, пока не попадёшь в конечный пункт, отбрасывая ветки с попаданиями в тупики и на которых встретил себя. Получится от 0 и больше разных путей.

← →
Kerk © (2013-03-04 16:40) [11]

Всем спасибо, накидали достаточно идей.

> Inovet © (04.03.13 16:38) [10]

Я вообще не понял о чем ты. Мне не нужны никакие пути. Мне нужен список допступных вершин, вообще всех.

← →
MBo © (2013-03-04 16:40) [12]

Раз возник такой вопрос, то, скорее всего, недоработан дизайн структуры данных графа.
Например, сам узел может хранить пометку (бит или несколько) - тогда ничего искать не надо, и вспомогательные данные - например, адрес узла, из которого пришли в текущий - тогда путь восстановить легко.

А в общем случае битовый массив флагов, как Дмитрий С уже сказал - быстрый вариант для пометок пройденных узлов.

← →
Inovet © (2013-03-04 16:42) [13]

> [10] Inovet © (04.03.13 16:38)

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

← →
Inovet © (2013-03-04 16:43) [14]

> [11] Kerk © (04.03.13 16:40)
> Мне не нужны никакие пути. Мне нужен список допступных вершин,
> вообще всех.

Ну тогда проще.

← →
Dimka Maslov © (2013-03-04 17:07) [15]

Я бы таки добавил в саму вершину свойство "Passed". А по завершении обхода - собрал бы список вершин и отсортировал. Так быстрее получится чем держать отдельный список с бинарным поиском.

← →
Pit (2013-03-04 17:12) [16]

> Мне список посещенных вершин (вершины, до которых можно
> дойти из заданной точки) нужен как конечный результат.

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

← →
Sha © (2013-03-04 17:28) [17]

> Kerk © (04.03.13 16:09)
> Общим местом у алгоритмов обхода графа ...
> Мне нужен список допступных вершин ...

Это 2 совершенно разных задачи.
Но при решении каждой из них удобно всю информацию хранить в вершинах,
а потом формировать результат.

← →
DevilDevil © (2013-03-04 17:49) [18]

> Kerk © (04.03.13 16:09)

1) кладёшь всё в массив или одно/дву связный список. Ужасно долгое время на поиск

2) делаешь сортированный массив. Быстро ищется, ужасно долго добавляется

3) самобалансирующееся дерево. Быстро ищется (дихотомией), быстро добавляется

4) хеш-массив. Очень быстро ищется, очень быстро добавляется

5) boolean-флаг в узле. Мега быстро определяется (1 такт), мега быстро добавляется (1 такт)

Если ты отчаянно сопротивляешься флагу - делай дерево или хеш-массив. Конечно придётся попотеть в поисках достойной реализации. Лично я ничего достойного не нашёл. В связи с этим (хотя лучше таки используй флаг), могу поделиться своим кодом: http://zalil.ru/34316387 . Но пояснять особо лень - разбирайся сам если хочешь

← →
oxffff © (2013-03-04 20:51) [19]

Флаг в вершине. Так делает сборщик мусор .NET

← →
oxffff © (2013-03-04 20:56) [20]

Про флажок здесь
http://www.rsdn.ru/article/dotnet/GC.xml

← →
Kerk © (2013-03-04 21:03) [21]

Да, я остановился на флаге. Только не флаг, а значение счетчика, который указывает порядковый номер в процессе посещения вершин - так удобнее результат составлять.

← →
DevilDevil © (2013-03-05 09:45) [22]

> Kerk © (04.03.13 21:03) [21]

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

← →
Юрий Зотов © (2013-03-05 21:27) [23]

Обход графа? Элементарно, Ватсон. Вот UML-диаграмма:
\o/ ->--+ | +-------> | / \ | | граф | | | +----------+

← →
Inovet © (2013-03-05 21:33) [24]

> [23] Юрий Зотов © (05.03.13 21:27)

А почему он ханде хох сделал?

← →
Rouse_ © (2013-03-05 21:42) [25]

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

← →
Юрий Зотов © (2013-03-05 21:55) [26]

> Inovet © (05.03.13 21:33) [24]
> А почему он ханде хох сделал?

Да его всего перекорежило.
Кривая UML-ка получилась, не будет работать.

← →
Pit (2013-03-05 21:55) [27]

а исключенными из списка мы считаем те вершины, у которых установлен определенный флаг...

Товарищи программисты, нам совсем чуть чуть осталось - и мы явно придумаем новое слово в науке и технике

← →
Юрий Зотов © (2013-03-05 21:58) [28]

> Rouse_ © (05.03.13 21:42) [25]

Розыч, помнишь разговор за UML? Вот, смотри - в [23] все наглядно, все просто, все понятно, а в [5] черт ногу сломит.

Теперь чуешь, какое преимущество дает UML?

← →
Rouse_ © (2013-03-05 22:18) [29]

> Юрий Зотов © (05.03.13 21:58) [28]

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

← →
Rouse_ © (2013-03-05 22:20) [30]

> а исключенными из списка мы считаем те вершины, у которых
> установлен определенный флаг...

Список уменьшается, стало быть имеем двойной выигрыш, за счет уменьшения самого списка меньшее кол-во проходов и + бонус за счет отсутствия проверки флага.
А так-то да, новое слово - алгоритмЪ :)

← →
Inovet © (2013-03-05 22:46) [31]

> [26] Юрий Зотов © (05.03.13 21:55)
> Да его всего перекорежило.
> Кривая UML-ка получилась, не будет работать.

После графина графена пара графов графоманов и с понтом граф графили пантографом параграф о графах. Какая уж тут работа, когда все стены в графити.

← →
Kerk © (2013-03-05 23:10) [32]

> > Rouse_ © (05.03.13 21:42) [25]
>
> Если под обходом графа является один единственный проход
> через вершину, то проще не вводить битовое поле и т.п. а
> просто исключать вершину из списка присутствующих.

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

← →
Rouse_ © (2013-03-05 23:25) [33]

Ребра при исключении естетсвенно автоматом тушатся, ибо проход то по ним и идет, а двойной проход по одному ребру в данной задаче - нонсенс.

← →
Kerk © (2013-03-05 23:47) [34]

В эту вершину могут и другие ребра вести. И они нифига автоматом не потушатся :)

← →
Rouse_ © (2013-03-05 23:53) [35]

Так это - тогда это уже не обход графа в том изложении, что я сказал :)
Ты точно опиши у тебя задача какая, обход вершин графа с условием одного прохода по каждому узлу и вершине?

← →
Rouse_ © (2013-03-05 23:58) [36]

> И они нифига автоматом не потушатся :)

У меня есть вот такая вот стааааарая наработочка (надоб ее обновить, а то реально устарела) http://rouse.drkb.ru/other.php#cobweb
У нее узлы и графы (немного странно называются Knot и еще че-то там) но там все автоматом учитывается при удалении как узла так и маршрута.
Могу завтра скинуть последний вариант не с таким вырвиглазным наименованием классов + с правкой глюков.

> Rouse_ © (05.03.13 23:53) [35]

Я тут выше писал уже. Дана вершина N. Нужен список вершин, которые можно достигнуть из этой вершины N.

В принципе при этом через каждую вершину можно проходить сколько хочешь раз, ничего страшного не произойдет, но больше одного раза это делать смысла мало :)

Я не о том. Ты представь конкретно что такое "удалить вершину". Это дофига действий потребует.

> Kerk © (06.03.13 00:01) [37]
>
> > Rouse_ © (05.03.13 23:53) [35]
>
> Я тут выше писал уже. Дана вершина N. Нужен список вершин,
> которые можно достигнуть из этой вершины N.

Для этого каждая вершина должна иметь список ребер

> Ты представь конкретно что такое "удалить вершину". Это
> дофига действий потребует.

Неа, тупо выкидываем из промежуточного листа и все.

> Вот ты там как граф хранишь?

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

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

> Rouse_ © (06.03.13 00:19) [39]
> Для этого каждая вершина должна иметь список ребер

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

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

так а текущая то сложность в чём ?
я честно говоря не понял )

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

Есть вершина - структура, есть ребро - структура
Список рёбер исходящих/входящих - это односвязный список (чтобы не париться с логикой двойного добавления)

Флаг посещённой вершины - boolean
Список посещённых вершин - односвязный список

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

Для выделения памяти под структуры я бы рекомендовал использовать свой пул, а не стандартный GetMem/FreeMem. Так и память будет тратиться эффективней, и производительность выше. По моим тестам профит не столько в выделении памяти, сколько во высвобождении.

Нет никакой проблемы давно уже.

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

Так-то флаг, конечно, костыль для производительности.

чёйто?

> [47] brother © (06.03.13 11:44)
> чёйто?

Ну а какую он смыловую нагрузку несёт? Ну знаем, что прошли по узлу, и что? Откуда пришли, куда пошли, сколько раз - нет информации. Так, для решения одной задачи.

ну и? обсуждаем ведь конкретно...

> [49] brother © (06.03.13 11:49)
> ну и? обсуждаем ведь конкретно...

Я и говорю, что для оптимизации решения конкретной задачи.

> Ну а какую он смыловую нагрузку несёт? Ну знаем, что прошли
> по узлу, и что? Откуда пришли, куда пошли, сколько раз -
> нет информации. Так, для решения одной задачи.

TComponent.Tag
Ровно точно такой же "костыль".

> [51] Ega23 © (06.03.13 11:52)
> TComponent.Tag
> Ровно точно такой же "костыль".

Да я не отговариваю, просто к обсуждению.

Обход графа Найти похожие ветки