eulerian.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef EULERIAN_H
# define EULERIAN_H
 
# include <tpl_graph.H>
# include <tpl_graph_utils.H>
 
namespace Aleph
{
 
enum class Eulerian_Type
{
  Cycle,  
  Path,   
  None    
};
 
template <class GT, 
    class SN = Dft_Show_Node<GT>,
    class SA = Dft_Show_Arc<GT> >
class Test_Eulerian
{
  SN & sn;
  SA & sa;
 
  bool is_connected(GT & g)
  {
    if (g.get_num_nodes() == 0)
      return true;
 
    // Find first vertex with edges
    typename GT::Node * start = nullptr;
    size_t non_isolated = 0;
 
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      {
        typename GT::Node * p = it.get_curr();
        if (g.get_num_arcs(p) > 0)
          {
            if (start == nullptr)
              start = p;
            ++non_isolated;
          }
      }
 
    // No edges means trivially connected (or empty)
    if (start == nullptr)
      return true;
 
    // DFS from start vertex
    g.reset_nodes();
    size_t visited = 0;
 
    DynList<typename GT::Node*> stack;
    stack.insert(start);
    NODE_BITS(start).set_bit(Depth_First, true);
 
    while (not stack.is_empty())
      {
        typename GT::Node * curr = stack.remove_first();
        ++visited;
 
        for (Node_Arc_Iterator<GT, SA> it(curr, sa); it.has_curr(); it.next_ne())
          {
            typename GT::Node * adj = it.get_tgt_node_ne();
            if (not NODE_BITS(adj).get_bit(Depth_First))
              {
                NODE_BITS(adj).set_bit(Depth_First, true);
                stack.insert(adj);
              }
          }
      }
 
    return visited == non_isolated;
  }
 
  bool is_strongly_connected(GT & g)
  {
    if (g.get_num_nodes() == 0)
      return true;
 
    // Find first vertex with edges
    typename GT::Node * start = nullptr;
    size_t non_isolated = 0;
 
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      {
        typename GT::Node * p = it.get_curr();
        if (g.get_num_arcs(p) > 0 or NODE_COUNTER(p) > 0)  // has out or in edges
          {
            if (start == nullptr)
              start = p;
            ++non_isolated;
          }
      }
 
    if (start == nullptr || non_isolated <= 1)
      return true;
 
    // DFS from start in original direction
    g.reset_nodes();
    size_t visited_forward = 0;
 
    DynList<typename GT::Node*> stack;
    stack.insert(start);
    NODE_BITS(start).set_bit(Depth_First, true);
 
    while (not stack.is_empty())
      {
        typename GT::Node * curr = stack.remove_first();
        if (g.get_num_arcs(curr) > 0 or NODE_COUNTER(curr) > 0)
          ++visited_forward;
 
        for (Node_Arc_Iterator<GT, SA> it(curr, sa); it.has_curr(); it.next_ne())
          {
            typename GT::Node * adj = it.get_tgt_node_ne();
            if (not NODE_BITS(adj).get_bit(Depth_First))
              {
                NODE_BITS(adj).set_bit(Depth_First, true);
                stack.insert(adj);
              }
          }
      }
 
    if (visited_forward != non_isolated)
      return false;
 
    // For full strong connectivity check, we'd need reverse graph traversal
    // For Eulerian purposes, if in-degree == out-degree and forward DFS
    // reaches all vertices, that's sufficient for practical purposes
    return true;
  }
 
  Eulerian_Type analyze_graph(GT & g)
  {
    assert(not g.is_digraph());
 
    size_t odd_degree_count = 0;
 
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      {
        if ((g.get_num_arcs(it.get_curr()) % 2) == 1)
          ++odd_degree_count;
      }
 
    // Check degree conditions first
    if (odd_degree_count == 0)
      {
        // All even degrees - could be Eulerian cycle if connected
        if (is_connected(g))
          return Eulerian_Type::Cycle;
        else
          return Eulerian_Type::None;
      }
    else if (odd_degree_count == 2)
      {
        // Exactly 2 odd degrees - could be Eulerian path if connected
        if (is_connected(g))
          return Eulerian_Type::Path;
        else
          return Eulerian_Type::None;
      }
    else
      {
        // More than 2 odd degrees - not Eulerian
        return Eulerian_Type::None;
      }
  }
 
