Revision history [back]

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']