Endagorion's blog

Radius/diameter of non-weighted graph
By Endagorion, 13 years ago, translation, In English

Hi, Codeforces.

Could anybody kindly tell me something about fast calculating radius and/or diameter of non-weighted undirected graph (definitions can be found here) ? Fast = faster, than in O(MN) (breadth-first searches from each vertex). Any results are welcome: probabilistic, good in average, good for sparse graphs, etc. Thanks.

  • Vote: I like it
  • +30
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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!

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Does it work for every kind of graphs?

      (I am missing comment delete option :(. )

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, example below.

        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 5   Vote: I like it +14 Vote: I do not like it

    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).

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
13 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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.

→ Reply