Tapkee
connected.hpp
Go to the documentation of this file.
00001 /* This software is distributed under BSD 3-clause license (see LICENSE file).
00002  *
00003  * Copyright (c) 2012-2013 Fernando J. Iglesias Garcia
00004  */
00005 
00006 #ifndef TAPKEE_CONNECTED_H_
00007 #define TAPKEE_CONNECTED_H_
00008 
00009 #include <stack>
00010 #include <vector>
00011 
00012 namespace tapkee
00013 {
00014 namespace tapkee_internal
00015 {
00016 
00017 template <class RandomAccessIterator>
00018 bool is_connected(RandomAccessIterator begin, RandomAccessIterator end,
00019         const Neighbors& neighbors)
00020 {
00021     timed_context context("Checking if graph is connected");
00022 
00023     // The number of data points
00024     int N = end-begin;
00025     // The number of neighbors used in KNN
00026     IndexType k = neighbors[0].size();
00027 
00028     typedef std::stack<int> DFSStack;
00029     typedef std::vector<bool> VisitedVector;
00030 
00031     VisitedVector visited(N, false);
00032     DFSStack stack;
00033     int nvisited = 0;
00034     stack.push(0);
00035 
00036     while (!stack.empty())
00037     {
00038         int current = stack.top();
00039         stack.pop();
00040 
00041         if (visited[current])
00042             continue;
00043 
00044         visited[current] = true;
00045         ++nvisited;
00046         
00047         if (nvisited == N) break;
00048 
00049         const LocalNeighbors& current_neighbors = neighbors[current];
00050 
00051         for(IndexType j=0; j<k; ++j)
00052         {
00053             int neighbor = current_neighbors[j];
00054             if (!visited[neighbor])
00055                 stack.push(neighbor);
00056         }
00057     }
00058 
00059     return (nvisited==N);
00060 }
00061 
00062 } /* namespace tapkee_internal */
00063 } /* namespace tapkee */
00064 
00065 #endif /* TAPKEE_CONNECTED_H_ */
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines