1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
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__
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>
19 #include <boost/graph/planar_detail/add_edge_visitors.hpp>
27 template <typename Graph
,
28 typename PlanarEmbedding
,
29 typename EdgeIndexMap
,
30 typename AddEdgeVisitor
32 void make_biconnected_planar(Graph
& g
,
33 PlanarEmbedding embedding
,
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
;
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
;
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
);
52 biconnected_components(g
, component_map
,
53 std::back_inserter(articulation_points
));
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
)
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();
65 for(; pi
!= pi_end
; ++pi
)
68 vertex_t
e_source(source(e
,g
));
69 vertex_t
e_target(target(e
,g
));
71 //Skip self-loops and parallel edges
72 if (e_source
== e_target
|| previous_vertex
== e_target
)
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
)
80 vis
.visit_vertex_pair(current_vertex
, previous_vertex
, g
);
82 previous_vertex
= current_vertex
;
83 previous_component
= current_component
;
92 template <typename Graph
,
93 typename PlanarEmbedding
,
96 inline void make_biconnected_planar(Graph
& g
,
97 PlanarEmbedding embedding
,
101 default_add_edge_visitor vis
;
102 make_biconnected_planar(g
, embedding
, em
, vis
);
108 template <typename Graph
,
109 typename PlanarEmbedding
111 inline void make_biconnected_planar(Graph
& g
, PlanarEmbedding embedding
)
113 make_biconnected_planar(g
, embedding
, get(edge_index
,g
));
121 #endif //__MAKE_BICONNECTED_PLANAR_HPP__