Tapkee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
connected.hpp
Go to the documentation of this file.
1 /* This software is distributed under BSD 3-clause license (see LICENSE file).
2  *
3  * Copyright (c) 2012-2013 Fernando J. Iglesias Garcia
4  */
5 
6 #ifndef TAPKEE_CONNECTED_H_
7 #define TAPKEE_CONNECTED_H_
8 
9 #include <stack>
10 #include <vector>
11 
12 namespace tapkee
13 {
14 namespace tapkee_internal
15 {
16 
17 template <class RandomAccessIterator>
18 bool is_connected(RandomAccessIterator begin, RandomAccessIterator end,
19  const Neighbors& neighbors)
20 {
21  timed_context context("Checking if graph is connected");
22 
23  // The number of data points
24  int N = end-begin;
25  // The number of neighbors used in KNN
26  IndexType k = neighbors[0].size();
27 
28  typedef std::stack<int> DFSStack;
29  typedef std::vector<bool> VisitedVector;
30 
31  VisitedVector visited(N, false);
32  DFSStack stack;
33  int nvisited = 0;
34  stack.push(0);
35 
36  while (!stack.empty())
37  {
38  int current = stack.top();
39  stack.pop();
40 
41  if (visited[current])
42  continue;
43 
44  visited[current] = true;
45  ++nvisited;
46 
47  if (nvisited == N) break;
48 
49  const LocalNeighbors& current_neighbors = neighbors[current];
50 
51  for(IndexType j=0; j<k; ++j)
52  {
53  int neighbor = current_neighbors[j];
54  if (!visited[neighbor])
55  stack.push(neighbor);
56  }
57  }
58 
59  return (nvisited==N);
60 }
61 
62 } /* namespace tapkee_internal */
63 } /* namespace tapkee */
64 
65 #endif /* TAPKEE_CONNECTED_H_ */
TAPKEE_INTERNAL_VECTOR< tapkee::IndexType > LocalNeighbors
Definition: synonyms.hpp:39
int IndexType
indexing type (non-overridable) set to int for compatibility with OpenMP 2.0
Definition: types.hpp:19
TAPKEE_INTERNAL_VECTOR< tapkee::tapkee_internal::LocalNeighbors > Neighbors
Definition: synonyms.hpp:40
bool is_connected(RandomAccessIterator begin, RandomAccessIterator end, const Neighbors &neighbors)
Definition: connected.hpp:18