DirectedAcyclicGraphT.h

// -*- tab-width: 2; indent-tabs-mode: nil; coding: utf-8-with-signature -*-
//-----------------------------------------------------------------------------
// Copyright 2000-2026 CEA (www.cea.fr) IFPEN (www.ifpenergiesnouvelles.com)
// See the top-level COPYRIGHT file for details.
// SPDX-License-Identifier: Apache-2.0
//-----------------------------------------------------------------------------
/*---------------------------------------------------------------------------*/
/* DirectedAcyclicGraphT.h                                     (C) 2000-2022 */
/*                                                                           */
/* Implementation of a directed acyclic graph                                */
/*---------------------------------------------------------------------------*/
#ifndef ARCANE_DIRECTEDACYCLICGRAPHT_H_
#define ARCANE_DIRECTEDACYCLICGRAPHT_H_
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
#include <iterator>
 
#include "arcane/utils/ArcaneGlobal.h"
#include "arcane/utils/GraphBaseT.h"
#include "arcane/utils/ITraceMng.h"
#include "arcane/utils/Math.h"
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
namespace Arcane
{
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
/*! Template class for DirectedAcyclicGraph.
 *  VertexType must implement a less comparison operator.
 *
 */
 
template <class VertexType, class EdgeType>
class DirectedAcyclicGraphT
: public GraphBaseT<VertexType, EdgeType>
{
  typedef VertexType& VertexRef;
  typedef EdgeType& EdgeRef;
 
 public:
 
  /** Constructor of the class */
  DirectedAcyclicGraphT(ITraceMng* trace_mng)
  : GraphBaseT<VertexType, EdgeType>(trace_mng)
  , m_compute_vertex_levels(true)
  {}
 
  /** Destructor of the class */
  virtual ~DirectedAcyclicGraphT() {}
 
 public:
 
  template <class ContainerT>
  class SortedElementSet
  {
   public:
 
    template <class T>
    class ReverseOrderSet
    {
     public:
 
      ReverseOrderSet(const T& elements)
      : m_elements(elements)
      {}
 
      virtual ~ReverseOrderSet() {}
 
      typedef typename std::reverse_iterator<typename T::iterator> iterator;
      typedef typename std::reverse_iterator<typename T::const_iterator> const_iterator;
 
      iterator begin() { return iterator(m_elements.end()); }
      const_iterator begin() const
      {
        return iterator(m_elements.end());
        ;
      }
 
      iterator end() { return iterator(m_elements.begin()); }
      const_iterator end() const { return iterator(m_elements.begin()); }
 
      Integer size() { return m_elements.size(); }
 
     private:
 
      T m_elements;
    };
 
   public:
 
    SortedElementSet(const ContainerT& elements)
    : m_elements(elements)
    {}
 
    SortedElementSet(ContainerT&& elements)
    : m_elements(elements)
    {}
 
    SortedElementSet() {}
 
    virtual ~SortedElementSet() {}
 
    typedef typename ContainerT::iterator iterator;
    typedef typename ContainerT::const_iterator const_iterator;
 
    iterator begin() { return m_elements.begin(); }
    const_iterator begin() const { return m_elements.begin(); }
 
    iterator end() { return m_elements.end(); }
    const_iterator end() const { return m_elements.end(); }
 
    Integer size() { return m_elements.size(); }
 
    ReverseOrderSet<ContainerT> reverseOrder() { return ReverseOrderSet<ContainerT>(m_elements); }
 
   private:
 
    ContainerT m_elements;
  };
 
  typedef GraphBaseT<VertexType, EdgeType> Base;
  typedef SortedElementSet<typename Base::EdgeTypeRefArray> SortedEdgeSet;
  typedef SortedElementSet<typename Base::VertexTypeRefArray> SortedVertexSet;
  typedef std::map<typename Base::VertexTypeConstRef, Integer> VertexLevelMap;
  typedef std::map<typename Base::EdgeTypeConstRef, Integer> EdgeLevelMap;
  typedef std::set<std::pair<VertexType, Integer>, std::function<bool(std::pair<VertexType, Integer>, std::pair<VertexType, Integer>)>> VertexLevelSet;
 
  void addEdge(const VertexType& source_vertex, const VertexType& target_vertex, const EdgeType& source_to_target_edge)
  {
    Base::addEdge(source_vertex, target_vertex, source_to_target_edge);
    m_compute_vertex_levels = true;
  }
 
  void addEdge(VertexType&& source_vertex, VertexType&& target_vertex, EdgeType&& source_to_target_edge)
  {
    Base::addEdge(source_vertex, target_vertex, source_to_target_edge);
    m_compute_vertex_levels = true;
  }
 
  SortedVertexSet topologicalSort()
  {
    if (m_compute_vertex_levels)
      _computeVertexLevels();
    typename Base::VertexTypeRefArray sorted_vertices;
    for (auto& vertex : this->m_vertices) {
      sorted_vertices.add(std::ref(vertex));
    }
    std::sort(sorted_vertices.begin(), sorted_vertices.end(), [&](const VertexType& a, const VertexType& b) { return m_vertex_level_map[a] < m_vertex_level_map[b]; });
    return SortedVertexSet(std::move(sorted_vertices));
  }
 
  SortedEdgeSet spanningTree()
  {
    if (m_compute_vertex_levels)
      _computeVertexLevels();
    typename Base::EdgeTypeRefArray spaning_tree_edges;
    for (auto& edge : this->m_edges) {
      Integer level = _computeEdgeLevel(edge);
      m_edge_level_map[edge] = level;
      if (level < 0)
        continue; // edge must not be accounted for in spanning tree
      spaning_tree_edges.add(std::ref(edge));
    }
    std::sort(spaning_tree_edges.begin(), spaning_tree_edges.end(), [&](const EdgeType& a, const EdgeType& b) { return m_edge_level_map[a] < m_edge_level_map[b]; });
    return SortedEdgeSet(spaning_tree_edges);
  }
 
  void print()
  {
    if (m_compute_vertex_levels)
      _computeVertexLevels();
    this->m_trace_mng->info() << "--- Directed Graph ---";
    for (const auto& vertex_entry : this->m_adjacency_list)
      _printGraphEntry(vertex_entry);
 
    std::ostringstream oss;
    this->m_trace_mng->info() << oss.str();
 
    for (const auto& vertex_level_set_entry : m_vertex_level_map)
      this->m_trace_mng->info() << "-- Graph has vertex " << vertex_level_set_entry.first << " with level " << vertex_level_set_entry.second;
  }
 
  /*! Cycle detection is done using a lazy pattern which is only triggered when calling topologicalSort() and print().
   *  This method allows knowing if the graph contains a cycle (which would cause topologicalSort() to fail).
   */
  bool hasCycle()
  {
    bool has_cycle = false;
    try {
      _computeVertexLevels();
    }
    catch (const FatalErrorException& e) {
      has_cycle = true;
    }
    return has_cycle;
  }
 
 private:
 
  std::set<typename Base::VertexTypeConstRef> m_colored_vertices;
  VertexLevelMap m_vertex_level_map;
  EdgeLevelMap m_edge_level_map;
  bool m_compute_vertex_levels;
 
 private:
 
  void _computeVertexLevels()
  {
    // Current algo cannot update vertex level ; need to clear the map.
    m_vertex_level_map.clear();
    // compute vertex level
    for (const auto& vertex_entry : this->m_adjacency_list)
      _computeVertexLevel(vertex_entry.first, 0);
    m_compute_vertex_levels = false;
  }
 
  void _computeVertexLevel(const VertexType& vertex, Integer level)
  {
    // Check for cycles
    if (!m_colored_vertices.insert(std::cref(vertex)).second)
      throw FatalErrorException("Cycle in graph. Exiting");
 
    // Try to insert vertex at the given level
    bool update_children = true;
    auto vertex_level_set_entry = m_vertex_level_map.insert(std::make_pair(std::cref(vertex), level)); // use emplace when available (gcc >= 4.8.0)
    if (!vertex_level_set_entry.second) // vertex already present
    {
      if (vertex_level_set_entry.first->second < level)
        vertex_level_set_entry.first->second = level;
      else
        update_children = false;
    }
    if (update_children) {
      auto vertex_adjacency_list = Base::m_adjacency_list.find(vertex);
      if (vertex_adjacency_list != Base::m_adjacency_list.end()) {
        ++level;
        for (const auto& child_vertex : vertex_adjacency_list->second.first)
          _computeVertexLevel(child_vertex, level);
      }
    }
    // Remove vertex from cycle detection
    m_colored_vertices.erase(vertex);
  }
 
  Integer _computeEdgeLevel(const EdgeType& edge)
  {
    auto edge_vertices_iterator = this->m_edge_to_vertex_map.find(edge);
    if (edge_vertices_iterator == this->m_edge_to_vertex_map.end())
      throw FatalErrorException("Not existing edge.");
    typename Base::VertexPair edge_vertices = edge_vertices_iterator->second;
    // edge level is set to source vertex level
    Integer edge_level = m_vertex_level_map[std::cref(edge_vertices.first)];
    // if the edge crosses graph levels (ie vertices level difference > 1), we put edge_level =-1, since we don't want to keep it in the spanning tree
    if (math::abs(edge_level - m_vertex_level_map[std::cref(edge_vertices.second)]) > 1)
      edge_level = -1;
    return edge_level;
  }
 
  void _printGraphEntry(const typename Base::AdjacencyListType::value_type& vertex_entry)
  {
    this->m_trace_mng->info() << "-- Vertex " << vertex_entry.first << " depends on ";
    for (const auto& connected_vertex : vertex_entry.second.first)
      this->m_trace_mng->info() << "  - " << connected_vertex;
  }
};
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
} // End namespace Arcane
 
/*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*/
 
#endif