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""" Bandwidth of undirected graphs
Definition ----------
The bandwidth `bw(M)` of a matrix `M` is the smallest integer `k` such that all non-zero entries of `M` are at distance `k` from the diagonal. The bandwidth `bw(G)` of an undirected graph `G` is the minimum bandwidth of the adjacency matrix of `G`, over all possible relabellings of its vertices.
**Path spanner:** alternatively, the bandwidth measures how tightly a path represents the distance of a graph `G`. Indeed, if the vertices of `G` can be ordered as `v_1,...,v_n` in such a way that `k \times d_G(v_i,v_j) \geq |i-j|` then `bw(G)\leq k`.
**Proof:** for all `v_i \sim v_j` (i.e. `d_G(v_i,v_j)=1`), the constraint ensures that `k\geq |i-j|`, meaning that adjacent vertices are at distance at most `k` in the path ordering. That alone is sufficient to ensure that `bw(G)\leq k`.
As a byproduct, we obtain that `k \times d_G(v_i,v_j) \geq |i-j|` in general: let `v_{s_0},...,v_{s_i}` be the vertices of a shortest `(v_i,v_j)`-path. We have:
.. MATH::
k \times d_G(v_i,v_j) &= k\times d_G(v_i,v_{s_0}) + k\times d_G(v_{s_0},v_{s_1}) + ... + k\times d_G(v_{s_{i-1}},v_{s_i}) + k\times d_G(v_{s_i},v_j)\\ &\geq |v_i-v_{s_0}| + |v_{s_0}-v_{s_1}| + ... + |v_{s_{i-1}}-v_{s_i}| + |v_{s_i}-v_j|\\ &\geq |v_i-v_j|\\
Satisfiability of a partial assignment --------------------------------------
Let us suppose that the first `i` vertices `v_1,...,v_i` of `G` have already been assigned positions `p_1,...,p_i` in an ordering of `V(G)` of bandwidth `\leq k`. Where can `v_{i+1}` appear ?
Because of the previous definition, `p_{i+1}` must be at distance at most `k\times d_G(v_1,v_{i+1})` from `p_1`, and in general at distance at most `k\times d_G(v_j,v_{i+1})` from `p_j`. Each range is an interval of `\{1,...,n\}\backslash \{p_1,...,p_i\}`, and because the intersection of two intervals is again an interval we deduce that in order to satisfy all these constraints simultaneously `p_j` must belong to an interval defined from this partial assignment.
Applying this rule to all non-assigned vertices, we deduce that each of them must be assigned to a given interval of `\{1,...,n\}`. Note that this can also be extended to the already assigned vertices, by saying that `v_j` with `j<i` must be assigned within the interval `[p_j,p_j]`.
This problem is not always satisfiable, e.g. 5 vertices cannot all be assigned to the elements of `[10,13]`. This is a matching problem which, because all admissible sets are intervals, can be solved quickly.
Solving the matching problem ----------------------------
Let `n` points `v_1,...,v_n` be given, along with two functions `m,M:[n]\mapsto [n]`. Is there an ordering `p_1,...,p_n` of them such that `m(v_i) \leq p_i \leq M(v_i)` ? This is equivalent to Hall's bipartite matching theorem, and can in this specific case be solved by the following algorithm:
- Consider all vertices `v` sorted increasingly according to `M(v)`
- For each of them, assign to `v` the smallest position in `[m(v),M(v)]` which has not been assigned yet. If there is none, the assignment problem is not satisfiable.
Note that the latest operation can be performed with very few bitset operations (provided that `n<64`).
The algorithm -------------
This section contains totally subjective choices, that may be changed in the hope to get better performances.
- Try to find a satisfiable ordering by filling positions, one after the other (and not by trying to find each vertex' position)
- Fill the positions in this order: `0,n-1,1,n-2,3,n-3, ...`
.. NOTE::
There is some symmetry to break as the reverse of a satisfiable ordering is also a satisfiable ordering.
This module contains the following methods ------------------------------------------
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`bandwidth` | Compute the bandwidth of an undirected graph :meth:`~sage.graphs.base.boost_graph.bandwidth_heuristics` | Uses Boost heuristics to approximate the bandwidth of the input graph
Functions --------- """
#***************************************************************************** # Copyright (C) 2015 Nathann Cohen <nathann.cohen@gmail.com> # # 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 libc.stdint cimport uint16_t from cysignals.signals cimport sig_check
from sage.graphs.distances_all_pairs cimport all_pairs_shortest_path_BFS from sage.graphs.base.boost_graph import bandwidth_heuristics from sage.ext.memory_allocator cimport MemoryAllocator
ctypedef uint16_t index_t
ctypedef struct range_t: index_t m index_t M
def bandwidth(G, k=None): r""" Compute the bandwidth of an undirected graph.
For a definition of the bandwidth of a graph, see the documentation of the :mod:`~sage.graphs.graph_decompositions.bandwidth` module.
INPUT:
- ``G`` (a graph)
- ``k`` -- set to an integer value to test whether `bw(G)\leq k`, or to ``None`` (default) to compute `bw(G)`.
OUTPUT:
When `k` is an integer value, the function returns either ``False`` or an ordering of cost `\leq k`.
When `k` is equal to ``None``, the function returns a pair ``(bw, ordering)``.
.. SEEALSO::
:meth:`sage.graphs.generic_graph.GenericGraph.adjacency_matrix` -- return the adjacency matrix from an ordering of the vertices.
EXAMPLES::
sage: from sage.graphs.graph_decompositions.bandwidth import bandwidth sage: G = graphs.PetersenGraph() sage: bandwidth(G,3) False sage: bandwidth(G) (5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2]) sage: G.adjacency_matrix(vertices=[0, 4, 5, 8, 1, 9, 3, 7, 6, 2]) [0 1 1 0 1 0 0 0 0 0] [1 0 0 0 0 1 1 0 0 0] [1 0 0 1 0 0 0 1 0 0] [0 0 1 0 0 0 1 0 1 0] [1 0 0 0 0 0 0 0 1 1] [0 1 0 0 0 0 0 1 1 0] [0 1 0 1 0 0 0 0 0 1] [0 0 1 0 0 1 0 0 0 1] [0 0 0 1 1 1 0 0 0 0] [0 0 0 0 1 0 1 1 0 0] sage: G = graphs.ChvatalGraph() sage: bandwidth(G) (6, [0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2]) sage: G.adjacency_matrix(vertices=[0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2]) [0 0 1 1 0 1 1 0 0 0 0 0] [0 0 0 1 1 1 0 1 0 0 0 0] [1 0 0 0 1 0 0 1 1 0 0 0] [1 1 0 0 0 0 0 0 1 1 0 0] [0 1 1 0 0 0 1 0 0 1 0 0] [1 1 0 0 0 0 0 0 0 0 1 1] [1 0 0 0 1 0 0 1 0 0 0 1] [0 1 1 0 0 0 1 0 0 0 1 0] [0 0 1 1 0 0 0 0 0 0 1 1] [0 0 0 1 1 0 0 0 0 0 1 1] [0 0 0 0 0 1 0 1 1 1 0 0] [0 0 0 0 0 1 1 0 1 1 0 0]
TESTS::
sage: bandwidth(2*graphs.PetersenGraph()) (5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2, 10, 14, 15, 18, 11, 19, 13, 17, 16, 12]) sage: bandwidth(Graph()) (0, []) sage: bandwidth(Graph(1)) (0, [0]) sage: bandwidth(Graph(3)) (0, [0, 1, 2])
Directed/weighted graphs::
sage: bandwidth(digraphs.Circuit(5)) Traceback (most recent call last): ... ValueError: This method only works on undirected graphs sage: bandwidth(Graph(graphs.PetersenGraph(), weighted=True)) Traceback (most recent call last): ... ValueError: This method only works on unweighted graphs
""" # Trivial cases else: return (G.vertices())
return False
# All that this function does is allocate/free the memory for function # bandwidth_C
cdef int i,j,kk
# fill d so that d[i][j] works
# ith_range_array
# initialize left_to_order
else:
cdef bint bandwidth_C(int n, int k, unsigned short ** d, index_t * current, # choice of vertex for the current position index_t * ordering, # the actual ordering of vertices index_t * left_to_order, # begins with the assigned vertices, ends with the others index_t * index_array_tmp, # tmp space range_t ** ith_range_array, # array of ranges, for every step of the algorithm range_t * range_array_tmp):# tmp space
cdef int i,v cdef int pi # the position for which a vertex is being chosen cdef int vi # the vertex being tested at position pi cdef int radius
# At first any vertex can be anywhere
# There are (n-i) choices for vertex i, as i-1 have already been # determined. Thus, i<=current[i]<n.
# All choices for this position i have been tested. We must change our # (i-1)th choice: i = i-1 left_to_order[i], left_to_order[current[i]] = left_to_order[current[i]], left_to_order[i] continue
# The position of the ith vertex. p0=0, p1=n-1, p2=1, p3=n-2, ...
# The ith vertex
# If pi is not an admissible position for pi:
# As the choice is admissible, we update left_to_order so that # left_to_order[i] = vi.
# vi is at position pi in the final ordering.
# If we found the position of the nth vertex, we are done.
# As vertex vi has been assigned position pi, we use that information to # update the intervals of admissible positions of all other vertices. # # \forall v, k*d[v][vi] >= |p_v-p_{vi}| (see module documentation)
# Check the feasibility of a matching with the updated intervals of # admissible positions (see module doc). # # If it is possible we explore deeper, otherwise we undo the changes as # pi is not a good position for vi after all. else: # swap back
cdef bint is_matching_feasible(int n, range_t * range_array, range_t * range_array_tmp, index_t * index_array_tmp): r""" Test if the matching is feasible
INPUT:
- ``n`` (integer) -- number of points
- ``range_array`` -- associates to every point an interval in which the point must be given a position.
- ``range_array_tmp`` -- temporary spaces with the same characteristics as ``range_array``
- ``index_array_tmp`` -- temporary space to associate an integer to every point.
OUTPUT:
The function must return a boolean, and does not change the content of ``range_array``. """ # Heuristic: check if some vertex has an empty range, that's an easy 'no'. cdef int v,M,m,j #print range_array[v].m, range_array[v].M return 0
# Sort the guys according to increasing value of M in O(n). # # Step 1: count the occurrences of each M
# Step 2: sorted table
# Satisfiability. We use index_array_tmp as a bitset, and mark every # assigned position.
else: |