PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_lineGraph.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_lineGraph.hpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 Function's developer:
9 Copyright (c) 2017 Vidhan Jain
10 Mail: vidhanj1307@gmail.com
11 
12 ------
13 This program is free software; you can redistribute it and/or modify
14 it under the terms of the GNU General Public License as published by
15 the Free Software Foundation; either version 2 of the License, or
16 (at your option) any later version.
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  ********************************************************************PGR-GNU*/
25 
26 #ifndef INCLUDE_COMPONENTS_PGR_LINEGRAPH_HPP_
27 #define INCLUDE_COMPONENTS_PGR_LINEGRAPH_HPP_
28 #pragma once
29 
30 
31 #include <vector>
32 #include <set>
33 #include <utility>
34 #include <map>
35 
37 #include "cpp_common/line_vertex.h"
39 
40 namespace pgrouting {
41 
42 namespace graph {
43 template <class G, typename T_V, typename T_E>
45 } // namespace graph
46 
47 typedef graph::Pgr_lineGraph <
48 boost::adjacency_list < boost::vecS, boost::vecS,
49  boost::bidirectionalS,
52 
53 namespace graph {
54 
55 template <class G, typename T_V, typename T_E>
56 class Pgr_lineGraph : public Pgr_base_graph<G, T_V, T_E> {
57  private:
58  int64_t m_num_edges;
59  std::map < int64_t, pgr_edge_t > m_edges;
60  std::map < std::pair< int64_t, int64_t >, int64_t > m_vertex_map;
61 
62  void add_vertices(std::vector< T_V > vertices);
63 
64  void create_edges(const pgrouting::DirectedGraph& digraph);
65 
66  template < typename T >
67  void graph_add_edge(int64_t, const T &source, const T&target, int64_t, int64_t);
68 
69 #if 0
70  template < typename T >
71  void disconnect_edge(const T& from, const T& to);
72 
73  template < typename T >
74  void get_ids(std::vector< T >& restrictions);
75 
76  void create_virtual_vertex(int64_t id);
77  void create_virtual_edge(
78  int64_t source_id,
79  int64_t source_vertex,
80  int64_t target_id,
81  int64_t target_vertex
82  );
83 #endif
84 
85  public:
86  typedef typename boost::graph_traits < G >::vertex_descriptor V;
87  typedef typename boost::graph_traits < G >::edge_descriptor E;
88  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
89  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
90  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
91 
92  std::ostringstream log;
93 
96  m_num_edges(0) {
97  }
98 
99  template < typename T >
100  void insert_vertices(const T* edges, int64_t count) {
101  insert_vertices(std::vector < T >(edges, edges + count));
102  }
103 
104  template < typename T >
105  void insert_vertices(const std::vector < T > &edges) {
106 
107  for (auto &it: edges)
108  m_edges[it.id] = it;
109  std::vector < Line_vertex > vertices = extract_vertices();
110 
111 #if 1
112  log << "\nVertices of line graph: \n";
113  for (auto vertex: vertices) {
114  log << vertex.id << "(" << vertex.source << " - > ";
115  log << vertex.target << ")" << vertex.cost << "\n";
116  }
117 #endif
118 
119  add_vertices(vertices);
120  }
121 
122 #if 0
123  template < typename T >
124  std::vector< Restriction > remove_restricted_edges(std::vector< T >& restrictions) {
125  get_ids(restrictions);
126  std::vector< T > remaining;
127  for (const auto &r: restrictions) {
128  if (r.restriction_size() > 2) {
129  remaining.push_back(r);
130  continue;
131  }
132  disconnect_edge(r.restrict_edges()[0], r.restrict_edges()[1]);
133  }
134  return remaining;
135  }
136 #endif
137 
138  std::vector < Line_vertex > extract_vertices();
139 
141  create_edges(digraph);
142  }
143 
144 #if 0
145  void create_virtual_vertices();
146 #endif
147 
148  int64_t num_edges() const { return m_num_edges; }
149  std::vector< Line_graph_rt > get_postgres_results_undirected();
150  std::vector< Line_graph_rt > get_postgres_results_directed();
151 
152  friend std::ostream& operator<<(
153  std::ostream &log, const Pgr_lineGraph< G, T_V, T_E > &g) {
154  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
155 
156  for (auto vi = vertices(g.graph).first;
157  vi != vertices(g.graph).second; ++vi) {
158  if ((*vi) >= g.m_num_vertices) break;
159  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
160  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
161  out != out_end; ++out) {
162  log << ' '
163  << g.graph[*out].id << "=("
164  << g[g.source(*out)].id << ", "
165  << g[g.target(*out)].id << ")\t";
166  }
167  log << std::endl;
168  }
169  return log;
170  }
171 };
172 
173 template < class G, typename T_V, typename T_E >
174 std::vector< Line_graph_rt >
176  std::vector< Line_graph_rt > results;
177 
178  typename boost::graph_traits < G >::edge_iterator edgeIt, edgeEnd;
179  int64_t count = 0;
180 
181  log << "\nPostgres results\n";
182  for (boost::tie(edgeIt, edgeEnd) = boost::edges(this->graph);
183  edgeIt != edgeEnd; edgeIt++) {
184  E e = *edgeIt;
185  auto e_source = this->graph[this->source(e)].vertex_id;
186  auto e_target = this->graph[this->target(e)].vertex_id;
187 
188  log << "e_source = " << e_source << " | e_target = " << e_target << "\n";
189 
190  Line_graph_rt edge = {
191  ++count,
192  e_source,
193  e_target,
194  1.0,
195  -1.0
196  };
197  results.push_back(edge);
198  }
199 
200  return results;
201 }
202 
203 template < class G, typename T_V, typename T_E >
204 std::vector< Line_graph_rt >
206  std::vector< Line_graph_rt > results;
207 
208  typename boost::graph_traits < G >::edge_iterator edgeIt, edgeEnd;
209  std::map < std::pair<int64_t,int64_t >, Line_graph_rt > unique;
210  int64_t count = 0;
211 
212  log << "\nPostgres results\n";
213  for (boost::tie(edgeIt, edgeEnd) = boost::edges(this->graph);
214  edgeIt != edgeEnd; edgeIt++) {
215  E e = *edgeIt;
216  auto e_source = this->graph[this->source(e)].vertex_id;
217  auto e_target = this->graph[this->target(e)].vertex_id;
218 
219  log << "e_source = " << e_source << " | e_target = " << e_target << "\n";
220 
221  if(unique.find( {e_target, e_source} ) != unique.end()) {
222  unique[ std::pair<int64_t,int64_t>(e_target, e_source) ].reverse_cost = 1.0;
223  continue;
224  }
225  e_source *= -1;
226  e_target *= -1;
227  if(unique.find( {e_target, e_source} ) != unique.end()) {
228  unique[ std::pair<int64_t,int64_t>(e_target, e_source) ].reverse_cost = 1.0;
229  continue;
230  }
231  e_source *= -1;
232  e_target *= -1;
233 
234  Line_graph_rt edge = {
235  ++count,
236  e_source,
237  e_target,
238  1.0,
239  -1.0
240  };
241  unique[ std::pair<int64_t,int64_t>(e_source, e_target)] = edge;
242  }
243  for (const auto &edge: unique) {
244  results.push_back(edge.second);
245  }
246  return results;
247 }
248 
249 #if 0
250 template < class G, typename T_V, typename T_E >
251 template < typename T >
252 void
253 Pgr_lineGraph< G, T_V, T_E >::get_ids(std::vector< T >& restrictions) {
254  for (auto &r: restrictions) {
255  auto restrict_edges = r.restrict_edges();
256  std::vector < int64_t > temp;
257 
258  pgassert(m_edges.find(restrict_edges[0]) != m_edges.end());
259  auto prev = m_edges[restrict_edges[0]];
260 
261  for (auto i = 1; i < (int64_t)restrict_edges.size(); i++) {
262  pgassert(m_edges.find(restrict_edges[i]) != m_edges.end());
263  auto cur = m_edges[restrict_edges[i]];
264 
265  if (prev.target == cur.target) {
266  std::swap(cur.source, cur.target);
267  std::swap(cur.cost, cur.reverse_cost);
268  }
269 
270  if(prev.source == cur.source) {
271  std::swap(prev.source, prev.target);
272  std::swap(prev.cost, prev.reverse_cost);
273  }
274 
275  if(prev.source == cur.target) {
276  std::swap(prev.source, prev.target);
277  std::swap(prev.cost, prev.reverse_cost);
278  std::swap(cur.source, cur.target);
279  std::swap(cur.cost, cur.reverse_cost);
280  }
281 
282  pgassert(m_vertex_map.find( {prev.id, prev.source} ) != m_vertex_map.end());
283  pgassert(m_vertex_map.find( {cur.id, cur.source} ) != m_vertex_map.end());
284 
285  if (temp.empty()) {
286  temp.push_back( m_vertex_map[ {prev.id, prev.source} ] );
287  }
288 
289  temp.push_back( m_vertex_map[ {cur.id, cur.source} ] );
290  prev = cur;
291  }
292  r.clear();
293  for (const auto &it: temp) r.restrict_edges(it);
294  }
295 }
296 
297 template < class G, typename T_V, typename T_E >
298 template < typename T >
299 void
300 Pgr_lineGraph< G, T_V, T_E >::disconnect_edge(const T& from, const T& to) {
301 
302  pgassert(this->vertices_map.find(from) != this->vertices_map.end());
303  pgassert(this->vertices_map.find(to) != this->vertices_map.end());
304 
305  auto vm_s = this->get_V(from);
306  auto vm_t = this->get_V(to);
307 
308  boost::remove_edge(vm_s, vm_t, this->graph);
309 }
310 
311 template < class G, typename T_V, typename T_E >
312 void
313 Pgr_lineGraph< G, T_V, T_E >::create_virtual_vertex(int64_t id) {
314  ++(this->m_num_vertices);
315  auto v = add_vertex(this->graph);
316  this->vertices_map[this->m_num_vertices] = v;
317  this->graph[v].cp_members(this->m_num_vertices, id);
318  m_vertex_map[ {id, -1} ] = this->m_num_vertices;
319  pgassert(boost::num_vertices(this->graph) == this->num_vertices());
320 }
321 
322 template < class G, typename T_V, typename T_E >
323 void
324 Pgr_lineGraph< G, T_V, T_E >::create_virtual_edge(
325  int64_t source_id,
326  int64_t source_vertex,
327  int64_t target_id,
328  int64_t target_vertex) {
329  bool inserted;
331 
332  if (source_id < 0) source_id *= -1;
333  if (target_id < 0) target_id *= -1;
334 
335  pgassert(m_vertex_map.find( {source_id, source_vertex} ) !=
336  m_vertex_map.end());
337  pgassert(m_vertex_map.find( {target_id, target_vertex} ) !=
338  m_vertex_map.end());
339 
340  auto index_source_edge = m_vertex_map[ {source_id, source_vertex} ];
341  auto index_target_edge = m_vertex_map[ {target_id, target_vertex} ];
342 
343  auto vm_s = this->get_V(index_source_edge);
344  auto vm_t = this->get_V(index_target_edge);
345 
346  boost::tie(e, inserted) =
347  boost::add_edge(vm_s, vm_t, this->graph);
348 
349  ++m_num_edges;
350  this->graph[e].id = m_num_edges;
351 }
352 
353 template < class G, typename T_V, typename T_E >
354 void
355 Pgr_lineGraph< G, T_V, T_E >::create_virtual_vertices() {
356  V_i vertexIt, vertexEnd;
357  boost::tie(vertexIt, vertexEnd) = boost::vertices(this->graph);
358  for (;vertexIt != vertexEnd; vertexIt++) {
359  auto vertex = this->graph[*vertexIt];
360  if (!m_vertex_map.count( {vertex.source, -1} )) {
361  create_virtual_vertex(vertex.source);
362  }
363  if(!m_vertex_map.count( {vertex.target, -1} )) {
364  create_virtual_vertex(vertex.target);
365  }
366 
367  pgassert(m_vertex_map.find( {vertex.source, -1} ) !=
368  m_vertex_map.end());
369  pgassert(m_vertex_map.find( {vertex.target, -1} ) !=
370  m_vertex_map.end());
371 
372  create_virtual_edge(vertex.source, -1, vertex.vertex_id, vertex.source);
373  create_virtual_edge(vertex.vertex_id, vertex.source, vertex.target, -1);
374  }
375 }
376 #endif
377 
378 template < class G, typename T_V, typename T_E >
379 std::vector < Line_vertex >
381  /*
382  m_vertex_map stores a unique id assigned to each vertex of Line Graph.
383 
384  In case of a directed edge, either 1 or 2 vertices are to be created in
385  the Line Graph for each of the edges.
386  Consider the following edge in directed graph:-
387  ID = 1 | source = 2 | target = 3 | cost = 10 | reverse_cost = 20
388  This creates 2 vertices in Line Graph:-
389  1. ID = 1 | source = 2 | target = 3 | cost = 10
390  2. ID = 1 | source = 3 | target = 2 | cost = 25
391  So, the values stored in m_vertex_map would be:-
392  1. {1, 2} = 1(Denoting the edge from 2 - > 3 of cost 10).
393  2. {1, 3} = 2(Denoting the edge from 3 - > 2 of cost 25).
394  where {key} = value in m_vertex_map.
395 
396  In case of undirected edge, either 2 or 4 vertices are to be created in
397  the Line Graph for each of the edges.
398  Consider the following edge in an undirected graph:-
399  ID = 1 | source = 2 | target = 3 | cost = 10 | reverse_cost = 25
400  This creates the following 4 vertices in Line Graph:-
401  1. ID = 1 | source = 2 | target = 3 | cost = 10
402  2. ID = 1 | source = 3 | target = 2 | cost = 10
403  3. ID = 1 | source = 3 | target = 2 | cost = 25
404  4. ID = 1 | source = 2 | target = 3 | cost = 25
405  so, the values stored in m_vertex_map would be:-
406  1. {1, 2} = 1(Denoting the edge from 2 - > 3 of cost 10).
407  2. {-1, 3} = 2(Denoting the edge from 3 - > 2 of cost 10).
408  3. {1, 3} = 3(Deonting the edge from 3 - > 2 of cost 25).
409  4. {-1, 2} = 4(Denoting the edge from 2 - > 3 of cost 25).
410  where {key} = value in m_vertex_map.
411  */
412  if (m_edges.empty()) return std::vector< Line_vertex >();
413 
414  std::vector< Line_vertex > vertices;
415 
416 #if 0
417  log << "\nEdges of original graph\n";
418 #endif
419 
420  for (const auto &it : m_edges) {
421  auto edge = it.second;
423 
424 #if 1
425  log << "ID: " << edge.id;
426  log << "| source: " << edge.source;
427  log << "| target: " << edge.target;
428  log << "| cost: " << edge.cost;
429  log << "| reverse_cost: " << edge.reverse_cost << "\n\n";
430 #endif
431 
432  if (edge.cost > 0) {
433  vertex.id = (++(this->m_num_vertices));
434  vertices.push_back(vertex);
435  m_vertex_map[ std::pair<int64_t,int64_t>(edge.id, edge.source) ] = this->m_num_vertices;
436 
437  if (this->m_gType == UNDIRECTED) {
438  vertex.id = (++(this->m_num_vertices));
439  std::swap(vertex.source, vertex.target);
440  vertices.push_back(vertex);
441  m_vertex_map[std::pair<int64_t,int64_t>(-1*edge.id, edge.target)] = this->m_num_vertices;
442  std::swap(vertex.source, vertex.target);
443  }
444  }
445 
446  if (edge.reverse_cost > 0) {
447  vertex.id = (++(this->m_num_vertices));
448  vertex.cost = edge.reverse_cost;
449  vertex.vertex_id *= -1;
450  std::swap(vertex.source, vertex.target);
451  vertices.push_back(vertex);
452  m_vertex_map[ std::pair<int64_t,int64_t>(edge.id, edge.target) ] = this->m_num_vertices;
453 
454  if (this->m_gType == UNDIRECTED) {
455  vertex.id = (++(this->m_num_vertices));
456  std::swap(vertex.source, vertex.target);
457  vertices.push_back(vertex);
458  m_vertex_map[std::pair<int64_t,int64_t>(-1*edge.id, edge.source)] = this->m_num_vertices;
459  }
460  }
461  }
462 #if 0
463  for (auto it: m_vertex_map) {
464  log << it.first.first << " | " << it.first.second << " | " << it.second << "\n";
465  }
466 #endif
467  return vertices;
468 }
469 
470 template < class G, typename T_V, typename T_E >
471 template < typename T>
472 void
474  int64_t _id,
475  const T &source,
476  const T &target,
477  int64_t source_in_edge,
478  int64_t source_out_edge) {
479 
480  bool inserted;
482 
483  pgassert(m_vertex_map.find( {source, source_in_edge} ) !=
484  m_vertex_map.end());
485  pgassert(m_vertex_map.find( {target, source_out_edge} ) !=
486  m_vertex_map.end());
487 
488  auto index_source_edge = m_vertex_map[ std::pair<int64_t,int64_t>(source, source_in_edge) ];
489  auto index_target_edge = m_vertex_map[ std::pair<int64_t,int64_t>(target, source_out_edge) ];
490 
491 #if 0
492  log << "\nsource_in_edge = " << source_in_edge << " | "
493  << "source_out_edge = " << source_out_edge << " | "
494  << "index_source_edge = " << index_source_edge << " | "
495  << "index_target_edge = " << index_target_edge << " | "
496  << "edge.source = " << source << " | "
497  << "edge.target = " << target << "\n";
498 #endif
499 
500  auto vm_s = this->get_V(index_source_edge);
501  auto vm_t = this->get_V(index_target_edge);
502 
503  pgassert(this->vertices_map.find(index_source_edge) != this->vertices_map.end());
504  pgassert(this->vertices_map.find(index_target_edge) != this->vertices_map.end());
505 
506  boost::tie(e, inserted) =
507  boost::add_edge(vm_s, vm_t, this->graph);
508 
509  this->graph[e].id = _id;
510 }
511 
512 template < class G, typename T_V, typename T_E >
513 void
515  const pgrouting::DirectedGraph& digraph) {
516 
517  V_i vertexIt, vertexEnd;
518  EO_i e_outIt, e_outEnd;
519  EI_i e_inIt, e_inEnd;
520 
521  /*
522  for (each vertex v in original graph) {
523  for( all incoming edges inn to vertex v) {
524  for( all outgoing edges outt from vertex v) {
525  create an edge in the line graph(inn, outt);
526  }
527  }
528  }
529  */
530 
531  for(boost::tie(vertexIt, vertexEnd) = boost::vertices(digraph.graph);
532  vertexIt != vertexEnd; vertexIt++) {
533  V vertex = *vertexIt;
534 
535  for (boost::tie(e_outIt, e_outEnd) = boost::out_edges(vertex, digraph.graph);
536  e_outIt != e_outEnd; e_outIt++) {
537  for (boost::tie(e_inIt, e_inEnd) = boost::in_edges(vertex, digraph.graph);
538  e_inIt != e_inEnd; e_inIt++) {
539 
540 #if 0
541  log << "\n";
542  log << digraph.graph[*inIt].id << " | " << digraph[digraph.source(*inIt)].id << " | " << digraph[digraph.target(*inIt)].id << " | " << digraph.graph[*inIt].cost << "\n";
543  log << digraph.graph[*outIt].id << " | " << digraph[digraph.source(*outIt)].id << " | " << digraph[digraph.target(*outIt)].id << " | " << digraph.graph[*outIt].cost << "\n\n";
544 #endif
545 
546  /*
547  Prevent self-edges from being created in the Line Graph
548  */
549  if (labs(digraph.graph[*e_inIt].id) == labs(digraph.graph[*e_outIt].id))
550  continue;
551 
552  auto source_in_edge = digraph.source(*e_inIt);
553 
554 #if 0
555  log << "source = " << digraph[source_in_edge] << " | mid = " << digraph[vertex] << "\n\n\n";
556 #endif
557 
558  ++m_num_edges;
559 
560  graph_add_edge(
561  m_num_edges,
562  (digraph.graph[*e_inIt]).id,
563  (digraph.graph[*e_outIt]).id,
564  digraph[source_in_edge].id,
565  digraph[vertex].id
566  );
567  }
568  }
569  }
570 }
571 
572 template < class G, typename T_V, typename T_E >
573  void
575  std::vector< T_V > vertices) {
576 
577  for (const auto vertex : vertices) {
578  pgassert(this->vertices_map.find(vertex.id) == this->vertices_map.end());
579 
580  auto v = add_vertex(this->graph);
581  this->vertices_map[vertex.id] = v;
582  this->graph[v].cp_members(vertex);
583 
584  pgassert(boost::num_vertices(this->graph) == this->num_vertices());
585  }
586  return;
587  }
588 
589 } // namespace graph
590 } // namespace pgrouting
591 
592 #endif // INCLUDE_COMPONENTS_PGR_LINEGRAPH_HPP_
static edge_t edges[22573]
boost::graph_traits< G >::edge_descriptor E
std::vector< Line_graph_rt > get_postgres_results_undirected()
float8 cost
Definition: trsp.h:35
Definition: trsp.h:31
boost::graph_traits< G >::vertex_descriptor V
boost::graph_traits< G >::edge_descriptor E
graph::Pgr_lineGraph< boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, Line_vertex, Basic_edge >, Line_vertex, Basic_edge > LinearDirectedGraph
void transform(pgrouting::DirectedGraph &digraph)
long id
Definition: trsp.h:32
boost::graph_traits< G >::vertex_iterator V_i
void insert_vertices(const T *edges, int64_t count)
void graph_add_edge(int64_t, const T &source, const T &target, int64_t, int64_t)
std::vector< Line_vertex > extract_vertices()
friend std::ostream & operator<<(std::ostream &log, const Pgr_lineGraph< G, T_V, T_E > &g)
std::map< std::pair< int64_t, int64_t >, int64_t > m_vertex_map
std::map< int64_t, pgr_edge_t > m_edges
std::vector< Line_graph_rt > get_postgres_results_directed()
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
boost::graph_traits< G >::out_edge_iterator EO_i
void insert_vertices(const std::vector< T > &edges)
std::vector< Basic_vertex > extract_vertices(std::vector< Basic_vertex > vertices, const std::vector< pgr_edge_t > data_edges)
boost::graph_traits< G >::in_edge_iterator EI_i
void disconnect_edge(int64_t p_from, int64_t p_to)
Disconnects all edges from p_from to p_to.
void add_vertices(std::vector< T_V > vertices)
void create_edges(const pgrouting::DirectedGraph &digraph)
graphType
Definition: graph_enum.h:30
long target
Definition: trsp.h:34
float8 reverse_cost
Definition: trsp.h:36
long source
Definition: trsp.h:33