1//=======================================================================
2// Copyright 2007 Aaron Windsor
3//
4// Distributed under the Boost Software License, Version 1.0. (See
5// accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7//=======================================================================
8#ifndef __MAKE_BICONNECTED_PLANAR_HPP__
9#define __MAKE_BICONNECTED_PLANAR_HPP__
10
11#include <boost/config.hpp>
12#include <boost/tuple/tuple.hpp> //for tie
13#include <boost/graph/biconnected_components.hpp>
14#include <boost/property_map/property_map.hpp>
15#include <vector>
16#include <iterator>
17#include <algorithm>
18
19#include <boost/graph/planar_detail/add_edge_visitors.hpp>
20
21
22namespace boost
23{
24
25
26
27 template <typename Graph,
28 typename PlanarEmbedding,
29 typename EdgeIndexMap,
30 typename AddEdgeVisitor
31 >
32 void make_biconnected_planar(Graph& g,
33 PlanarEmbedding embedding,
34 EdgeIndexMap em,
35 AddEdgeVisitor& vis
36 )
37 {
38 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
39 typedef typename graph_traits<Graph>::edge_descriptor edge_t;
40 typedef typename graph_traits<Graph>::edges_size_type edge_size_t;
41 typedef typename
42 property_traits<PlanarEmbedding>::value_type embedding_value_t;
43 typedef typename embedding_value_t::const_iterator embedding_iterator_t;
44 typedef iterator_property_map
45 <std::vector<std::size_t>::iterator, EdgeIndexMap> component_map_t;
46
47 edge_size_t n_edges(num_edges(g));
48 std::vector<vertex_t> articulation_points;
49 std::vector<edge_size_t> component_vector(n_edges);
50 component_map_t component_map(component_vector.begin(), em);
51
52 biconnected_components(g, component_map,
53 std::back_inserter(articulation_points));
54
55 typename std::vector<vertex_t>::iterator ap, ap_end;
56 ap_end = articulation_points.end();
57 for(ap = articulation_points.begin(); ap != ap_end; ++ap)
58 {
59 vertex_t v(*ap);
60 embedding_iterator_t pi = embedding[v].begin();
61 embedding_iterator_t pi_end = embedding[v].end();
62 edge_size_t previous_component(n_edges + 1);
63 vertex_t previous_vertex = graph_traits<Graph>::null_vertex();
64
65 for(; pi != pi_end; ++pi)
66 {
67 edge_t e(*pi);
68 vertex_t e_source(source(e,g));
69 vertex_t e_target(target(e,g));
70
71 //Skip self-loops and parallel edges
72 if (e_source == e_target || previous_vertex == e_target)
73 continue;
74
75 vertex_t current_vertex = e_source == v ? e_target : e_source;
76 edge_size_t current_component = component_map[e];
77 if (previous_vertex != graph_traits<Graph>::null_vertex() &&
78 current_component != previous_component)
79 {
80 vis.visit_vertex_pair(current_vertex, previous_vertex, g);
81 }
82 previous_vertex = current_vertex;
83 previous_component = current_component;
84 }
85 }
86
87 }
88
89
90
91
92 template <typename Graph,
93 typename PlanarEmbedding,
94 typename EdgeIndexMap
95 >
96 inline void make_biconnected_planar(Graph& g,
97 PlanarEmbedding embedding,
98 EdgeIndexMap em
99 )
100 {
101 default_add_edge_visitor vis;
102 make_biconnected_planar(g, embedding, em, vis);
103 }
104
105
106
107
108 template <typename Graph,
109 typename PlanarEmbedding
110 >
111 inline void make_biconnected_planar(Graph& g, PlanarEmbedding embedding)
112 {
113 make_biconnected_planar(g, embedding, get(edge_index,g));
114 }
115
116
117} // namespace boost
118
119
120
121#endif //__MAKE_BICONNECTED_PLANAR_HPP__
122

source code of boost/boost/graph/make_biconnected_planar.hpp