SubgraphStruct ParallelSampler::khop()

in para_graph_sampler/graph_engine/backend/ParallelSampler.cpp [510:556]

• 45 lines of code
• 10 McCabe index (conditional complexity)

SubgraphStruct ParallelSampler::khop(
  std::vector<NodeType>& targets, 
  std::unordered_map<std::string, std::string>& config,
  std::set<std::string>& config_aug
) {
  int depth = std::stoi(config.at("depth"));
  int budget = std::stoi(config.at("budget"));
  double t1 = omp_get_wtime();
  std::vector<std::set<NodeType>> nodes_per_level;
  nodes_per_level.push_back(std::set<NodeType>());
  for (auto t : targets) {
    nodes_per_level[0].insert(t);
  }
  // traverse from roots
  for (int lvl = 0; lvl < depth; lvl++) {
    std::set<NodeType> nodes_frontier;
    for (auto v : nodes_per_level[lvl]) {
      NodeType deg = graph_full.indptr[v+1] - graph_full.indptr[v];
      if (deg <= budget || budget < 0) {
        for (NodeType i = graph_full.indptr[v]; i < graph_full.indptr[v+1]; i++) {
          nodes_frontier.insert(graph_full.indices[i]);
        }
      } else {
        for (int i = 0; i < budget; i++) {
          auto offset = rand()%deg;
          nodes_frontier.insert(graph_full.indices[graph_full.indptr[v] + offset]);
        }
      }
    }
    nodes_per_level.push_back(nodes_frontier);
  }
  // prepare nodes_touched
  std::unordered_map<NodeType, PPRType> nodes_touched;
  for (auto& nodes_layer : nodes_per_level) {
    for (auto node : nodes_layer) {
      nodes_touched.insert(std::make_pair(node, -1));
    }
  }
  double t2 = omp_get_wtime();
  auto add_self_edge = _extract_bool_config(config, "add_self_edge", false);
  auto include_target_conn = _extract_bool_config(config, "include_target_conn", false);
  auto ret = _node_induced_subgraph(nodes_touched, targets, add_self_edge, include_target_conn, config_aug);
  double t3 = omp_get_wtime();
  time_sampler_total += t2 - t1;
  time_induction_total += t3 - t2;
  return ret;
}