Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Hyperbolicity
**Definition** :
The hyperbolicity `\delta` of a graph `G` has been defined by Gromov [Gromov87]_ as follows (we give here the so-called 4-points condition):
Let `a, b, c, d` be vertices of the graph, let `S_1`, `S_2` and `S_3` be defined by
.. MATH::
S_1 = dist(a, b) + dist(d, c)\\ S_2 = dist(a, c) + dist(b, d)\\ S_3 = dist(a, d) + dist(b, c)\\
and let `M_1` and `M_2` be the two largest values among `S_1`, `S_2`, and `S_3`. We define `hyp(a, b, c, d) = M_1 - M_2`, and the hyperbolicity `\delta(G)` of the graph is the maximum of `hyp` over all possible 4-tuples `(a, b, c, d)` divided by 2. That is, the graph is said `\delta`-hyperbolic when
.. MATH::
\delta(G) = \frac{1}{2}\max_{a,b,c,d\in V(G)}hyp(a, b, c, d)
(note that `hyp(a, b, c, d)=0` whenever two elements among `a,b,c,d` are equal)
**Some known results** :
- Trees and cliques are `0`-hyperbolic
- `n\times n` grids are `n-1`-hyperbolic
- Cycles are approximately `n/4`-hyperbolic
- Chordal graphs are `\leq 1`-hyperbolic
Besides, the hyperbolicity of a graph is the maximum over all its biconnected components.
**Algorithms and complexity** :
The time complexity of the naive implementation (i.e. testing all 4-tuples) is `O( n^4 )`, and an algorithm with time complexity `O(n^{3.69})` has been proposed in [FIV12]_. This remains very long for large-scale graphs, and much harder to implement.
Several improvements over the naive algorithm have been proposed and are implemented in the current module.
- Another upper bound on `hyp(a, b, c, d)` has been proved in [CCL15]_. It is used to design an algorithm with worse case time complexity in `O(n^4)` but that behaves much better in practice.
Assume that `S_1 = dist(a, b) + dist(c, d)` is the largest sum among `S_1,S_2,S_3`. We have
.. MATH::
S_2 + S_3 =& dist(a, c) + dist(b, d) + dist(a, d) + dist(b, c)\\ =& [ dist(a, c) + dist(b, c) ] + [ dist(a, d) + dist(b, d)]\\ \geq &dist(a,b) + dist(a,b)\\ \geq &2dist(a,b)\\
Now, since `S_1` is the largest sum, we have
.. MATH::
hyp(a, b, c, d) =& S_1 - \max\{S_2, S_3\}\\ \leq& S_1 - \frac{S_2+ S_3}{2}\\ \leq& S_1 - dist(a, b)\\ =& dist(c, d)\\
We obtain similarly that `hyp(a, b, c, d) \leq dist(a, b)`. Consequently, in the implementation of the 'CCL' algorithm, we ensure that `S_1` is larger than `S_2` and `S_3` using an ordering of the pairs by decreasing lengths. Then, we use the best value `h` found so far to stop exploration as soon as `dist(a, b) \leq h`.
The worst case time complexity of this algorithm is `O(n^4)`, but it performs very well in practice since it cuts the search space. This algorithm can be turned into an approximation algorithm since at any step of its execution we maintain an upper and a lower bound. We can thus stop execution as soon as a multiplicative approximation factor or an additive one is proven.
- The notion of ''far-apart pairs'' has been introduced in [Soto11]_ to further reduce the number of 4-tuples to consider. We say that the pair `(a,b)` is far-apart if for every `w` in `V\setminus\{a,b\}` we have
.. MATH::
dist(w,a)+dist(a,b) > dist(w,b) \text{ and }dist(w,b)+dist(a,b) > dist(w,a)
Determining the set of far-apart pairs can be done in time `O(nm)` using BFS. Now, it is proved in [Soto11]_ that there exists two far-apart pairs `(a,b)` and `(c,d)` satisfying `\delta(G) = hyp(a, b, c, d)/2`. For instance, the `n\times m`-grid has only two far-apart pairs, and so computing its hyperbolicity is immediate once the far-apart pairs are found. The 'CCL+FA' or 'CCL+' algorithm improves the 'CCL' algorithm since it uses far-apart pairs.
- This algorithm was further improved in [BCCM15]_: instead of iterating twice over all pairs of vertices, in the "inner" loop, we cut several pairs by exploiting properties of the underlying graph.
.. TODO::
- Add exact methods for the hyperbolicity of chordal graphs
- Add method for partitioning the graph with clique separators
**This module contains the following functions**
At Python level :
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~hyperbolicity` | Return the hyperbolicity of the graph or an approximation of this value. :meth:`~hyperbolicity_distribution` | Return the hyperbolicity distribution of the graph or a sampling of it.
REFERENCES:
.. [BCCM15] \M. Borassi, D. Coudert, P. Crescenzi, and A. Marino. On Computing the Hyperbolicity of Real-World Graphs. Proceedings of the 23rd European Symposium on Algorithms (ESA 2015)
.. [CCL15] \N. Cohen, D. Coudert, and A. Lancin. On computing the Gromov hyperbolicity. ACM Journal of Experimental Algorithmics, 20(1.6):1-18, 2015. :doi:`10.1145/2780652` or [`<https://hal.inria.fr/hal-01182890>`_].
.. [FIV12] \H. Fournier, A. Ismail, and A. Vigneron. *Computing the Gromov hyperbolicity of a discrete metric space*. :arxiv:`1210.3323`.
.. [Gromov87] \M. Gromov. Hyperbolic groups. Essays in Group Theory, 8:75--263, 1987.
.. [Soto11] \M. A. Soto Gomez. 2011. Quelques proprietes topologiques des graphes et applications a internet et aux reseaux. Ph.D. Dissertation. Univ. Paris Diderot (Paris 7).
AUTHORS:
- David Coudert (2012): initial version, exact and approximate algorithm, distribution, sampling - David Coudert (2014): improved exact algorithm using far-apart pairs - Michele Borassi (2015): cleaned the code and implemented the new algorithm - Karan Desai (2016): fixed minor typo in documentation
Methods ------- """
#***************************************************************************** # Copyright (C) 2012 David Coudert <david.coudert@inria.fr> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import print_function
from libc.string cimport memset from cysignals.memory cimport check_allocarray, sig_free from cysignals.signals cimport sig_on, sig_off
from sage.graphs.distances_all_pairs cimport c_distances_all_pairs from sage.ext.memory_allocator cimport MemoryAllocator from sage.graphs.base.static_sparse_graph cimport short_digraph from sage.graphs.base.static_sparse_graph cimport init_short_digraph from sage.graphs.base.static_sparse_graph cimport free_short_digraph from libc.stdint cimport uint16_t, uint32_t, uint64_t include "sage/data_structures/bitset.pxi"
# Defining a pair of vertices as a C struct ctypedef struct pair: uint32_t s uint32_t t
###################################################################### # Speedup functions ######################################################################
r""" Return the subgraph containing the given vertices
This method considers only the connectivity. Therefore, edge labels are ignored as well as any other decoration of the graph (vertex position, etc.).
If ``relabel`` is ``True``, the vertices of the new graph are relabeled with integers in the range '0\cdots \mid vertices \mid -1'. The relabeling map is returned if ``return_map`` is also ``True``.
TESTS:
Giving anything else than a Graph::
sage: from sage.graphs.hyperbolicity import _my_subgraph as mysub sage: mysub([],[]) Traceback (most recent call last): ... ValueError: The input parameter must be a Graph.
Subgraph of a PetersenGraph::
sage: from sage.graphs.hyperbolicity import _my_subgraph as mysub sage: H = mysub(graphs.PetersenGraph(), [0,2,4,6]) sage: H.edges(labels=None) [(0, 4)] sage: H.vertices() [0, 2, 4, 6] """ return (H,{}) if (relabel and return_map) else H
map = dict(zip(iter(vertices), xrange(len(vertices)))) else:
###################################################################### # Building blocks ######################################################################
cdef inline int __hyp__(unsigned short ** distances, int a, int b, int c, int d): """ Return the hyperbolicity of the given 4-tuple. """ cdef int S1, S2, S3, h else: else: else:
###################################################################### # Basic algorithm for the hyperbolicity ######################################################################
cdef tuple hyperbolicity_basic_algorithm(int N, unsigned short ** distances, verbose): """ Returns **twice** the hyperbolicity of a graph, and a certificate.
This method implements the basic algorithm for computing the hyperbolicity of a graph which tests all 4-tuples of vertices not satisfying a cutting rule proposed in [Soto11]_.
INPUT:
- ``N`` -- number of vertices of the graph.
- ``distances`` -- path distance matrix (see the distance_all_pairs module).
- ``verbose`` -- (default: ``False``) is boolean. Set to True to display some information during execution.
OUTPUT:
This function returns a tuple ( h, certificate ), where:
- ``h`` -- the maximum computed value over all 4-tuples, and so is twice the hyperbolicity of the graph. If no such 4-tuple is found, -1 is returned.
- ``certificate`` -- 4-tuple of vertices maximizing the value `h`. If no such 4-tuple is found, the empty list [] is returned.
""" cdef int a, b, c, d, hh, h_LB cdef list certificate
# We use the cutting rule proposed in [Soto11]_
# We use the cutting rule proposed in [Soto11]_
# We compute the hyperbolicity of the 4-tuple
# We compare the value with previously known bound
print('New lower bound:', ZZ(hh)/2)
# Last, we return the computed value and the certificate else: return ( -1, [] )
###################################################################### # Greedy dominating set ######################################################################
r""" Returns a greedy approximation of a dominating set """
print("Greedy dominating set:", sorted(list(DOM)))
###################################################################### # Distances and far-apart pairs ######################################################################
cdef inline distances_and_far_apart_pairs(gg, unsigned short * distances, unsigned short * far_apart_pairs): """ Compute both distances between all pairs and far-apart pairs.
See the module's documentation for the definition of far-apart pairs.
This method assumes that:
- The input graph gg is connected. If not, the result will be incorrect.
- The arrays distances and far_apart_pairs have already been allocated with size `n^2`. """
cdef int i
raise ValueError("distances or far_apart_pairs is a NULL pointer") # Computing the distances/far_apart_pairs can only be done if we have # less than MAX_UNSIGNED_SHORT vertices. raise ValueError("The graph backend contains more than {} nodes and " "we cannot compute the matrix of distances/far-apart " "pairs on something" "like that!".format(<unsigned short> -1))
# The list of waiting vertices
# The vertices which have already been visited cdef bitset_t seen
# the beginning and the end of the list stored in waiting_list cdef uint32_t waiting_beginning, waiting_end
cdef uint32_t source cdef uint32_t v, u
# All pairs are initially far-apart
# Copying the whole graph to obtain the list of neighbors quicker than by # calling out_neighbors. This data structure is well documented in the # module sage.graphs.base.static_sparse_graph cdef short_digraph sd cdef uint32_t * p_tmp cdef uint32_t * end
# We run n different BFS taking each vertex as a source
# The source is seen
# and added to the queue
# For as long as there are vertices left to explore
# We pick the first one
# Iterating over all the outneighbors u of v
# If we notice one of these neighbors is not seen yet, we set # its parameters and add it to the queue to be explored later.
# v is on the path from source to u
cdef inline pair** sort_pairs(uint32_t N, uint16_t D, unsigned short ** values, unsigned short ** to_include, uint32_t * nb_p, uint32_t * nb_pairs_of_length ): """ Returns an array of unordered pairs {i,j} in increasing order of values.
Uses counting sort to list pairs {i,j} in increasing order of values(i,j). If to_include[i][j] = 0, the pair is ignored. We assume N and D to be correct with respect to the arrays values and to_include, that values and to_include are symmetric (that is, values[i][j] = values[j][i] and to_include[i][j] = to_include[j][i], and that nb_p, nb_pairs_of_length are already allocated.
INPUT:
- ``N`` -- the range of i and j (that is, the square root of the number of pairs to be sorted);
- ``D`` -- the maximum value of an element;
- ``values`` -- an array containing in position (i,j) the value of the pair (i,j);
- ``to_include`` -- an array such that to_include[i][j] contains "1" if pair (i,j) should be included, "0" otherwise. If NULL, all elements are included;
OUTPUT:
- ``nb_p`` -- the number of pairs to be included;
- ``nb_pairs_of_length`` -- an array containing in position k the number of pairs (i,j) that are included and such that values[i][j] = k.
- ``pairs_of_length`` -- this function returns this array, containing in position k a pointer to the first included pair (i,j) such that values[i][j] = k. """ # pairs_of_length[d] is the list of pairs of vertices at distance d cdef unsigned short *p_to_include cdef uint32_t i,j,k
# fills nb_pairs_of_length and nb_p
else:
# temporary variable used to fill pairs_of_length
# ==> Defines pairs_of_length[d] for all d
# ==> Fills pairs_of_length[d] for all d else:
###################################################################### # Compute the hyperbolicity using the algorithm of [BCCM15]_ ######################################################################
cdef tuple hyperbolicity_BCCM(int N, unsigned short **distances, unsigned short **far_apart_pairs, int D, int h_LB, float approximation_factor, float additive_gap, verbose = False): """ Return the hyperbolicity of a graph.
This method implements the exact and the approximate algorithms proposed in [BCCM15]_. See the module's documentation for more details.
This method assumes that the graph under consideration is connected.
INPUT:
- ``N`` -- number of vertices of the graph
- ``distances`` -- path distance matrix
- ``far_apart_pairs`` -- 0/1 matrix of far-apart pairs. Pair ``(i,j)`` is far-apart if ``far_apart_pairs[i][j]\neq 0``.
- ``D`` -- diameter of the graph
- ``h_LB`` -- lower bound on the hyperbolicity
- ``approximation_factor`` -- When the approximation factor is set to some value larger than 1.0, the function stop computations as soon as the ratio between the upper bound and the best found solution is less than the approximation factor. When the approximation factor is 1.0, the problem is solved optimally.
- ``additive_gap`` -- When sets to a positive number, the function stop computations as soon as the difference between the upper bound and the best found solution is less than additive gap. When the gap is 0.0, the problem is solved optimally.
- ``verbose`` -- (default: ``False``) is boolean set to ``True`` to display some information during execution
OUTPUT:
This function returns a tuple ( h, certificate, h_UB ), where:
- ``h`` -- is an integer. When 4-tuples with hyperbolicity larger or equal to `h_LB are found, h is the maximum computed value and so twice the hyperbolicity of the graph. If no such 4-tuple is found, it returns -1.
- ``certificate`` -- is a list of vertices. When 4-tuples with hyperbolicity larger that h_LB are found, certificate is the list of the 4 vertices for which the maximum value (and so the hyperbolicity of the graph) has been computed. If no such 4-tuple is found, it returns the empty list [].
- ``h_UB`` -- is an integer equal to the proven upper bound for `h`. When ``h == h_UB``, the returned solution is optimal. """ cdef int a, b, c, d, h_UB, n_val, n_acc, i, j cdef int hplusone cdef int condacc cdef int x, y, S1, S2, S3 cdef uint32_t nb_p # The total number of pairs. cdef unsigned short *dist_a cdef unsigned short *dist_b
# Variable used to store "mates".
# The farness of all vertices (the farness of v is the sum of the distances # between v and all other vertices).
# We compute the farness and the eccentricity of all vertices. # We set central as the vertex with minimum farness raise ValueError("The input graph must be connected.")
# We put in variable mates_decr_order_value[a] all vertices b, in # decreasing order of ecc[b]-distances[a][b]
# We sort pairs, in increasing order of distance
&nb_p, nb_pairs_of_length)
print("Current 2 connected component has %d vertices and diameter %d" %(N,D)) if far_apart_pairs == NULL: print("Number of pairs: %d" %(nb_p)) print("Repartition of pairs:", [(i, nb_pairs_of_length[i]) for i in range(1, D+1) if nb_pairs_of_length[i]>0]) else: print("Number of far-apart pairs: %d\t(%d pairs in total)" %(nb_p, binomial(N, 2))) print("Repartition of far-apart pairs:", [(i, nb_pairs_of_length[i]) for i in range(1, D+1) if nb_pairs_of_length[i]>0])
# We start iterating from pairs with maximum distance.
# Without loss of generality, a has smaller farness than b. a,b = b,a
# If we cannot improve further, we stop h_UB = h GOTO_RETURN = 1 break
# Termination if required approximation is found GOTO_RETURN = 1 break
# We update variable mate, adding pair (a,b)
# We compute acceptable and valuable vertices
# Vertex c is acceptable # Vertex c is valuable else:
# For each pair (c,d) where c is valuable and d is acceptable, we # compute the hyperbolicity of (a,b,c,d), and we update h if necessary else:
# We update current bound on the hyperbolicity and the # search space. # # Note that if hh==0, we first make sure that a,b,c,d are # all distinct and are a valid certificate.
print("New lower bound:", ZZ(hh)/2)
# We reset acc_bool
# Needed because sometimes h_UB is not updated, if the analysis is no cut.
# We now free the memory
print("Visited 4-tuples:", nq)
# Last, we return the computed value and the certificate return ( -1, [], h_UB ) else: # When using far-apart pairs, the loops may end before improving the # upper-bound
###################################################################### # Compute the hyperbolicity using the algorithm of [CCL15]_ ######################################################################
cdef tuple hyperbolicity_CCL(int N, unsigned short ** distances, unsigned short ** far_apart_pairs, int D, int h_LB, float approximation_factor, float additive_gap, verbose = False): """ Return the hyperbolicity of a graph.
This method implements the exact and the approximate algorithms proposed in [CCL15]_. See the module's documentation for more details.
This method assumes that the graph under consideration is connected.
INPUT:
- ``N`` -- number of vertices of the graph
- ``distances`` -- path distance matrix
- ``far_apart_pairs`` -- 0/1 matrix of far-apart pairs. Pair ``(i,j)`` is far-apart if ``far_apart_pairs[i][j]\neq 0``.
- ``D`` -- diameter of the graph
- ``h_LB`` -- lower bound on the hyperbolicity
- ``approximation_factor`` -- When the approximation factor is set to some value larger than 1.0, the function stop computations as soon as the ratio between the upper bound and the best found solution is less than the approximation factor. When the approximation factor is 1.0, the problem is solved optimally.
- ``additive_gap`` -- When sets to a positive number, the function stop computations as soon as the difference between the upper bound and the best found solution is less than additive gap. When the gap is 0.0, the problem is solved optimally.
- ``verbose`` -- (default: ``False``) is boolean set to ``True`` to display some information during execution
OUTPUT:
This function returns a tuple ( h, certificate, h_UB ), where:
- ``h`` -- is an integer. When 4-tuples with hyperbolicity larger or equal to `h_LB are found, h is the maximum computed value and so twice the hyperbolicity of the graph. If no such 4-tuple is found, it returns -1.
- ``certificate`` -- is a list of vertices. When 4-tuples with hyperbolicity larger that h_LB are found, certificate is the list of the 4 vertices for which the maximum value (and so the hyperbolicity of the graph) has been computed. If no such 4-tuple is found, it returns the empty list [].
- ``h_UB`` -- is an integer equal to the proven upper bound for `h`. When ``h == h_UB``, the returned solution is optimal. """ cdef int hh # can get negative value cdef int a, b, c, d, h, h_UB cdef int x, y, l1, l2, S1, S2, S3 cdef uint32_t nb_p # The total number of pairs.
# Test if the distance matrix corresponds to a connected graph, i.e., if # distances from node 0 are all less or equal to N-1. raise ValueError("The input graph must be connected.")
# nb_pairs_of_length[d] is the number of pairs of vertices at distance d
raise MemoryError
&nb_p, nb_pairs_of_length)
print("Current 2 connected component has %d vertices and diameter %d" %(N,D)) if far_apart_pairs == NULL: print("Number of pairs: %d" %(nb_p)) print("Repartition of pairs:", [(i, nb_pairs_of_length[i]) for i in range(1, D+1) if nb_pairs_of_length[i]>0]) else: print("Number of far-apart pairs: %d\t(%d pairs in total)" %(nb_p, binomial(N, 2))) print("Repartition of far-apart pairs:", [(i, nb_pairs_of_length[i]) for i in range(1, D+1) if nb_pairs_of_length[i]>0])
# We create the list of triples (sum,length1,length2) sorted in decreasing # lexicographic order: decreasing by sum, decreasing by length2, decreasing # length1. This is to ensure a valid ordering for S1, to avoid some tests, # and to ease computation of bounds.
# We use some short-cut variables for efficiency cdef pair * pairs_of_length_l1 cdef pair * pairs_of_length_l2 cdef uint32_t nb_pairs_of_length_l1, nb_pairs_of_length_l2 cdef unsigned short * dist_a cdef unsigned short * dist_b
# S1 = l1+l2 # l1 = dist(a,b) # l2 = dist(c,d) # l1 >= l2
print("New upper bound:", ZZ(h_UB) / 2)
# Termination if required approximation is found
# If we cannot improve further, we stop # # See the module's documentation for a proof that this cut is # valid. Remember that the triples are sorted in a specific order. h_UB = h break
# We do not want to test pairs of pairs twice if l1 == l2
# We compute the hyperbolicity of the 4-tuple. We have S1 = l1 + # l2, and the order in which pairs are visited allow us to claim # that S1 = max( S1, S2, S3 ). Indeed, if S1 is not the maximum # value, the order ensures that the maximum value has previously # been checked. else:
# We update current bound on the hyperbolicity and the # search space. # # Note that if hh==0, we first make sure that a,b,c,d are # all distinct and are a valid certificate.
print("New lower bound:", ZZ(hh) / 2)
# If we cannot improve further, we stop
# Termination if required approximation is found
# We now free the memory
# Last, we return the computed value and the certificate return ( -1, [], h_UB ) else: # When using far-apart pairs, the loops may end before improving the # upper-bound
algorithm='BCCM', approximation_factor=None, additive_gap=None, verbose = False): r""" Returns the hyperbolicity of the graph or an approximation of this value.
The hyperbolicity of a graph has been defined by Gromov [Gromov87]_ as follows: Let `a, b, c, d` be vertices of the graph, let `S_1 = dist(a, b) + dist(b, c)`, `S_2 = dist(a, c) + dist(b, d)`, and `S_3 = dist(a, d) + dist(b, c)`, and let `M_1` and `M_2` be the two largest values among `S_1`, `S_2`, and `S_3`. We have `hyp(a, b, c, d) = |M_1 - M_2|`, and the hyperbolicity of the graph is the maximum over all possible 4-tuples `(a,b, c,d)` divided by 2. The worst case time complexity is in `O( n^4 )`.
See the documentation of :mod:`sage.graphs.hyperbolicity` for more information.
INPUT:
- ``G`` -- a connected Graph
- ``algorithm`` -- (default: ``'BCCM'``) specifies the algorithm to use among:
- ``'basic'`` is an exhaustive algorithm considering all possible 4-tuples and so have time complexity in `O(n^4)`.
- ``'CCL'`` is an exact algorithm proposed in [CCL15_]. It considers the 4-tuples in an ordering allowing to cut the search space as soon as a new lower bound is found (see the module's documentation). This algorithm can be turned into a approximation algorithm.
- ``'CCL+FA'`` or ``'CCL+'`` uses the notion of far-apart pairs as proposed in [Soto11]_ to significantly reduce the overall computation time of the ``'CCL'`` algorithm.
- ``'BCCM'`` is an exact algorithm proposed in [BCCM15_]. It improves ``'CCL+FA'`` by cutting several 4-tuples (for more information, see the module's documentation).
- ``'dom'`` is an approximation with additive constant four. It computes the hyperbolicity of the vertices of a dominating set of the graph. This is sometimes slower than ``'CCL'`` and sometimes faster. Try it to know if it is interesting for you. The ``additive_gap`` and ``approximation_factor`` parameters cannot be used in combination with this method and so are ignored.
- ``approximation_factor`` -- (default: None) When the approximation factor is set to some value (larger than 1.0), the function stop computations as soon as the ratio between the upper bound and the best found solution is less than the approximation factor. When the approximation factor is 1.0, the problem is solved optimally. This parameter is used only when the chosen algorithm is ``'CCL'``, ``'CCL+FA'``, or ``'BCCM'``.
- ``additive_gap`` -- (default: None) When sets to a positive number, the function stop computations as soon as the difference between the upper bound and the best found solution is less than additive gap. When the gap is 0.0, the problem is solved optimally. This parameter is used only when the chosen algorithm is ``'CCL'`` or ``'CCL+FA'``, or ``'BCCM'``.
- ``verbose`` -- (default: ``False``) is a boolean set to True to display some information during execution: new upper and lower bounds, etc.
OUTPUT:
This function returns the tuple ( delta, certificate, delta_UB ), where:
- ``delta`` -- the hyperbolicity of the graph (half-integer value).
- ``certificate`` -- is the list of the 4 vertices for which the maximum value has been computed, and so the hyperbolicity of the graph.
- ``delta_UB`` -- is an upper bound for ``delta``. When ``delta == delta_UB``, the returned solution is optimal. Otherwise, the approximation factor if ``delta_UB/delta``.
EXAMPLES:
Hyperbolicity of a `3\times 3` grid::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.GridGraph([3,3]) sage: hyperbolicity(G,algorithm='BCCM') (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2) sage: hyperbolicity(G,algorithm='CCL') (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2) sage: hyperbolicity(G,algorithm='basic') (2, [(0, 0), (0, 2), (2, 0), (2, 2)], 2)
Hyperbolicity of a PetersenGraph::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.PetersenGraph() sage: hyperbolicity(G,algorithm='BCCM') (1/2, [6, 7, 8, 9], 1/2) sage: hyperbolicity(G,algorithm='CCL') (1/2, [0, 1, 2, 3], 1/2) sage: hyperbolicity(G,algorithm='CCL+') (1/2, [0, 1, 2, 3], 1/2) sage: hyperbolicity(G,algorithm='CCL+FA') (1/2, [0, 1, 2, 3], 1/2) sage: hyperbolicity(G,algorithm='basic') (1/2, [0, 1, 2, 3], 1/2) sage: hyperbolicity(G,algorithm='dom') (0, [0, 2, 8, 9], 1)
Asking for an approximation in a grid graph::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.GridGraph([2,10]) sage: hyperbolicity(G,algorithm='CCL', approximation_factor=1.5) (1, [(0, 0), (0, 9), (1, 0), (1, 9)], 3/2) sage: hyperbolicity(G,algorithm='CCL+', approximation_factor=1.5) (1, [(0, 0), (0, 9), (1, 0), (1, 9)], 1) sage: hyperbolicity(G,algorithm='CCL', approximation_factor=4) (1, [(0, 0), (0, 9), (1, 0), (1, 9)], 4) sage: hyperbolicity(G,algorithm='CCL', additive_gap=2) (1, [(0, 0), (0, 9), (1, 0), (1, 9)], 3) sage: hyperbolicity(G,algorithm='dom') (1, [(0, 1), (0, 9), (1, 0), (1, 8)], 5)
Asking for an approximation in a cycle graph::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.CycleGraph(10) sage: hyperbolicity(G,algorithm='CCL', approximation_factor=1.5) (2, [0, 2, 5, 7], 5/2) sage: hyperbolicity(G,algorithm='CCL+FA', approximation_factor=1.5) (2, [0, 2, 5, 7], 5/2) sage: hyperbolicity(G,algorithm='CCL+FA', additive_gap=1) (2, [0, 2, 5, 7], 5/2)
Comparison of results::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: for i in range(10): # long time ....: G = graphs.RandomBarabasiAlbert(100,2) ....: d1,_,_ = hyperbolicity(G,algorithm='basic') ....: d2,_,_ = hyperbolicity(G,algorithm='CCL') ....: d3,_,_ = hyperbolicity(G,algorithm='CCL+') ....: d4,_,_ = hyperbolicity(G,algorithm='CCL+FA') ....: d5,_,_ = hyperbolicity(G,algorithm='BCCM') ....: l3,_,u3 = hyperbolicity(G,approximation_factor=2) ....: if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1: ....: print("That's not good!")
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: import random sage: random.seed() sage: for i in range(10): # long time ....: n = random.randint(2, 20) ....: m = random.randint(0, n*(n-1) / 2) ....: G = graphs.RandomGNM(n, m) ....: for cc in G.connected_components_subgraphs(): ....: d1,_,_ = hyperbolicity(cc, algorithm='basic') ....: d2,_,_ = hyperbolicity(cc, algorithm='CCL') ....: d3,_,_ = hyperbolicity(cc, algorithm='CCL+') ....: d4,_,_ = hyperbolicity(cc, algorithm='CCL+FA') ....: d5,_,_ = hyperbolicity(cc, algorithm='BCCM') ....: l3,_,u3 = hyperbolicity(cc, approximation_factor=2) ....: if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1: ....: print("Error in graph ", cc.edges())
The hyperbolicity of a graph is the maximum value over all its biconnected components::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.PetersenGraph() * 2 sage: G.add_edge(0, 11) sage: hyperbolicity(G) (1/2, [6, 7, 8, 9], 1/2)
TESTS:
Giving anything else than a Graph::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: hyperbolicity([]) Traceback (most recent call last): ... ValueError: The input parameter must be a Graph.
Giving a non connected graph::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = Graph([(0,1),(2,3)]) sage: hyperbolicity(G) Traceback (most recent call last): ... ValueError: The input Graph must be connected.
Giving wrong approximation factor::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = graphs.PetersenGraph() sage: hyperbolicity(G,algorithm='CCL', approximation_factor=0.1) Traceback (most recent call last): ... ValueError: The approximation factor must be >= 1.0.
Giving negative additive gap::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = Graph() sage: hyperbolicity(G,algorithm='CCL', additive_gap=-1) Traceback (most recent call last): ... ValueError: The additive gap must be a real positive number.
Asking for an unknown algorithm::
sage: from sage.graphs.hyperbolicity import hyperbolicity sage: G = Graph() sage: hyperbolicity(G,algorithm='tip top') Traceback (most recent call last): ... ValueError: Algorithm 'tip top' not yet implemented. Please contribute. """
# Abbreviations for algorithms are expanded.
pass else: raise ValueError("The approximation_factor is ignored when using" "the '%s' algorithm." %(algorithm)) pass else: raise ValueError("The additive_gap is ignored when using the '%s' algorithm." %(algorithm))
# The hyperbolicity is defined on connected graphs
# The hyperbolicity of some classes of graphs is known. If it is easy and # fast to test that a graph belongs to one of these classes, we do it. # The hyperbolicity of a graph with 3 vertices is 0. # The certificate is the set of vertices. return 0, G.vertices(), 0
# G is a tree # Any set of 4 vertices is a valid certificate return 0, G.vertices()[:4], 0
# Any set of 4 vertices is a valid certificate return 0, G.vertices()[:4], 0
cdef int i, j, D cdef list certif
# # The hyperbolicity of a graph is the maximum over its 2-connected # components. #
# we compute the distribution of size of the blocks L = [len(V) for V in B] print("Graph with %d blocks" %(len(B))) print("Blocks size distribution:", {x:L.count(x) for x in L})
# The hyperbolicity of a graph with 3 vertices is 0, and a graph # cannot have hyperbolicity larger than N/2. So we consider only # larger 2-connected subgraphs.
# We test if the new computed value improves upon previous value.
# We update independently the upper bound for cases in which we # are asking for an approximation.
# Last, we return the computed value and the certificate
# # Now the graph is 2-connected, has at least 4 vertices and is not a clique. #
cdef unsigned short * _distances_ cdef unsigned short ** distances cdef unsigned short * _far_apart_pairs_ cdef unsigned short ** far_apart_pairs
# We compute the distances and store the results in a 2D array raise MemoryError("Unable to allocate array 'distances'.")
else:
# We call the cython function for computing the hyperbolicity with the # required parameters.
# Computes a dominating set DOM of G, and computes the hyperbolicity # considering only vertices in DOM # We need at least 4 vertices DOM.add(G.random_vertex()) # We map the dominating set to [0..N-1] # We set null distances to vertices outside DOM. This way these # vertices will not be considered anymore.
verbose=verbose)
# We now release the memory
# Map the certificate 'certif' with the corresponding vertices in the graph
# Last, we return the computed value and the certificate
###################################################################### # Distribution of the hyperbolicity of 4-tuples ######################################################################
cdef dict __hyperbolicity_distribution__(int N, unsigned short ** distances): """ Return the distribution of the hyperbolicity of the 4-tuples of the graph.
The hyperbolicity of a graph has been defined by Gromov [Gromov87]_ as follows: Let `a, b, c, d` be vertices of the graph, let `S_1 = dist(a, b) + dist(b, c)`, `S_2 = dist(a, c) + dist(b, d)`, and `S_3 = dist(a, d) + dist(b, c)`, and let `M_1` and `M_2` be the two largest values among `S_1`, `S_2`, and `S_3`. We have `hyp(a, b, c, d) = |M_1 - M_2|`, and the hyperbolicity of the graph is the maximum over all possible 4-tuples `(a, b, c, d)` divided by 2.
The computation of the hyperbolicity of each 4-tuple, and so the hyperbolicity distribution, takes time in `O( n^4 )`.
We use ``unsigned long int`` on 64 bits, so ``uint64_t``, to count the number of 4-tuples of given hyperbolicity. So we cannot exceed `2^64-1`. This value should be sufficient for most users.
INPUT:
- ``N`` -- number of vertices of the graph (and side of the matrix)
- ``distances`` -- matrix of distances in the graph
OUTPUT:
- ``hdict`` -- A dictionary such that hdict[i] is the number of 4-tuples of hyperbolicity i among the considered 4-tuples. """ # We initialize the table of hyperbolicity. We use an array of unsigned long # int instead of a dictionary since it is much faster. cdef int i
raise MemoryError
# We now compute the hyperbolicity of each 4-tuple cdef int a, b, c, d
# We prepare the dictionary of hyperbolicity distribution to return
# We use this trick since it is way faster than using the sage randint function. cdef extern from "stdlib.h": long c_libc_random "random"() void c_libc_srandom "srandom"(unsigned int seed)
cdef dict __hyperbolicity_sampling__(int N, unsigned short ** distances, uint64_t sampling_size): """ Return a sampling of the hyperbolicity distribution of the graph.
The hyperbolicity of a graph has been defined by Gromov [Gromov87]_ as follows: Let `a, b, c, d` be vertices of the graph, let `S_1 = dist(a, b) + dist(b, c)`, `S_2 = dist(a, c) + dist(b, d)`, and `S_3 = dist(a, d) + dist(b, c)`, and let `M_1` and `M_2` be the two largest values among `S_1`, `S_2`, and `S_3`. We have `hyp(a, b, c, d) = |M_1 - M_2|`, and the hyperbolicity of the graph is the maximum over all possible 4-tuples `(a, b, c, d)` divided by 2.
We use ``unsigned long int`` on 64 bits, so ``uint64_t``, to count the number of 4-tuples of given hyperbolicity. So we cannot exceed `2^64-1`. This value should be sufficient for most users.
INPUT:
- ``N`` -- number of vertices of the graph (and side of the matrix)
- ``distances`` -- matrix of distances in the graph
- ``sampling_size`` -- number of 4-tuples considered. Default value is 1000.
OUTPUT:
- ``hdict`` -- A dictionary such that hdict[i] is the number of 4-tuples of hyperbolicity i among the considered 4-tuples. """ cdef int i, a, b, c, d cdef uint64_t j
if N < 4: raise ValueError("N must be at least 4")
# We initialize the table of hyperbolicity. We use an array of unsigned long # int instead of a dictionary since it is much faster. cdef uint64_t * hdistr = <uint64_t *>check_calloc(N+1,sizeof(uint64_t)) if hdistr == NULL: raise MemoryError
# We now compute the hyperbolicity of each quadruple for 0 <= j < sampling_size: a = c_libc_random() % N b = c_libc_random() % N c = c_libc_random() % N d = c_libc_random() % N while a == b: b = c_libc_random() % N while a == c or b == c: c = c_libc_random() % N while a == d or b == d or c == d: d = c_libc_random() % N
hdistr[ __hyp__(distances, a, b, c, d) ] += 1
# We prepare the dictionary of hyperbolicity distribution from sampling cdef dict hdict = dict( [ (ZZ(i)/2, ZZ(hdistr[i])/ZZ(sampling_size)) for 0 <= i <= N if hdistr[i] > 0 ] )
sig_free(hdistr)
return hdict
r""" Return the hyperbolicity distribution of the graph or a sampling of it.
The hyperbolicity of a graph has been defined by Gromov [Gromov87]_ as follows: Let `a, b, c, d` be vertices of the graph, let `S_1 = dist(a, b) + dist(b, c)`, `S_2 = dist(a, c) + dist(b, d)`, and `S_3 = dist(a, d) + dist(b, c)`, and let `M_1` and `M_2` be the two largest values among `S_1`, `S_2`, and `S_3`. We have `hyp(a, b, c, d) = |M_1 - M_2|`, and the hyperbolicity of the graph is the maximum over all possible 4-tuples `(a, b, c, d)` divided by 2.
The computation of the hyperbolicity of each 4-tuple, and so the hyperbolicity distribution, takes time in `O( n^4 )`.
INPUT:
- ``G`` -- a Graph.
- ``algorithm`` -- (default: 'sampling') When algorithm is 'sampling', it returns the distribution of the hyperbolicity over a sample of ``sampling_size`` 4-tuples. When algorithm is 'exact', it computes the distribution of the hyperbolicity over all 4-tuples. Be aware that the computation time can be HUGE.
- ``sampling_size`` -- (default: `10^6`) number of 4-tuples considered in the sampling. Used only when ``algorithm == 'sampling'``.
OUTPUT:
- ``hdict`` -- A dictionary such that hdict[i] is the number of 4-tuples of hyperbolicity i.
EXAMPLES:
Exact hyperbolicity distribution of the Petersen Graph::
sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution sage: G = graphs.PetersenGraph() sage: hyperbolicity_distribution(G,algorithm='exact') {0: 3/7, 1/2: 4/7}
Exact hyperbolicity distribution of a `3\times 3` grid::
sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution sage: G = graphs.GridGraph([3,3]) sage: hyperbolicity_distribution(G,algorithm='exact') {0: 11/18, 1: 8/21, 2: 1/126}
TESTS:
Giving anything else than a Graph::
sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution sage: hyperbolicity_distribution([]) Traceback (most recent call last): ... ValueError: The input parameter must be a Graph.
Giving a non connected graph::
sage: from sage.graphs.hyperbolicity import hyperbolicity_distribution sage: G = Graph([(0,1),(2,3)]) sage: hyperbolicity_distribution(G) Traceback (most recent call last): ... ValueError: The input Graph must be connected. """ # The hyperbolicity is defined on connected graphs
# The hyperbolicity distribution of some classes of graphs is known. If it # is easy and fast to test that a graph belongs to one of these classes, we # do it. return {0: sampling_size if algorithm=='sampling' else binomial(G.num_verts(),4)}
cdef int i, j cdef unsigned short ** distances cdef unsigned short * _distances_ cdef dict hdict
# We compute the all pairs shortest path and store the result in a 2D array # for faster access. sig_free(_distances_) raise MemoryError
elif algorithm == 'sampling': hdict = __hyperbolicity_sampling__(N, distances, sampling_size) else: raise ValueError("Algorithm '%s' not yet implemented. Please contribute." %(algorithm))
# We release memory
|