traversal_common.hpp

/**
 * @file traversal_common.hpp
 * @brief Common utilities and visitor concepts for graph traversal algorithms
 * 
 * This file provides shared functionality used by graph traversal and shortest path algorithms,
 * including:
 * - Visitor concepts that define callback interfaces for algorithm events
 * - Initialization utilities for distance and predecessor tracking
 * - Edge weight function concepts for weighted graph algorithms
 * - Helper types for optional predecessor tracking
 * 
 * The visitor concepts enable customizable behavior during graph traversal without modifying
 * the core algorithm implementations. Algorithms check for the presence of visitor methods
 * at compile time and only invoke those that are defined.
 * 
 * Used by: breadth_first_search, depth_first_search, dijkstra_shortest_paths,
 *          bellman_ford_shortest_paths, and topological_sort.
 */

#pragma once

#include <algorithm>
#include <concepts>
#include <numeric>
#include <type_traits>
#include <graph/detail/graph_using.hpp>
#include <graph/graph_concepts.hpp>
#include <graph/adj_list/vertex_property_map.hpp>

#ifndef GRAPH_TRAVERSAL_COMMON_HPP
#  define GRAPH_TRAVERSAL_COMMON_HPP

namespace graph {

//
// Edge weight function concepts
//
// Note on std::remove_reference_t<G>:
// Algorithm templates declare G&& (forwarding reference), so for lvalue arguments G deduces
// as a reference type (e.g. vector<…>&). Writing "const G&" when G is already a reference
// triggers reference collapsing: const (vector<…>&) & → vector<…>& — the const is silently
// discarded because it qualifies the reference, not the referent. We use
// std::remove_reference_t<G> in concept constraints, invoke_result_t, and std::function
// default types so that "const std::remove_reference_t<G>&" always means a true const ref.
// Default lambdas use "const auto&" instead of "const G&" to sidestep the issue entirely.
//

/**
 * @brief Concept for a generalized edge weight function with custom comparison and combination.
 * 
 * This concept refines edge_value_function with additional arithmetic constraints: the
 * weight value must be combinable with distances and assignable back to the distance type.
 * 
 * @tparam G Graph type
 * @tparam WF Weight function type (e.g., lambda returning edge weight)
 * @tparam DistanceValue The arithmetic type used for distances
 * @tparam Compare Comparison operation for distance values (e.g., std::less for shortest paths)
 * @tparam Combine Combination operation for distances (e.g., std::plus for distance accumulation)
 */
template <class G, class WF, class DistanceValue, class Compare, class Combine>
concept basic_edge_weight_function =
      edge_value_function<WF, std::remove_reference_t<G>, edge_t<G>> && 
      std::strict_weak_order<Compare, DistanceValue, DistanceValue> &&
      std::assignable_from<
            std::add_lvalue_reference_t<DistanceValue>,
            invoke_result_t<Combine, DistanceValue, invoke_result_t<WF, const std::remove_reference_t<G>&, edge_t<G>>>>;

/**
 * @brief Concept for a standard edge weight function using default comparison and addition.
 * 
 * This is a convenience concept for the common case of shortest path algorithms that use
 * less-than comparison and addition for distance operations. Subsumes edge_value_function
 * (via basic_edge_weight_function) and additionally requires an arithmetic return type.
 * 
 * @tparam G Graph type
 * @tparam WF Weight function type that returns an arithmetic value for each edge
 * @tparam DistanceValue The arithmetic type used for distances
 */
template <class G, class WF, class DistanceValue>
concept edge_weight_function =
      is_arithmetic_v<DistanceValue> && //
      is_arithmetic_v<invoke_result_t<WF, const std::remove_reference_t<G>&, edge_t<G>>> &&
      basic_edge_weight_function<G, WF, DistanceValue, less<DistanceValue>, plus<DistanceValue>>;

//
// Shortest path initialization utilities
//

/**
 * @ingroup graph_algorithms
 * @brief Returns a value representing infinite distance for shortest path algorithms.
 * 
 * Used to initialize distance values before running shortest path algorithms. Vertices with
 * this distance value are considered unreachable.
 * 
 * @tparam DistanceValue The arithmetic type used for distances.
 * 
 * @return A sentinel value representing infinite distance (std::numeric_limits<T>::max()).
 */
template <class DistanceValue>
constexpr auto infinite_distance() {
  return std::numeric_limits<DistanceValue>::max();
}

/**
 * @ingroup graph_algorithms
 * @brief Returns a zero distance value.
 * 
 * Used as the initial distance for source vertices in shortest path algorithms.
 * 
 * @tparam DistanceValue The arithmetic type used for distances.
 * 
 * @return A zero-initialized distance value.
 */
template <class DistanceValue>
constexpr auto zero_distance() {
  return DistanceValue();
}

/// General concept: a callable returning a mutable lvalue reference to any per-vertex property value.
/// Used by connected_components, label_propagation, and similar algorithms with per-vertex
/// property output parameters.
template <class VF, class G>
concept vertex_property_fn_for =
      std::invocable<VF&, const std::remove_reference_t<G>&, const vertex_id_t<G>&> &&
      std::is_lvalue_reference_v<
            std::invoke_result_t<VF&, const std::remove_reference_t<G>&, const vertex_id_t<G>&>>;

/// Type alias: extracts the value type from a vertex property function's return type
template <class VF, class G>
using vertex_fn_value_t = std::remove_cvref_t<
    std::invoke_result_t<VF&, const std::remove_reference_t<G>&, const vertex_id_t<G>&>>;

//
// Distance and predecessor function concepts
//
// These concepts enable algorithms to accept functions for per-vertex distance and
// predecessor access: distance(g, uid) and predecessor(g, uid). This is more flexible
// than requiring a specific container, because the values can reside on a vertex property
// or in an external container.
//

/// Concept: a callable returning a mutable reference to a per-vertex distance value
template <class DF, class G>
concept distance_fn_for = vertex_property_fn_for<DF, G>;

/// Type alias: extracts the distance value type from a distance function's return type
template <class DF, class G>
using distance_fn_value_t = vertex_fn_value_t<DF, G>;

/// Type alias: extracts the predecessor value type from a predecessor function's return type
/// Concept: a callable returning a mutable reference to a per-vertex predecessor value
template <class PF, class G>
concept predecessor_fn_for = vertex_property_fn_for<PF, G>;

template <class PF, class G>
using predecessor_fn_value_t = vertex_fn_value_t<PF, G>;

/// Null predecessor function — used when predecessor tracking is not needed.
/// Detected at compile time via is_null_predecessor_fn_v to skip predecessor writes.
struct _null_predecessor_fn {
  template <class G, class VId>
  size_t& operator()(const G&, const VId&) {
    static size_t dummy = 0;
    return dummy;
  }
};

/// Global instance of the null predecessor function
inline _null_predecessor_fn _null_predecessor;

/// Type trait to detect _null_predecessor_fn at compile time
template <class T>
inline constexpr bool is_null_predecessor_fn_v = std::is_same_v<std::remove_cvref_t<T>, _null_predecessor_fn>;

/// Function object that adapts a subscriptable container into a property function.
/// Wraps container[uid] into fn(g, uid) -> auto&, satisfying distance_fn_for
/// and predecessor_fn_for concepts.
///
/// Usage:
///   std::vector<int> distances(num_vertices(g));
///   dijkstra_shortest_paths(g, source, container_value_fn(distances), ...);
///
template <class Container>
struct container_value_fn {
  Container& c;

