Download code

Jump to: navigation, search

Back to Depth-first_search_(C_Plus_Plus)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

dfs_sample.cpp

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Depth-first_search_(C_Plus_Plus)?oldid=19114
 14 */
 15 
 16 #include <iostream>
 17 #include <vector>
 18 #include <list>
 19 
 20 
 21 using namespace std;
 22 
 23 template <typename T>
 24 class vertex
 25 {
 26 private:
 27     T data;
 28     std::list<vertex<T>*> _successors;
 29 
 30 public:
 31     vertex<T>(const T data) { this->data = data; }
 32     T get_data() const { return data; }
 33     typedef typename std::list<vertex<T>*>::const_iterator successor_list_iterator;
 34     std::list<vertex<T>*>& successors() { return _successors; }
 35 };
 36 
 37 
 38 template <typename T, typename GoalFunction>
 39 bool depth_first_search(vertex<T>& start,
 40                         GoalFunction is_goal,
 41                         std::list< vertex<T>* >& result)
 42 {
 43     if (std::find(result.begin(), result.end(), &start) != result.end())
 44     {
 45         return false;
 46     }
 47 
 48     result.push_back(&start);
 49 
 50     if (is_goal(start))
 51     {
 52         return true;
 53     }
 54     typename vertex<T>::successor_list_iterator iter = start.successors().begin();
 55     while (iter != start.successors().end())
 56     {
 57         if (depth_first_search(**iter, is_goal, result))
 58         {
 59             return true;
 60         }
 61         iter++;
 62     }
 63 
 64     // No path was found
 65     result.pop_back();
 66     return false; 
 67 }
 68 
 69 vector< vertex<int> > PetersenGraph()
 70 {
 71     vector< vertex<int> > v;
 72     for(int i=0; i<10; i++)
 73     {
 74         v.push_back(vertex<int>(i));
 75     }
 76     struct { int source; int target; } edges[] =
 77         {{0,1}, {1,0}, {1,2}, {2,1}, {2,3}, {3,2}, {3,4}, {4,3}, {4,0}, {0,4},
 78          {5,6}, {6,5}, {6,7}, {7,6}, {7,8}, {8,7}, {8,9}, {9,8}, {9,5}, {5,9},
 79          {5,0}, {0,5}, {6,2}, {2,6}, {7,4}, {4,7}, {8,1}, {1,8}, {9,3}, {3,9}};
 80     for (unsigned int i=0; i<sizeof(edges)/sizeof(edges[0]); i++)
 81     {
 82         v[edges[i].source].successors().push_back(&v[edges[i].target]);
 83     }
 84     return v;
 85 }
 86 
 87 bool is_goal(vertex<int> v)
 88 {
 89     return v.get_data() == 7;
 90 }
 91 
 92 int main(void)
 93 {
 94     vector< vertex<int> > v = PetersenGraph();
 95     list< vertex<int>* > path;
 96     if (depth_first_search(v[0], is_goal, path))
 97     {
 98         cout << "Found path: ";
 99         list< vertex<int>* >::iterator iter = path.begin();
100         while (iter != path.end())
101         {
102             cout << (*iter)->get_data() << " ";
103             iter++;
104         }
105         cout << endl;
106     }
107     else
108     {
109         cout << "No path found" << endl;
110     }
111     return 0;
112 }
113 


hijacker
hijacker
hijacker
hijacker

build.log

1 /tmp/litprog9286952/dfs_sample.cpp: In function 'bool depth_first_search(vertex<T>&, GoalFunction, std::list<vertex<T>*>&) [with T = int, GoalFunction = bool (*)(vertex<int>)]':
2 /tmp/litprog9286952/dfs_sample.cpp:96:47:   instantiated from here
3 /tmp/litprog9286952/dfs_sample.cpp:43:5: error: no matching function for call to 'find(std::list<vertex<int>*, std::allocator<vertex<int>*> >::iterator, std::list<vertex<int>*, std::allocator<vertex<int>*> >::iterator, vertex<int>*)'
4 /tmp/litprog9286952/dfs_sample.cpp:43:5: note: candidate is:
5 /usr/include/c++/4.6/bits/streambuf_iterator.h:359:5: note: template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT2, std::char_traits<_CharT> > >::__type std::find(std::istreambuf_iterator<_CharT2, std::char_traits<_CharT> >, std::istreambuf_iterator<_CharT2, std::char_traits<_CharT> >, const _CharT2&)


hijacker
hijacker
hijacker
hijacker