Skip to content

Instantly share code, notes, and snippets.

@neoblizz
Last active Mar 15, 2022
Embed
What would you like to do?
Parallel SSSP using C++20.
#include <vector>
#include <algorithm>
#include <execution>
#include <mutex>
#include <utility>
#include <ranges>
struct frontier_t {
// Underlying representation of frontier.
std::vector<int> active_vertices;
// Get the number of active vertices.
int size() {
return active_vertices.size();
}
// Get the active vertex at a given index.
int get_active_vertex(int const& i) {
return active_vertices[i];
}
// Add a vertex to the frontier.
void add_vertex(int const& v) {
active_vertices.push_back(v);
}
};
// Compressed-Sparse Row (CSR) matrix.
struct csr_t {
int rows;
int cols;
std::vector<int> row_offsets;
std::vector<int> column_indices;
std::vector<float> values;
};
struct graph_t : public csr_t {
// Get edge weight for a given edge.
float get_edge_weight(int const& e) {
return values[e];
}
int get_num_vertices() { return rows; }
int get_dest_vertex(const int& e) { return column_indices[e]; }
auto get_edges(const int& v) { return std::ranges::iota_view{row_offsets[v], row_offsets[v+1]}; }
auto get_vertices() { return std::ranges::iota_view{0, get_num_vertices()}; }
};
// Neighbors expand implemented in C++ 20.
template<typename expand_cond_t>
frontier_t neighbors_expand(
graph_t& g,
frontier_t& f,
expand_cond_t condition
) {
std::mutex m;
frontier_t output;
auto expand = [&] (int const& v) {
// For all edges of vertex v.
for (auto e : g.get_edges(v)) {
auto n = g.get_dest_vertex(e);
auto w = g.get_edge_weight(e);
// If expand condition is
// true, add the neighbor into
// the output frontier.
if (condition(v, n, e, w)) {
std::lock_guard<std::mutex>
guard(m);
output.add_vertex(n);
}
}
};
// For all active vertices in the
// frontier, process in parallel.
std::for_each(std::execution::par,
f.active_vertices.begin(),
f.active_vertices.end(),
expand);
// Return the new output frontier.
return output;
}
namespace atomic {
template<typename T>
T min(T* a, T b) {
T old = *a;
T ans =std::min(old, b);
*a = ans;
return old;
}
}
std::vector<float> sssp(
graph_t& g,
int const& source
) {
// Initialize data.
std::vector<float> distances(g.get_num_vertices());
for (auto v : g.get_vertices())
distances[v] = std::numeric_limits<float>::max();
distances[source] = 0;
frontier_t f;
f.add_vertex(source);
std::vector<std::mutex> m_locks(g.get_num_vertices());
while(f.size() != 0) {
// Expand the frontier.
f = neighbors_expand(g, f,
// User-defined condition for SSSP.
[&](int const& src, // source
int const& dst, // destination
int const& edge, // edge
float const& weight // weight
) {
float new_d = distances[src] + weight;
// atomic::min atomically updates the distances array at dst with the minimum of new_d or its current value. And returns the old value. (eq: mutex updates)
std::lock_guard<std::mutex> guard(m_locks[dst]);
float curr_d = atomic::min(&distances[dst], new_d);
return new_d < curr_d;
});
}
return distances;
}
@neoblizz
Copy link
Author

neoblizz commented Feb 1, 2022

https://godbolt.org/z/8e4c6KMoG

