make_biconnected_planar

Adds edges to a connected planar graph to make it biconnected while preserving planarity.

Complexity: O(n)
Defined in: <boost/graph/make_biconnected_planar.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/make_biconnected_planar.hpp>
#include <iostream>
#include <vector>

using namespace boost;

// Bundled edge field holds the contiguous index that planar algorithms need.
struct Edge { int idx; };

using Graph = adjacency_list<vecS, vecS, undirectedS, no_property, Edge>;
using Descriptor = graph_traits<Graph>::edge_descriptor;

void reindex(Graph& g) {
    int i = 0;
    for (auto e : make_iterator_range(edges(g))) { g[e].idx = i++; }
}

int main() {
    // A path graph: 0-1-2-3 (planar but not biconnected)
    Graph g(4);
    add_edge(0, 1, g); add_edge(1, 2, g); add_edge(2, 3, g);

    reindex(g);

    // Compute planar embedding
    using EmbStorage = std::vector<std::vector<Descriptor>>;
    EmbStorage storage(num_vertices(g));
    auto embedding = make_iterator_property_map(storage.begin(), get(vertex_index, g));
    boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
        boyer_myrvold_params::embedding = embedding);

    std::cout << "Edges before: " << num_edges(g) << "\n";
    reindex(g);
    boost::graph::make_biconnected_planar(g, embedding, get(&Edge::idx, g));
    std::cout << "Edges after make_biconnected_planar: " << num_edges(g) << "\n";
}

Edges before: 3
Edges after make_biconnected_planar: 5

Synopsis

namespace boost::graph {
template <typename Graph, typename PlanarEmbedding,
          typename EdgeIndexMap, typename AddEdgeVisitor>
void make_biconnected_planar(
    Graph& g,
    PlanarEmbedding embedding,
    EdgeIndexMap em,
    AddEdgeVisitor vis);
}

Direction Parameter Description

Direction	Parameter	Description
IN/OUT	`Graph& g`	An undirected graph. The type `Graph` must be a model of VertexListGraph, IncidenceGraph, and MutableGraph.
IN	`PlanarEmbedding embedding`	A model of PlanarEmbedding.
IN	`EdgeIndexMap em`	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 vis`	A model of AddEdgeVisitor. The visitor is passed by value, so the algorithm works on a copy. Wrap it in `std::ref(vis)` to have your own visitor updated in place. Default: `default_add_edge_visitor`, a class that defines `visit_vertex_pair` to dispatch its calls to `add_edge`.

IN/OUT

Graph& g

An undirected graph. The type Graph must be a model of VertexListGraph, IncidenceGraph, and MutableGraph.

PlanarEmbedding embedding

A model of PlanarEmbedding.

EdgeIndexMap em

A Readable Property Map that maps edges from g to distinct integers in the range [0, num_edges(g)).
Default: get(edge_index, g)

AddEdgeVisitor vis

A model of AddEdgeVisitor. The visitor is passed by value, so the algorithm works on a copy. Wrap it in std::ref(vis) to have your own visitor updated in place.
Default: default_add_edge_visitor, a class that defines visit_vertex_pair to dispatch its calls to add_edge.

Migrating from `boost::make_biconnected_planar`

The boost::make_biconnected_planar overloads are deprecated. They took the visitor by non-const reference, which rejected temporaries and differed from the other BGL algorithms. Removal planned for Boost 1.95. Calls left unchanged then fail to compile instead of silently changing behavior.

Replace boost::make_biconnected_planar with boost::graph::make_biconnected_planar. Unqualified calls need qualifying too, since argument dependent lookup only finds the deprecated overloads.
If you read the visitor after the call, pass it as std::ref(vis). Otherwise the algorithm works on a copy and your visitor is left unchanged.

// Before
make_biconnected_planar(g, embedding, get(edge_index, g), edge_updater);

// After
boost::graph::make_biconnected_planar(g, embedding, get(edge_index, g), std::ref(edge_updater));

`boost::make_biconnected_planar` (deprecated)

Deprecated: use boost::graph::make_biconnected_planar. Removal planned for Boost 1.95. See the migration steps.

namespace boost {
template <typename Graph, typename PlanarEmbedding, typename EdgeIndexMap, typename AddEdgeVisitor>
void make_biconnected_planar(Graph& g, PlanarEmbedding embedding, EdgeIndexMap em, AddEdgeVisitor& vis);

template <typename Graph, typename PlanarEmbedding, typename EdgeIndexMap>
void make_biconnected_planar(Graph& g, PlanarEmbedding embedding, EdgeIndexMap em);

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

Description

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 connected planar 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 overridden by providing a visitor 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.