PGROUTING  3.2
pgr_lengauerTarjanDominatorTree_driver.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_lengauerTarjanDominatorTree_driver.hpp
3 
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
7 
8 Function's developer:
9 Copyright (c) 2020 Prakash Tiwari
11 
12 ------
13 
14 This program is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18 
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23 
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 
28  ********************************************************************PGR-GNU*/
29 
30 
31 #ifndef INCLUDE_DOMINATOR_PGR_LENGAUERTARJANDOMINATORTREE_DRIVER_HPP_
32 #define INCLUDE_DOMINATOR_PGR_LENGAUERTARJANDOMINATORTREE_DRIVER_HPP_
33 #pragma once
34 
35 
36 #include <boost/graph/adjacency_list.hpp>
37 #include <boost/graph/dominator_tree.hpp>
38 #include <boost/property_map/property_map.hpp>
39 #include <boost/property_map/vector_property_map.hpp>
40 #include <boost/type_traits.hpp>
41 
42 #include <vector>
43 #include <algorithm>
47 
48 
49 namespace pgrouting {
50 namespace functions {
51 
52 template<class G>
54  public:
55  typedef typename G::V Vertex;
56  typedef typename G::E_i E_i;
57  typedef typename G::V_i V_i;
58  std::vector <pgr_ltdtree_rt> pgr_ltdtree(
59  G &graph,
60  int64_t root
61  ){
62  std::vector<pgr_ltdtree_rt> results;
63  std::vector<int64_t> idoms = std::vector<int64_t>(boost::num_vertices(graph.graph), -1);
64  auto dominatorTree =
65  make_iterator_property_map
66  (idoms.begin(), boost::get(boost::vertex_index, graph.graph));
67  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
68  CHECK_FOR_INTERRUPTS();
69  try {
70  // calling the boost function
71  boost::lengauer_tarjan_dominator_tree(graph.graph, graph.get_V(root), dominatorTree);
72  } catch (boost::exception const& ex) {
73  (void)ex;
74  throw;
75  } catch (std::exception &e) {
76  (void)e;
77  throw;
78  } catch (...) {
79  throw;
80  }
81 
82  V_i v, vend;
83  for (boost::tie(v, vend) = vertices(graph.graph); v != vend; ++v) {
84  int64_t vid = graph[*v].id;
85  results.push_back({vid, (idoms[*v] != -1 ? (idoms[*v]+1) : 0) });
86  }
87 
88  return results;
89  }
90 };
91 } // namespace functions
92 } // namespace pgrouting
93 #endif // INCLUDE_DOMINATOR_PGR_LENGAUERTARJANDOMINATORTREE_DRIVER_HPP_
94 
pgrouting::Pgr_messages
Definition: pgr_messages.h:39
pgrouting::functions::Pgr_LTDTree::E_i
G::E_i E_i
Definition: pgr_lengauerTarjanDominatorTree_driver.hpp:56
interruption.h
pgrouting::functions::Pgr_LTDTree
Definition: pgr_lengauerTarjanDominatorTree_driver.hpp:53
pgr_base_graph.hpp
pgr_messages.h
pgrouting::functions::Pgr_LTDTree::pgr_ltdtree
std::vector< pgr_ltdtree_rt > pgr_ltdtree(G &graph, int64_t root)
Definition: pgr_lengauerTarjanDominatorTree_driver.hpp:58
pgrouting::functions::Pgr_LTDTree::V_i
G::V_i V_i
Definition: pgr_lengauerTarjanDominatorTree_driver.hpp:57
pgrouting::functions::Pgr_LTDTree::Vertex
G::V Vertex
Definition: pgr_lengauerTarjanDominatorTree_driver.hpp:55
pgrouting::alphashape::G
graph::Pgr_base_graph< BG, XY_vertex, Basic_edge > G
Definition: pgr_alphaShape.h:56
pgrouting::alphashape::V
boost::graph_traits< BG >::vertex_descriptor V
Definition: pgr_alphaShape.h:58
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56