  template <class G, class VId>
  constexpr auto& operator()(const G&, const VId& uid) const {
    return c[uid];
  }
};

template <class Container>
container_value_fn(Container&) -> container_value_fn<Container>;

//
// Visitor concepts
//
// These concepts enable compile-time detection of visitor callback methods. Algorithms check
// for the presence of these methods and invoke them at specific points during traversal.
// Users can implement only the callbacks they need; missing methods are simply not called.
//

// Vertex visitor concepts

/// Concept for visitors that handle vertex initialization events (descriptor overload)
template <class G, class Visitor>
concept has_on_initialize_vertex = requires(Visitor& v, const G& g, const vertex_t<G>& vdesc) {
  { v.on_initialize_vertex(g, vdesc) };
};

/// Concept for visitors that handle vertex initialization events (vertex id overload)
template <class G, class Visitor>
concept has_on_initialize_vertex_id = requires(Visitor& v, const G& g, const vertex_id_t<G>& uid) {
  { v.on_initialize_vertex(g, uid) };
};

/// Concept for visitors that handle vertex discovery events (descriptor overload)
template <class G, class Visitor>
concept has_on_discover_vertex = requires(Visitor& v, const G& g, const vertex_t<G>& vdesc) {
  { v.on_discover_vertex(g, vdesc) };
};

/// Concept for visitors that handle vertex discovery events (vertex id overload)
template <class G, class Visitor>
concept has_on_discover_vertex_id = requires(Visitor& v, const G& g, const vertex_id_t<G>& uid) {
  { v.on_discover_vertex(g, uid) };
};

/// Concept for visitors that handle vertex examination events (descriptor overload)
template <class G, class Visitor>
concept has_on_examine_vertex = requires(Visitor& v, const G& g, const vertex_t<G>& vdesc) {
  { v.on_examine_vertex(g, vdesc) };
};

/// Concept for visitors that handle vertex examination events (vertex id overload)
template <class G, class Visitor>
concept has_on_examine_vertex_id = requires(Visitor& v, const G& g, const vertex_id_t<G>& uid) {
  { v.on_examine_vertex(g, uid) };
};

/// Concept for visitors that handle vertex finish events (descriptor overload)
template <class G, class Visitor>
concept has_on_finish_vertex = requires(Visitor& v, const G& g, const vertex_t<G>& vdesc) {
  { v.on_finish_vertex(g, vdesc) };
};

/// Concept for visitors that handle vertex finish events (vertex id overload)
template <class G, class Visitor>
concept has_on_finish_vertex_id = requires(Visitor& v, const G& g, const vertex_id_t<G>& uid) {
  { v.on_finish_vertex(g, uid) };
};

// Edge visitor concepts

/// Concept for visitors that handle edge examination events
template <class G, class Visitor>
concept has_on_examine_edge = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_examine_edge(g, e) };
};

