Voglio costruire un grafico a tempo esteso con discretizzazione temporale Dt che inizia a t = 0 e termina a t = T dove tra il nodo (n1, t) e il nodo (n2, t ') è un arco se e solo se (n1, n2) erano collegati nel grafico originale.
Come può essere implementato in pseudo-codice? Il problema su cui sono bloccato è come passare dal grafico originale al tempo espanso.
(Io uso le librerie C ++ e Boost per scrivere il codice)
Non è mai troppo tardi per rispondere a una domanda. Questo è come l'ho fatto, potrebbe aiutarti ragazzi.
Quindi, qual è il grafico espanso nel tempo e come lo facciamo? Controlla questo articolo , non così sofisticato che hai pensato.
Supponiamo di avere N nodi per il grafico statico (ovvero nessuna informazione sul tempo) e possiamo e abbiamo previsto il loro spostamento su una scala temporale di T con intervallo di t (i), dove t (i) è una funzione che indicare l'intervallo di tempo dopo l'ultimo punto temporale. Per semplificarlo, lascia che t (i) = 1, per l'intera scala temporale.
Come indicato dalla carta, abbiamo bisogno di tre passaggi per ottenere un grafico esteso nel tempo.
Allora, abbiamo finito. Per il codice boost, questo è mio:
// g_vec_ is vector of static graph
// g_vede_m_ is vector of map of Vertex descriptor
118 AdobDo_02(int node_number, int teg_layer_n, int max_range) {
119 // add all node to it node-n-t-i
120 Graph g;
121 map<string, VeDe> name2vd;
122 map<pair<string, string>, EdDe> pair2ed;
123 for (int n = 0; n < node_number; n++) {
124 for (int t = 0; t < teg_layer_n; t++) {
125 stringstream ss;
126 ss << "node-" << n << "-" << t;
127 VeDe tmp_d = add_vertex(VertexProperties(ss.str()), g);
128 name2vd[ss.str()] = tmp_d;
129 }
130 }
131 // add temporal link
132 // g_vec_ is vector of static graph
133 const int hypothetic_distance_of_temporal_link = 0;
134 for (int t = 0; t < teg_layer_n - 1; t++) {
135 for (int n = 0; n < node_number; n++) {
136 stringstream ss;
137 ss << "node-" << n << "-" << t;
138 auto name_0 = ss.str();
139 ss.str("");
140 ss << "node-" << n << "-" << t + 1;
141 auto name_1 = ss.str();
142 auto vd_0 = name2vd[name_0];
143 auto vd_1 = name2vd[name_1];
144 auto tmp_ed = add_edge(vd_0, vd_1, EdgeProperties(hypothetic_distance_of_temporal_link, 0), g);
145 }
146 }
147 // for each layer add transmit link if distance_ of link 'a' of static upper layer graph is under max_range
148 // and the distance of link 'b' of static lower layer graph is also under max_range
149 assert(g_vec_.size() >= teg_layer_n);
150 // assume that g_vede_m_ == teg_layer_n
151 for (int t = 0; t < teg_layer_n - 1; t++) {
152 auto tmp_g = g_vec_[t];
153 auto tmp_g_other = g_vec_[t + 1];
154 for (int i = 0; i < node_number; i++) {
155 for (int j = i; j < node_number; j++) {
156 auto i_d = g_vede_m_[t][i];
157 auto j_d = g_vede_m_[t][j];
158 auto e_p = edge(i_d, j_d, tmp_g);
159 auto i_d_other = g_vede_m_[t + 1][i];
160 auto j_d_other = g_vede_m_[t + 1][j];
161 auto e_p_other = edge(i_d_other, j_d_other, tmp_g_other);
162 if (e_p.second && e_p_other.second) {
163 auto ed = e_p.first;
164 auto ed_other = e_p_other.first;
165 if (tmp_g[ed].distance_ < max_range && tmp_g_other[ed_other].distance_ < max_range) {
166 auto tmp_id_of_g = g_vede_m_[t][i];
167 auto tmp_id_of_g_other = g_vede_m_[t + 1][i];
168 auto tmp_jd_of_g = g_vede_m_[t][j];
169 auto tmp_jd_of_g_other = g_vede_m_[t + 1][j];
170 auto tmp_edge_of_g = add_edge(tmp_id_of_g, tmp_jd_of_g_other, EdgeProperties(
171 (tmp_g[ed].distance_ / 2) + (tmp_g_other[ed_other].distance_ / 2), 1), g);
172 }
173 } else {
174 std::cerr << "Error: can't acess edge" << " : line " << __LINE__ << std::endl;
175 std::abort();
176 }
177 }
178 }
179 }
180 }