Dear Miguel,
Memory is not the sole limitation here. The main problem is that the worst
case time complexity is O(n^4). For instance, it took me several weeks of
computation to determine the hyperbolicity of the latest CAIDA maps (2012
and 2013).
There is currently no exact algorithm for computing the hyperbolicity of
graphs with millions of nodes. In fact, for such large graphs, it is
already challenging to compute the diameter using classical approach.
David.
On Tuesday, April 22, 2014 3:27:23 PM UTC+2, leif wrote:
>
> Vincent Delecroix wrote:
> > I was a bit wrong with my computations. Have a look at the file
> > SAGE_ROOT/src/sage/graphs/distance_all_pairs.pyx
> >
> > You will see that matrices for distances are implemented as unsigned
> > short (whose maximum is 65535=2^16) while eccentricity is made of int
> > (whose maximum depends on your architecture). This was made for
> > economy of space... if you want to compute all distances for a graphs
> > you still have this memory issue (you will need 16Go of RAM).
>
> Well, here RAM apparently wasn't the limiting factor (otherwise the
> function would have bailed out differently, with a MemoryError).
>
> Obviously, the (length of a) shortest path between two vertices on a
> graph of more than 2^16 vertices can exceed 2^16-1, and likewise the
> current implementation cannot represent a predecessor whose "name" is
> above 2^16-1, hence here actually /the number of vertices/ (70000) is
> the limiting factor.
>
>
> -leif
>
>
> > 2014-04-22 12:56 UTC+02:00, Vincent Delecroix
> > <20100.d...@gmail.com<javascript:>>:
>
> >> Hello Miguel,
> >>
> >> If you need support in Sage you should use the sage-support
> >> googlegroups or ask.sagemath.org. The sage-devel mailing list is about
> >> development and bug report.
> >>
> >> To answer your question, if you want to compute all distances in a
> >> graph with more than 65535 vertices then your RAM must be greater than
> >> 255To (because you need 65535 x 65535 x 2^16 bits of data)... in other
> >> words it is a very very huge matrix. There is currently no hardware
> >> that would support that quantity of data.
> >>
> >> 2014-04-22 12:36 UTC+02:00, Miguel Camelo
> >> <migu...@gmail.com<javascript:>>:
>
> >>> Hi everyone,
> >>>
> >>> I'm interesting in to compute both the diameter and hyperbolicity of
> >>> large
> >>> graphs (between 10k and 10M of nodes) using SAGE. At the beginning I
> had
> >>> problems computing the diameter. However I solved the problem using
> the
> >>> solutions presented in the ticked #15507. Then, I tried to compute the
> >>> hyperbolicity for a random graph with 70000 nodes and 209991 edges.
> >>> However, I received the following error:
> >>>
> >>> hyperbolicity(graphs.RandomBarabasiAlbert(70000,3))
> >>> Exception ValueError: ValueError('The graph backend contains more than
> >>> 65535 nodes and we cannot compute the matrix of distances/predecessors
> on
> >>> something like that !',) in
> >>> 'sage.graphs.distances_all_pairs.c_distances_all_pairs' ignored.
> >>>
> >>> Is there any way to solve this problem? I also saw the same problem
> when
> >>> I
> >>> tried to compute the distance matrix of the graph.
> >>>
> >>> Thanks very much.
> >>>
> >>> Miguel Camelo
>
> --
> () The ASCII Ribbon Campaign
> /\ Help Cure HTML E-Mail
>
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
