Representation of time expanded graph

It's never too late to answer a question. This is how I did it, may help you guys.

So, what is time-expanded graph and how we do it? Check this paper, not that sophisticated you thought.

Assume we had N nodes for static graph(that's say no time information) and we can and we did predict their moving at a time scale of T with interval of t(i), where t(i) is a function that indicate time interval after last time point. To simplify it, let t(i) = 1, for whole time scale.

As, the paper indicate, we need three steps to get time-expanded graph.

1. We add nodes for our graph, naming node name as 'node-${n}-t-${i}'.
2. We add temporal link, for every 'node-n-t-${i}' for each n in range(0, n, 1), with 'EdgeProperty.color = 0' to distinct with transmit link.
3. We add transmit link, for every edge what both exist in graph of t(i) and graph of t(i + k), with 'EdgeProperty.color = k'. Here I would explain some for the 'color' : it express the delay of one transmit which was stated in that paper, if you don't care this, just let k = 1.

Then, we done. For boost code, this is mine :

    // 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                     }