Edge Connectivity

Computes the minimum number of edges whose removal disconnects the graph. Optionally outputs the disconnecting edge set.

Complexity: O(V * max_flow)
Defined in: <boost/graph/edge_connectivity.hpp>

Example

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

using namespace boost;
using Graph = adjacency_list<vecS, vecS, undirectedS>;
using Edge = graph_traits<Graph>::edge_descriptor;

int main() {
    Graph g(4);
    add_edge(0, 1, g); add_edge(0, 2, g);
    add_edge(1, 2, g); add_edge(1, 3, g); add_edge(2, 3, g);

    std::vector<Edge> cut_edges;
    auto connectivity = edge_connectivity(g, std::back_inserter(cut_edges));

    std::cout << "Edge connectivity: " << connectivity << "\n";
    std::cout << "Min cut edges: " << cut_edges.size() << "\n";
}
Edge connectivity: 2
Min cut edges: 2

Synopsis

template <typename VertexListGraph, typename OutputIterator>
typename graph_traits<VertexListGraph>::degree_size_type
edge_connectivity(VertexListGraph& g, OutputIterator disconnecting_set);
Direction Parameter Description

IN

VertexListGraph& g

Must model VertexListGraph and EdgeMutableGraph (the algorithm internally constructs a flow network).

OUT

OutputIterator disconnecting_set

Receives the edges in the minimum disconnecting set.

Returns the edge connectivity (minimum cut size).

This function internally uses max-flow. It constructs a temporary copy of the graph for flow computation.
Edit this Page