File: make_biconnected_planar.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (121 lines) | stat: -rw-r--r-- 3,879 bytes parent folder | download | duplicates (17)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//=======================================================================
// Copyright 2007 Aaron Windsor
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef __MAKE_BICONNECTED_PLANAR_HPP__
#define __MAKE_BICONNECTED_PLANAR_HPP__

#include <boost/config.hpp>
#include <boost/tuple/tuple.hpp>   //for tie
#include <boost/graph/biconnected_components.hpp>
#include <boost/property_map/property_map.hpp>
#include <vector>
#include <iterator>
#include <algorithm>

#include <boost/graph/planar_detail/add_edge_visitors.hpp>


namespace boost
{



  template <typename Graph,
            typename PlanarEmbedding,
            typename EdgeIndexMap,
            typename AddEdgeVisitor
            >
  void make_biconnected_planar(Graph& g,
                               PlanarEmbedding embedding, 
                               EdgeIndexMap em, 
                               AddEdgeVisitor& vis
                               )
  {
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;
    typedef typename graph_traits<Graph>::edges_size_type edge_size_t;
    typedef typename 
      property_traits<PlanarEmbedding>::value_type embedding_value_t;
    typedef typename embedding_value_t::const_iterator embedding_iterator_t;
    typedef iterator_property_map
      <std::vector<std::size_t>::iterator, EdgeIndexMap> component_map_t;

    edge_size_t n_edges(num_edges(g));
    std::vector<vertex_t> articulation_points;
    std::vector<edge_size_t> component_vector(n_edges);
    component_map_t component_map(component_vector.begin(), em);

    biconnected_components(g, component_map, 
                           std::back_inserter(articulation_points));

    typename std::vector<vertex_t>::iterator ap, ap_end;
    ap_end = articulation_points.end();
    for(ap = articulation_points.begin(); ap != ap_end; ++ap)
      {
        vertex_t v(*ap);
        embedding_iterator_t pi = embedding[v].begin();
        embedding_iterator_t pi_end = embedding[v].end();
        edge_size_t previous_component(n_edges + 1);
        vertex_t previous_vertex = graph_traits<Graph>::null_vertex();

        for(; pi != pi_end; ++pi)
          {
            edge_t e(*pi);
            vertex_t e_source(source(e,g));
            vertex_t e_target(target(e,g));

            //Skip self-loops and parallel edges
            if (e_source == e_target || previous_vertex == e_target)
              continue;

            vertex_t current_vertex = e_source == v ? e_target : e_source;
            edge_size_t current_component = component_map[e];
            if (previous_vertex != graph_traits<Graph>::null_vertex() &&
                current_component != previous_component)
              {
                vis.visit_vertex_pair(current_vertex, previous_vertex, g);
              }
            previous_vertex = current_vertex;
            previous_component = current_component;
          }
      }

  }




  template <typename Graph,
            typename PlanarEmbedding,
            typename EdgeIndexMap
            >
  inline void make_biconnected_planar(Graph& g, 
                                      PlanarEmbedding embedding, 
                                      EdgeIndexMap em
                                      )
  {
    default_add_edge_visitor vis;
    make_biconnected_planar(g, embedding, em, vis); 
  }




  template <typename Graph,
            typename PlanarEmbedding
            >
  inline void make_biconnected_planar(Graph& g, PlanarEmbedding embedding)
  {
    make_biconnected_planar(g, embedding, get(edge_index,g));
  }


} // namespace boost



#endif //__MAKE_BICONNECTED_PLANAR_HPP__