hamiltonian.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 HAMILTONIAN_H
# define HAMILTONIAN_H
 
# include <tpl_graph.H>
 
namespace Aleph 
{
 
template <class GT, 
    class SN = Dft_Show_Node<GT>,
    class SA = Dft_Show_Arc<GT> >
class Test_Hamiltonian_Sufficiency
{
  SN & sn;
  SA & sa;
 
    bool are_adjacent(GT & g, typename GT::Node * src, typename GT::Node * tgt)
    {
      (void) g;
 
      for (Node_Arc_Iterator<GT, SA> it(src, sa); it.has_curr(); it.next_ne())
        if (it.get_tgt_node_ne() == tgt)
          return true;
      return false;
    }
 
  bool test_graph(GT & g)
  {
    assert(not g.is_digraph());
 
    const size_t n = g.get_num_nodes();
 
    // Ore's theorem requires n >= 3
    if (n < 3)
      return false;
 
    // Check all pairs of distinct vertices
    for (Node_Iterator<GT, SN> i(g, sn); i.has_curr(); i.next_ne())
      {
        typename GT::Node * src = i.get_curr();
        const size_t nsrc = g.get_num_arcs(src);
 
        // Start j from the node after i to avoid duplicate pairs
        Node_Iterator<GT, SN> j(i);
        j.next_ne();
 
        for (; j.has_curr(); j.next_ne())
          {
            typename GT::Node * tgt = j.get_curr();
 
            // Only check NON-ADJACENT pairs (Ore's theorem condition)
            if (are_adjacent(g, src, tgt))
              continue;
 
            // For non-adjacent pairs, check if deg(u) + deg(v) >= n
            if (nsrc + g.get_num_arcs(tgt) < n)
              return false;
          }
      }
 
    return true;
  }
 
  bool has_arc(typename GT::Node * src, typename GT::Node * tgt)
  {
    for (Node_Arc_Iterator<GT, SA> it(src, sa); it.has_curr(); it.next_ne())
      if (it.get_tgt_node_ne() == tgt)
        return true;
    return false;
  }
 
  bool test_digraph(GT & g)
  {
    assert(g.is_digraph());
 
    const size_t n = g.get_num_nodes();
 
    // Requires n >= 3
    if (n < 3)
      return false;
 
    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())++;
 
    // Check all ordered pairs (src, tgt) where src != tgt
    for (Node_Iterator<GT, SN> i(g, sn); i.has_curr(); i.next_ne())
      {
        typename GT::Node * src = i.get_curr();
        const size_t out_deg_src = g.get_num_arcs(src);
 
        for (Node_Iterator<GT, SN> j(g, sn); j.has_curr(); j.next_ne())
          {
            typename GT::Node * tgt = j.get_curr();
 
            if (src == tgt)
              continue;
 
            // If condition is satisfied, skip
            if (out_deg_src + NODE_COUNTER(tgt) >= n)
              continue;
 
            // Condition not satisfied; check if arc src→tgt exists
            // If arc exists, this pair doesn't need to satisfy the condition
            if (has_arc(src, tgt))
              continue;
 
            // Non-adjacent pair that doesn't satisfy the condition
            return false;
          }
      }
 
    return true;
  }
 
public:
 
  Test_Hamiltonian_Sufficiency(SN && __sn = SN(), SA && __sa = SA()) 
    : sn(__sn), sa(__sa)
  {
    // empty 
  }
 
  bool operator () (GT & g)
  {
    if (g.is_digraph())
      return test_digraph(g);
    else
      return test_graph(g);
  }
};
 
template <class GT, 
          class SN = Dft_Show_Node<GT>,
          class SA = Dft_Show_Arc<GT> >
class Test_Dirac_Condition
{
  SN & sn;
  SA & sa;
 
  bool test_graph(GT & g)
  {
    assert(not g.is_digraph());
 
    const size_t n = g.get_num_nodes();
 
    // Dirac's theorem requires n >= 3
    if (n < 3)
      return false;
 
    const size_t min_degree = (n + 1) / 2;  // Ceiling of n/2
 
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      {
        if (g.get_num_arcs(it.get_curr()) < min_degree)
          return false;
      }
 
    return true;
  }
 
  bool test_digraph(GT & g)
  {
    assert(g.is_digraph());
 
    const size_t n = g.get_num_nodes();
 
    if (n < 3)
      return false;
 
    const size_t min_degree = (n + 1) / 2;
 
    g.reset_counter_nodes();
 
    // First pass: count in-degrees
    for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
      NODE_COUNTER(it.get_tgt_node_ne())++;
 
    // Second pass: check both in-degree and out-degree
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      {
        typename GT::Node * p = it.get_curr();
        const size_t out_deg = g.get_num_arcs(p);
        const size_t in_deg = NODE_COUNTER(p);
 
        // Both must be at least n/2
        if (out_deg < min_degree || in_deg < min_degree)
          return false;
      }
 
    return true;
  }
 
public:
 
  Test_Dirac_Condition(SN && __sn = SN(), SA && __sa = SA()) 
    : sn(__sn), sa(__sa)
  {
    // empty 
  }
 
  bool operator () (GT & g)
  {
    if (g.is_digraph())
      return test_digraph(g);
    else
      return test_graph(g);
  }
 
  size_t min_required_degree(GT & g) const
  {
    return (g.get_num_nodes() + 1) / 2;
  }
 
  std::pair<size_t, typename GT::Node*> find_min_degree_vertex(GT & g)
  {
    size_t min_deg = std::numeric_limits<size_t>::max();
    typename GT::Node * min_node = nullptr;
 
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      {
        typename GT::Node * p = it.get_curr();
        size_t deg = g.get_num_arcs(p);
        if (deg < min_deg)
          {
            min_deg = deg;
            min_node = p;
          }
      }
 
    return {min_deg, min_node};
  }
};
 
} // end namespace Aleph
 
# endif // HAMILTONIAN_H