Repository: TheAlgorithms/C-Plus-Plus
File: graph/number_of_paths.cpp (C++)

Code before:
 * all paths from the source node `u` to the destination node `v`.
 * 
 * @author [Aditya Borate](https://github.com/adi776borate)
 * @see https://en.wikipedia.org/wiki/Path_(graph_theory)
 */

#include <vector>   /// for std::vector
#include <iostream> /// for IO operations
#include <cassert>  /// for assert

/**
 * @namespace graph
 * @brief Graph algorithms
 */
namespace graph {

    /**
     * @brief Helper function to perform DFS and count the number of paths from node `u` to node `v`
     * @param A adjacency matrix representing the graph (1: edge exists, 0: no edge)
     * @param u the starting node
     * @param v the destination node
     * @param n the number of nodes in the graph
     * @param visited a vector to keep track of visited nodes in the current DFS path
     * @returns the number of paths from node `u` to node `v`
     */
    int count_paths_dfs(const std::vector<std::vector<unsigned int>>& A, int u, int v, int n, std::vector<bool>& visited) {
        if (u == v) {
            return 1; // Base case: Reached the destination node
        }

        visited[u] = true; // Mark the current node as visited
        int path_count = 0; // Count of all paths from `u` to `v`

        for (int i = 0; i < n; i++) {
            if (A[u][i] == 1 && !visited[i]) { // Check if there is an edge and the node is not visited
                path_count += count_paths_dfs(A, i, v, n, visited); // Recursively explore paths from `i` to `v`
            }
        }

        visited[u] = false; // Unmark the current node as visited (backtracking)
        return path_count;
    }

    /**
     * @brief Counts the number of paths from node `u` to node `v` in a directed graph
     * using Depth First Search (DFS)
     * 
     * @param A adjacency matrix representing the graph (1: edge exists, 0: no edge)
     * @param u the starting node
     * @param v the destination node
     * @param n the number of nodes in the graph

Review comment (suggestion):
since its impossible for the number of paths from u to v to be negative use unsigned integer as the return type 

Code after:
 * all paths from the source node `u` to the destination node `v`.
 * 
 * @author [Aditya Borate](https://github.com/adi776borate)
 * @see https://en.wikipedia.org/wiki/Path_(graph_theory)
 */

#include <vector>   /// for std::vector
#include <iostream> /// for IO operations
#include <cassert>  /// for assert
#include <cstdint>  /// for fixed-size integer types (e.g., std::uint32_t)

/**
 * @namespace graph
 * @brief Graph algorithms
 */
namespace graph {

    /**
     * @brief Helper function to perform DFS and count the number of paths from node `u` to node `v`
     * @param A adjacency matrix representing the graph (1: edge exists, 0: no edge)
     * @param u the starting node
     * @param v the destination node
     * @param n the number of nodes in the graph
     * @param visited a vector to keep track of visited nodes in the current DFS path
     * @returns the number of paths from node `u` to node `v`
     */
    std::uint32_t count_paths_dfs(const std::vector<std::vector<std::uint32_t>>& A, 
                              std::uint32_t u, 
                              std::uint32_t v, 
                              std::uint32_t n, 
                              std::vector<bool>& visited) {
        if (u == v) {
            return 1;  // Base case: Reached the destination node
        }

        visited[u] = true;  // Mark the current node as visited
        std::uint32_t path_count = 0;  // Count of all paths from `u` to `v`

        for (std::uint32_t i = 0; i < n; i++) {
            if (A[u][i] == 1 && !visited[i]) {  // Check if there is an edge and the node is not visited
                path_count += count_paths_dfs(A, i, v, n, visited);  // Recursively explore paths from `i` to `v`
            }
        }

        visited[u] = false;  // Unmark the current node as visited (backtracking)
        return path_count;
    }


    /**
     * @brief Counts the number of paths from node `u` to node `v` in a directed graph