All Paths from Source Lead to Destination

class Solution {
    
    enum State { VISITING, VISITED };
    
    public boolean canReachDestination(int number_of_nodes, int[][] links, int start, int target) {
        
        List<Integer>[] adjacencyList = createGraph(number_of_nodes, links);
        return checkPath(adjacencyList, start, target, new State[number_of_nodes]);
    }
    
    private boolean checkPath(List<Integer>[] adjList, int current, int end, State[] visited) {
        
        if (visited[current] != null) {
            return visited[current] == State.VISITED;
        }
        
        if (adjList[current].isEmpty()) {
            return current == end;
        }
        
        visited[current] = State.VISITING;
        
        for (int neighbor : adjList[current]) {
            if (!checkPath(adjList, neighbor, end, visited)) {
                return false;
            }
        }
        
        visited[current] = State.VISITED;
        return true;
    }
    
    private List<Integer>[] createGraph(int nodes, int[][] connection) {
        List<Integer>[] resultGraph = new List[nodes];
        for (int i = 0; i < nodes; i++) {
            resultGraph[i] = new ArrayList<>();
        }
        
        for (int[] link : connection) {
            resultGraph[link[0]].add(link[1]);
        }
        
        return resultGraph;
    }
}

The given Java code defines a method to determine whether all possible paths from a specified source node lead to a designated destination node in a directed graph. This is performed within the Solution class, utilizing a depth-first search (DFS) algorithm enhanced with state tracking to manage node visits.

Key features of the solution:

• Graph Representation and Initialization: A graph is represented using an adjacency list, where each node index contains a list of direct connections to other nodes. The createGraph method initializes this representation based on the input number of nodes and their connections.

• State Tracking: Nodes in the graph are tracked using an enumeration State with values VISITING and VISITED, to prevent revisits and detect cycles or paths that might not reach the target.

• Path Checking: The checkPath method implements the core DFS logic. If a node is already visited and labeled as VISITED, it confirms a valid path to the target already exists through this route. Nodes without outgoing links are check ends, directly comparing the current node to the target. During the traversal, it marks nodes as VISITING and upon completion of all possible routes from that node, it marks them as VISITED.

• Overall Handling: The canReachDestination method serves as the entry point, where it creates the adjacency list for the graph, initializes the state array for nodes, and triggers the path checking from the source node to the target.

The code provides scalability and efficiency in determining valid paths in a graph structure using systematic state transitions and depth-first traversal, making it suitable for problems dealing with route validations in directed graphs.

class Solution:
    IN_PROGRESS = 1
    COMPLETED = 2

    def hasPath(self, node_count: int, connections: List[List[int]], start: int, end: int) -> bool:
        adjacency_list = self.createGraph(node_count, connections)
        return self.checkPath(adjacency_list, start, end, [None] * node_count)
        
    def checkPath(self, graph, current_node, target, visited_states):

        if visited_states[current_node] is not None:
            return visited_states[current_node] == Solution.COMPLETED
        
        if not graph[current_node]:
            return current_node == target
        
        visited_states[current_node] = Solution.IN_PROGRESS
        
        for neighbor in graph[current_node]:
            if not self.checkPath(graph, neighbor, target, visited_states):
                return False
        
        visited_states[current_node] = Solution.COMPLETED
        return True

    def createGraph(self, total_nodes, links):
        adj_list = [[] for _ in range(total_nodes)]
        
        for link in links:
            adj_list[link[0]].append(link[1])
            
        return adj_list

The Python3 program features the Solution class designed to determine if all paths starting from a source node can consistently lead to a destination node in a directed graph. The algorithm is structured around three key functions:

• hasPath: Initializes the graph from the input and invokes checkPath to explore possible routes from the source to the target.
• checkPath: Recursively explores each path and checks for cycles using a state array, ensuring paths do not re-enter 'in-progress' nodes.
• createGraph: Constructs an adjacency list from the input connections to represent the graph.

The solution employs depth-first search (DFS) for path traversal, conducted primarily in the checkPath function. Here's a succinct overview of its approach:

1. The graph is first converted into an adjacency list to facilitate efficient traversal of connections.
2. A recursive DFS is guided by the checkPath function, which employs a three-state system (None, IN_PROGRESS, COMPLETED) stored in visited_states to manage the exploration status of each node:
   • None indicates the node hasn't been visited.
   • IN_PROGRESS marks nodes currently being explored, assisting in cycle detection.
   • COMPLETED denotes nodes fully processed without finding invalid paths.
3. During the DFS, if a node has no outgoing edges, it checks if the node is the destination. If it's currently being explored and found again, a cycle is detected, and False is immediately returned.
4. The process continues for all neighbors of the node; if any path check returns False, the function propagates this to prevent further unnecessary checks.

This method ensures that all explorations are not only efficient but also robust against cycles and incomplete paths. The efficient backtracking and state management allow the function to handle complex graphs effectively without revisiting or reprocessing completed nodes. This program thus offers a reliable way to assess path completeness in directed graphs from a given start to end node.