/// Concept for visitors that handle edge relaxation events (distance was improved)
template <class G, class Visitor>
concept has_on_edge_relaxed = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_edge_relaxed(g, e) };
};

/// Concept for visitors that handle non-relaxation events (distance was not improved)
template <class G, class Visitor>
concept has_on_edge_not_relaxed = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_edge_not_relaxed(g, e) };
};

/// Concept for visitors that handle edge minimization events (used in negative cycle detection)
template <class G, class Visitor>
concept has_on_edge_minimized = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_edge_minimized(g, e) };
};

/// Concept for visitors that handle non-minimization events
template <class G, class Visitor>
concept has_on_edge_not_minimized = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_edge_not_minimized(g, e) };
};

// DFS-specific visitor concepts

/// Concept for visitors that handle DFS start events (descriptor overload)
template <class G, class Visitor>
concept has_on_start_vertex = requires(Visitor& v, const G& g, const vertex_t<G>& vdesc) {
  { v.on_start_vertex(g, vdesc) };
};

/// Concept for visitors that handle DFS start events (vertex id overload)
template <class G, class Visitor>
concept has_on_start_vertex_id = requires(Visitor& v, const G& g, const vertex_id_t<G>& uid) {
  { v.on_start_vertex(g, uid) };
};

/// Concept for visitors that handle tree edge events (edge to undiscovered vertex)
template <class G, class Visitor>
concept has_on_tree_edge = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_tree_edge(g, e) };
};

/// Concept for visitors that handle back edge events (edge to ancestor in DFS tree, indicates cycle)
template <class G, class Visitor>
concept has_on_back_edge = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_back_edge(g, e) };
};

/// Concept for visitors that handle forward or cross edge events (edge to already-finished vertex)
template <class G, class Visitor>
concept has_on_forward_or_cross_edge = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_forward_or_cross_edge(g, e) };
};

