3rdParty/boost/1.78.0/libs/graph/doc/make_biconnected_planar.html
template <typename Graph, typename PlanarEmbedding, typename EdgeIndexMap, typename AddEdgeVisitor>
void make_biconnected_planar(Graph& g, PlanarEmbedding embedding, EdgeIndexMap em, AddEdgeVisitor& vis);
A graph G is biconnected if, for every pair of vertices u,v in G, there is a cycle containing both u and v. Alternatively, a graph is biconnected if it is connected and cannot be made disconnected by removing any single vertex. make_biconnected_planar takes a connectedplanar graph g as input and adds zero or more edges to make g biconnected while preserving planarity.
The default behavior of make_biconnected_planar is to modify the graph g by calling add_edge(u,v,g) for every pair of vertices (u,v) where an edge needs to be added to make g biconnected. This behavior can be overriden by providing a vistor as the AddEdgeVisitor parameter. The only requirement for an AddEdgeVisitor is that it define a member function with the following signature:
template <typename Graph, typename Vertex>
void visit_vertex_pair(Vertex u, Vertex v, Graph& g);
This event point can also be used as a hook to update the underlying edge index map automatically as edges are added. See the documentation for the AddEdgeVisitor concept for more information.
boost/graph/make_biconnected_planar.hpp
IN/OUT: Graph& g
An undirected graph. The graph type must be a model of Vertex List Graph, Incidence Graph, and a Mutable Graph
IN: PlanarEmbedding embedding
A model of PlanarEmbedding.
IN: EdgeIndexMap vm
A Readable Property Map that maps edges from g to distinct integers in the range [0, num_edges(g) )
Default : get(edge_index,g)
IN: AddEdgeVisitor
A model of AddEdgeVisitor.
Default : default_add_edge_visitor, a class defines visit_vertex_pair to dispatch its calls to add_edge.
On a planar graph with n vertices, make_biconnected_planar runs in time O(n)
examples/make_biconnected_planar.cpp
Planar Graphs in the Boost Graph Library
Copyright © 2007 Aaron Windsor ([email protected])