PGROUTING  2.6-dev
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_LINEGRAPH_PGR_LINEGRAPH_HPP_
27 #define INCLUDE_LINEGRAPH_PGR_LINEGRAPH_HPP_
28 #pragma once
29 
30 
31 #include <vector>
32 #include <set>
33 #include <utility>
34 #include <map>
35 #include <algorithm>
36 
38 #include "cpp_common/line_vertex.h"
39 
40 namespace pgrouting {
41 
42 namespace graph {
43 
44 template <class G, typename T_V, typename T_E>
45 class Pgr_lineGraph : public Pgr_base_graph<G, T_V, T_E> {
46  public:
47  typedef typename boost::graph_traits < G >::vertex_descriptor V;
48  typedef typename boost::graph_traits < G >::edge_descriptor E;
49  typedef typename boost::graph_traits < G >::vertex_iterator V_i;
50  typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
51  typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
52 
53 
56  }
57 
60  insert_vertices(digraph);
61  create_edges(digraph);
62  }
63 
64 
65  friend std::ostream& operator<<(
66  std::ostream &log, const Pgr_lineGraph< G, T_V, T_E > &g) {
67  typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;
68 
69  for (auto vi = vertices(g.graph).first;
70  vi != vertices(g.graph).second; ++vi) {
71  if ((*vi) >= g.num_vertices()) break;
72  log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
73  for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
74  out != out_end; ++out) {
75  log << ' '
76  << g.graph[*out].id << "=("
77  << g[g.source(*out)].id << ", "
78  << g[g.target(*out)].id << ")\t";
79  }
80  log << std::endl;
81  }
82  return log;
83  }
84 
85 
86  std::vector< Line_graph_rt >
88  std::vector< Line_graph_rt > results;
89 
90  typename boost::graph_traits < G >::edge_iterator edgeIt, edgeEnd;
91  std::map < std::pair<int64_t, int64_t >, Line_graph_rt > unique;
92  int64_t count = 0;
93 
94  for (boost::tie(edgeIt, edgeEnd) = boost::edges(this->graph);
95  edgeIt != edgeEnd; edgeIt++) {
96  E e = *edgeIt;
97  auto e_source = this->graph[this->source(e)].vertex_id;
98  auto e_target = this->graph[this->target(e)].vertex_id;
99 
100  if (unique.find({e_target, e_source}) != unique.end()) {
101  unique[std::pair<int64_t, int64_t>(e_target,
102  e_source)].reverse_cost = 1.0;
103  continue;
104  }
105  e_source *= -1;
106  e_target *= -1;
107  if (unique.find({e_target, e_source}) != unique.end()) {
108  unique[std::pair<int64_t, int64_t>(e_target,
109  e_source)].reverse_cost = 1.0;
110  continue;
111  }
112  e_source *= -1;
113  e_target *= -1;
114 
115  Line_graph_rt edge = {
116  ++count,
117  e_source,
118  e_target,
119  1.0,
120  -1.0
121  };
122  unique[std::pair<int64_t, int64_t>(e_source, e_target)] = edge;
123  }
124  for (const auto &edge : unique) {
125  results.push_back(edge.second);
126  }
127  return results;
128  }
129 
131  const pgrouting::DirectedGraph& digraph) {
132  auto es = boost::edges(digraph.graph);
133  for (auto eit = es.first; eit != es.second; ++eit) {
134  auto edge = *eit;
136  digraph[edge].id,
137  digraph[boost::source(edge, digraph.graph)].id,
138  digraph[boost::target(edge, digraph.graph)].id,
139  digraph[edge].cost,
140  -1});
142  }
143  }
144 
145 
146 
147  private:
148  template < typename T>
149  void
151  const T &source,
152  const T &target) {
153  bool inserted;
154  E e;
155 
156  auto vm_s = this->get_V(source);
157  auto vm_t = this->get_V(target);
158 
159  boost::tie(e, inserted) =
160  boost::add_edge(vm_s, vm_t, this->graph);
161 
162  this->graph[e].id = this->num_edges();
163  }
164 
166  const pgrouting::DirectedGraph& digraph) {
167  V_i vertexIt, vertexEnd;
168  EO_i e_outIt, e_outEnd;
169  EI_i e_inIt, e_inEnd;
170 
171 
172  /* for (each vertex v in original graph) */
173  for (boost::tie(vertexIt, vertexEnd) = boost::vertices(digraph.graph);
174  vertexIt != vertexEnd; vertexIt++) {
175  auto vertex = *vertexIt;
176 
177  /* for( all incoming edges in to vertex v) */
178  for (boost::tie(e_outIt, e_outEnd) =
179  boost::out_edges(vertex, digraph.graph);
180  e_outIt != e_outEnd;
181  e_outIt++) {
182  /* for( all outgoing edges out from vertex v) */
183  for (boost::tie(e_inIt, e_inEnd) =
184  boost::in_edges(vertex, digraph.graph);
185  e_inIt != e_inEnd; e_inIt++) {
186  /*
187  Prevent self-edges from being created in the Line Graph
188  */
189 
191  (digraph.graph[*e_inIt]).id,
192  (digraph.graph[*e_outIt]).id);
193  }
194  }
195  }
196  }
197 
199  T_V vertex) {
200  auto v = add_vertex(this->graph);
201  this->vertices_map[vertex.id] = v;
202  this->graph[v].cp_members(vertex);
203 
204  pgassert(boost::num_vertices(this->graph) == this->num_vertices());
205  return v;
206  }
207 
208  private:
209  std::map < int64_t, pgr_edge_t > m_edges;
210 
211  public:
212  std::ostringstream log;
213 };
214 } // namespace graph
215 } // namespace pgrouting
216 
217 #endif // INCLUDE_LINEGRAPH_PGR_LINEGRAPH_HPP_
boost::graph_traits< G >::edge_descriptor E
boost::graph_traits< G >::out_edge_iterator EO_i
Definition: trsp.h:31
boost::graph_traits< G >::vertex_descriptor V
void graph_add_edge(const T &source, const T &target)
V get_V(const T_V &vertex)
get the vertex descriptor of the vertex
boost::graph_traits< G >::vertex_iterator V_i
friend std::ostream & operator<<(std::ostream &log, const Pgr_lineGraph< G, T_V, T_E > &g)
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
boost::graph_traits< G >::in_edge_iterator EI_i
void insert_vertices(const pgrouting::DirectedGraph &digraph)
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
void create_edges(const pgrouting::DirectedGraph &digraph)
graphType
Definition: graph_enum.h:30
id_to_V vertices_map
id -> graph id