Блог пользователя Endagorion

Автор Endagorion, 13 лет назад, По-русски

Привет, Кодфорсес.

Друзья, а расскажите, пожалуйста, что вы знаете про быстрое нахождение радиуса и/или диаметра невзвешенного неориентированного графа (определения тут) ? Быстрое = быстрее, чем за O(MN) (т.е. обходы в ширину из каждой вершины). Интересуют любые результаты: вероятностные, в среднем, для неплотных графов и т.д. Благодарю.

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Гипотеза: если рассмотреть произвольную вершину a, найти самую удалённую от неё вершину b, а потом найти самую удалённую от b вершину с, то расстояние между b и c будет диаметром.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Нашёл контрпример:

    7 8

    0 1

    0 3

    0 4

    1 2

    1 3

    1 4

    3 5

    4 6

    a = 0, b = 2, c = 5. А диаметр равен 4.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Хорошая гипотеза. Для дерева она даже верна. =)

    Для произвольного графа не всегда, к сожалению. Рассмотрим граф, состоящий из цикла длины 6 и еще одной вершины, связанной ребром с какой-нибудь вершиной цикла, что-то вроде этого (буквы — это вершины):

    A---B---C---D
    |       |
    E---F---G
    

    Тогда, запустившись, например, от B, найдем самую удаленную вершину F. От нее все расстояния не больше 3, при том, что диаметр равен 4 (E — D).

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      А если попробовать проитерировать этот алгоритм MAGIC раз? Ну для MAGIC = 10-20.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        ответ чуть ниже)

      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится
            .
            |
            .
           /|\
          . . .
         /  |  \
        .-.-.-.-.
         \  |  /
          . . .
           \|/
            .
            |
            .
        

        Из левой вершины приходим в правую, из правой — в левую. Клинч. А диаметр, между тем, между верхней и нижней.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Тестили, не работает.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      И ведь даже неверно, что если две вершины являются друг для друга самыми удалёнными, то расстояние между ними является диаметром.

      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Немного неправильно понял.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Таких пар просто может быть несколько с разным расстоянием(см. примеры выше)

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Не две самые удалённые вершины, а вершины, которые являются самыми удалёнными друг для друга, то есть, среди всех вершин графа вершина b находится дальше всех от a, а вершина a — дальше всех от b.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

    Не годится: Для графа

    http://i021.radikal.ru/1203/12/81ff712b94e6.png

    Если идти от вершины 10, то найдём вершину 11 и от неё 8 или 1. Но диаметр это путь от 8 до 1.

    UPD: впрочем опоздал :)

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +37 Проголосовать: не нравится

А вопрос практический или теоретический? Я просто вроде придумал какой-то треш за n2 × ln4(n) =)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    Просто вроде можно хитрыми махинациями с сетами (испльзуя бинпоиск по ответу) перемножить два графа (в смысле, перемножить их ориентированные матрицы смежности) за n2 × ln2(n). Если будут желающие, могу пояснить, как это делать.

    А тогда можно за n2 × ln3(n) возвести граф в степень d (квадрат графа, степень — аналогично) и выяснить, является ли она полным графом (для диаметра) или есть ли вершина, смежная со всеми (радиус графа). А значит, можно бинпоиском по ответу найти диаметр или радиус за n2 × ln4(n).

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      В предположении, что можно перемножать графы за n2ln2(n), можно решать и за n2ln3(n). За n2ln3(n) возведем граф во все степени, являющиеся степенями двойки, и запомним все эти графы. Делая бинпоиск, будем хранить помимо чисел-границ бинпоиска граф в степени левой границы бинпоиска. За n2ln2(n) будем его обновлять при каждом шаге бинпоиска вправо.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      И да, мне интересно, как это делать :)

      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Что-то я теперь перестал понимать, как это делать. Постараюсь к вечеру снова понять. Суть у меня была в том, что это не обычные матрицы, в каждой ячейке произведения лежит не сумма n элементов, а or. Поэтому необязательно искать все элемнты — наоборот, желательно действовать так, чтобы каждое ребро было найдено только один раз.

        Нехорошо получилось, я всех заинтриговал, а теперь не знаю, как это делать =(

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Кстати, алгоритм Штрассена же перемножает матрицы за nln27, так что можно найти радиус и диаметр за то же самое умножить на ln(n). Когда рёбер достаточно много, это меньше, чем n × m.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Он, конечно, перемножает, но ему нужна обратная операция к "сложению". Поэтому его нельзя применять к поиску кратчайших путей и иже с ним, у минимума и логического "ИЛИ" нет обратной операции.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            ммм, да, действительно. Обидно.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            Разве здесь не достаточно простого умножения матриц? Матрица смежности в какой-то степени это количество путей какой-то длины между всеми парами вершин. Нам тут только нужно сравнивать эти количества с нулем.

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Ну, это то же умножение матриц, только вместо сложения — ИЛИ, а вместо умножения —И, ну или максимум с минимумом. Кстати, вроде бы метод четырех русских для такого умножения работал, если мне память не изменяет.

              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                Да нет, можно использовать именно умножение и сложение, и считать количество путей.

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Да, похоже на правду. Что-то я не о том думал, когда писал прошлый комментарий.

                  Значит, сложность выходит nln27logn. Неплохо. =) А ведь матрицы можно перемножать еще быстрее, хотя на практике быстрее Штрассена вроде ничего не используется.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  По поводу битовых матриц.

                  http://www.sciencedirect.com/science/article/pii/S0019995873902283

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  Да на практике и это, весьма вероятно, будет работать дольше, чем куб, особенно хорошо написанный. Гораздо лучше (чем Штрассен) применить битовую оптимизацию и грамотное отсечение с рандомом.

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится

              Кстати, а ты прав. Можно ведь возводить в степень не матрицу boolean'ов, а матрицу int'ов.

  • »
    »
    13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится -6 Проголосовать: не нравится

    Что-то мне подсказывает, что n2×ln4(n) хуже, чем n * m :)

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Ну теоретически лучше, но на практике хуже, конечно) Потому я и спрашивал, теоретический это вопрос или практический =)

      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится -35 Проголосовать: не нравится

        Ну даже если n=100, то nln4(n) = 40'960'000 а n×m = 500'000

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          Я же уже согласился, что n × m на практике лучше?

          Примеры, когда n2 × ln3(n) меньше, чем n × m (формально, без учёта константы) начинаются примерно с n = 10000, даже если считать, что m = n2 / 2.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Скорее практический, но теоретически тоже интересно.

    Круто, у меня вот никакого прогресса не вышло. А как вы так быстро матрицы перемножаете? =)

