in flex/engines/hqps_db/core/operator/path_expand.h [762:941]
static auto path_expandp_multi_triplet(
const GRAPH_INTERFACE& graph,
const std::vector<std::array<label_id_t, 3>>&
edge_label_triplets, // src, dst, edge
const std::vector<label_id_t>& get_v_labels, const Direction& direction,
const std::vector<vertex_id_t>& vertices_vec,
const std::vector<label_id_t>& src_labels_set,
const std::vector<label_id_t>& src_v_labels_vec, const Range& range) {
std::vector<std::vector<vertex_id_t>> other_vertices;
std::vector<std::vector<label_id_t>> other_labels_vec;
std::vector<std::vector<offset_t>> other_offsets;
other_vertices.resize(range.limit_);
other_offsets.resize(range.limit_);
other_labels_vec.resize(range.limit_);
for (size_t i = 0; i < range.limit_; ++i) {
other_offsets[i].reserve(vertices_vec.size() + 1);
}
other_vertices[0].insert(other_vertices[0].end(), vertices_vec.begin(),
vertices_vec.end());
other_labels_vec[0] = src_v_labels_vec;
for (size_t i = 0; i < vertices_vec.size(); ++i) {
other_offsets[0].emplace_back(i);
}
other_offsets[0].emplace_back(vertices_vec.size());
// the input vertices can have many labels. Should be the union of
// src_vertex_labels and other_labels.
std::vector<label_id_t> src_label_candidates;
{
// insert src and dst labels in edge_label_triplets to
// src_label_candidates
for (auto& edge_label_triplet : edge_label_triplets) {
auto src_label = edge_label_triplet[0];
auto dst_label = edge_label_triplet[1];
src_label_candidates.emplace_back(src_label);
src_label_candidates.emplace_back(dst_label);
}
std::sort(src_label_candidates.begin(), src_label_candidates.end());
// dedup
auto last =
std::unique(src_label_candidates.begin(), src_label_candidates.end());
src_label_candidates.erase(last, src_label_candidates.end());
}
VLOG(10) << "src_label_candidates: " << gs::to_string(src_label_candidates);
// iterate for all hops
for (size_t cur_hop = 1; cur_hop < range.limit_; ++cur_hop) {
using nbr_list_type =
std::pair<std::vector<gs::mutable_csr_graph_impl::Nbr>, label_id_t>;
std::vector<std::vector<nbr_list_type>> nbr_lists;
nbr_lists.resize(other_vertices[cur_hop - 1].size());
std::vector<bool> indicator(other_vertices[cur_hop - 1].size(), false);
for (auto& src_other_label : src_label_candidates) {
// for each kind of src vertices, try each edge triplet.
label_id_t dst_other_label;
for (auto& edge_triplet : edge_label_triplets) {
if (direction == Direction::In) {
if (src_other_label != edge_triplet[1]) {
continue;
} else {
dst_other_label = edge_triplet[0];
}
} else if (direction == Direction::Out) {
if (src_other_label != edge_triplet[0]) {
continue;
} else {
dst_other_label = edge_triplet[1];
}
} else {
// both
if (src_other_label != edge_triplet[0] &&
src_other_label != edge_triplet[1]) {
continue;
} else {
if (src_other_label == edge_triplet[0]) {
dst_other_label = edge_triplet[1];
} else {
dst_other_label = edge_triplet[0];
}
}
}
auto cur_edge_label = edge_triplet[2];
std::vector<size_t> indices;
std::vector<vertex_id_t> other_vertices_for_cur_label;
std::tie(other_vertices_for_cur_label, indices) =
get_vertices_with_label(other_vertices[cur_hop - 1],
other_labels_vec[cur_hop - 1],
src_other_label);
if (indices.size() > 0) {
VLOG(10) << "Get vertices with label: "
<< std::to_string(src_other_label) << ", "
<< other_vertices_for_cur_label.size();
label_id_t real_src_label, real_dst_label;
if (direction == Direction::Out) {
real_src_label = src_other_label;
real_dst_label = dst_other_label;
} else {
// in or both.
real_src_label = dst_other_label;
real_dst_label = src_other_label;
}
auto cur_nbr_list = graph.GetOtherVertices(
real_src_label, real_dst_label, cur_edge_label,
other_vertices_for_cur_label, gs::to_string(direction),
INT_MAX);
{
size_t tmp_sum = 0;
for (size_t i = 0; i < cur_nbr_list.size(); ++i) {
tmp_sum += cur_nbr_list.get_vector(i).size();
}
VLOG(10) << "Get other vertices: " << cur_nbr_list.size()
<< ", nbr size: " << tmp_sum
<< ", from: " << std::to_string(real_src_label)
<< ", to: " << std::to_string(real_dst_label)
<< ", dst other_label: "
<< std::to_string(dst_other_label)
<< ", edge_label: " << std::to_string(cur_edge_label)
<< ", direction: " << gs::to_string(direction);
}
for (size_t i = 0; i < indices.size(); ++i) {
auto index = indices[i];
nbr_lists[index].emplace_back(cur_nbr_list.get_vector(i),
dst_other_label);
indicator[index] = true;
}
} else {
VLOG(10) << "No vertices with label: "
<< std::to_string(src_other_label);
}
}
}
// extract vertices from nbrs, and add them to other_vertices[cur_hop]
// and update other_offset
auto& cur_other_vertices = other_vertices[cur_hop];
auto& cur_other_offsets =
other_offsets[cur_hop]; // other_offset is always aligned with
// src_vertices.
auto& cur_other_labels_vec = other_labels_vec[cur_hop];
size_t cur_hop_new_vnum = 0;
for (size_t i = 0; i < nbr_lists.size(); ++i) {
for (auto& nbr_list_pair : nbr_lists[i]) {
cur_hop_new_vnum += nbr_list_pair.first.size();
}
}
VLOG(10) << "cur_hop_new_vnum: " << cur_hop_new_vnum;
cur_other_vertices.reserve(cur_hop_new_vnum);
// cur_other_offsets.reserve(cur_hop_new_vnum);
cur_other_labels_vec.reserve(cur_hop_new_vnum);
cur_other_offsets.reserve(vertices_vec.size() + 1);
// cur_other_offsets.emplace_back(0);
std::vector<offset_t> tmp_cur_offset;
tmp_cur_offset.reserve(cur_hop_new_vnum);
tmp_cur_offset.emplace_back(0);
size_t cur_cnt = 0;
for (size_t i = 0; i < nbr_lists.size(); ++i) {
for (auto& nbr_list_pair : nbr_lists[i]) {
auto cur_other_vertex_label = nbr_list_pair.second;
auto& nbr_list = nbr_list_pair.first;
for (size_t j = 0; j < nbr_list.size(); ++j) {
auto& nbr = nbr_list[j];
cur_other_vertices.emplace_back(nbr.neighbor());
cur_other_labels_vec.emplace_back(cur_other_vertex_label);
}
cur_cnt += nbr_list.size();
}
tmp_cur_offset.emplace_back(cur_cnt);
}
for (size_t i = 0; i < other_offsets[cur_hop - 1].size(); ++i) {
other_offsets[cur_hop].emplace_back(
tmp_cur_offset[other_offsets[cur_hop - 1][i]]);
}
}
return std::make_tuple(std::move(other_vertices),
std::move(other_labels_vec),
std::move(other_offsets));
}