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 , and are expected to return corresponding dictionaries of
size
, 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 vertices as a dictionary of dictionaries
takes around 200MB, while storing the same information as a C array requires
4MB.
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
has size
, and is such that vertex
is a predecessor of
on a shortest
-path. Hence, this matrix efficiently encodes the information of a shortest
-path for any
: indeed, to go from
to
you should first find a shortest
-path, then jump from
to
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
and associates to any
the distance from
to
.
The vector of eccentricities.
This vector of size
encodes for each vertex
the distance to vertex which is furthest from
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
. Set to NULL if you do not want to compute the predecessors.
- unsigned short * distances – a pointer toward an array of size
. The computation of the distances is necessary for the algorithm, so this value can not be set to NULL.
- unsigned short * eccentricity – a pointer toward an array of size
. Set to NULL if you do not want to compute the eccentricity.
Technical details
- The vertices are encoded as
as they appear in the ordering of G.vertices().
- Because this function works on matrices whose size is quadratic compared to the number of vertices, it uses short variables to store the vertices’ names 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
nodes creates in memory
tables on
short elements (2bytes each), for a total of
bytes or
gigabytes.
- In the C version of these functions, a value of <unsigned short> -1 = 65535 for a distance or a predecessor means respectively +Infinity and None. 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:
REFERENCE:
[KRG96b] | (1, 2) S. Klavzar, A. Rajapakse, and I. Gutman. The Szeged and the Wiener index of graphs. Applied Mathematics Letters, 9(5):45–49, 1996. |
[GYLL93c] | I. Gutman, Y.-N. Yeh, S.-L. Lee, and Y.-L. Luo. Some recent results in the theory of the Wiener number. Indian Journal of Chemistry, 32A:651–661, 1993. |
Returns the diameter of .
EXAMPLE:
sage: from sage.graphs.distances_all_pairs import diameter
sage: g = graphs.PetersenGraph()
sage: diameter(g)
2
Returns the matrix of distances in G.
This function returns a double dictionary D of vertices, in which the distance between vertices u and v is D[u][v].
EXAMPLE:
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}}
Returns the matrix of distances in G and the matrix of predecessors.
Distances : the matrix returned is of length
, and the distance
between vertices
and
is
. The integer corresponding to a
vertex is its index in the list G.vertices().
Predecessors : the matrix returned has size
, and is such that
vertex
is a predecessor of
on a shortest
-path. Hence, this
matrix efficiently encodes the information of a shortest
-path for any
: indeed, to go from
to
you should first find a shortest
-path, then jump from
to
as it is one of its
outneighbors.
The integer corresponding to a vertex is its index in the list G.vertices().
EXAMPLE:
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}})
Returns 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 distance k (if any) is equal to.
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 at distance
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()
{}
A Graph of order 1:
sage: g = Graph()
sage: g.add_vertex(1)
sage: 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}
The Petersen Graph:
sage: g = graphs.PetersenGraph()
sage: 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}
The de Bruijn digraph dB(2,3):
sage: D = digraphs.DeBruijn(2,3)
sage: D.distances_distribution()
{1: 1/4, 2: 11/28, 3: 5/14}
Returns the vector of eccentricities in G.
The array returned is of length n, and its ith component is the eccentricity of the ith vertex in G.vertices().
EXAMPLE:
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]
Computes the shortest path/distances between all pairs of vertices.
For more information on the Floyd-Warshall algorithm, see the Wikipedia article on Floyd-Warshall.
INPUT:
- gg – the graph on which to work.
- paths (boolean) – whether to return the dictionary of shortest paths. Set to True by default.
- distances (boolean) – whether to return the dictionary of distances. Set to False by default.
OUTPUT:
Depending on the input, this function return the dictionary of paths, the dictionary of distances, or a pair of dictionaries (distances, paths) where distance[u][v] denotes the distance of a shortest path fromto
and paths[u][v] denotes an inneighbor
of
such that
.
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 nodes
creates in memory
tables on
short elements (2bytes each),
for a total of
bytes or
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, setting distances=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, 1): {(0, 1): None, (1, 0): (0, 0), (0, 0): (0, 1), (1, 1): (0, 1)},
(1, 0): {(0, 1): (0, 0), (1, 0): None, (0, 0): (1, 0), (1, 1): (1, 0)},
(0, 0): {(0, 1): (0, 0), (1, 0): (0, 0), (0, 0): None, (1, 1): (0, 1)},
(1, 1): {(0, 1): (1, 1), (1, 0): (1, 1), (0, 0): (0, 1), (1, 1): None}}
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
Checking a random path is valid
sage: u,v = g.random_vertex(), g.random_vertex()
sage: p = [v]
sage: while p[0] != None:
... p.insert(0,path[u][p[0]])
sage: len(p) == dist[u][v] + 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}}
TESTS:
Too large graphs:
sage: from sage.graphs.distances_all_pairs import floyd_warshall
sage: floyd_warshall(Graph(65536))
Traceback (most recent call last):
...
ValueError: The graph backend contains more than 65535 nodes
Returns the matrix of predecessors in G.
The matrix returned has size
, and is such that vertex
is
a predecessor of
on a shortest
-path. Hence, this matrix efficiently
encodes the information of a shortest
-path for any
: indeed,
to go from
to
you should first find a shortest
-path, then
jump from
to
as it is one of its outneighbors.
The integer corresponding to a vertex is its index in the list G.vertices().
EXAMPLE:
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}}
Returns the Wiener index of the graph.
The Wiener index of a graph can be defined in two equivalent
ways [KRG96b] :
EXAMPLE:
From [GYLL93c], cited in [KRG96b]:
sage: g=graphs.PathGraph(10)
sage: w=lambda x: (x*(x*x -1)/6)
sage: g.wiener_index()==w(10)
True