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: 2Synopsis
template <typename VertexListGraph, typename OutputIterator>
typename graph_traits<VertexListGraph>::degree_size_type
edge_connectivity(VertexListGraph& g, OutputIterator disconnecting_set);| Direction | Parameter | Description |
|---|---|---|
IN |
|
Must model VertexListGraph and EdgeMutableGraph (the algorithm internally constructs a flow network). |
OUT |
|
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. |