# How to determine there is a k-path between two vertices

The new functionall_paths_iterator (sagemath 10.3) can enumerate paths between two vertices with a maximum length of k . However, if I just want to directly determine there is a k-path between two vertices, is there a better way?

The second question is: Is there a way to enumerate only k paths between two vertices? Currently, the enumeration order of path seems to be random.

A answer is nice for non-simple paths. But I just consider simple paths.

edit retag close merge delete

Sort by ยป oldest newest most voted

If you are fine with exponential time in $k$, then to compute the number of $k$-paths you can employ the approach outlined in Section 4 of my paper https://arxiv.org/abs/1602.01396

def number_of_k_paths(G,s,t,k):
V = G.vertices(sort=True)
i_s = V.index(s)
i_t = V.index(t)
r = 0
for Tsize in range(k):
for T in Subsets(Set(V) - Set({s,t}),Tsize):
L = [i for i,v in enumerate(V) if v==s or v==t or v in T]
r += (-1)^(k+1-len(L)) * binomial(len(V)-len(L),k+1-len(L)) * (A.matrix_from_rows_and_columns(L,L)^k)[L.index(i_s),L.index(i_t)]
return r


For example, number_of_k_paths(graphs.AfricaMap(),'Namibia', 'Libya',5) gives 9, which is consistent with the example given by @dan_fulea.

more

I think your approach is excellent in terms of counting. By the way, can your method showcase these paths?

( 2024-03-30 14:07:26 +0200 )edit
1

This approach enumerates the paths, but does not generate them. However, you can use it recursively to obtains the actual $k$-paths by enumerating $(k-1)$-paths from $v$ to $t$ for every neighbor $v$ of $s$ in the graph obtained from the given one by removing vertex $s$, and so on.

( 2024-03-30 16:17:33 +0200 )edit

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

more

Sorry. I lost something. I just want simple paths. Can kth power of adjacent matrix do more?

( 2024-03-27 17:28:01 +0200 )edit

Power of adjacency matrix enumerates walks not paths.

( 2024-03-27 17:33:51 +0200 )edit
2

As I did not know the difference between walk and path I searched the web and find this link:

https://www.quora.com/What-is-the-dif...

**Walk : Vertices may repeat. Edges may repeat (Closed or Open)

Trail : Vertices may repeat. Edges cannot repeat (Open)

Circuit : Vertices may repeat. Edges cannot repeat (Closed)

Path : Vertices cannot repeat. Edges cannot repeat (Open)

Cycle : Vertices cannot repeat. Edges cannot repeat (Closed)**

( 2024-03-28 12:47:47 +0200 )edit

A code from chatgpt seems OK.

def is_exactly_one_path(G, start, end, length):
"""
Check if there exists exactly one path from start to end with length in graph G.
Stop searching when two paths are found.
Return True if exactly one path is found.
Return False if no path is found.
"""
paths = []  # Used to store found paths
stack = [(start, [start])]  # Initialize stack with tuples of (current node, path)

while stack:
current, path = stack.pop()
if len(paths) > 1:  # If more than one path is found, terminate early
return False
if len(path) - 1 == length:  # Check path length
if current == end:
paths.append(path)  # If valid path, add to paths
continue  # Move to the next iteration

# Explore neighbors of the current node
for neighbor in G.neighbors(current):
if neighbor not in path:  # Avoid cyclic paths
stack.append((neighbor, path + [neighbor]))  # Add new state to stack

return len(paths) == 1  # Return True if exactly one path is found

# Assume G is a predefined graph object, for example:
# G = graphs.PetersenGraph()
# Call the function to check if exactly one path from 0 to 4 with length 3 exists
# result = is_exactly_one_path(G, 0, 4, 3)
# print(result)


construct all paths:

def em_k_path(G, start, end, length):
paths = []  # Used to store found paths
stack = [(start, [start])]  # Initialize stack with tuples of (current node, path)

while stack:
current, path = stack.pop()
if len(path) - 1 == length:  # Check path length
if current == end:
paths.append(path)  # If valid path, add to paths
continue  # Move to the next iteration

# Explore neighbors of the current node
for neighbor in G.neighbors(current):
if neighbor not in path:  # Avoid cyclic paths
stack.append((neighbor, path + [neighbor]))  # Add new state to stack

return paths

more

1

The code answers a different question, although it does internally construct all paths. Its worst-case complexity is also exponential in k.

( 2024-04-03 23:09:17 +0200 )edit

Yes, with a slight modification, this function can enumerate all k-paths. I did a simple test, and as k increases, the speed gets slower. But for the Tutte graph(46 vertices), it is ok.

H=graphs.TutteGraph()
H.vertices()
relabeling = {v: i for i, v in enumerate(H.vertices())}
T_relabel = H.relabel(relabeling)
H.plot()

( 2024-04-04 08:42:19 +0200 )edit

On a minor note, there is no point to store pairs (current node, path). Just path is enough as the current node can be obtained as path[-1].

( 2024-04-04 13:46:47 +0200 )edit

Another exponential time solution is to compute all shortest simple paths:

def find_k_paths(G, start, end, length):
for p in G.shortest_simple_paths(start, end):
if len(p) - 1 == length:
print(p)
elif len(p) - 1 > length:
break


This method can be modified to check if there is a unique k path or none or many.

( 2024-04-05 08:12:58 +0200 )edit