File GeometryGraph.h

File List > detail > graph > GeometryGraph.h

Go to the documentation of this file

// Copyright (c) 2012-2013, IGN France.
// Copyright (c) 2012-2022, Oslandia.
// SPDX-License-Identifier: LGPL-2.0-or-later

#ifndef _SFCGAL_GRAPH_GEOMETRYGRAPH_H_
#define _SFCGAL_GRAPH_GEOMETRYGRAPH_H_

#include <boost/graph/adjacency_list.hpp>

#include "SFCGAL/detail/graph/Edge.h"
#include "SFCGAL/detail/graph/Vertex.h"

namespace SFCGAL {
namespace graph {

typedef enum { DIRECT = 0, REVERSE = 1 } EdgeDirection;

inline EdgeDirection
reverse(const EdgeDirection &direction)
{
  return (EdgeDirection)(1 - direction);
}

template <typename VertexProperties, typename EdgeProperties>
class GeometryGraphT {
public:
  typedef VertexProperties vertex_properties;
  typedef EdgeProperties   edge_properties;

  typedef boost::adjacency_list<
      boost::listS, /* stable identifiers */
      boost::listS, /* parallel edges allowed + stable identifiers */
      boost::bidirectionalS, vertex_properties, edge_properties>
      graph_t;

  typedef typename boost::graph_traits<graph_t>::vertex_descriptor
      vertex_descriptor;
  typedef
      typename boost::graph_traits<graph_t>::edge_descriptor edge_descriptor;

  typedef
      typename boost::graph_traits<graph_t>::vertex_iterator   vertex_iterator;
  typedef typename boost::graph_traits<graph_t>::edge_iterator edge_iterator;
  typedef std::pair<edge_descriptor, EdgeDirection> directed_edge_descriptor;

  typedef
      typename boost::graph_traits<graph_t>::in_edge_iterator in_edge_iterator;
  typedef typename boost::graph_traits<graph_t>::out_edge_iterator
      out_edge_iterator;

  inline size_t
  numVertices() const
  {
    return boost::num_vertices(_graph);
  }

  inline std::pair<vertex_iterator, vertex_iterator>
  vertices() const
  {
    return boost::vertices(_graph);
  }

  vertex_descriptor
  addVertex(const vertex_properties &properties = vertex_properties())
  {
    return boost::add_vertex(properties, _graph);
  }
  void
  removeVertex(const vertex_descriptor &vertex)
  {
    boost::clear_vertex(vertex);
    boost::remove_vertex(vertex);
  }

  inline size_t
  numEdges() const
  {
    return boost::num_edges(_graph);
  }

  inline std::pair<edge_iterator, edge_iterator>
  edges() const
  {
    return boost::edges(_graph);
  }

  edge_descriptor
  addEdge(const vertex_descriptor &source, const vertex_descriptor &target,
          const EdgeProperties &properties = EdgeProperties())
  {
    return boost::add_edge(source, target, properties, _graph).first;
  }

  vertex_descriptor
  source(const edge_descriptor &edge) const
  {
    return boost::source(edge, _graph);
  }
  vertex_descriptor
  source(const edge_descriptor &edge, const EdgeDirection &direction) const
  {
    return direction == DIRECT ? boost::source(edge, _graph)
                               : boost::target(edge, _graph);
  }
  vertex_descriptor
  source(const directed_edge_descriptor &edge) const
  {
    return source(edge.first, edge.second);
  }

  vertex_descriptor
  target(const edge_descriptor &edge) const
  {
    return boost::target(edge, _graph);
  }
  vertex_descriptor
  target(const edge_descriptor &edge, const EdgeDirection &direction) const
  {
    return direction == DIRECT ? boost::target(edge, _graph)
                               : boost::source(edge, _graph);
  }
  vertex_descriptor
  target(const directed_edge_descriptor &edge) const
  {
    return target(edge.first, edge.second);
  }
  void
  removeEdge(const edge_descriptor &edge)
  {
    boost::remove_edge(edge, _graph);
  }