Encoded link: https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DIApACYAQuYukl9ZATwDKjdAGFUtAK4sGIAMwAnKSuADJ4DJgAcj4ARpjEEtIADqgKhE4MHt6%2BAcGp6Y4C4ZExLPGJUraY9kUMQgRMxATZPn5B1bWZDU0EJdFxCUm2jc2tuR0Ko30RA%2BVDUgCUtqhexMjsHOb%2BEcjeWADUJv5uAG6YDiTH2CYaAILbu/uYRydiwCSECCzXtw9mOwYey8h2ObkwqguXjqv3ujyBz1ebhY0IhsP%2BgOBoJO0LohAAnuj4ViXmDiIZgJgFET7lNiF4HAcqMRZHgEgB9AhHADsVnuBwFBwA9EKDnIGFhiLR8RFgAdiJhkgqlIImHUDqgqEyWYI2cQAHR/QUHKboEAgc6XYhgiIEa4HJgOPDndnnZp4DbU/x8u7Go2CkUHADimC5BAQLwYg2IGq1jsc5wObscnsN/MFtpNeAAXpgIIseT7jcaFQQ1gwHU6XcmPVT9elc/njkXBSZuQARf0CwMhsMRysJl7JiEOrlMA7AZ2MA4RLCqNO%2BjOCCeh9nxqeuhIECEQTNoBhTcwANhnBbbLeL8tD5YHG5rnpMAFYLHgn53vV2eZ3093RXd0OgDpJluI5EAc4YvMyrIJAuxqnKgeCAUwAGbs0O57gIh5mCepxnryn7Guu1ZbrWCj6skXgKAg7KxI6ADWEC4c2n5tt%2BDwdsxcL3IGHgsEqVJKOgAC0QjJE0SgHAASqgADuBwQG4QiSQWLBqsQeDzn8dIMlyyAKMQnKFp%2BmYsjJXoXjOy5oLQ5mfqa5qWkQ1onLa9qmeympUEoBC2T%2BJoEGaFoXE5NqCPa1ltOys6kZxi4CvZQVWmCVC0Kgar2qcYheFSsWsbltIEPSjLAOSyTUVyIAHBRsS0B6Bx6QZXLnp%2BPahgcmDoJSBwyZgeDAAgXL8DG46TucFYdZSsGCilaVcpSBDshNmDsj1fUDbuVmYXa2HtXhFkltexAVpl3g5c%2BmBvrFfocVxcWWXNq5RiwqEplS%2BaFleZZHfKsnmV%2BxnLvN7JYFML07vuUz3ceu0faWN4Rb4UUSjF52Xd6/1%2BUw0KoCuC1LQoEAQ1yrk7bhsOHRWCXkkYVLmk4jSumyMnnu5nnedSz6nG%2BpA/TJHlUF5oYcxYXOWFwl0cejeWY9juMvaR73np9N5UxStMgPTTCM5gzO8hoPNA098uek2ksWBj7Hvj6fyBlEvX9bEJAKO1qhiRKM58fQbCCB1lkHG41jWAcZgaAu26e2qF0nAQ%2BLJIwrAvBCbvoOy%2B4p3a/g3PcUG6hyXKRGtjvEAoi2u4Y6AQJ%2BJVMGVnLQ8APOfjnjh59DVCN35Sfl6nAjp/VvcZAIfx7XZAXmii26qAcPwfn5zd6oZqwEBRGcWVjYFd%2B7xztkcz7Hm%2B8kYQe204SPfnGoGABiJAOrQtDtZ1VKxsBaFT6cU2XkN8nrzjLyVcA%2Bogb40YosM%2Bd1LwCh/gcCs28JyANXCDBaw5VAQEwIsK6EDCKyzkrAgBQDH4rXtutNBGDMG/gOAASS1JvQCadB4VjwNSc%2BEDAyFWyjzZCgEILQKIUXe6qACIsNFNwpeK9tTQQNIIy8eAtSEwHnURiPMGA80wDzGSoCjLMLIf5QKqVkB0XZMALwTR0BggShPNEmcjhaO0YKIxJiIAsHQbPcBtjRHQn1JwsGKCGDOP2hA6WriBSBOulbP4LVRTX2GnfW8iZ7xPwiOBCMETxG5zIFVFknpnaJLEuSO%2BNQP46PNENRajoEAQAShCKEdRzS5I7kEpkniqzLXiWReIk4GD5nqZgqgTTBzGzrK4Lp1iGk0L8SxPygZJIUySZGHWGpoRiPnjBT8cNvruNXuEm6Dx7jMDYAoMSGxRyoBYHVZqflw7JAMNuMEMc457JeAAFXRMaR508IgQEeQAKgdDzN5sQwGYLeZ4QCsCvlMFIcWN5hhnbb3MR8kFPMAWQuNOC14O8YUosFGsisILIWBIJQVQKjkrgnBmulKxCgqXJErjY401da4nwnKQKRxYj5YRPAoVY6wLr3EBQGUUFCGAZDEDmF46A1RMEKQlElzk3DkoztgA4%2BApiGBNngx6PgBkE1AZCr%2BEAoGnAOP/eBSCSIm11TYlVjQgRnRFgfWBCUnoJA9OyWqpyfLJVShS7A48mAoPGX5a1aq7VcrWBsB1/gd4aD1TqFujUmR6s8ShZBFTuUbEDTsu6MrgqkrcOY1Eqh7TPT0XRAmGqFpG1afmTNn4ZIIDoHmXpDY8wFjAGAWBGh%2BWXkDNgMu7tuHLMkTYrUsCC4OydqXZO0Aebt1ZYGRQCQhJYBoJEWh8jMhMhvkIHdyh9QjMwU%2BKw2E3wbV0ltaG%2BlkA8wvqKMNPLWXGnZUy9AUwb0CuVVSRwzB1SPqXOe4%2B0MlrvuFKKJaf6BQKv7oBnaq1%2BpckDHBgarLu1kKg5EPmoKo3KsYTah8z4r0OssN1Ihmy6UfrVCcj049EmUdOaIO%2B%2BIDheGSBK7cztuHBttc7Jo5ImNqmVZDGSXxZnvOFSiFgz8MPAw1DGQgztkBrAVMuE62V913Hdjijj/YQVJiypgfdqCACOlULFTxY2xqk6DyOQe9bpJTMnYF0eoyAU5nTjxcfwxYV9dpHztiUTrYGmbbHK2%2BtJrDbh6oOdMS4w9HZgutm2QdL6FZPM5RcaxDgyxaCcEfLwPwHAtCkFQJwAOlgg73qOdsHgpACCaCy8sOiIBHz6xyxwSQ%2BX6vFc4LwBQIB9Z1cK1l0gcBYAwEQCgE5yRG1kAoHIviM2QDAC4FwMwfA6DbmLpQWIXXYgRCaPiTgNW0AsG9gQAA8gwaUXWsCqSMOIIbpB8AKmaX1x7VTFPbiO7wW0NQuu1ViOSYg%2BIPBYC64VPALBvvLBSkwYACgABqTNzv3O%2BzIQQIgxDsCqPwQQi61Bdd0FwfQFIUCB0sPoPAsQ%2BuQGWKgZIdQ3tCVNNvUw5XLAh16zUYKmQXASnGH4YnYRZhlAqHoAo9CBfi7SPQ/oouFidB5wIHoYxPBtD0HYJX9Rphy%2BjBr6YUviequaLr%2BYlRliVex7VhUmweDZdy51x7JWOCqAABxHiEkeSQE5kDIAOCt/UZh5JlePTYA4uBCA32qzzXi036Axmq4sXgg2tCgNIE1lr%2BhOAddIFDzPBWivO96/12r9XlijYmxs8glATtx4Vx1SPlR0fCAY9j6QuP5BKAJ49wqmBbe8BkqVaHWeOB5dIAX3gzvzuLOhM/N3Huvc%2B79wHoPCkpszaOACLgSfS9DbTxGZCQwultZz3n/WE/uscGLwNsvjXmutc4P4R3heeu79T/bjgZhn%2BT9fynhrpA3R0hnBJAgA%3D%3D%3D

@neoblizz
Copy link
Author

neoblizz commented Feb 15, 2022

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment