LCOV - code coverage report
Current view: top level - neighbors - connected.hpp (source / functions) Hit Total Coverage
Test: clean.info Lines: 22 22 100.0 %
Date: 2013-05-24 Functions: 2 2 100.0 %
Branches: 47 78 60.3 %

           Branch data     Line data    Source code
       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                 :         14 : bool is_connected(RandomAccessIterator begin, RandomAccessIterator end,
      19                 :            :                 const Neighbors& neighbors)
      20                 :            : {
      21 [ +  - ][ +  - ]:         14 :         timed_context context("Checking if graph is connected");
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
      22                 :            : 
      23                 :            :         // The number of data points
      24         [ +  - ]:         14 :         int N = end-begin;
      25                 :            :         // The number of neighbors used in KNN
      26                 :         14 :         IndexType k = neighbors[0].size();
      27                 :            : 
      28                 :            :         typedef std::stack<int> DFSStack;
      29                 :            :         typedef std::vector<bool> VisitedVector;
      30                 :            : 
      31 [ +  - ][ +  - ]:         14 :         VisitedVector visited(N, false);
      32 [ +  - ][ +  - ]:         14 :         DFSStack stack;
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
      33                 :         14 :         int nvisited = 0;
      34 [ +  - ][ +  - ]:         14 :         stack.push(0);
      35                 :            : 
      36 [ +  - ][ +  - ]:       2462 :         while (!stack.empty())
         [ +  - ][ +  - ]
      37                 :            :         {
      38 [ +  - ][ +  - ]:       2462 :                 int current = stack.top();
      39 [ +  - ][ +  - ]:       2462 :                 stack.pop();
      40                 :            : 
      41 [ +  + ][ +  + ]:       2462 :                 if (visited[current])
      42                 :       1592 :                         continue;
      43                 :            : 
      44                 :        870 :                 visited[current] = true;
      45                 :        870 :                 ++nvisited;
      46                 :            :                 
      47 [ +  + ][ +  + ]:        870 :                 if (nvisited == N) break;
      48                 :            : 
      49                 :        856 :                 const LocalNeighbors& current_neighbors = neighbors[current];
      50                 :            : 
      51 [ +  + ][ +  + ]:       9321 :                 for(IndexType j=0; j<k; ++j)
      52                 :            :                 {
      53                 :       8465 :                         int neighbor = current_neighbors[j];
      54   [ +  +  +  + ]:       8465 :                         if (!visited[neighbor])
      55 [ +  - ][ +  - ]:       4074 :                                 stack.push(neighbor);
      56                 :            :                 }
      57                 :            :         }
      58                 :            : 
      59 [ +  - ][ +  - ]:         14 :         return (nvisited==N);
         [ +  - ][ +  - ]
      60                 :            : }
      61                 :            : 
      62                 :            : } /* namespace tapkee_internal */
      63                 :            : } /* namespace tapkee */
      64                 :            : 
      65                 :            : #endif /* TAPKEE_CONNECTED_H_ */

Generated by: LCOV version 1.9