Loading [MathJax]/jax/output/HTML-CSS/jax.js
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 0 years ago

dan_fulea gravatar image

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