![]() | 1 | initial version |
For the first question, on can use the $k$'th power of the adjacency matrix of the graph. (With or without the diagonal, depending on the needs.) For instance:
sage: G = graphs.AfricaMap()
sage: V = G.vertices()
sage: V[0:2]
['Namibia', 'Libya']
sage: A = G.adjacency_matrix() + identity_matrix(len(V))
sage: a0 = vector([1 if v == 'Namibia' else 0 for v in V])
sage: a1 = vector([1 if v == 'Libya' else 0 for v in V])
sage: a0 * A^3 * a1
0
sage: a0 * A^4 * a1
0
sage: a0 * A^5 * a1
10
sage: G.distance(v0, v1)
5
So there are $10$ paths from Namibia to Libya of length five. (Alternatively, use the distance.)
To get them, take a look first at the iterator,
sage: G.all_paths_iterator?
then let us use it:
for path in G.all_paths_iterator(starting_vertices=[v0]
, ending_vertices=[v1]
, simple=True
, max_length=5):
print(path)
An this gives the ten paths:
['Namibia', 'Angola', 'Republic of the Congo', 'Cameroon', 'Chad', 'Libya']
['Namibia', 'Angola', 'Republic of the Congo', 'Central Africa', 'Chad', 'Libya']
['Namibia', 'Angola', 'Republic of the Congo', 'Central Africa', 'Sudan', 'Libya']
['Namibia', 'Angola', 'Democratic Republic of the Congo', 'South Sudan', 'Sudan', 'Libya']
['Namibia', 'Angola', 'Democratic Republic of the Congo', 'Central Africa', 'Chad', 'Libya']
['Namibia', 'Angola', 'Democratic Republic of the Congo', 'Central Africa', 'Sudan', 'Libya']
['Namibia', 'Zambia', 'Democratic Republic of the Congo', 'South Sudan', 'Sudan', 'Libya']
['Namibia', 'Zambia', 'Democratic Republic of the Congo', 'Central Africa', 'Chad', 'Libya']
['Namibia', 'Zambia', 'Democratic Republic of the Congo', 'Central Africa', 'Sudan', 'Libya']