Line data    Source code

       1              : /*
       2              :  * Copyright (c) 2013-2015:  G-CSC, Goethe University Frankfurt
       3              :  * Author: Sebastian Reiter
       4              :  * 
       5              :  * This file is part of UG4.
       6              :  * 
       7              :  * UG4 is free software: you can redistribute it and/or modify it under the
       8              :  * terms of the GNU Lesser General Public License version 3 (as published by the
       9              :  * Free Software Foundation) with the following additional attribution
      10              :  * requirements (according to LGPL/GPL v3 §7):
      11              :  * 
      12              :  * (1) The following notice must be displayed in the Appropriate Legal Notices
      13              :  * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
      14              :  * 
      15              :  * (2) The following notice must be displayed at a prominent place in the
      16              :  * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
      17              :  * 
      18              :  * (3) The following bibliography is recommended for citation and must be
      19              :  * preserved in all covered files:
      20              :  * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
      21              :  *   parallel geometric multigrid solver on hierarchically distributed grids.
      22              :  *   Computing and visualization in science 16, 4 (2013), 151-164"
      23              :  * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
      24              :  *   flexible software system for simulating pde based models on high performance
      25              :  *   computers. Computing and visualization in science 16, 4 (2013), 165-179"
      26              :  * 
      27              :  * This program is distributed in the hope that it will be useful,
      28              :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      29              :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
      30              :  * GNU Lesser General Public License for more details.
      31              :  */
      32              : 
      33              : #ifndef __H__UG__ntree_traversal__
      34              : #define __H__UG__ntree_traversal__
      35              : 
      36              : namespace ug{
      37              : 
      38              : enum TraversalStates{
      39              :         DONT_TRAVERSE_CHILDREN,
      40              :         TRAVERSE_CHILDREN,
      41              :         ABORT_TRAVERSAL
      42              : };
      43              : 
      44              : template <class tree_t, class traverser_t>
      45            0 : void TraverseBreadthFirst(const tree_t& tree, traverser_t& traverser)
      46              : {
      47              :         std::vector<size_t> nodes;
      48            0 :         nodes.reserve(tree.num_nodes());
      49            0 :         nodes.push_back(0);
      50              :         int curInd = 0;
      51              : 
      52              :         traverser.begin_traversal(tree);
      53              : 
      54              : //      traverse upwards
      55            0 :         while(curInd < (int)nodes.size()){
      56            0 :                 size_t node = nodes[curInd];
      57              :                 int state = traverser.visit_up(tree, node);
      58              :                 switch(state){
      59              :                         case TRAVERSE_CHILDREN:{
      60              :                                 size_t numChildren = tree.num_child_nodes(node);
      61              :                                 const size_t* child = tree.child_node_ids(node);
      62            0 :                                 for(size_t i = 0; i < numChildren; ++i)
      63            0 :                                         nodes.push_back(child[i]);
      64              :                         }break;
      65              :                         case ABORT_TRAVERSAL:
      66              :                                 return;
      67              :                         default: break;
      68              :                 }
      69              : 
      70            0 :                 ++curInd;
      71              :         }
      72              : 
      73              : //      traverse downwards
      74              :         curInd = (int)nodes.size() - 1;
      75              :         while(curInd >= 0){
      76              :                 size_t node = nodes[curInd];
      77              :                 traverser.visit_down(tree, node);
      78              :                 --curInd;
      79              :         }
      80              : 
      81              :         traverser.end_traversal(tree);
      82            0 : }
      83              : 
      84              : template <class tree_t, class traverser_t>
      85              : int
      86            0 : TraverseDepthFirstRecursion(const tree_t& tree, traverser_t& traverser, int curNode)
      87              : {
      88            0 :         int state = traverser.visit_up(tree, curNode);
      89            0 :         switch(state){
      90            0 :                 case TRAVERSE_CHILDREN:{
      91              :                         size_t numChildren = tree.num_child_nodes(curNode);
      92              :                         const size_t* child = tree.child_node_ids(curNode);
      93            0 :                         for(size_t i = 0; i < numChildren; ++i){
      94            0 :                                 int childState = TraverseDepthFirstRecursion(tree, traverser, child[i]);
      95            0 :                                 if(childState == ABORT_TRAVERSAL){
      96            0 :                                         traverser.visit_down(tree, curNode);
      97            0 :                                         return ABORT_TRAVERSAL;
      98              :                                 }
      99              :                         }
     100              :                 } break;
     101              :         }
     102            0 :         traverser.visit_down(tree, curNode);
     103            0 :         return state;
     104              : }
     105              : 
     106              : template <class tree_t, class traverser_t>
     107              : void TraverseDepthFirst(const tree_t& tree, traverser_t& traverser)
     108              : {
     109              :         traverser.begin_traversal(tree);
     110            0 :         TraverseDepthFirstRecursion(tree, traverser, 0);
     111              :         traverser.end_traversal(tree);
     112            0 : }
     113              : 
     114              : }// end of namespace
     115              : 
     116              : #endif