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

savecancel

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