pgr_base_graph.hpp

Go to the documentation of this file.

/*PGR-GNU*****************************************************************
 *

Copyright (c) 2015 Celia Virginia Vergara Castillo
vicky_vergara@hotmail.com

------

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

#pragma once
#if defined(__MinGW32__) || defined(_MSC_VER)
#include <winsock2.h>
#include <windows.h>
#undef min
#undef max
#ifdef open
#undef open
#endif
#endif



#include <boost/graph/iteration_macros.hpp>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

#include <deque>
#include <vector>
#include <set>
#include <map>
#include <limits>

#include "./pgr_types.h"  // for pgr_edge_t

#include "./ch_vertex.h"
#include "./ch_edge.h"
#include "./basic_vertex.h"
#include "./xy_vertex.h"

#include "./basic_edge.h"
#include "./pgr_assert.h"

namespace pgrouting {

namespace graph {
template <class G, typename Vertex, typename Edge>
class Pgr_base_graph;

}  // namespace graph


typedef graph::Pgr_base_graph <
boost::adjacency_list < boost::vecS, boost::vecS,
    boost::undirectedS,
    Basic_vertex, Basic_edge >,
    Basic_vertex, Basic_edge > UndirectedGraph;

typedef graph::Pgr_base_graph <
boost::adjacency_list < boost::vecS, boost::vecS,
    boost::bidirectionalS,
    Basic_vertex, Basic_edge >,
    Basic_vertex, Basic_edge > DirectedGraph;

typedef graph::Pgr_base_graph <
boost::adjacency_list < boost::listS, boost::vecS,
    boost::undirectedS,
    XY_vertex, Basic_edge >,
    XY_vertex, Basic_edge > xyUndirectedGraph;

typedef graph::Pgr_base_graph <
boost::adjacency_list < boost::listS, boost::vecS,
    boost::bidirectionalS,
    XY_vertex, Basic_edge >,
    XY_vertex, Basic_edge > xyDirectedGraph;

#if 0
// TODO(Rohith) this is only used on internal query tests
typedef graph::Pgr_base_graph <
boost::adjacency_list < boost::listS, boost::vecS,
    boost::undirectedS,
    contraction::Vertex, Basic_edge >,
    contraction::Vertex, Basic_edge > CUndirectedGraph;

typedef graph::Pgr_base_graph <
boost::adjacency_list < boost::listS, boost::vecS,
    boost::bidirectionalS,
    contraction::Vertex, Basic_edge >,
    contraction::Vertex, Basic_edge > CDirectedGraph;
#endif



namespace graph {

template <class G, typename T_V, typename T_E>
class Pgr_base_graph {
 public:
     typedef G B_G;
     typedef typename boost::graph_traits < G >::vertex_descriptor V;
     typedef typename boost::graph_traits < G >::edge_descriptor E;
     typedef typename boost::graph_traits < G >::vertex_iterator V_i;
     typedef typename boost::graph_traits < G >::edge_iterator E_i;
     typedef typename boost::graph_traits < G >::out_edge_iterator EO_i;
     typedef typename boost::graph_traits < G >::in_edge_iterator EI_i;

     typedef typename boost::graph_traits < G >::vertices_size_type
         vertices_size_type;
     typedef typename boost::graph_traits < G >::edges_size_type
         edges_size_type;
     typedef typename boost::graph_traits < G >::degree_size_type
         degree_size_type;



     typedef typename std::map< int64_t, V > id_to_V;
     typedef typename id_to_V::const_iterator LI;



     G graph;                
     size_t m_num_vertices;  
     graphType m_gType;      




     id_to_V  vertices_map;   




     std::deque< T_E > removed_edges;






     Pgr_base_graph< G , T_V, T_E >(
             const std::vector< T_V > &vertices, graphType gtype)
         : graph(vertices.size()),
         m_num_vertices(vertices.size()),
         m_gType(gtype) {
             pgassert(boost::num_vertices(graph) == num_vertices());
             pgassert(boost::num_vertices(graph) == vertices.size());
#if 0
             // This code does not work with contraction
             pgassert(pgrouting::check_vertices(vertices) == 0);
#endif
             size_t i = 0;
             for (auto vi = boost::vertices(graph).first;
                     vi != boost::vertices(graph).second; ++vi) {
                 vertices_map[vertices[i].id] = (*vi);
                 graph[(*vi)].cp_members(vertices[i++]);
             }
         }

     explicit Pgr_base_graph< G , T_V, T_E >(graphType gtype)
         : graph(0),
         m_num_vertices(0),
         m_gType(gtype) {
         }




     template < typename T >
         void graph_insert_data(const T *edges, int64_t count) {
             graph_insert_data(std::vector < T >(edges, edges + count));
         }
     template < typename T >
         void graph_insert_data(const std::vector < T > &edges) {
#if 0
             // This code does not work with contraction
             if (num_vertices() == 0) {
                 auto vertices = pgrouting::extract_vertices(edges);
                 pgassert(pgrouting::check_vertices(vertices) == 0);
                 add_vertices(vertices);
             }
#endif
             for (const auto edge : edges) {
                 graph_add_edge(edge);
             }
         }

 private:
     void add_vertices(std::vector< T_V > vertices);

 public:


     degree_size_type out_degree(int64_t vertex_id) const {
         if (!has_vertex(vertex_id)) {
             return 0;
         }
         return out_degree(get_V(vertex_id));
     }


     V get_V(const T_V &vertex) {
         auto vm_s(vertices_map.find(vertex.id));
         if (vm_s == vertices_map.end()) {
             auto v =  add_vertex(graph);
             graph[v].cp_members(vertex);
             vertices_map[vertex.id] =  v;
             return v;
         }
         return vm_s->second;
     }

     V get_V(int64_t vid) const {
         pgassert(has_vertex(vid));
         return vertices_map.find(vid)->second;
     }

     bool has_vertex(int64_t vid) const {
         return vertices_map.find(vid) != vertices_map.end();
     }

     degree_size_type in_degree(V &v) const {
         return boost::in_degree(v, graph);
     }

     degree_size_type out_degree(V &v) const {
         return boost::out_degree(v, graph);
     }





     void disconnect_edge(int64_t p_from, int64_t p_to);



     void disconnect_out_going_edge(int64_t vertex_id, int64_t edge_id);





     void disconnect_vertex(int64_t p_vertex);
     void disconnect_vertex(V vertex);


     void restore_graph();




     friend std::ostream& operator<<(
             std::ostream &log, const Pgr_base_graph< G, T_V, T_E > &g) {
         typename Pgr_base_graph< G, T_V, T_E >::EO_i out, out_end;

         for (auto vi = vertices(g.graph).first;
                 vi != vertices(g.graph).second; ++vi) {
             if ((*vi) >= g.m_num_vertices) break;
             log << (*vi) << ": " << " out_edges_of(" << g.graph[(*vi)] << "):";
             for (boost::tie(out, out_end) = out_edges(*vi, g.graph);
                     out != out_end; ++out) {
                 log << ' '
                     << g.graph[*out].id << "=("
                     << g.graph[source(*out, g.graph)].id << ", "
                     << g.graph[target(*out, g.graph)].id << ") = "
                     << g.graph[*out].cost <<"@t";
             }
             log << std::endl;
         }
         return log;
     }



     int64_t get_edge_id(V from, V to, double &distance) const;

     size_t num_vertices() const { return boost::num_vertices(graph);}

     T_V operator[](V v) const {
         return graph[v];
     }


     void graph_add_edge(const T_E &edge);

     template < typename T >
         void graph_add_edge(const T &edge);
};




template < class G, typename T_V, typename T_E >
void
Pgr_base_graph< G, T_V, T_E >::disconnect_edge(int64_t p_from, int64_t p_to) {
    T_E d_edge;

    // nothing to do, the vertex doesn't exist
    if (!has_vertex(p_from) || !has_vertex(p_to)) return;

    EO_i out, out_end;
    V g_from(get_V(p_from));
    V g_to(get_V(p_to));

    // store the edges that are going to be removed
    for (boost::tie(out, out_end) = out_edges(g_from, graph);
            out != out_end; ++out) {
        if (target(*out, graph) == g_to) {
            d_edge.id = graph[*out].id;
            d_edge.source = graph[source(*out, graph)].id;
            d_edge.target = graph[target(*out, graph)].id;
            d_edge.cost = graph[*out].cost;
            removed_edges.push_back(d_edge);
        }
    }
    // the actual removal
    boost::remove_edge(g_from, g_to, graph);
}



template < class G, typename T_V, typename T_E >
void
Pgr_base_graph< G, T_V, T_E >::disconnect_out_going_edge(
        int64_t vertex_id, int64_t edge_id) {
    T_E d_edge;

    // nothing to do, the vertex doesn't exist
    if (!has_vertex(vertex_id)) return;
    auto v_from(get_V(vertex_id));

    EO_i out, out_end;
    bool change = true;
    // store the edge that are going to be removed
    while (change) {
        change = false;
        for (boost::tie(out, out_end) = out_edges(v_from, graph);
                out != out_end; ++out) {
            if (graph[*out].id  == edge_id) {
                d_edge.id = graph[*out].id;
                d_edge.source = graph[source(*out, graph)].id;
                d_edge.target = graph[target(*out, graph)].id;
                d_edge.cost = graph[*out].cost;
                removed_edges.push_back(d_edge);
                boost::remove_edge((*out), graph);
                change = true;
                break;
            }
        }
    }
}


template < class G, typename T_V, typename T_E >
void
Pgr_base_graph< G, T_V, T_E >::disconnect_vertex(int64_t vertex) {
    if (!has_vertex(vertex)) return;
    disconnect_vertex(get_V(vertex));
}

template < class G, typename T_V, typename T_E >
void
Pgr_base_graph< G, T_V, T_E >::disconnect_vertex(V vertex) {
    T_E d_edge;

    EO_i out, out_end;
    // store the edges that are going to be removed
    for (boost::tie(out, out_end) = out_edges(vertex, graph);
            out != out_end; ++out) {
        d_edge.id = graph[*out].id;
        d_edge.source = graph[source(*out, graph)].id;
        d_edge.target = graph[target(*out, graph)].id;
        d_edge.cost = graph[*out].cost;
        removed_edges.push_back(d_edge);
    }

    // special case
    if (m_gType == DIRECTED) {
        EI_i in, in_end;
        for (boost::tie(in, in_end) = in_edges(vertex, graph);
                in != in_end; ++in) {
            d_edge.id = graph[*in].id;
            d_edge.source = graph[source(*in, graph)].id;
            d_edge.target = graph[target(*in, graph)].id;
            d_edge.cost = graph[*in].cost;
            removed_edges.push_back(d_edge);
        }
    }

    // delete incoming and outgoing edges from the vertex
    boost::clear_vertex(vertex, graph);
}

template < class G, typename T_V, typename T_E >
void
Pgr_base_graph< G, T_V, T_E >::restore_graph() {
    while (removed_edges.size() != 0) {
        graph_add_edge(removed_edges[0]);
        removed_edges.pop_front();
    }
}


template < class G, typename T_V, typename T_E >
int64_t
Pgr_base_graph< G, T_V, T_E >::get_edge_id(
        V from,
        V to,
        double &distance) const {
    E e;
    EO_i out_i, out_end;
    V v_source, v_target;
    double minCost =  std::numeric_limits<double>::max();
    int64_t minEdge = -1;
    for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
            out_i != out_end; ++out_i) {
        e = *out_i;
        v_target = target(e, graph);
        v_source = source(e, graph);
        if ((from == v_source) && (to == v_target)
                && (distance == graph[e].cost))
            return graph[e].id;
        if ((from == v_source) && (to == v_target)
                && (minCost > graph[e].cost)) {
            minCost = graph[e].cost;
            minEdge = graph[e].id;
        }
    }
    distance = minEdge == -1? 0: minCost;
    return minEdge;
}


template < class G, typename T_V, typename T_E >
void
Pgr_base_graph< G, T_V, T_E >::graph_add_edge(const T_E &edge ) {
    bool inserted;
    typename Pgr_base_graph< G, T_V, T_E >::LI vm_s, vm_t;
    typename Pgr_base_graph< G, T_V, T_E >::E e;

    vm_s = vertices_map.find(edge.source);
    if (vm_s == vertices_map.end()) {
        vertices_map[edge.source]=  m_num_vertices;
        vm_s = vertices_map.find(edge.source);
    }

    vm_t = vertices_map.find(edge.target);
    if (vm_t == vertices_map.end()) {
        vertices_map[edge.target]=  m_num_vertices;
        vm_t = vertices_map.find(edge.target);
    }

    if (edge.cost >= 0) {
        boost::tie(e, inserted) =
            boost::add_edge(vm_s->second, vm_t->second, graph);
        graph[e].cp_members(edge);
    }
}


template < class G, typename T_V, typename T_E >
template < typename T>
void
Pgr_base_graph< G, T_V, T_E >::graph_add_edge(const T &edge) {
    bool inserted;
    typename Pgr_base_graph< G, T_V, T_E >::E e;
    if ((edge.cost < 0) && (edge.reverse_cost < 0))
        return;

    /*
     * true: for source
     * false: for target
     */
    auto vm_s = get_V(T_V(edge, true));
    auto vm_t = get_V(T_V(edge, false));

    pgassert(vertices_map.find(edge.source) != vertices_map.end());
    pgassert(vertices_map.find(edge.target) != vertices_map.end());
    if (edge.cost >= 0) {
        boost::tie(e, inserted) =
            boost::add_edge(vm_s, vm_t, graph);
        graph[e].cost = edge.cost;
        graph[e].id = edge.id;
        graph[e].first = true;
    }

    if (edge.reverse_cost >= 0) {
        boost::tie(e, inserted) =
            boost::add_edge(vm_t, vm_s, graph);

        graph[e].cost = edge.reverse_cost;
        graph[e].id = edge.id;
        graph[e].first = false;
    }
}

/******************  PRIVATE *******************/

template < class G, typename T_V, typename T_E >
void
Pgr_base_graph< G, T_V, T_E >::add_vertices(
        std::vector< T_V > vertices) {
    pgassert(m_num_vertices == 0);
    for (const auto vertex : vertices) {
        pgassert(vertices_map.find(vertex.id) == vertices_map.end());

        auto v =  add_vertex(graph);
        vertices_map[vertex.id] =  m_num_vertices++;
        graph[v].cp_members(vertex);

        pgassert(boost::num_vertices(graph) == num_vertices());
    }
    return;
}

}  // namespace graph
}  // namespace pgrouting