tpl_spanning_tree.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 TPL_SPANNING_TREE_H
# define TPL_SPANNING_TREE_H
 
# include <tpl_graph.H>
# include <tpl_graph_utils.H>
# include <ah-errors.H>
 
namespace Aleph {
 
template <class GT, class SA = Dft_Show_Arc<GT>> 
class Find_Depth_First_Spanning_Tree
{
  SA sa;
  GT * gptr = nullptr;
  GT * tptr = nullptr;
 
  // Recursive DFS helper to build the spanning tree
  bool build_tree(typename GT::Node * gnode, typename GT::Arc * garc, 
                  typename GT::Node * tnode)
  {
    // Mark node and arc as part of spanning tree
    NODE_BITS(gnode).set_bit(Spanning_Tree, true);
    ARC_BITS(garc).set_bit(Spanning_Tree, true);
 
    // Create corresponding node in tree and establish mapping
    auto tree_tgt_node = tptr->insert_node(gnode->get_info());
    GT::map_nodes(gnode, tree_tgt_node);
 
    // Create corresponding arc in tree and establish mapping
    auto tarc = tptr->insert_arc(tnode, tree_tgt_node, garc->get_info()); 
    GT::map_arcs(garc, tarc);
 
    tnode = tree_tgt_node; 
    
    // Check if spanning tree is complete (all nodes covered)
    if (tptr->get_num_nodes() == gptr->get_num_nodes())
      return true;
 
    // Invariant: tree must be acyclic (nodes > arcs)
    assert(tptr->get_num_nodes() > tptr->get_num_arcs());
 
    // Explore adjacent nodes via DFS
    for (Node_Arc_Iterator<GT, SA> i(gnode, sa); 
         i.has_curr() and tptr->get_num_nodes() < gptr->get_num_nodes();
         i.next_ne())
      {
        auto arc = i.get_current_arc_ne();
        if (IS_ARC_VISITED(arc, Spanning_Tree)) 
          continue;
 
        auto arc_tgt_node = i.get_tgt_node();
        if (IS_NODE_VISITED(arc_tgt_node, Spanning_Tree))
          continue;  // Target already visited via another arc
 
        if (build_tree(arc_tgt_node, arc, tnode))
          return true;
      }
 
    return false;
  }
 
  // Main algorithm entry point
  bool build_tree(GT & g, typename GT::Node * gnode, GT & tree)
  {
    gptr = &g;
    tptr = &tree;
 
    // Reset all control bits for fresh traversal
    gptr->reset_nodes();
    gptr->reset_arcs(); 
 
    // Ensure output tree is empty
    clear_graph(*tptr);
  
    // Mark starting node as visited
    NODE_BITS(gnode).set_bit(Spanning_Tree, true);
  
    // Create root node in tree and establish mapping
    auto tnode = tree.insert_node(gnode->get_info()); 
    GT::map_nodes(gnode, tnode);
  
    // Explore all adjacent arcs via DFS
    for (Node_Arc_Iterator<GT, SA> i(gnode, sa); 
         i.has_curr() and tptr->get_num_nodes() < gptr->get_num_nodes(); 
         i.next_ne())
      {
        auto arc = i.get_current_arc_ne();
        if (IS_ARC_VISITED(arc, Spanning_Tree)) 
          continue;
 
        auto arc_tgt_node = i.get_tgt_node();
        if (IS_NODE_VISITED(arc_tgt_node, Spanning_Tree))
          continue;  // Target already visited via another arc
 
        if (build_tree(arc_tgt_node, arc, tnode))
          return true;
      }
 
    return true;
  }
 
public:
 
  Find_Depth_First_Spanning_Tree(SA arc_filter = SA()) : sa(arc_filter) { /* empty */ }
 
  typename GT::Node * operator () (GT & g, GT & tree)
  {
    ah_domain_error_if(g.get_num_nodes() == 0)
      << "Find_Depth_First_Spanning_Tree: graph is empty";
 
    auto start = g.get_first_node();
    if (not build_tree(g, start, tree)) 
      return nullptr;
 
    return start;
  }
 
  typename GT::Node * operator () (GT & g, typename GT::Node * gnode, GT & tree)
  {
    ah_invalid_argument_if(gnode == nullptr)
      << "Find_Depth_First_Spanning_Tree: source node cannot be null";
 
    this->build_tree(g, gnode, tree);
    return static_cast<typename GT::Node *>(NODE_COOKIE(gnode));
  }
};
 
 
template <class GT, class SA = Dft_Show_Arc<GT>> 
class Find_Breadth_First_Spanning_Tree
{
  SA sa;
 
