|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
[алгоритмическая задача] подсчитать количество достижимых вершин
12.02.2010 17:22
|
|
|
Задача: для каждой вершины произвольного ориентированного графа подсчитать количество достижимых из нее вершин. Размеры графов - от десятков тысяч до миллионов вершин, так что оптимизация по скорости критична. Куда копать?
Редактировал DarkGray (13.02.2010 13:29)
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
vissi
|
|
|
|
|
|
|
|
|
Рег.: 30.09.2007
|
|
Сообщений: 9275
|
|
|
|
Рейтинг: 8222
|
|
|
ребер у вершины сколько бывает?
я правильно понимаю, что тебе подойдет поиск в ширину?
если граф сильно связный (со множеством сильно связных компонент), то это же вообще довольно много данных.
|
|
|
|
eyescream
|
|
nächste Riff
|
|
|
|
|
|
|
Рег.: 20.02.2005
|
|
Сообщений: 426
|
|
|
|
Рейтинг: 392
|
|
|
В каком виде хранится граф?
|
Current Mortal Sin: гордыня.
Current Wise Thought: was ist wenn der Vorhang fällt? |
|
|
Vlad
|
|
addict
|
|
|
|
|
|
|
Рег.: 18.09.2004
|
|
Сообщений: 446
|
|
|
|
Рейтинг: 236
|
|
|
Для начала выдели сильно связные компоненты (за линейное от числа вершин и ребер время, если не ошибаюсь).
Засчет этого можно (если повезет) ощутимо уменьшить размер задачи, и рассматривать только даги.
|
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: vissi]
12.02.2010 17:32
|
|
|
Quote:
ребер у вершины сколько бывает?
Исходящих - от 0 до нескольких десятков. С поиском в ширину - там ведь могут быть циклы, так что не получится учесть, считали мы уже текущую вершину или нет.
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: eyescream]
12.02.2010 17:33
|
|
|
Quote:
В каком виде хранится граф?
Специальные внутренние форматы. Или я не понял вопрос?
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
1. Построить фактор-граф по отношению эквивалентности - вхождение в одну компонент сильно-связности. Сложность O(V+E). Результатом является ациклический ориентированный граф, вершины которого соответствуют компонентам сильно-связности исходного графа.
2. Начиная с "листовых" компонент для каждой вершины суммируем кол-во вершин в содержащей ее компоненте, а также в тех компонентах, которые достижимы из данной. Сложность O(V + N^2), где N - число компонент связности.
Редактировал FMX (12.02.2010 18:54)
|
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
12.02.2010 17:37
|
|
|
Спасибо =)
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
Vlad
|
|
addict
|
|
|
|
|
|
|
Рег.: 18.09.2004
|
|
Сообщений: 446
|
|
|
|
Рейтинг: 236
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
12.02.2010 17:37
|
|
|
А как избежать повторного суммирования (как в случае с ромбом например)?
|
|
|
reincarnation
|
|
knight
|
|
|
|
|
|
|
Рег.: 12.09.2006
|
|
Сообщений: 719
|
|
|
|
Рейтинг: 666
|
|
|
Мне кажется, можно сделать что-то на основе алгоритма поиска сильно связных компонент. Параллельно с поиском ССК можно строить конденсацию графа, и потом проходом в ширину найти искомое число достижимых вершин (оно будет одинаковым для всех вершин одной СКК). Вроде бы это даже можно скомбинировать в одном цикле и конденсацию явно в виде отдельного графа не строить.
Опоздал 
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: Подскажите хороший алгоритм...
[re: Vlad]
12.02.2010 17:39
|
|
|
Каждой компоненте присваивается целое число - количество вершин, достижимых из вершин этой компоненты. Так вот начиная с листовых компонент можно избежать необходимости повторного суммирования.
Редактировал FMX (12.02.2010 18:04)
|
|
|
Vlad
|
|
addict
|
|
|
|
|
|
|
Рег.: 18.09.2004
|
|
Сообщений: 446
|
|
|
|
Рейтинг: 236
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
12.02.2010 17:42
|
|
|
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: Подскажите хороший алгоритм...
[re: Vlad]
12.02.2010 17:49
|
|
|
Здесь была лажа
Пусть F(X) - вычисление результата для вершин из множества X
F(A) = |A|
F(B) = |B| + F(A)
F(C) = |C| + F(A)
F(D) = |D| + F(B) + F(C)
Для каждого из множеств A, B, C, D функция F вычисляется ровно 1 раз.
Редактировал FMX (12.02.2010 18:49)
|
|
|
reincarnation
|
|
knight
|
|
|
|
|
|
|
Рег.: 12.09.2006
|
|
Сообщений: 719
|
|
|
|
Рейтинг: 666
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
12.02.2010 17:55
|
|
|
Неправильно вычисляется, у тебя получится F(D) = |D|+|B|+|C|+2|A|.
|
|
|
reincarnation
|
|
knight
|
|
|
|
|
|
|
Рег.: 12.09.2006
|
|
Сообщений: 719
|
|
|
|
Рейтинг: 666
|
|
|
Как сделать правильно без хранения списка всех компонент, которые "ниже", хз.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
да, тут я ступил
|
|
|
reincarnation
|
|
knight
|
|
|
|
|
|
|
Рег.: 12.09.2006
|
|
Сообщений: 719
|
|
|
|
Рейтинг: 666
|
|
|
О, можно сделать транзитивное замыкание, но вроде это не быстро.
|
|
|
pianist
|
|
аццкий
|
|
|
|
|
|
|
Рег.: 25.10.2002
|
|
Сообщений: 10841
|
|
Из: ---
|
|
Рейтинг: 7701
|
|
|
Quote:
Задача: для каждой вершины произвольного ориентированного графа подсчитать количество достижимых из нее вершин. Размеры графов - от десятков тысяч до миллионов вершин, так что оптимизация по скорости критична. Куда копать?
Начинать надо с формата, в котором задан граф.
Как и где он хранится. В памяти? На диске? Может он настолько увесистый, что память лопнет...
|
Убей в себе государство!!1 |
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
12.02.2010 18:02
|
|
|
Тогда вместо хранения целого числа для каждой компоненты надо хранить список идентификаторов включенных компонент связности. Тогда оценка сложности будет O(V + E + n^2), где n - число компонент связности.
|
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: pianist]
12.02.2010 18:04
|
|
|
Quote:
Как и где он хранится. В памяти? На диске? Может он настолько увесистый, что память лопнет..
Он вполне себе увесистый (от сотен мегабайт до нескольких гигабайт). В памяти хранится, насколько понимаю, в каждый момент лишь некоторая часть графа.
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
Список
Плоский
Дерево
