Ask Your Question
0

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

asked 2024-03-27 04:55:02 +0200

licheng gravatar image

updated 2024-03-27 17:33:09 +0200

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 flag offensive close merge delete

3 Answers

Sort by ยป oldest newest most voted
1

answered 2024-03-28 18:21:29 +0200

Max Alekseyev gravatar image

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)
    A = G.adjacency_matrix()
    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.

edit flag offensive delete link more

Comments

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

licheng gravatar imagelicheng ( 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.

Max Alekseyev gravatar imageMax Alekseyev ( 2024-03-30 16:17:33 +0200 )edit
1

answered 2024-03-27 17:25:12 +0200

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']
edit flag offensive delete link more

Comments

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

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

Power of adjacency matrix enumerates walks not paths.

Max Alekseyev gravatar imageMax Alekseyev ( 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)**

ortollj gravatar imageortollj ( 2024-03-28 12:47:47 +0200 )edit
0

answered 2024-04-03 16:58:27 +0200

licheng gravatar image

updated 2024-04-04 09:06:40 +0200

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
edit flag offensive delete link more

Comments

1

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

Max Alekseyev gravatar imageMax Alekseyev ( 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()
licheng gravatar imagelicheng ( 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].

Max Alekseyev gravatar imageMax Alekseyev ( 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.

David Coudert gravatar imageDavid Coudert ( 2024-04-05 08:12:58 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2024-03-27 04:55:02 +0200

Seen: 225 times

Last updated: Apr 04