pgr_contractionGraph.hpp

Go to the documentation of this file.

/*PGR-GNU*****************************************************************
File: pgr_contractionGraph.hpp
 
Generated with Template by:
Copyright (c) 2015 pgRouting developers
Mail: [email protected]
 
Function's developer:
Copyright (c) 2016 Rohith Reddy
Mail:
 
------
 
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
 
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
 
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 
 ********************************************************************PGR-GNU*/
 
#ifndef INCLUDE_CONTRACTION_PGR_CONTRACTIONGRAPH_HPP_
#define INCLUDE_CONTRACTION_PGR_CONTRACTIONGRAPH_HPP_
#pragma once
 
#include <boost/graph/iteration_macros.hpp>
 
#include <limits>
#include <algorithm>
#include <vector>
#include <iostream>
#include <tuple>
 
#include "cpp_common/pgr_base_graph.hpp"
#include "cpp_common/ch_vertex.h"
#include "cpp_common/ch_edge.h"
 
 
namespace pgrouting {
namespace graph {
 
template <class G>
class Pgr_contractionGraph : public Pgr_base_graph<G, CH_vertex, CH_edge> {
 public:
     typedef typename boost::graph_traits < G >::vertex_descriptor V;
     typedef typename boost::graph_traits < G >::edge_descriptor E;
     typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
     typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;
 
     explicit Pgr_contractionGraph<G>(graphType gtype)
         : Pgr_base_graph<G, CH_vertex, CH_edge >(gtype) {
         }
 
     Identifiers<V> find_adjacent_vertices(V v) const {
         EO_i out, out_end;
         EI_i in, in_end;
         Identifiers<V> adjacent_vertices;
 
         for (boost::tie(out, out_end) = out_edges(v, this->graph);
                 out != out_end; ++out) {
             adjacent_vertices += this->adjacent(v, *out);
         }
         for (boost::tie(in, in_end) = in_edges(v, this->graph);
                 in != in_end; ++in) {
             adjacent_vertices += this->adjacent(v, *in);
         }
         return adjacent_vertices;
     }
 
 
     std::tuple<double, Identifiers<int64_t>, bool>
     get_min_cost_edge(V u, V v) {
         E min_edge;
         Identifiers<int64_t> contracted_vertices;
         double min_cost = (std::numeric_limits<double>::max)();
         bool found = false;
 
         if (this->is_directed()) {
             BGL_FORALL_OUTEDGES_T(u, e, this->graph, G) {
                 if (this->target(e) == v) {
                     contracted_vertices += this->graph[e].contracted_vertices();
                     if (this->graph[e].cost < min_cost) {
                         min_cost = this->graph[e].cost;
                         min_edge = e;
                         found = true;
                     }
                 }
             }
             return std::make_tuple(min_cost, contracted_vertices, found);
         }
 
         pgassert(this->is_undirected());
         BGL_FORALL_OUTEDGES_T(u, e, this->graph, G) {
             if (this->adjacent(u, e) == v) {
                 contracted_vertices += this->graph[e].contracted_vertices();
                 if (this->graph[e].cost < min_cost) {
                     min_cost = this->graph[e].cost;
                     min_edge = e;
                     found = true;
                 }
             }
         }
         return std::make_tuple(min_cost, contracted_vertices, found);
     }
 
 
     friend
     std::ostream& operator <<(
             std::ostream &os,
             const Pgr_contractionGraph &g) {
         EO_i out, out_end;
         for (auto vi = vertices(g.graph).first;
                 vi != vertices(g.graph).second;
                 ++vi) {
             if ((*vi) >= g.num_vertices()) break;
             os << g.graph[*vi].id << "(" << (*vi) << ")"
                 << g.graph[*vi].contracted_vertices() << std::endl;
             os << " out_edges_of(" << g.graph[*vi].id << "):";
             for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
                     out != out_end; ++out) {
                 os << ' ' << g.graph[*out].id
                     << "=(" << g.graph[g.source(*out)].id
                     << ", " << g.graph[g.target(*out)].id << ") = "
                     <<  g.graph[*out].cost <<"\t";
             }
             os << std::endl;
         }
         return os;
     }
 
 
     void add_shortcut(const CH_edge &edge, V u, V v) {
         bool inserted;
         E e;
         if (edge.cost < 0) return;
 
         boost::tie(e, inserted) = boost::add_edge(u, v, this->graph);
 
         this->graph[e]= edge;
     }
 
 
     bool has_u_v_w(V u, V v, V w) const {
         return boost::edge(u, v, this->graph).second &&  boost::edge(v, w, this->graph).second;
     }
 
     bool is_shortcut_possible(
             V u,
             V v,
             V w) {
         if (u == v || v == w || u == w) return false;
         pgassert(u != v);
         pgassert(v != w);
         pgassert(u != w);
         if (this->is_undirected()) {
             /*
              * u - v - w
              */
             return has_u_v_w(u, v, w);
         }
 
         pgassert(this->is_directed());
         return
             /*
              * u <-> v <-> w
              */
             (has_u_v_w(u, v, w) && has_u_v_w(w, v, u))
             /*
              * u -> v -> w
              */
             ||
             (has_u_v_w(u, v, w) && !(boost::edge(v, u, this->graph).second || boost::edge(w, v, this->graph).second))
             /*
              * u <- v <- w
              */
             ||
             (has_u_v_w(w, v, u) && !(boost::edge(v, w, this->graph).second || boost::edge(u, v, this->graph).second));
     }
 
     bool is_linear(V v) {
         // Checking adjacent vertices constraint
         auto adjacent_vertices = find_adjacent_vertices(v);
 
         if (adjacent_vertices.size() == 2) {
             // Checking u - v - w
             V u = adjacent_vertices.front();
             adjacent_vertices.pop_front();
             V w = adjacent_vertices.front();
             adjacent_vertices.pop_front();
             if (is_shortcut_possible(u, v, w)) {
                 return true;
             }
             return false;
         }
         return false;
     }
};
 
}  // namespace graph
}  // namespace pgrouting
 
#endif  // INCLUDE_CONTRACTION_PGR_CONTRACTIONGRAPH_HPP_