/// Concept for visitors that handle edge finish events (after edge and its target are fully processed)
template <class G, class Visitor>
concept has_on_finish_edge = requires(Visitor& v, const G& g, const edge_t<G>& e) {
  { v.on_finish_edge(g, e) };
};

//
// Visitor types
//

/// Empty visitor type for algorithms that don't require custom callbacks
struct empty_visitor {};

//
// Aggregate / strict visitor concepts
//

/// Concept satisfied when a visitor handles at least one recognized traversal event.
/// This is the disjunction of every has_on_* visitor concept. It is used by valid_visitor
/// to distinguish a deliberately empty visitor from one whose callbacks were misnamed.
template <class G, class Visitor>
concept has_any_visitor_event =                                                       //
    has_on_initialize_vertex<G, Visitor> || has_on_initialize_vertex_id<G, Visitor> || //
    has_on_discover_vertex<G, Visitor> || has_on_discover_vertex_id<G, Visitor> ||     //
    has_on_examine_vertex<G, Visitor> || has_on_examine_vertex_id<G, Visitor> ||       //
    has_on_finish_vertex<G, Visitor> || has_on_finish_vertex_id<G, Visitor> ||         //
    has_on_start_vertex<G, Visitor> || has_on_start_vertex_id<G, Visitor> ||           //
    has_on_examine_edge<G, Visitor> || has_on_edge_relaxed<G, Visitor> ||              //
    has_on_edge_not_relaxed<G, Visitor> || has_on_edge_minimized<G, Visitor> ||        //
    has_on_edge_not_minimized<G, Visitor> || has_on_tree_edge<G, Visitor> ||           //
    has_on_back_edge<G, Visitor> || has_on_forward_or_cross_edge<G, Visitor> ||        //
    has_on_finish_edge<G, Visitor>;

/// Strict visitor concept: a type is a valid visitor for graph G if it is the empty_visitor
/// sentinel or it provides at least one recognized on_* callback. This catches the common
/// mistake of misspelling a callback name (e.g. on_discover_vertx), which would otherwise be
/// silently ignored because each event is detected independently via the has_on_* concepts.
template <class G, class Visitor>
concept valid_visitor = std::same_as<std::remove_cvref_t<Visitor>, empty_visitor> || //
                        has_any_visitor_event<G, Visitor>;

/**
 * @brief A null range type for optional predecessor tracking in shortest path algorithms.
 * 
 * This is a unique type that algorithms can detect at compile time to determine whether
 * predecessor tracking should be performed. It derives from std::vector<size_t> but remains
 * perpetually empty regardless of operations performed on it.
 * 
 * This enables a single algorithm implementation to support both cases:
 * - When predecessors are needed: use a real vector that stores parent vertices
 * - When predecessors are not needed: use this type to avoid tracking overhead
 * 
 * Implementation detail: Not part of the P1709 graph library proposal.
 */
class _null_range_type : public std::vector<size_t> {
  using T         = size_t;
  using Allocator = std::allocator<T>;
  using Base      = std::vector<T, Allocator>;

public:
  _null_range_type() noexcept(noexcept(Allocator())) = default;
  explicit _null_range_type([[maybe_unused]] const Allocator&) noexcept {}
  _null_range_type([[maybe_unused]] Base::size_type count, [[maybe_unused]] const T& value, const Allocator& = Allocator()) {}
  explicit _null_range_type([[maybe_unused]] Base::size_type count, const Allocator& = Allocator()) {}
  template <class InputIt>
  _null_range_type([[maybe_unused]] InputIt first, [[maybe_unused]] InputIt last, const Allocator& = Allocator()) {}
  _null_range_type(const _null_range_type&) : Base() {}
  _null_range_type(const _null_range_type&, const Allocator&) {}
  _null_range_type(_null_range_type&&) noexcept {}
  _null_range_type(_null_range_type&&, const Allocator&) {}
  _null_range_type(std::initializer_list<T>, const Allocator& = Allocator()) {}
};

/// Global instance of the null range used when predecessor tracking is not needed
inline static _null_range_type _null_predecessors;

/**
 * @brief Type trait to detect _null_range_type at compile time.
 *
 * Algorithms use `if constexpr (is_null_range_v<Predecessors>)` to skip
 * predecessor tracking when the caller passes _null_predecessors.
 *
 * @tparam T The type to test
 */
