Something went wrong. Try again.
Distances on Directed Graphs in R
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404#include "graph.h"
void graph::add_to_v2e_map (vert2edge_map_t &vert2edge_map, const vertex_id_t vid, const edge_id_t eid){ std::unordered_set <edge_id_t> edge_ids; if (vert2edge_map.find (vid) == vert2edge_map.end ()) { edge_ids.emplace (eid); vert2edge_map.emplace (vid, edge_ids); } else { edge_ids = vert2edge_map [vid]; edge_ids.insert (eid); vert2edge_map [vid] = edge_ids; }}
void graph::erase_from_v2e_map (vert2edge_map_t &vert2edge_map, const vertex_id_t vid, const edge_id_t eid){ std::unordered_set <edge_id_t> edge_ids = vert2edge_map [vid]; if (edge_ids.find (eid) != edge_ids.end ()) { edge_ids.erase (eid); vert2edge_map [vid] = edge_ids; }}
//' graph_has_components//'//' Does a graph have a vector of connected component IDs? Only used in//' \code{sample_one_vertex}//' @noRdbool graph::graph_has_components (const Rcpp::DataFrame &graph){ Rcpp::CharacterVector graph_names = graph.attr ("names"); for (auto n: graph_names) if (n == "component") return true;
return false;}
//' @name graph_from_df//'//' Convert a standard graph data.frame into an object of class graph. Graphs //' are standardised with the function \code{dodgr_convert_graph()$graph}, and//' contain only the four columns [from, to, d, w]//'//' @noRdbool graph::graph_from_df (const Rcpp::DataFrame &gr, vertex_map_t &vm, edge_map_t &edge_map, vert2edge_map_t &vert2edge_map){ Rcpp::StringVector edge_id = gr ["edge_id"]; Rcpp::StringVector from = gr ["from"]; Rcpp::StringVector to = gr ["to"]; Rcpp::NumericVector dist = gr ["d"]; Rcpp::NumericVector weight = gr ["d_weighted"]; Rcpp::StringVector colnames = gr.attr ("names"); bool has_times = false; Rcpp::NumericVector time, timew; if (gr.ncol () == 7) { has_times = true; time = gr ["time"]; timew = gr ["time_weighted"]; }
std::vector <edge_id_t> replacement_edges; // all empty here
for (R_xlen_t i = 0; i < to.length (); i ++) { Rcpp::checkUserInterrupt (); vertex_id_t from_id = std::string (from [i]); vertex_id_t to_id = std::string (to [i]);
if (vm.find (from_id) == vm.end ()) { vertex_t fromV = vertex_t (); vm.emplace (from_id, fromV); } vertex_t from_vtx = vm.at (from_id); from_vtx.add_neighbour_out (to_id); vm [from_id] = from_vtx;
if (vm.find (to_id) == vm.end ()) { vertex_t toV = vertex_t (); vm.emplace (to_id, toV); } vertex_t to_vtx = vm.at (to_id); to_vtx.add_neighbour_in (from_id); vm [to_id] = to_vtx;
edge_id_t edge_id_str = Rcpp::as <edge_id_t> (edge_id [i]);
double wt = weight [i]; if (weight [i] < 0.0) wt = INFINITE_DOUBLE; // # nocov
std::vector <double> weights; if (!has_times) weights = {dist [i], wt}; else weights = {dist [i], wt, time [i], timew [i]};
edge_t edge = edge_t (from_id, to_id, weights, edge_id_str, replacement_edges);
edge_map.emplace (edge_id_str, edge); graph::add_to_v2e_map (vert2edge_map, from_id, edge_id_str); graph::add_to_v2e_map (vert2edge_map, to_id, edge_id_str); }
return has_times;}
//' identify_graph_components//'//' Identify initial graph components for each **vertex**//' Identification for edges is subsequently performed with //' \code{rcpp_get_component_vector}.//'//' @param v unordered_map <vertex_id_t, vertex_t>//' @param com component map from each vertex to component numbers//' @noRdsize_t graph::identify_graph_components (vertex_map_t &v, std::unordered_map <vertex_id_t, size_t> &com){ // initialize components map std::unordered_set <vertex_id_t> all_verts; for (auto it: v) all_verts.emplace (it.first); com.clear ();
std::unordered_set <vertex_id_t> nbs_todo, nbs_done; nbs_todo.insert (*all_verts.begin ()); size_t compnum = 0; while (all_verts.size () > 0) { Rcpp::checkUserInterrupt (); vertex_id_t vt = (*nbs_todo.begin ()); all_verts.erase (vt);
vertex_t vtx = v.find (vt)->second; std::unordered_set <vertex_id_t> nbs = vtx.get_all_neighbours (); for (auto nvtx: nbs) { com.emplace (nvtx, compnum); if (nbs_done.find (nvtx) == nbs_done.end ()) nbs_todo.emplace (nvtx); } nbs_done.emplace (vt); com.emplace (vt, compnum); nbs_todo.erase (vt);
if (nbs_todo.size () == 0 && all_verts.size () > 0) { nbs_todo.insert (*all_verts.begin ()); compnum++; } }
long int largest_id = 0; if (compnum > 0) { std::vector <size_t> comp_sizes (compnum + 1, 0); for (auto c: com) comp_sizes [c.second]++; auto maxi = std::max_element (comp_sizes.begin (), comp_sizes.end ());
largest_id = std::distance (comp_sizes.begin (), maxi); }
return static_cast <size_t> (largest_id);}
//' strong_connect//'//' Helper function for applying Tarjan's algroithm to identify//' strong components recursively//'//' @param vt id of vertex currently being evaluated//' @param v unordered_map <vertex_id_t, vertex_t>//' @param com component map from each vertex to component numbers//' @param index_map map from each vertex to index number//' @param lowlink_map map from each vertex to lowlink number//' @param on_stack set of all vertices currently on stack//' @param s stack used to execute algorithm//' @param index used to execute algoritm//' @param compnum the current component number//' @noRdvoid graph::strong_connect(vertex_id_t vt, vertex_map_t &v, std::unordered_map <vertex_id_t, size_t> &com, std::unordered_map <vertex_id_t, size_t> &index_map, std::unordered_map <vertex_id_t, size_t> &lowlink_map, std::unordered_set <vertex_id_t> &on_stack, std::stack <vertex_id_t> &s, size_t &index, size_t &compnum){
Rcpp::checkUserInterrupt ();
index_map [vt] = index; lowlink_map [vt] = index; index++; s.push (vt); on_stack.insert (vt);
vertex_t vtx = v.find (vt)->second; std::unordered_set<vertex_id_t> nbs = vtx.get_out_neighbours ();
for (auto nvtx : nbs) { if (index_map.find (nvtx) == index_map.end ()) { strong_connect (nvtx, v, com, index_map, lowlink_map, on_stack, s, index, compnum); lowlink_map [vt] = std::min (lowlink_map [vt], lowlink_map [nvtx]); } else if (on_stack.find (nvtx) != on_stack.end ()) { lowlink_map [vt] = std::min (lowlink_map [vt], index_map [nvtx]); } }
if (lowlink_map [vt] == index_map [vt]) { vertex_id_t w; do { w = s.top (); s.pop (); on_stack.erase (w); com [w] = compnum; } while (w != vt); compnum++; }}
//' identify_graph_strong_components//'//' Identify initial graph strong components for each **vertex**//' Identification for edges is subsequently performed with //' \code{rcpp_get_component_vector}.//'//' @param v unordered_map <vertex_id_t, vertex_t>//' @param com component map from each vertex to component numbers//' @noRdsize_t graph::identify_graph_strong_components (vertex_map_t &v, std::unordered_map <vertex_id_t, size_t> &com){ com.clear ();
size_t index = 0; size_t compnum = 0;
std::unordered_map <vertex_id_t, size_t> index_map; std::unordered_map <vertex_id_t, size_t> lowlink_map; std::unordered_set <vertex_id_t> on_stack; std::stack <vertex_id_t> s;
for (auto it : v) { vertex_id_t vt = it.first; if (index_map.find (vt) == index_map.end ()) strong_connect (vt, v, com, index_map, lowlink_map, on_stack, s, index, compnum); }
long int largest_id = 0; if (compnum > 0) { std::vector <size_t> comp_sizes (compnum + 1, 0); for (auto c: com) comp_sizes [c.second]++; auto maxi = std::max_element (comp_sizes.begin (), comp_sizes.end ());
largest_id = std::distance (comp_sizes.begin (), maxi); }
return static_cast <size_t> (largest_id);}
//' rcpp_get_component_vector//'//' Get component numbers for each edge of graph//'//' @param graph graph to be processed; stripped down and standardised to five//' columns//'//' @param strong A Boolean flag to indicate whether components should be strong,//' i.e. its vertices connected bidirectionally. Defaults to FALSE.//'//' @return Two vectors: one of edge IDs and one of corresponding component//' numbers//' @noRd// [[Rcpp::export]]Rcpp::List rcpp_get_component_vector (const Rcpp::DataFrame &graph, bool strong = false){ vertex_map_t vertices; edge_map_t edge_map; vert2edge_map_t vert2edge_map;
bool has_times = graph::graph_from_df (graph, vertices, edge_map, vert2edge_map); has_times = false; // rm unused variable warning
std::unordered_map <vertex_id_t, size_t> components; size_t largest_component;
if (strong) largest_component = graph::identify_graph_strong_components (vertices, components); else largest_component = graph::identify_graph_components (vertices, components);
largest_component++; // suppress unused variable warning
// Then map component numbers of vertices onto edges std::unordered_map <edge_id_t, size_t> comp_nums; for (auto e : edge_map) { vertex_id_t vi = e.second.get_from_vertex (); comp_nums.emplace (e.first, components.find(vi)->second); }
Rcpp::StringVector edge_id (comp_nums.size ()); Rcpp::IntegerVector comp_num (comp_nums.size ()); size_t i = 0; for (auto cn: comp_nums) { edge_id (i) = cn.first; comp_num (i) = static_cast <int> (cn.second) + 1L; // 1-indexed for R i++; }
return Rcpp::List::create ( Rcpp::Named ("edge_id") = edge_id, Rcpp::Named ("edge_component") = comp_num);}
//' rcpp_unique_rownames//'//' Construct vertex (from, to) ID values from unique pairs of coordinates//' rounded to <precision>. Used when vertices have no ID values.//'//' @noRd// [[Rcpp::export]]Rcpp::DataFrame rcpp_unique_rownames (Rcpp::DataFrame xyfrom, Rcpp::DataFrame xyto, const int precision = 10){ const size_t prec_size_t = static_cast <size_t> (precision);
std::vector <double> xf = xyfrom ["x"], yf = xyfrom ["y"], xt = xyto ["x"], yt = xyto ["y"]; const size_t n = static_cast <size_t> (xyfrom.nrow ());
std::vector <std::string> s_f (n), s_t (n); std::vector <std::string> i_f (n), i_t (n); // indices as rownames std::unordered_map <std::string, std::string> xynames; size_t count = 0; for (size_t i = 0; i < n; i++) { std::string xfs = std::to_string (xf [i]), yfs = std::to_string (yf [i]), xts = std::to_string (xt [i]), yts = std::to_string (yt [i]); s_f [i] = xfs.substr(0, xfs.find(".") + prec_size_t + 1) + yfs.substr (0, yfs.find(".") + prec_size_t + 1); s_t [i] = xts.substr (0, xts.find(".") + prec_size_t + 1) + yts.substr (0, yts.find(".") + prec_size_t + 1);
if (xynames.find (s_f [i]) != xynames.end ()) { i_f [i] = xynames.at (s_f [i]); } else { i_f [i] = std::to_string (count); xynames.emplace (s_f [i], i_f [i]); count++; }
if (xynames.find (s_t [i]) != xynames.end ()) { i_t [i] = xynames.at (s_t [i]); } else { i_t [i] = std::to_string (count); xynames.emplace (s_t [i], i_t [i]); count++; } }
Rcpp::DataFrame res = Rcpp::DataFrame::create ( Rcpp::Named ("from_id") = i_f, Rcpp::Named ("to_id") = i_t, Rcpp::_["stringsAsFactors"] = false); return res;}