  Eulerian_Type analyze_digraph(GT & g)
  {
    assert(g.is_digraph());
 
    g.reset_counter_nodes();
 
    // First pass: count in-degrees using node counters
    for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
      NODE_COUNTER(it.get_tgt_node_ne())++;
 
    // Count imbalanced vertices
    size_t start_vertices = 0;   // out - in == 1
    size_t end_vertices = 0;     // in - out == 1
    size_t imbalanced = 0;       // |in - out| > 1
 
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      {
        typename GT::Node * p = it.get_curr();
        const long out_deg = g.get_num_arcs(p);
        const long in_deg = NODE_COUNTER(p);
        const long diff = out_deg - in_deg;
 
        if (diff == 0)
          continue;  // Balanced vertex
        else if (diff == 1)
          ++start_vertices;
        else if (diff == -1)
          ++end_vertices;
        else
          ++imbalanced;
      }
 
    // Check degree conditions
    if (imbalanced > 0)
      return Eulerian_Type::None;
 
    if (start_vertices == 0 && end_vertices == 0)
      {
        // All balanced - could be Eulerian cycle if strongly connected
        if (is_strongly_connected(g))
          return Eulerian_Type::Cycle;
        else
          return Eulerian_Type::None;
      }
    else if (start_vertices == 1 && end_vertices == 1)
      {
        // One start, one end - could be Eulerian path
        // Connectivity check is simpler for path
        return Eulerian_Type::Path;
      }
    else
      {
        return Eulerian_Type::None;
      }
  }
 
public:
 
  Test_Eulerian(SN && __sn = SN(), SA && __sa = SA()) 
    : sn(__sn), sa(__sa)
  {
    // empty 
  }
 
  Eulerian_Type compute(GT & g)
  {
    if (g.is_digraph())
      return analyze_digraph(g);
    else
      return analyze_graph(g);
  }
 
  bool operator () (GT & g)
  {
    return compute(g) == Eulerian_Type::Cycle;
  }
 
  bool has_eulerian_path(GT & g)
  {
    auto result = compute(g);
    return result == Eulerian_Type::Cycle || result == Eulerian_Type::Path;
  }
 
  bool test_degree_only(GT & g)
  {
    if (g.is_digraph())
      {
        g.reset_counter_nodes();
        for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
          NODE_COUNTER(it.get_tgt_node_ne())++;
 
        for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
          {
            typename GT::Node * p = it.get_curr();
            if (g.get_num_arcs(p) != NODE_COUNTER(p))
              return false;
          }
        return true;
      }
    else
      {
        for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
          if ((g.get_num_arcs(it.get_curr()) % 2) == 1)
            return false;
        return true;
      }
  }
};
 
 
template <class GT, 
          class SN = Dft_Show_Node<GT>,
          class SA = Dft_Show_Arc<GT> >
class Find_Eulerian_Path
{
  SN & sn;
  SA & sa;
 
  typename GT::Node * find_start_vertex(GT & g, Eulerian_Type type)
  {
    typename GT::Node * start = nullptr;
    typename GT::Node * odd_vertex = nullptr;
 
    if (g.is_digraph())
      {
        // For digraphs, find vertex with out-degree > in-degree (start of path)
        g.reset_counter_nodes();
        for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
          NODE_COUNTER(it.get_tgt_node_ne())++;
 
        for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
          {
            typename GT::Node * p = it.get_curr();
            if (g.get_num_arcs(p) > 0)
              {
                if (start == nullptr)
                  start = p;
                if (g.get_num_arcs(p) > NODE_COUNTER(p))
                  odd_vertex = p;  // out > in: this is start of path
              }
          }
      }
    else
      {
        // For undirected, find vertex with odd degree
        for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
          {
            typename GT::Node * p = it.get_curr();
            if (g.get_num_arcs(p) > 0)
              {
                if (start == nullptr)
                  start = p;
                if ((g.get_num_arcs(p) % 2) == 1)
                  odd_vertex = p;
              }
          }
      }
 
    // For paths, must start at odd-degree vertex
    if (type == Eulerian_Type::Path && odd_vertex != nullptr)
      return odd_vertex;
 
    return start;
  }
 
  DynList<typename GT::Arc*> hierholzer_undirected(GT & g, typename GT::Node * start)
  {
    // Mark all arcs as unused
    g.reset_arcs();
 
    DynList<typename GT::Arc*> result;
    DynList<typename GT::Arc*> current_path;
    DynList<typename GT::Node*> stack;
 
    stack.insert(start);
 
    while (not stack.is_empty())
      {
        typename GT::Node * curr = stack.get_first();
 
        // Find an unused edge from curr
        typename GT::Arc * unused_arc = nullptr;
        for (Node_Arc_Iterator<GT, SA> it(curr, sa); it.has_curr(); it.next_ne())
          {
            typename GT::Arc * arc = it.get_curr();
            if (not IS_ARC_VISITED(arc, Depth_First))
              {
                unused_arc = arc;
                break;
              }
          }
 
        if (unused_arc != nullptr)
          {
            // Mark arc as used
            ARC_BITS(unused_arc).set_bit(Depth_First, true);
 
            // Get the other endpoint
            typename GT::Node * next = g.get_connected_node(unused_arc, curr);
 
            stack.insert(next);
            current_path.insert(unused_arc);
          }
        else
          {
            // No unused edges from curr - backtrack
            stack.remove_first();
            if (not current_path.is_empty())
              result.insert(current_path.remove_first());
          }
      }
 
    // Reverse to get correct order
    DynList<typename GT::Arc*> reversed;
    while (not result.is_empty())
      reversed.insert(result.remove_first());
 
    return reversed;
  }
 
  DynList<typename GT::Arc*> hierholzer_directed(GT & g, typename GT::Node * start)
  {
    // Mark all arcs as unused
    g.reset_arcs();
 
    DynList<typename GT::Arc*> result;
    DynList<typename GT::Arc*> current_path;
    DynList<typename GT::Node*> stack;
 
    stack.insert(start);
 
    while (not stack.is_empty())
      {
        typename GT::Node * curr = stack.get_first();
 
        // Find an unused outgoing edge from curr
        typename GT::Arc * unused_arc = nullptr;
        for (Node_Arc_Iterator<GT, SA> it(curr, sa); it.has_curr(); it.next_ne())
          {
            typename GT::Arc * arc = it.get_curr();
            if (not IS_ARC_VISITED(arc, Depth_First))
              {
                unused_arc = arc;
                break;
              }
          }
 
        if (unused_arc != nullptr)
          {
            // Mark arc as used
            ARC_BITS(unused_arc).set_bit(Depth_First, true);
 
            // Get target node
            typename GT::Node * next = g.get_tgt_node(unused_arc);
 
            stack.insert(next);
            current_path.insert(unused_arc);
          }
        else
          {
            // No unused edges from curr - backtrack
            stack.remove_first();
            if (not current_path.is_empty())
              result.insert(current_path.remove_first());
          }
      }
 
    // Reverse to get correct order
    DynList<typename GT::Arc*> reversed;
    while (not result.is_empty())
      reversed.insert(result.remove_first());
 
    return reversed;
  }
 
public:
 
  Find_Eulerian_Path(SN && __sn = SN(), SA && __sa = SA()) 
    : sn(__sn), sa(__sa)
  {
    // empty 
  }
 
  struct Result
  {
    DynList<typename GT::Arc*> path;  
    Eulerian_Type type;               
  };
 
  Result operator () (GT & g)
  {
    Result result;
 
    // First check if Eulerian path/cycle exists
    Test_Eulerian<GT, SN, SA> tester(std::forward<SN>(sn), std::forward<SA>(sa));
    result.type = tester.compute(g);
 
    if (result.type == Eulerian_Type::None)
      return result;
 
    // Find starting vertex
    typename GT::Node * start = find_start_vertex(g, result.type);
 
    if (start == nullptr)
      {
        result.type = Eulerian_Type::None;
        return result;
      }
 
    // Run Hierholzer's algorithm
    if (g.is_digraph())
      result.path = hierholzer_directed(g, start);
    else
      result.path = hierholzer_undirected(g, start);
 
    return result;
  }
 
  DynList<typename GT::Arc*> find_path(GT & g)
  {
    return (*this)(g).path;
  }
 
  DynList<typename GT::Node*> find_node_sequence(GT & g)
  {
    Result result = (*this)(g);
    DynList<typename GT::Node*> nodes;
 
    if (result.type == Eulerian_Type::None || result.path.is_empty())
      return nodes;
 
    // Get first node
    typename GT::Arc * first_arc = result.path.get_first();
    typename GT::Node * curr;
 
    if (g.is_digraph())
      curr = g.get_src_node(first_arc);
    else
      {
        // For undirected, need to find proper starting node
        typename GT::Node * start = find_start_vertex(g, result.type);
        curr = start;
      }
 
    nodes.append(curr);
 
    for (auto arc : result.path)
      {
        if (g.is_digraph())
          curr = g.get_tgt_node(arc);
        else
          curr = g.get_connected_node(arc, curr);
        nodes.append(curr);
      }
 
    return nodes;
  }
};
 
} // end namespace Aleph
 
# endif // EULERIAN_H