template <class T>
inline constexpr bool is_null_range_v = std::is_same_v<std::remove_cvref_t<T>, _null_range_type>;

// ─────────────────────────────────────────────────────────────────────────────
// Graph-parameterized init_shortest_paths overloads
//
// These overloads accept the graph as the first parameter, enabling correct
// initialization for both index-based (vector) and map-based (unordered_map)
// vertex_property_map containers.
//
// For index graphs: identical behavior to the legacy overloads above.
// For mapped graphs: iterates vertexlist(g) to populate entries.
// ─────────────────────────────────────────────────────────────────────────────

/**
 * @ingroup graph_algorithms
 * @brief Initialize distances for shortest path algorithms (graph-aware).
 *
 * Sets every vertex's distance to infinite_distance().
 *
 * For index graphs (Distances is a random_access_range):
 *   std::ranges::fill(distances, infinite).
 * For mapped graphs (Distances is an unordered_map):
 *   if the map is empty, populates all vertices from vertexlist(g);
 *   if pre-populated, fills existing entries.
 *
 * @tparam G Graph type satisfying adjacency_list
 * @tparam Distances vertex_property_map container (vector or unordered_map)
 * @param g The graph
 * @param distances The distance map to initialize
 */
template <class G, class Distances>
  requires adjacency_list<G> && vertex_property_map_for<Distances, G>
constexpr void init_shortest_paths(const G& g, Distances& distances) {
  using dist_value = vertex_property_map_value_t<Distances>;
  constexpr auto infinite = infinite_distance<dist_value>();

  if constexpr (std::ranges::random_access_range<Distances>) {
    // Index graph: fill the pre-sized vector
    std::ranges::fill(distances, infinite);
  } else {
    // Mapped graph
    if (distances.empty()) {
      // Lazy map: populate all vertices
      for (auto&& [uid, u] : views::vertexlist(g)) {
        distances[uid] = infinite;
      }
    } else {
      // Pre-populated map: fill existing entries
      for (auto& [key, val] : distances) {
        val = infinite;
      }
    }
  }
}

/**
 * @ingroup graph_algorithms
 * @brief Initialize distances and predecessors for shortest path algorithms (graph-aware).
 *
 * Sets every vertex's distance to infinite_distance() and
 * every vertex's predecessor to itself.
 *
 * For index graphs: distances are filled, predecessors are iota'd from 0.
 * For mapped graphs: vertices are iterated via vertexlist(g) to set both.
 * Predecessors of type _null_range_type are skipped via is_null_range_v.
 *
 * @tparam G Graph type satisfying adjacency_list
 * @tparam Distances vertex_property_map container (vector or unordered_map)
 * @tparam Predecessors vertex_property_map container (vector or unordered_map), or _null_range_type
 * @param g The graph
 * @param distances The distance map to initialize
 * @param predecessors The predecessor map to initialize (each vertex → itself)
 */
template <class G, class Distances, class Predecessors>
  requires adjacency_list<G> && vertex_property_map_for<Distances, G> &&
           (vertex_property_map_for<Predecessors, G> || is_null_range_v<Predecessors>)
constexpr void init_shortest_paths(const G& g, Distances& distances, Predecessors& predecessors) {
  using dist_value = vertex_property_map_value_t<Distances>;
  constexpr auto infinite = infinite_distance<dist_value>();

  if constexpr (std::ranges::random_access_range<Distances>) {
    // Index graph: fill distances, iota predecessors
    std::ranges::fill(distances, infinite);
    if constexpr (!is_null_range_v<Predecessors>) {
      std::iota(predecessors.begin(), predecessors.end(), 0);
    }
  } else {
    // Mapped graph: iterate vertexlist to set both maps
    for (auto&& [uid, u] : views::vertexlist(g)) {
      distances[uid] = infinite;
      if constexpr (!is_null_range_v<Predecessors>) {
        predecessors[uid] = uid;
      }
    }
  }
}

} // namespace graph

#endif // GRAPH_TRAVERSAL_COMMON_HPP