Distances/shortest paths between all pairs of vertices#
This module implements a few functions that deal with the computation of distances or shortest paths between all pairs of vertices.
Efficiency : Because these functions involve listing many times the (out)-neighborhoods of (di)-graphs, it is useful in terms of efficiency to build a temporary copy of the graph in a data structure that makes it easy to compute quickly. These functions also work on large volume of data, typically dense matrices of size \(n^2\), and are expected to return corresponding dictionaries of size \(n^2\), where the integers corresponding to the vertices have first been converted to the vertices’ labels. Sadly, this last translating operation turns out to be the most time-consuming, and for this reason it is also nice to have a Cython module, and version of these functions that return C arrays, in order to avoid these operations when they are not necessary.
Memory cost : The methods implemented in the current module sometimes need large amounts of memory to return their result. Storing the distances between all pairs of vertices in a graph on \(1500\) vertices as a dictionary of dictionaries takes around 200MB, while storing the same information as a C array requires 4MB.
The module’s main function#
The C function all_pairs_shortest_path_BFS
actually does all the
computations, and all the others (except for Floyd_Warshall
) are just
wrapping it. This function begins with copying the graph in a data structure
that makes it fast to query the out-neighbors of a vertex, then starts one
Breadth First Search per vertex of the (di)graph.
What can this function compute ?
The matrix of predecessors.
This matrix \(P\) has size \(n^2\), and is such that vertex \(P[u,v]\) is a predecessor of \(v\) on a shortest \(uv\)-path. Hence, this matrix efficiently encodes the information of a shortest \(uv\)-path for any \(u,v\in G\) : indeed, to go from \(u\) to \(v\) you should first find a shortest \(uP[u,v]\)-path, then jump from \(P[u,v]\) to \(v\) as it is one of its outneighbors. Apply recursively and find out what the whole path is !.
The matrix of distances.
This matrix has size \(n^2\) and associates to any \(uv\) the distance from \(u\) to \(v\).
The vector of eccentricities.
This vector of size \(n\) encodes for each vertex \(v\) the distance to vertex which is furthest from \(v\) in the graph. In particular, the diameter of the graph is the maximum of these values.
What does it take as input ?
gg
a (Di)Graph.unsigned short * predecessors
– a pointer toward an array of size \(n^2\cdot\text{sizeof(unsigned short)}\). Set toNULL
if you do not want to compute the predecessors.unsigned short * distances
– a pointer toward an array of size \(n^2\cdot\text{sizeof(unsigned short)}\). The computation of the distances is necessary for the algorithm, so this value can not be set toNULL
.int * eccentricity
– a pointer toward an array of size \(n\cdot\text{sizeof(int)}\). Set toNULL
if you do not want to compute the eccentricity.
Technical details
The vertices are encoded as \(1, ..., n\) as they appear in the ordering of
G.vertices(sort=True)
, unless another ordering is specified by the user.Because this function works on matrices whose size is quadratic compared to the number of vertices when computing all distances or predecessors, it uses short variables to store the vertices’ names instead of long ones to divide by 2 the size in memory. This means that only the diameter/eccentricities can be computed on a graph of more than 65536 nodes. For information, the current version of the algorithm on a graph with \(65536=2^{16}\) nodes creates in memory \(2\) tables on \(2^{32}\) short elements (2bytes each), for a total of \(2^{33}\) bytes or \(8\) gigabytes. In order to support larger sizes, we would have to replace shorts by 32-bits int or 64-bits int, which would then require respectively 16GB or 32GB.
In the C version of these functions, infinite distances are represented with
<unsigned short> -1 = 65535
forunsigned short
variables, and byINT32_MAX
otherwise. These case happens when the input is a disconnected graph, or a non-strongly-connected digraph.A memory error is raised when data structures allocation failed. This could happen with large graphs on computers with low memory space.
Warning
The function all_pairs_shortest_path_BFS
has no reason to be called
by the user, even though he would be writing his code in Cython and look for
efficiency. This module contains wrappers for this function that feed it
with the good parameters. As the function is inlined, using those wrappers
actually saves time as it should avoid testing the parameters again and
again in the main function’s body.
AUTHOR:
Nathann Cohen (2011)
David Coudert (2014) – 2sweep, multi-sweep and iFUB for diameter computation
Functions#
- sage.graphs.distances_all_pairs.antipodal_graph(G)[source]#
Return the antipodal graph of \(G\).
The antipodal graph of a graph \(G\) has the same vertex set of \(G\) and two vertices are adjacent if their distance in \(G\) is equal to the diameter of \(G\).
This method first computes the eccentricity of all vertices and determines the diameter of the graph. Then, it for each vertex \(u\) with eccentricity the diameter, it computes BFS distances from \(u\) and add an edge in the antipodal graph for each vertex \(v\) at diamter distance from \(u\) (i.e., for each antipodal vertex).
The drawback of this method is that some BFS distances may be computed twice, one time to determine the eccentricities and another time is the vertex has eccentricity equal to the diameter. However, in practive, this is much more efficient. See the documentation of method
c_eccentricity_DHV()
.EXAMPLES:
The antipodal graph of a grid graph has only 2 edges:
sage: from sage.graphs.distances_all_pairs import antipodal_graph sage: G = graphs.Grid2dGraph(5, 5) sage: A = antipodal_graph(G) sage: A.order(), A.size() (25, 2)
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import antipodal_graph >>> G = graphs.Grid2dGraph(Integer(5), Integer(5)) >>> A = antipodal_graph(G) >>> A.order(), A.size() (25, 2)
The antipodal graph of a disjoint union of cliques is its complement:
sage: from sage.graphs.distances_all_pairs import antipodal_graph sage: G = graphs.CompleteGraph(3) * 3 sage: A = antipodal_graph(G) sage: A.is_isomorphic(G.complement()) True
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import antipodal_graph >>> G = graphs.CompleteGraph(Integer(3)) * Integer(3) >>> A = antipodal_graph(G) >>> A.is_isomorphic(G.complement()) True
The antipodal graph can also be constructed as the
sage.graphs.generic_graph.distance_graph()
for diameter distance:sage: from sage.graphs.distances_all_pairs import antipodal_graph sage: G = graphs.RandomGNP(10, .2) sage: A = antipodal_graph(G) sage: B = G.distance_graph(G.diameter()) sage: A.is_isomorphic(B) True
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import antipodal_graph >>> G = graphs.RandomGNP(Integer(10), RealNumber('.2')) >>> A = antipodal_graph(G) >>> B = G.distance_graph(G.diameter()) >>> A.is_isomorphic(B) True
- sage.graphs.distances_all_pairs.diameter(G, algorithm=None, source=None)[source]#
Return the diameter of \(G\).
This method returns Infinity if the (di)graph is not connected. It can also quickly return a lower bound on the diameter using the
2sweep
,2Dsweep
andmulti-sweep
schemes.INPUT:
algorithm
– string (default:None
); specifies the algorithm to use among:'standard'
– Computes the diameter of the input (di)graph as the largest eccentricity of its vertices. This is the classical algorithm with time complexity in \(O(nm)\).'2sweep'
– Computes a lower bound on the diameter of an unweighted undirected graph using 2 BFS, as proposed in [MLH2008]. It first selects a vertex \(v\) that is at largest distance from an initial vertex source using BFS. Then it performs a second BFS from \(v\). The largest distance from \(v\) is returned as a lower bound on the diameter of \(G\). The time complexity of this algorithm is linear in the size of \(G\).'2Dsweep'
– Computes lower bound on the diameter of an unweighted directed graph using directed version of2sweep
as proposed in [Broder2000]. If the digraph is not strongly connected, the returned value is infinity.'DHV'
– Computes diameter of unweighted undirected graph using the algorithm proposed in [Dragan2018].'multi-sweep'
– Computes a lower bound on the diameter of an unweighted undirected graph using several iterations of the2sweep
algorithms [CGHLM2013]. Roughly, it first uses2sweep
to identify two vertices \(u\) and \(v\) that are far apart. Then it selects a vertex \(w\) that is at same distance from \(u\) and \(v\). This vertex \(w\) will serve as the new source for another iteration of the2sweep
algorithm that may improve the current lower bound on the diameter. This process is repeated as long as the lower bound on the diameter is improved.'iFUB'
– The iFUB (iterative Fringe Upper Bound) algorithm, proposed in [CGILM2010], computes the exact value of the diameter of an unweighted undirected graph. It is based on the following observation:The diameter of the graph is equal to the maximum eccentricity of a vertex. Let \(v\) be any vertex, and let \(V\) be partitionned into \(A\cup B\) where:
\[\begin{split}d(v,a) \leq i, \forall a \in A\\ d(v,b) \geq i, \forall b \in B\end{split}\]As all vertices from \(A\) are at distance \(\leq 2i\) from each other, a vertex \(a\in A\) with eccentricity \(ecc(a)>2i\) is at distance \(ecc(a)\) from some vertex \(b\in B\).
Consequently, if we have already computed the maximum eccentricity \(m\) of all vertices in \(B\) and if \(m>2i\), then we do not need to compute the eccentricity of the vertices in \(A\).
Starting from a vertex \(v\) obtained through a multi-sweep computation (which refines the 4sweep algorithm used in [CGHLM2013]), we compute the diameter by computing the eccentricity of all vertices sorted decreasingly according to their distance to \(v\), and stop as allowed by the remark above. The worst case time complexity of the iFUB algorithm is \(O(nm)\), but it can be very fast in practice.
'DiFUB'
– The directed version of iFUB (iterative Fringe Upper Bound) algorithm. See the code’s documentation and [CGLM2012] for more details. If the digraph is not strongly connected, the returned value is infinity.
source
– (default:None
) vertex from which to start the first BFS. Ifsource==None
, an arbitrary vertex of the graph is chosen. Raise an error if the initial vertex is not in \(G\). This parameter is not used whenalgorithm=='standard'
.
Note
As the graph is first converted to a short_digraph, all complexity have an extra \(O(m+n)\) for
SparseGraph
and \(O(n^2)\) forDenseGraph
.EXAMPLES:
sage: from sage.graphs.distances_all_pairs import diameter sage: G = graphs.PetersenGraph() sage: diameter(G, algorithm='iFUB') 2 sage: G = Graph({0: [], 1: [], 2: [1]}) sage: diameter(G, algorithm='iFUB') +Infinity sage: G = digraphs.Circuit(6) sage: diameter(G, algorithm='2Dsweep') 5 sage: G = graphs.PathGraph(7).to_directed() sage: diameter(G, algorithm='DiFUB') 6
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import diameter >>> G = graphs.PetersenGraph() >>> diameter(G, algorithm='iFUB') 2 >>> G = Graph({Integer(0): [], Integer(1): [], Integer(2): [Integer(1)]}) >>> diameter(G, algorithm='iFUB') +Infinity >>> G = digraphs.Circuit(Integer(6)) >>> diameter(G, algorithm='2Dsweep') 5 >>> G = graphs.PathGraph(Integer(7)).to_directed() >>> diameter(G, algorithm='DiFUB') 6
Although max( ) is usually defined as -Infinity, since the diameter will never be negative, we define it to be zero:
sage: G = graphs.EmptyGraph() sage: diameter(G, algorithm='iFUB') 0
>>> from sage.all import * >>> G = graphs.EmptyGraph() >>> diameter(G, algorithm='iFUB') 0
Comparison of exact algorithms for graphs:
sage: # needs networkx sage: G = graphs.RandomBarabasiAlbert(100, 2) sage: d1 = diameter(G, algorithm='standard') sage: d2 = diameter(G, algorithm='iFUB') sage: d3 = diameter(G, algorithm='iFUB', source=G.random_vertex()) sage: d4 = diameter(G, algorithm='DHV') sage: if d1 != d2 or d1 != d3 or d1 != d4: print("Something goes wrong!")
>>> from sage.all import * >>> # needs networkx >>> G = graphs.RandomBarabasiAlbert(Integer(100), Integer(2)) >>> d1 = diameter(G, algorithm='standard') >>> d2 = diameter(G, algorithm='iFUB') >>> d3 = diameter(G, algorithm='iFUB', source=G.random_vertex()) >>> d4 = diameter(G, algorithm='DHV') >>> if d1 != d2 or d1 != d3 or d1 != d4: print("Something goes wrong!")
Comparison of lower bound algorithms:
sage: lb2 = diameter(G, algorithm='2sweep') # needs networkx sage: lbm = diameter(G, algorithm='multi-sweep') # needs networkx sage: if not (lb2 <= lbm and lbm <= d3): print("Something goes wrong!") # needs networkx
>>> from sage.all import * >>> lb2 = diameter(G, algorithm='2sweep') # needs networkx >>> lbm = diameter(G, algorithm='multi-sweep') # needs networkx >>> if not (lb2 <= lbm and lbm <= d3): print("Something goes wrong!") # needs networkx
Comparison of exact algorithms for digraphs:
sage: # needs networkx sage: D = DiGraph(graphs.RandomBarabasiAlbert(50, 2)) sage: d1 = diameter(D, algorithm='standard') sage: d2 = diameter(D, algorithm='DiFUB') sage: d3 = diameter(D, algorithm='DiFUB', source=D.random_vertex()) sage: d1 == d2 and d1 == d3 True
>>> from sage.all import * >>> # needs networkx >>> D = DiGraph(graphs.RandomBarabasiAlbert(Integer(50), Integer(2))) >>> d1 = diameter(D, algorithm='standard') >>> d2 = diameter(D, algorithm='DiFUB') >>> d3 = diameter(D, algorithm='DiFUB', source=D.random_vertex()) >>> d1 == d2 and d1 == d3 True
- sage.graphs.distances_all_pairs.distances_all_pairs(G)[source]#
Return the matrix of distances in G.
This function returns a double dictionary
D
of vertices, in which the distance between verticesu
andv
isD[u][v]
.EXAMPLES:
sage: from sage.graphs.distances_all_pairs import distances_all_pairs sage: g = graphs.PetersenGraph() sage: distances_all_pairs(g) {0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9: 2}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0, 5: 2, 6: 2, 7: 2, 8: 2, 9: 1}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 0, 6: 2, 7: 1, 8: 1, 9: 2}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4: 2, 5: 2, 6: 0, 7: 2, 8: 1, 9: 1}, 7: {0: 2, 1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9: 1}, 8: {0: 2, 1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2}, 9: {0: 2, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0}}
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import distances_all_pairs >>> g = graphs.PetersenGraph() >>> distances_all_pairs(g) {0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9: 2}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0, 5: 2, 6: 2, 7: 2, 8: 2, 9: 1}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 0, 6: 2, 7: 1, 8: 1, 9: 2}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4: 2, 5: 2, 6: 0, 7: 2, 8: 1, 9: 1}, 7: {0: 2, 1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9: 1}, 8: {0: 2, 1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2}, 9: {0: 2, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0}}
- sage.graphs.distances_all_pairs.distances_and_predecessors_all_pairs(G)[source]#
Return the matrix of distances in G and the matrix of predecessors.
Distances : the matrix \(M\) returned is of length \(n^2\), and the distance between vertices \(u\) and \(v\) is \(M[u,v]\). The integer corresponding to a vertex is its index in the list
G.vertices(sort=True)
.Predecessors : the matrix \(P\) returned has size \(n^2\), and is such that vertex \(P[u,v]\) is a predecessor of \(v\) on a shortest \(uv\)-path. Hence, this matrix efficiently encodes the information of a shortest \(uv\)-path for any \(u,v\in G\) : indeed, to go from \(u\) to \(v\) you should first find a shortest \(uP[u,v]\)-path, then jump from \(P[u,v]\) to \(v\) as it is one of its outneighbors.
EXAMPLES:
sage: from sage.graphs.distances_all_pairs import distances_and_predecessors_all_pairs sage: g = graphs.PetersenGraph() sage: distances_and_predecessors_all_pairs(g) ({0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9: 2}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0, 5: 2, 6: 2, 7: 2, 8: 2, 9: 1}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 0, 6: 2, 7: 1, 8: 1, 9: 2}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4: 2, 5: 2, 6: 0, 7: 2, 8: 1, 9: 1}, 7: {0: 2, 1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9: 1}, 8: {0: 2, 1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2}, 9: {0: 2, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0}}, {0: {0: None, 1: 0, 2: 1, 3: 4, 4: 0, 5: 0, 6: 1, 7: 5, 8: 5, 9: 4}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0, 5: 0, 6: 1, 7: 2, 8: 6, 9: 6}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3, 5: 7, 6: 1, 7: 2, 8: 3, 9: 7}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3, 5: 8, 6: 8, 7: 2, 8: 3, 9: 4}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None, 5: 0, 6: 9, 7: 9, 8: 3, 9: 4}, 5: {0: 5, 1: 0, 2: 7, 3: 8, 4: 0, 5: None, 6: 8, 7: 5, 8: 5, 9: 7}, 6: {0: 1, 1: 6, 2: 1, 3: 8, 4: 9, 5: 8, 6: None, 7: 9, 8: 6, 9: 6}, 7: {0: 5, 1: 2, 2: 7, 3: 2, 4: 9, 5: 7, 6: 9, 7: None, 8: 5, 9: 7}, 8: {0: 5, 1: 6, 2: 3, 3: 8, 4: 3, 5: 8, 6: 8, 7: 5, 8: None, 9: 6}, 9: {0: 4, 1: 6, 2: 7, 3: 4, 4: 9, 5: 7, 6: 9, 7: 9, 8: 6, 9: None}})
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import distances_and_predecessors_all_pairs >>> g = graphs.PetersenGraph() >>> distances_and_predecessors_all_pairs(g) ({0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9: 2}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0, 5: 2, 6: 2, 7: 2, 8: 2, 9: 1}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 0, 6: 2, 7: 1, 8: 1, 9: 2}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4: 2, 5: 2, 6: 0, 7: 2, 8: 1, 9: 1}, 7: {0: 2, 1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9: 1}, 8: {0: 2, 1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2}, 9: {0: 2, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0}}, {0: {0: None, 1: 0, 2: 1, 3: 4, 4: 0, 5: 0, 6: 1, 7: 5, 8: 5, 9: 4}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0, 5: 0, 6: 1, 7: 2, 8: 6, 9: 6}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3, 5: 7, 6: 1, 7: 2, 8: 3, 9: 7}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3, 5: 8, 6: 8, 7: 2, 8: 3, 9: 4}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None, 5: 0, 6: 9, 7: 9, 8: 3, 9: 4}, 5: {0: 5, 1: 0, 2: 7, 3: 8, 4: 0, 5: None, 6: 8, 7: 5, 8: 5, 9: 7}, 6: {0: 1, 1: 6, 2: 1, 3: 8, 4: 9, 5: 8, 6: None, 7: 9, 8: 6, 9: 6}, 7: {0: 5, 1: 2, 2: 7, 3: 2, 4: 9, 5: 7, 6: 9, 7: None, 8: 5, 9: 7}, 8: {0: 5, 1: 6, 2: 3, 3: 8, 4: 3, 5: 8, 6: 8, 7: 5, 8: None, 9: 6}, 9: {0: 4, 1: 6, 2: 7, 3: 4, 4: 9, 5: 7, 6: 9, 7: 9, 8: 6, 9: None}})
- sage.graphs.distances_all_pairs.distances_distribution(G)[source]#
Return the distances distribution of the (di)graph in a dictionary.
This method ignores all edge labels, so that the distance considered is the topological distance.
OUTPUT:
A dictionary
d
such that the number of pairs of vertices at distancek
(if any) is equal to \(d[k] \cdot |V(G)| \cdot (|V(G)|-1)\).Note
We consider that two vertices that do not belong to the same connected component are at infinite distance, and we do not take the trivial pairs of vertices \((v, v)\) at distance \(0\) into account. Empty (di)graphs and (di)graphs of order 1 have no paths and so we return the empty dictionary
{}
.EXAMPLES:
An empty Graph:
sage: g = Graph() sage: g.distances_distribution() {}
>>> from sage.all import * >>> g = Graph() >>> g.distances_distribution() {}
A Graph of order 1:
sage: g = Graph() sage: g.add_vertex(1) sage: g.distances_distribution() {}
>>> from sage.all import * >>> g = Graph() >>> g.add_vertex(Integer(1)) >>> g.distances_distribution() {}
A Graph of order 2 without edge:
sage: g = Graph() sage: g.add_vertices([1,2]) sage: g.distances_distribution() {+Infinity: 1}
>>> from sage.all import * >>> g = Graph() >>> g.add_vertices([Integer(1),Integer(2)]) >>> g.distances_distribution() {+Infinity: 1}
The Petersen Graph:
sage: g = graphs.PetersenGraph() sage: g.distances_distribution() {1: 1/3, 2: 2/3}
>>> from sage.all import * >>> g = graphs.PetersenGraph() >>> g.distances_distribution() {1: 1/3, 2: 2/3}
A graph with multiple disconnected components:
sage: g = graphs.PetersenGraph() sage: g.add_edge('good','wine') sage: g.distances_distribution() {1: 8/33, 2: 5/11, +Infinity: 10/33}
>>> from sage.all import * >>> g = graphs.PetersenGraph() >>> g.add_edge('good','wine') >>> g.distances_distribution() {1: 8/33, 2: 5/11, +Infinity: 10/33}
The de Bruijn digraph dB(2,3):
sage: D = digraphs.DeBruijn(2,3) # needs sage.combinat sage: D.distances_distribution() # needs sage.combinat {1: 1/4, 2: 11/28, 3: 5/14}
>>> from sage.all import * >>> D = digraphs.DeBruijn(Integer(2),Integer(3)) # needs sage.combinat >>> D.distances_distribution() # needs sage.combinat {1: 1/4, 2: 11/28, 3: 5/14}
- sage.graphs.distances_all_pairs.eccentricity(G, algorithm='standard', vertex_list=None)[source]#
Return the vector of eccentricities in G.
The array returned is of length \(n\), and its \(i\)-th component is the eccentricity of the ith vertex in
G.vertices(sort=True)
.INPUT:
G
– a Graph or a DiGraph.algorithm
– string (default:'standard'
); name of the method used to compute the eccentricity of the vertices.'standard'
– Computes eccentricity by performing a BFS from each vertex.'bounds'
– Computes eccentricity using the fast algorithm proposed in [TK2013] for undirected graphs.'DHV'
– Computes all eccentricities of undirected graph using the algorithm proposed in [Dragan2018].
vertex_list
– list (default:None
); a list of \(n\) vertices specifying a mapping from \((0, \ldots, n-1)\) to vertex labels in \(G\). When set,ecc[i]
is the eccentricity of vertexvertex_list[i]
. Whenvertex_list
isNone
,ecc[i]
is the eccentricity of vertexG.vertices(sort=True)[i]
.
EXAMPLES:
sage: from sage.graphs.distances_all_pairs import eccentricity sage: g = graphs.PetersenGraph() sage: eccentricity(g) [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] sage: g.add_edge(0, g.add_vertex()) sage: V = list(g) sage: eccentricity(g, vertex_list=V) [2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3] sage: eccentricity(g, vertex_list=V[::-1]) [3, 3, 3, 3, 3, 2, 2, 3, 3, 2, 2]
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import eccentricity >>> g = graphs.PetersenGraph() >>> eccentricity(g) [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] >>> g.add_edge(Integer(0), g.add_vertex()) >>> V = list(g) >>> eccentricity(g, vertex_list=V) [2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3] >>> eccentricity(g, vertex_list=V[::-Integer(1)]) [3, 3, 3, 3, 3, 2, 2, 3, 3, 2, 2]
- sage.graphs.distances_all_pairs.floyd_warshall(gg, paths=True, distances=False)[source]#
Compute the shortest path/distances between all pairs of vertices.
For more information on the Floyd-Warshall algorithm, see the Wikipedia article Floyd-Warshall_algorithm.
INPUT:
gg
– the graph on which to work.paths
– boolean (default:True
); whether to return the dictionary of shortest pathsdistances
– boolean (default:False
); whether to return the dictionary of distances
OUTPUT:
Depending on the input, this function return the dictionary of paths, the dictionary of distances, or a pair of dictionaries
(distances, paths)
wheredistance[u][v]
denotes the distance of a shortest path from \(u\) to \(v\) andpaths[u][v]
denotes an inneighbor \(w\) of \(v\) such that \(dist(u,v) = 1 + dist(u,w)\).Warning
Because this function works on matrices whose size is quadratic compared to the number of vertices, it uses short variables instead of long ones to divide by 2 the size in memory. This means that the current implementation does not run on a graph of more than 65536 nodes (this can be easily changed if necessary, but would require much more memory. It may be worth writing two versions). For information, the current version of the algorithm on a graph with \(65536 = 2^{16}\) nodes creates in memory \(2\) tables on \(2^{32}\) short elements (2bytes each), for a total of \(2^{34}\) bytes or \(16\) gigabytes. Let us also remember that if the memory size is quadratic, the algorithm runs in cubic time.
Note
When
paths = False
the algorithm saves roughly half of the memory as it does not have to maintain the matrix of predecessors. However, settingdistances=False
produces no such effect as the algorithm can not run without computing them. They will not be returned, but they will be stored while the method is running.EXAMPLES:
Shortest paths in a small grid
sage: g = graphs.Grid2dGraph(2,2) sage: from sage.graphs.distances_all_pairs import floyd_warshall sage: print(floyd_warshall(g)) {(0, 0): {(0, 0): None, (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (0, 1)}, (0, 1): {(0, 1): None, (0, 0): (0, 1), (1, 0): (0, 0), (1, 1): (0, 1)}, (1, 0): {(1, 0): None, (0, 0): (1, 0), (0, 1): (0, 0), (1, 1): (1, 0)}, (1, 1): {(1, 1): None, (0, 0): (0, 1), (0, 1): (1, 1), (1, 0): (1, 1)}}
>>> from sage.all import * >>> g = graphs.Grid2dGraph(Integer(2),Integer(2)) >>> from sage.graphs.distances_all_pairs import floyd_warshall >>> print(floyd_warshall(g)) {(0, 0): {(0, 0): None, (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (0, 1)}, (0, 1): {(0, 1): None, (0, 0): (0, 1), (1, 0): (0, 0), (1, 1): (0, 1)}, (1, 0): {(1, 0): None, (0, 0): (1, 0), (0, 1): (0, 0), (1, 1): (1, 0)}, (1, 1): {(1, 1): None, (0, 0): (0, 1), (0, 1): (1, 1), (1, 0): (1, 1)}}
Checking the distances are correct
sage: g = graphs.Grid2dGraph(5,5) sage: dist,path = floyd_warshall(g, distances=True) sage: all(dist[u][v] == g.distance(u, v) for u in g for v in g) True
>>> from sage.all import * >>> g = graphs.Grid2dGraph(Integer(5),Integer(5)) >>> dist,path = floyd_warshall(g, distances=True) >>> all(dist[u][v] == g.distance(u, v) for u in g for v in g) True
Checking a random path is valid
sage: u,v = g.random_vertex(), g.random_vertex() sage: p = [v] sage: while p[0] is not None: ....: p.insert(0,path[u][p[0]]) sage: len(p) == dist[u][v] + 2 True
>>> from sage.all import * >>> u,v = g.random_vertex(), g.random_vertex() >>> p = [v] >>> while p[Integer(0)] is not None: ... p.insert(Integer(0),path[u][p[Integer(0)]]) >>> len(p) == dist[u][v] + Integer(2) True
Distances for all pairs of vertices in a diamond:
sage: g = graphs.DiamondGraph() sage: floyd_warshall(g, paths=False, distances=True) {0: {0: 0, 1: 1, 2: 1, 3: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 1}, 2: {0: 1, 1: 1, 2: 0, 3: 1}, 3: {0: 2, 1: 1, 2: 1, 3: 0}}
>>> from sage.all import * >>> g = graphs.DiamondGraph() >>> floyd_warshall(g, paths=False, distances=True) {0: {0: 0, 1: 1, 2: 1, 3: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 1}, 2: {0: 1, 1: 1, 2: 0, 3: 1}, 3: {0: 2, 1: 1, 2: 1, 3: 0}}
- sage.graphs.distances_all_pairs.is_distance_regular(G, parameters=False)[source]#
Test if the graph is distance-regular
A graph \(G\) is distance-regular if for any integers \(j,k\) the value of \(|\{x:d_G(x,u)=j,x\in V(G)\} \cap \{y:d_G(y,v)=j,y\in V(G)\}|\) is constant for any two vertices \(u,v\in V(G)\) at distance \(i\) from each other. In particular \(G\) is regular, of degree \(b_0\) (see below), as one can take \(u=v\).
Equivalently a graph is distance-regular if there exist integers \(b_i,c_i\) such that for any two vertices \(u,v\) at distance \(i\) we have
\(b_i = |\{x:d_G(x,u)=i+1,x\in V(G)\}\cap N_G(v)\}|, \ 0\leq i\leq d-1\)
\(c_i = |\{x:d_G(x,u)=i-1,x\in V(G)\}\cap N_G(v)\}|, \ 1\leq i\leq d,\)
where \(d\) is the diameter of the graph. For more information on distance-regular graphs, see the Wikipedia article Distance-regular_graph.
INPUT:
parameters
– boolean (default:False
); if set toTrue
, the function returns the pair(b, c)
of lists of integers instead of a boolean answer (see the definition above)
See also
EXAMPLES:
sage: g = graphs.PetersenGraph() sage: g.is_distance_regular() True sage: g.is_distance_regular(parameters = True) ([3, 2, None], [None, 1, 1])
>>> from sage.all import * >>> g = graphs.PetersenGraph() >>> g.is_distance_regular() True >>> g.is_distance_regular(parameters = True) ([3, 2, None], [None, 1, 1])
Cube graphs, which are not strongly regular, are a bit more interesting:
sage: graphs.CubeGraph(4).is_distance_regular() True sage: graphs.OddGraph(5).is_distance_regular() True
>>> from sage.all import * >>> graphs.CubeGraph(Integer(4)).is_distance_regular() True >>> graphs.OddGraph(Integer(5)).is_distance_regular() True
Disconnected graph:
sage: (2*graphs.CubeGraph(4)).is_distance_regular() True
>>> from sage.all import * >>> (Integer(2)*graphs.CubeGraph(Integer(4))).is_distance_regular() True
- sage.graphs.distances_all_pairs.radius_DHV(G)[source]#
Return the radius of unweighted graph \(G\).
This method computes the radius of unweighted undirected graph using the algorithm given in [Dragan2018].
This method returns Infinity if graph is not connected.
EXAMPLES:
sage: from sage.graphs.distances_all_pairs import radius_DHV sage: G = graphs.PetersenGraph() sage: radius_DHV(G) 2 sage: G = graphs.RandomGNP(20,0.3) sage: from sage.graphs.distances_all_pairs import eccentricity sage: radius_DHV(G) == min(eccentricity(G, algorithm='bounds')) True
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import radius_DHV >>> G = graphs.PetersenGraph() >>> radius_DHV(G) 2 >>> G = graphs.RandomGNP(Integer(20),RealNumber('0.3')) >>> from sage.graphs.distances_all_pairs import eccentricity >>> radius_DHV(G) == min(eccentricity(G, algorithm='bounds')) True
- sage.graphs.distances_all_pairs.shortest_path_all_pairs(G)[source]#
Return the matrix of predecessors in G.
The matrix \(P\) returned has size \(n^2\), and is such that vertex \(P[u,v]\) is a predecessor of \(v\) on a shortest \(uv\)-path. Hence, this matrix efficiently encodes the information of a shortest \(uv\)-path for any \(u,v\in G\) : indeed, to go from \(u\) to \(v\) you should first find a shortest \(uP[u,v]\)-path, then jump from \(P[u,v]\) to \(v\) as it is one of its outneighbors.
EXAMPLES:
sage: from sage.graphs.distances_all_pairs import shortest_path_all_pairs sage: g = graphs.PetersenGraph() sage: shortest_path_all_pairs(g) {0: {0: None, 1: 0, 2: 1, 3: 4, 4: 0, 5: 0, 6: 1, 7: 5, 8: 5, 9: 4}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0, 5: 0, 6: 1, 7: 2, 8: 6, 9: 6}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3, 5: 7, 6: 1, 7: 2, 8: 3, 9: 7}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3, 5: 8, 6: 8, 7: 2, 8: 3, 9: 4}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None, 5: 0, 6: 9, 7: 9, 8: 3, 9: 4}, 5: {0: 5, 1: 0, 2: 7, 3: 8, 4: 0, 5: None, 6: 8, 7: 5, 8: 5, 9: 7}, 6: {0: 1, 1: 6, 2: 1, 3: 8, 4: 9, 5: 8, 6: None, 7: 9, 8: 6, 9: 6}, 7: {0: 5, 1: 2, 2: 7, 3: 2, 4: 9, 5: 7, 6: 9, 7: None, 8: 5, 9: 7}, 8: {0: 5, 1: 6, 2: 3, 3: 8, 4: 3, 5: 8, 6: 8, 7: 5, 8: None, 9: 6}, 9: {0: 4, 1: 6, 2: 7, 3: 4, 4: 9, 5: 7, 6: 9, 7: 9, 8: 6, 9: None}}
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import shortest_path_all_pairs >>> g = graphs.PetersenGraph() >>> shortest_path_all_pairs(g) {0: {0: None, 1: 0, 2: 1, 3: 4, 4: 0, 5: 0, 6: 1, 7: 5, 8: 5, 9: 4}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0, 5: 0, 6: 1, 7: 2, 8: 6, 9: 6}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3, 5: 7, 6: 1, 7: 2, 8: 3, 9: 7}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3, 5: 8, 6: 8, 7: 2, 8: 3, 9: 4}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None, 5: 0, 6: 9, 7: 9, 8: 3, 9: 4}, 5: {0: 5, 1: 0, 2: 7, 3: 8, 4: 0, 5: None, 6: 8, 7: 5, 8: 5, 9: 7}, 6: {0: 1, 1: 6, 2: 1, 3: 8, 4: 9, 5: 8, 6: None, 7: 9, 8: 6, 9: 6}, 7: {0: 5, 1: 2, 2: 7, 3: 2, 4: 9, 5: 7, 6: 9, 7: None, 8: 5, 9: 7}, 8: {0: 5, 1: 6, 2: 3, 3: 8, 4: 3, 5: 8, 6: 8, 7: 5, 8: None, 9: 6}, 9: {0: 4, 1: 6, 2: 7, 3: 4, 4: 9, 5: 7, 6: 9, 7: 9, 8: 6, 9: None}}
- sage.graphs.distances_all_pairs.szeged_index(G, algorithm=None)[source]#
Return the Szeged index of the graph \(G\).
Let \(G = (V, E)\) be a connected graph, and for any \(uv\in E\), let \(N_u(uv) = \{w\in V:d(u,w)<d(v,w)\}\) and \(n_u(uv)=|N_u(uv)|\). The Szeged index of \(G\) is then defined as [KRG1996]
\[`\sum_{uv \in E(G)}n_u(uv)\times n_v(uv)`\]See the Wikipedia article Szeged_index for more details.
INPUT:
G
– a Sage graphalgorithm
– string (default:None
); algorithm to use among:"low"
– algorithm with time complexity in \(O(nm)\) and space complexity in \(O(m)\). This implementation is currently valid only for simple (without loops or multiple edges) connected graphs."high"
– algorithm with time complexity in \(O(nm)\) and space complexity in \(O(n^2)\). It cannot be used on graphs with more than \(65536 = 2^{16}\) vertices.
By default (
None
), the"low"
algorithm is used for graphs and the"high"
algorithm for digraphs.
Note
As the graph is converted to a short_digraph, the complexity for the case
algorithm == "high"
has an extra \(O(m+n)\) forSparseGraph
and \(O(n^2)\) forDenseGraph
. Ifalgorithm == "low"
, the extra complexity is \(O(n + m\log{m})\) forSparseGraph
and \(O(n^2\log{m})\) forDenseGraph
(becauseinit_short_digraph
is called withsort_neighbors=True
).EXAMPLES:
True for any connected graph [KRG1996]:
sage: from sage.graphs.distances_all_pairs import szeged_index sage: g = graphs.PetersenGraph() sage: g.wiener_index() <= szeged_index(g) True
>>> from sage.all import * >>> from sage.graphs.distances_all_pairs import szeged_index >>> g = graphs.PetersenGraph() >>> g.wiener_index() <= szeged_index(g) True
True for all trees [KRG1996]:
sage: g = Graph() sage: g.add_edges(graphs.CubeGraph(5).min_spanning_tree()) sage: g.wiener_index() == szeged_index(g) True
>>> from sage.all import * >>> g = Graph() >>> g.add_edges(graphs.CubeGraph(Integer(5)).min_spanning_tree()) >>> g.wiener_index() == szeged_index(g) True
Check that both algorithms return same value:
sage: # long time, needs networkx sage: G = graphs.RandomBarabasiAlbert(100, 2) sage: a = szeged_index(G, algorithm='low') sage: b = szeged_index(G, algorithm='high') sage: a == b True
>>> from sage.all import * >>> # long time, needs networkx >>> G = graphs.RandomBarabasiAlbert(Integer(100), Integer(2)) >>> a = szeged_index(G, algorithm='low') >>> b = szeged_index(G, algorithm='high') >>> a == b True
The Szeged index of a directed circuit of order \(n\) is \((n-1)^2\):
sage: [digraphs.Circuit(n).szeged_index() for n in range(1, 8)] [0, 1, 4, 9, 16, 25, 36]
>>> from sage.all import * >>> [digraphs.Circuit(n).szeged_index() for n in range(Integer(1), Integer(8))] [0, 1, 4, 9, 16, 25, 36]
- sage.graphs.distances_all_pairs.wiener_index(G)[source]#
Return the Wiener index of the graph.
The Wiener index of an undirected graph \(G\) is defined as \(W(G) = \frac{1}{2} \sum_{u,v\in G} d(u,v)\) where \(d(u,v)\) denotes the distance between vertices \(u\) and \(v\) (see [KRG1996]).
The Wiener index of a directed graph \(G\) is defined as the sum of the distances between each pairs of vertices, \(W(G) = \sum_{u,v\in G} d(u,v)\).
EXAMPLES:
From [GYLL1993], cited in [KRG1996]:
sage: g=graphs.PathGraph(10) sage: w=lambda x: (x*(x*x -1)/6) sage: g.wiener_index()==w(10) True
>>> from sage.all import * >>> g=graphs.PathGraph(Integer(10)) >>> w=lambda x: (x*(x*x -Integer(1))/Integer(6)) >>> g.wiener_index()==w(Integer(10)) True
Wiener index of complete (di)graphs:
sage: n = 5 sage: g = graphs.CompleteGraph(n) sage: g.wiener_index() == (n * (n - 1)) / 2 True sage: g = digraphs.Complete(n) sage: g.wiener_index() == n * (n - 1) True
>>> from sage.all import * >>> n = Integer(5) >>> g = graphs.CompleteGraph(n) >>> g.wiener_index() == (n * (n - Integer(1))) / Integer(2) True >>> g = digraphs.Complete(n) >>> g.wiener_index() == n * (n - Integer(1)) True
Wiener index of a graph of order 1:
sage: Graph(1).wiener_index() 0
>>> from sage.all import * >>> Graph(Integer(1)).wiener_index() 0
The Wiener index is not defined on the empty graph:
sage: Graph().wiener_index() Traceback (most recent call last): ... ValueError: Wiener index is not defined for the empty graph
>>> from sage.all import * >>> Graph().wiener_index() Traceback (most recent call last): ... ValueError: Wiener index is not defined for the empty graph