Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2013.07.28;
Скачать: CL | DM;

Вниз

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

 
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 и еще че-то там) но там все автоматом учитывается при удалении как узла так и маршрута.
Могу завтра скинуть последний вариант не с таким вырвиглазным наименованием классов + с правкой глюков.


 
Kerk ©   (2013-03-06 00:01) [37]


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

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

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

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


 
Kerk ©   (2013-03-06 00:02) [38]


> Rouse_ ©   (05.03.13 23:58) [36]

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


 
Rouse_ ©   (2013-03-06 00:19) [39]


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

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


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

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


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

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

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


 
Kerk ©   (2013-03-06 00:23) [40]


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

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



Страницы: 1 2 вся ветка

Текущий архив: 2013.07.28;
Скачать: CL | DM;

Наверх




Память: 0.59 MB
Время: 0.009 c
3-1291295803
svb
2010-12-02 16:16
2013.07.28
Одна таблица или много маленьких


15-1362429004
Юрий
2013-03-05 00:30
2013.07.28
С днем рождения ! 5 марта 2013 вторник


15-1362341410
Хыхы
2013-03-04 00:10
2013.07.28
Singleton в Delphi


11-1247619060
Osmiy
2009-07-15 04:51
2013.07.28
Не отрисовывается Bitmap в ToolBar


15-1362398967
Kerk
2013-03-04 16:09
2013.07.28
Обход графа