»
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

wil93 and I once attended a conference about the theme. You can find some useful papers here, under "Fast Computation of the Neighbourhood Function and Distance Distribution", and here (look at the links in the bottom of the text). Hope this helps :)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Yep, the algorithm they presented was as follows:

    1. Pick a random vertex U
    2. Run a BFS from U to find the farthest vertex V.
    3. If Dist(U,V) is better than the best diameter found then update it, else exit.
    4. Assign V to U and go back to step 2

    The interesting thing is that the algorithm founds the diameter very soon.

    If you want an approximate diameter, then you can stop manually after having done, say, K searches. The algorithm is then O(MK). It is worth noting that you will find very good results even with very small K.

    When they presented this algorithm, they showed us the results and the running time of some test with (if I'm not mistaken) K = 10, compared to the O(MN) algorithm. It turned out that even with that value of K the diameter found was very close to the "best" one.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      Yes, that seems to be cool thing to use in practice. But, as we discussed a bit earlier (in Russian, though =)), we can choose U in such unlucky way that we won't find precise diameter ever.

      Well, in the real task that I approached graphs could be pretty dense, so there's no sense in "approximating" radii or diameters, as they were quite small.

      Still, thanks for pointing out the papers and nice description!

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      Does it work for every kind of graphs?

      (I am missing comment delete option :(. )

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        No, example below.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes it does. But it is an approximate algorithm, as you are running only K iterations (where K ~ 10 or more, depending on you). It is interesting as it finds quickly the optimal solution (the "optimal in average" K is relatively small, so using a fixed small K can works well). Maybe this algorithm isn't very reliable in programming contest, because of its "approximate" nature, but in practice it is good.

»
13 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Tranvick is correct. I mistaken the problem. Many thanks.

  • »
    »
    13 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +14 Проголосовать: не нравится

    You are wrong, it works only for trees.

    A---G---C---D
    |       |
    E---F---B
    

    We run BFS from A, then from B and answer will be 3. But really answer is 4(E — D).

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Your algorithm is ok for get a tree's diameter, but it's wrong for get a graph's diameter.

»
13 лет назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

Сорри, отвечу про взвешенный случай:

Раньше думал, что диаметер графа (правда для взвешенного случая) не умеют решать быстрее чем APSP. Но вот тут говорят обратное: http://arxiv.org/abs/1011.6181

На практике предлагается параллелить BFS (Дейкстру), как сделать это очень эффективно можно прочитать тут http://is.gd/P7YLL1

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

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Есть забавная идея в этом направлении.

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

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Кстати, забавная оптимизация алгоритма за O(N*M) получается. Можно вместо того, чтобы каждый раз пускать BFS, обрабатывать предка наибольшего поддерева дерева кратчайших путей. В этом случае можно автоматически не рассматривать все вершины его поддерева, так как они уже кратчайшие. Наверное, можно еще что-то поотсекать.

»
13 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Может быть стоит переименовать тему, чтобы она соответствовала содержанию? Ну "Поиск диаметра произвольного графа".

»
12 лет назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

Our group in Florence recently worked on the computation of the diameter of large real-world graphs. You can download our software at http://amici.dsi.unifi.it/lasagne. In the web site, all the references are also listed. I hope this helps.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Для взвешенных графов есть такая статья http://arxiv.org/abs/1011.6181 В ней же есть библиография, тоже интересно.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Обидно правда, что там опять используется умножение матриц за N^{2.376}. Это, конечно, хороший алгоритм. Но для N <= 10^{100} вроде ускорения не дает из-за константы :)

    В общем, работа представляет интерес для чистых теоретиков.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Что-то я не читал этот пост, когда он активно обсуждался. Сейчас просмотрел, в комментариях не нашел такой простой метод.

  1. Используя метод 4-х русских, я умею за N^3 / log^2 перемножить 2 матрицы операциями AND и OR.

  2. Используя идею, которую уже озвучили в комментариях (предподсчитать все степени D^{2^k}, где D — матрица смежности + бинпоиск по ответу), мы получили решение за N^3 / log, что строго лучше чем NM для почти полных графов. Т.е. для почти полных графов есть решение :-)

Теперь про произвольные графы:

Уже обсуждалась идея "возьмем случайную вершину, от нее самую дальнюю, от нее тоже, так будем делать, пока расстояние увеличивается, а все это запустим 100 раз".

Я знаю существенное улучшение этой идеи: по ходу можно отмечать "уже бесполезные вершины", а потом обрывать процесс, когда мы попадаем в "бесполезную вершину". Чем лучше работает определитель "бесполезности", тем быстрее алгоритм сходится. Можно еще неравенство треугольника использовать (d[a][b] <= d[a][c] + d[c][b]).