  // Main BFS algorithm to build spanning tree
  void build_tree(GT & g, typename GT::Node * gp, GT & tree)
  {
    // Reset control bits for fresh traversal
    g.reset_bit_nodes(Spanning_Tree);
    g.reset_bit_arcs(Spanning_Tree);
 
    // Ensure output tree is empty
    clear_graph(tree); 
 
    // Create root node in tree and establish mapping
    auto tp = tree.insert_node(gp->get_info());
    GT::map_nodes(gp, tp);
 
    // Initialize queue with arcs adjacent to starting node
    DynListQueue<typename GT::Arc*> q;
    for (Node_Arc_Iterator<GT, SA> i(gp, sa); i.has_curr(); i.next_ne())
      q.put(i.get_current_arc_ne());
 
    // Mark starting node as visited
    NODE_BITS(gp).set_bit(Spanning_Tree, true); 
 
    // BFS loop
    while (not q.is_empty()) 
      {
        auto garc = q.get(); 
        ARC_BITS(garc).set_bit(Spanning_Tree, true); 
        auto gsrc = g.get_src_node(garc);  
        auto gtgt = g.get_tgt_node(garc);
 
        // Skip if both endpoints already visited
        if (IS_NODE_VISITED(gsrc, Spanning_Tree) and 
            IS_NODE_VISITED(gtgt, Spanning_Tree))
          continue;
 
        // Ensure gsrc is the visited node and gtgt is the new one
        if (IS_NODE_VISITED(gtgt, Spanning_Tree))
          std::swap(gsrc, gtgt);
 
        auto tsrc = mapped_node<GT>(gsrc);
        NODE_BITS(gtgt).set_bit(Spanning_Tree, true);
 
        // Create new node in tree and establish mapping
        auto ttgt = tree.insert_node(gtgt->get_info());
        GT::map_nodes(gtgt, ttgt);
 
        // Create new arc in tree and establish mapping
        auto tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
        GT::map_arcs(garc, tarc);
        
        // Check if spanning tree is complete
        if (tree.get_num_nodes() == g.get_num_nodes())
          break; 
 
        // Enqueue arcs adjacent to newly added node
        for (Node_Arc_Iterator<GT, SA> i(gtgt, sa); i.has_curr(); i.next_ne())
          {
            auto current_arc = i.get_current_arc_ne();
            if (IS_ARC_VISITED(current_arc, Spanning_Tree)) 
              continue;
 
            // Skip arcs where both endpoints are already visited
            if (IS_NODE_VISITED(g.get_src_node(current_arc), Spanning_Tree) and 
                IS_NODE_VISITED(g.get_tgt_node(current_arc), Spanning_Tree))
              continue;
            q.put(current_arc);
          }
      }
  }
 
public:
 
  Find_Breadth_First_Spanning_Tree(SA arc_filter = SA()) : sa(arc_filter) { /* empty */ }
 
  void operator () (GT & g, typename GT::Node * gnode, GT & tree) 
  {
    ah_invalid_argument_if(gnode == nullptr)
      << "Find_Breadth_First_Spanning_Tree: source node cannot be null";
 
    this->build_tree(g, gnode, tree);
  }
 
  typename GT::Node * operator () (GT & g, GT & tree)
  {
    ah_domain_error_if(g.get_num_nodes() == 0)
      << "Find_Breadth_First_Spanning_Tree: graph is empty";
 
    auto start = g.get_first_node();
    this->build_tree(g, start, tree);
    return static_cast<typename GT::Node *>(NODE_COOKIE(start));
  }
};
 
template <class GT>
class Build_Spanning_Tree
{
public:
 
  GT operator () (const DynArray<typename GT::Arc*> & arcs) const
  {
    return build_spanning_tree<GT>(arcs);
  }
 
  GT operator () (const DynArray<typename GT::Arc*> * arcs) const
  {
    ah_invalid_argument_if(arcs == nullptr)
      << "Build_Spanning_Tree: arcs array cannot be null";
    return build_spanning_tree<GT>(*arcs);
  }
};
 
} // end namespace Aleph
 
# endif //  TPL_SPANNING_TREE_H