faif
DepthFirst.h
1 #ifndef FAIF_DEPTH_FIRST_SEARCH_HPP
2 #define FAIF_DEPTH_FIRST_SEARCH_HPP
3 
4 #include <vector>
5 #include <stack>
6 
7 #include <boost/concept_check.hpp>
8 
9 #include "TreeNodeImpl.hpp"
10 
11 
12 namespace faif {
13  namespace search {
14 
15 
16  /**
17  @brief The depth-first search algorithm (DFS)
18 
19  from starting state the function build the tree structure,
20  explores as far as possible, backtracks. Function uses the protection
21  against the cycles in the graph and the maximum depth of tree border.
22 
23  @return the first path from the starting to the finishing state.
24  */
25  template<typename T>
26  typename Node<T>::Path searchDepthFirst(boost::shared_ptr<T> start, int max = 200) {
27  //the methods to create tree-like structures are required
28  BOOST_CONCEPT_ASSERT((NodeWithChildrenConcept<T>));
29  BOOST_CONCEPT_ASSERT((NodeWithFinalFlagConcept<T>));
30 
31  std::stack< TreeNode<T>* > buffer;
32  std::stack< TreeNode<T>* > trash;
33 
34  TreeNode<T> root(start);
35  TreeNode<T>* curr = &root;
36 
37  buffer.push(&root);
38 
39  while (!buffer.empty()) {
40 
41  curr = buffer.top();
42  buffer.pop();
43 
44  //cout << "Buffer size " << buffer.size() << " curr " << endl << *(curr->getPoint()) << endl;
45 
46  if ( !trash.empty() )
47  while (curr->getLevel() <= trash.top()->getLevel()) {
48  trash.top()->eraseChildren();
49  trash.pop();
50  }
51 
52  //check if the node is twice on the path from node to root
53  if ( checkNodeInPath( *curr ) )
54  continue;
55 
56  //check if the node is the final node
57  if (curr->getPoint()->isFinal() )
58  break;
59 
60  //check if the maximum depth
61  if (curr->getLevel() == max)
62  continue;
63  typename TreeNode<T>::Children ch = curr->getChildren();
64  for( typename TreeNode<T>::Children::const_iterator it = ch.begin(); it != ch.end(); ++it )
65  buffer.push( *it );
66 
67  trash.push(curr);
68  }
69 
70  typename Node<T>::Path path;
71 
72  if (curr->getPoint()->isFinal() )
73  path = curr->generatePathToRoot();
74 
75  return path;
76  }
77 
78  }//namespace search
79 } //namespace faif
80 
81 #endif //FAIF_DEPTH_FIRST_SEARCH_HPP
82 
Definition: Chain.h:17
the concept for node with children
Definition: Node.hpp:44
boost::shared_ptr< T > getPoint() const
Definition: TreeNodeImpl.hpp:45
the struct to create node in search space from individual
Definition: Node.hpp:26
Node< T >::Path searchDepthFirst(boost::shared_ptr< T > start, int max=200)
The depth-first search algorithm (DFS)
Definition: DepthFirst.h:26
the template to create the node in tree-based search methods
Definition: TreeNodeImpl.hpp:17
the concept for node with final flag for search in tree-like structures The function &#39;searchDepthFirs...
Definition: Node.hpp:60
Children getChildren()
Definition: TreeNodeImpl.hpp:95
Node< T >::Path generatePathToRoot() const
Definition: TreeNodeImpl.hpp:135
short getLevel() const
Definition: TreeNodeImpl.hpp:61
bool checkNodeInPath(const TreeNode< T > &n)
Definition: TreeNodeImpl.hpp:82