mpadge.tngl.sh
Distances on Directed Graphs in R
1#pragma once
2
3#include <Rcpp.h>
4#include <algorithm> // std::find
5#include <vector>
6#include <map>
7#include <limits>
8#include <string> // stoi
9#include <cmath> // round
10#include <math.h> // isnan
11
12const float INFINITE_FLOAT = std::numeric_limits <float>::max ();
13const double INFINITE_DOUBLE = std::numeric_limits <double>::max ();
14const long int INFINITE_INT = std::numeric_limits <long int>::max ();
15
16typedef std::string vertex_id_t, edge_id_t;
17typedef std::unordered_map <size_t,
18 std::unordered_set <size_t> > int2ints_map_t;
19
20struct edge_component
21{
22 // used only for edge sampling on graphs without component numbers
23 edge_id_t edge;
24 size_t component;
25};
26
27struct vertex_t
28{
29 private:
30 std::unordered_set <vertex_id_t> in, out;
31
32 public:
33 void add_neighbour_in (vertex_id_t vert_id) { in.insert (vert_id); }
34 void add_neighbour_out (vertex_id_t vert_id) { out.insert (vert_id); }
35 size_t get_degree_in () { return in.size (); }
36 size_t get_degree_out () { return out.size (); }
37
38 std::unordered_set <vertex_id_t> get_all_neighbours ()
39 {
40 std::unordered_set <vertex_id_t> all_neighbours = in;
41 all_neighbours.insert (out.begin (), out.end ());
42 return all_neighbours;
43 }
44
45 std::unordered_set <vertex_id_t> get_in_neighbours ()
46 {
47 return in;
48 }
49
50 std::unordered_set <vertex_id_t> get_out_neighbours ()
51 {
52 return out;
53 }
54
55 void replace_neighbour (vertex_id_t n_old, vertex_id_t n_new)
56 {
57 if (in.find (n_old) != in.end ())
58 {
59 in.erase (n_old);
60 in.insert (n_new);
61 }
62 if (out.find (n_old) != out.end ())
63 {
64 out.erase (n_old);
65 out.insert (n_new);
66 }
67 }
68
69 // in can equal out, so get_all_neighbours is vital here:
70 bool is_intermediate_single ()
71 {
72 return (in.size () == 1 && out.size () == 1 &&
73 get_all_neighbours ().size () == 2);
74 }
75
76 bool is_intermediate_double ()
77 {
78 return (in.size () == 2 && out.size () == 2 &&
79 get_all_neighbours ().size () == 2);
80 }
81};
82
83struct edge_t
84{
85 private:
86 vertex_id_t from, to;
87 edge_id_t id;
88 std::vector <edge_id_t> old_edges;
89
90 public:
91 double dist;
92 double weight;
93 double time;
94 double timew;
95 bool replaced_by_compact;
96
97 vertex_id_t get_from_vertex () { return from; }
98 vertex_id_t get_to_vertex () { return to; }
99 edge_id_t getID () { return id; }
100 std::vector <edge_id_t> get_old_edges () { return old_edges; }
101
102 edge_t (vertex_id_t from_id, vertex_id_t to_id,
103 std::vector <double> weights_in, edge_id_t id_in,
104 std::vector <edge_id_t> replacement_edges)
105 {
106 replaced_by_compact = false;
107 this -> to = to_id;
108 this -> from = from_id;
109 this -> dist = this -> weight = this -> time = weights_in [0];
110 if (weights_in.size () > 1)
111 this -> weight = weights_in [1];
112 if (weights_in.size () > 2)
113 this -> time = weights_in [2];
114 if (weights_in.size () > 3)
115 this -> timew = weights_in [3];
116 this -> id = id_in;
117 this -> old_edges.insert (old_edges.end (),
118 replacement_edges.begin (),
119 replacement_edges.end ());
120 }
121};
122
123
124typedef std::unordered_map <vertex_id_t, vertex_t> vertex_map_t;
125typedef std::unordered_map <edge_id_t, edge_t> edge_map_t;
126typedef std::unordered_map <vertex_id_t,
127 std::unordered_set <edge_id_t> > vert2edge_map_t;
128
129//----------------------------
130//----- functions in graph.cpp
131//----------------------------
132
133namespace graph {
134
135void add_to_v2e_map (vert2edge_map_t &vert2edge_map, const vertex_id_t vid,
136 const edge_id_t eid);
137
138void erase_from_v2e_map (vert2edge_map_t &vert2edge_map, const vertex_id_t vid,
139 const edge_id_t eid);
140
141bool graph_has_components (const Rcpp::DataFrame &graph);
142
143bool graph_from_df (const Rcpp::DataFrame &gr, vertex_map_t &vm,
144 edge_map_t &edge_map, vert2edge_map_t &vert2edge_map);
145
146size_t identify_graph_components (vertex_map_t &v,
147 std::unordered_map <vertex_id_t, size_t> &com);
148
149} // end namespace graph
150
151Rcpp::List rcpp_get_component_vector (const Rcpp::DataFrame &graph);
152
153Rcpp::DataFrame rcpp_unique_rownames (Rcpp::DataFrame xyfrom, Rcpp::DataFrame xyto,
154 const int precision);
155
156//----------------------------
157//----- functions in graph-sample.cpp
158//----------------------------
159
160namespace graph_sample {
161
162edge_component sample_one_edge_no_comps (vertex_map_t &vertices,
163 edge_map_t &edge_map);
164
165edge_id_t sample_one_edge_with_comps (Rcpp::DataFrame graph,
166 edge_map_t &edge_map);
167
168vertex_id_t sample_one_vertex (Rcpp::DataFrame graph, vertex_map_t &vertices,
169 edge_map_t &edge_map);
170
171vertex_id_t select_random_vert (Rcpp::DataFrame graph,
172 edge_map_t &edge_map, vertex_map_t &vertices);
173
174} // end namespace graph_sample
175
176Rcpp::StringVector rcpp_sample_graph (Rcpp::DataFrame graph,
177 size_t nverts_to_sample);
178
179//----------------------------
180//----- functions in graph-contract.cpp
181//----------------------------
182
183namespace graph_contract {
184
185void get_to_from (const edge_map_t &edge_map,
186 const std::unordered_set <edge_id_t> &edges,
187 const std::vector <vertex_id_t> &two_nbs,
188 vertex_id_t &vt_from, vertex_id_t &vt_to,
189 edge_id_t &edge_from_id, edge_id_t &edge_to_id);
190
191void contract_one_edge (vert2edge_map_t &vert2edge_map,
192 vertex_map_t &vertex_map, edge_map_t &edge_map,
193 const std::unordered_set <edge_id_t> &edgelist,
194 const vertex_id_t vtx_id, const vertex_id_t vt_from,
195 const vertex_id_t vt_to,
196 const edge_id_t edge_from_id, const edge_id_t edge_to_id,
197 const edge_id_t new_edge_id,
198 bool has_times);
199
200bool same_hwy_type (const edge_map_t &edge_map, const edge_id_t &e1,
201 const edge_id_t &e2);
202
203void contract_graph (vertex_map_t &vertex_map, edge_map_t &edge_map,
204 vert2edge_map_t &vert2edge_map,
205 std::unordered_set <vertex_id_t> verts_to_keep,
206 bool has_times);
207
208void sort_edges (
209 const std::vector <edge_id_t> &old_edges,
210 const std::unordered_map <edge_id_t, size_t> &edge_sequence,
211 std::vector <edge_id_t> &edges_sorted);
212
213} // end namespace graph_contract
214
215Rcpp::List rcpp_contract_graph (const Rcpp::DataFrame &graph,
216 Rcpp::Nullable <Rcpp::StringVector> &vertlist_in);
217
218Rcpp::NumericVector rcpp_merge_flows (Rcpp::DataFrame graph);