  std::vector<directed_edge_descriptor>
  edges(const vertex_descriptor &a, const vertex_descriptor &b) const
  {
    std::vector<directed_edge_descriptor> result;

    // out_edges from a targeting b
    {
      out_edge_iterator it, end;

      for (boost::tie(it, end) = boost::out_edges(a, _graph); it != end; ++it) {
        if (target(*it) != b) {
          continue;
        }

        result.push_back(std::make_pair(*it, DIRECT));
      }
    }
    // out_edges from b targeting a
    {
      out_edge_iterator it, end;

      for (boost::tie(it, end) = boost::out_edges(b, _graph); it != end; ++it) {
        if (target(*it) != a) {
          continue;
        }

        result.push_back(std::make_pair(*it, REVERSE));
      }
    }
    return result;
  }

  inline size_t
  degree(const vertex_descriptor &vertex) const
  {
    return boost::degree(vertex, _graph);
  }

  std::vector<edge_descriptor>
  inEdges(const vertex_descriptor &vertex)
  {
    std::vector<edge_descriptor> edges;

    in_edge_iterator it, end;

    for (boost::tie(it, end) = boost::in_edges(vertex, _graph); it != end;
         ++it) {
      edges.push_back(*it);
    }

    return edges;
  }
  std::vector<edge_descriptor>
  outEdges(const vertex_descriptor &vertex) const
  {
    std::vector<edge_descriptor> edges;

    out_edge_iterator it, end;

    for (boost::tie(it, end) = boost::out_edges(vertex, _graph); it != end;
         ++it) {
      edges.push_back(*it);
    }

    return edges;
  }
  std::vector<directed_edge_descriptor>
  inOutEdges(const vertex_descriptor &vertex) const
  {
    std::vector<directed_edge_descriptor> edges;
    {
      in_edge_iterator it, end;

      for (boost::tie(it, end) = boost::in_edges(vertex, _graph); it != end;
           ++it) {
        edges.push_back(std::make_pair(*it, REVERSE));
      }
    }

    // out edges
    {
      out_edge_iterator it, end;

      for (boost::tie(it, end) = boost::out_edges(vertex, _graph); it != end;
           ++it) {
        edges.push_back(std::make_pair(*it, DIRECT));
      }
    }
    return edges;
  }

  std::set<vertex_descriptor>
  adjacentVertices(const vertex_descriptor &vertex,
                   bool                     withReverseDirection = true)
  {
    std::set<vertex_descriptor> vertices;
    // out edges
    {
      out_edge_iterator it, end;

      for (boost::tie(it, end) = boost::out_edges(vertex, _graph); it != end;
           ++it) {
        vertex_descriptor reached = target(*it);

        if (reached != vertex) {
          vertices.insert(reached);
        }
      }
    }

    // in edges
    if (withReverseDirection) {
      in_edge_iterator it, end;

      for (boost::tie(it, end) = boost::in_edges(vertex, _graph); it != end;
           ++it) {
        vertex_descriptor reached = source(*it);

        if (reached != vertex) {
          vertices.insert(reached);
        }
      }
    }

    return vertices;
  }

  inline bool
  areOpposite(const edge_descriptor &a, const edge_descriptor &b) const
  {
    return source(a) == target(b) && target(a) == source(b);
  }
  inline bool
  areParallel(const edge_descriptor &a, const edge_descriptor &b) const
  {
    return source(a) == source(b) && target(a) == target(b);
  }

  void
  reverse(std::vector<edge_descriptor> &edges)
  {
    std::vector<edge_descriptor> result;

    for (typename std::vector<edge_descriptor>::reverse_iterator it =
             edges.rbegin();
         it != edges.rend(); ++it) {
      edge_descriptor newEdge = addEdge(target(*it), source(*it), (*this)[*it]);
      result.push_back(newEdge);
      removeEdge(*it);
    }

    edges = result;
  }

  inline const vertex_properties &
  operator[](const vertex_descriptor &vertex) const
  {
    return _graph[vertex];
  }
  inline vertex_properties &
  operator[](const vertex_descriptor &vertex)
  {
    return _graph[vertex];
  }

  inline const edge_properties &
  operator[](const edge_descriptor &edge) const
  {
    return _graph[edge];
  }
  inline edge_properties &
  operator[](const edge_descriptor &edge)
  {
    return _graph[edge];
  }

  inline graph_t &
  graph()
  {
    return _graph;
  }
  inline const graph_t &
  graph() const
  {
    return _graph;
  }

  operator graph_t &(void) { return _graph; }
  operator const graph_t &(void) const { return _graph; }

private:
  graph_t _graph;
};

typedef GeometryGraphT<Vertex, Edge> GeometryGraph;

} // namespace graph
} // namespace SFCGAL

#endif