1
#include <Rcpp.h>
2

3
using namespace Rcpp;
4
using namespace std;
5
// [[Rcpp::export]]
6 1
NumericMatrix dependency(std::vector<std::vector<int> > adj) {
7 1
  int n=adj.size();
8 1
  std::vector<std::vector<int> > Pred(n);
9 1
  std::vector<int> dist(n,-1);
10 1
  std::vector<int> sigma(n);
11 1
  std::vector<double> delta(n);
12 1
  NumericMatrix rel(n,n);
13 1
  std::vector<int> Q;
14 1
  List S;
15
  
16 1
  NumericVector bc(n);
17
  
18 1
  for(int s=0;s<n; ++s){
19
    /* SSP */
20 1
    for(int w=0;w<n; ++w){
21 1
      Pred[w].clear();
22 1
      dist[w]=-1;
23 1
      sigma[w]=0;
24
    }
25 1
    dist[s]=0;
26 1
    sigma[s]=1;
27 1
    Q.push_back(s);
28 1
    while(!Q.empty()){
29 1
      Rcpp::checkUserInterrupt();
30 1
      int v=Q[0];
31 1
      Q.erase(Q.begin());
32 1
      S.push_front(v);
33 1
      std::vector<int> Nv=adj[v];
34 1
      int m = Nv.size();
35 1
      for(int i=0; i<m; ++i){
36 1
        int w=Nv[i];
37
        /* path discovery */
38 1
        if(dist[w]<0){
39 1
          dist[w]=dist[v]+1;
40 1
          Q.push_back(w);
41
        }
42
        /* path counting */
43 1
        if(dist[w]==dist[v]+1){
44 1
          sigma[w]=sigma[w]+sigma[v];
45 1
          Pred[w].push_back(v);
46
        }
47
      }
48
    }
49
    /* accumulation */
50 1
    for(int v=0; v<n;++v){
51 1
      delta[v]=0;
52
    }
53 1
    while(S.size()>0){
54 1
      Rcpp::checkUserInterrupt();
55 1
      int w=S[0];
56 1
      S.erase(S.begin());
57 1
      int m = Pred[w].size();
58 1
      for(int i=0;i<m; ++i){
59 1
        int v=Pred[w][i];
60 1
        delta[v]+=double(sigma[v])/double(sigma[w])*(1+delta[w]);
61
      }
62 1
      if(w!=s){
63 1
        rel(w,s)+=delta[w];
64
      }
65
      
66
    }
67
  }
68 1
  return rel;
69
}
70

71

Read our documentation on viewing source code .

Loading