185 lines
6.8 KiB
C++
185 lines
6.8 KiB
C++
//=======================================================================
|
|
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
|
|
//
|
|
// Distributed under the Boost Software License, Version 1.0. (See
|
|
// accompanying file LICENSE_1_0.txt or copy at
|
|
// http://www.boost.org/LICENSE_1_0.txt)
|
|
//=======================================================================
|
|
|
|
/*
|
|
IMPORTANT!!!
|
|
~~~~~~~~~~~~
|
|
This example uses interfaces that have been deprecated and removed from Boost.Grpah.
|
|
Someone needs to update it, as it does NOT compile.
|
|
*/
|
|
|
|
#include <boost/config.hpp>
|
|
#include <algorithm>
|
|
#include <utility>
|
|
#include <boost/graph/edmonds_karp_max_flow.hpp>
|
|
#include <boost/graph/push_relabel_max_flow.hpp>
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
#include <boost/graph/graphviz.hpp>
|
|
|
|
namespace boost
|
|
{
|
|
template < typename Graph >
|
|
std::pair < typename graph_traits < Graph >::vertex_descriptor,
|
|
typename graph_traits < Graph >::degree_size_type >
|
|
min_degree_vertex(Graph & g)
|
|
{
|
|
typename graph_traits < Graph >::vertex_descriptor p;
|
|
typedef typename graph_traits < Graph >::degree_size_type size_type;
|
|
size_type delta = (std::numeric_limits < size_type >::max)();
|
|
typename graph_traits < Graph >::vertex_iterator i, iend;
|
|
for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
|
|
if (degree(*i, g) < delta)
|
|
{
|
|
delta = degree(*i, g);
|
|
p = *i;
|
|
}
|
|
return std::make_pair(p, delta);
|
|
}
|
|
|
|
template < typename Graph, typename OutputIterator >
|
|
void neighbors(const Graph & g,
|
|
typename graph_traits < Graph >::vertex_descriptor u,
|
|
OutputIterator result)
|
|
{
|
|
typename graph_traits < Graph >::adjacency_iterator ai, aend;
|
|
for (boost::tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
|
|
*result++ = *ai;
|
|
}
|
|
template < typename Graph, typename VertexIterator,
|
|
typename OutputIterator > void neighbors(const Graph & g,
|
|
VertexIterator first,
|
|
VertexIterator last,
|
|
OutputIterator result)
|
|
{
|
|
for (; first != last; ++first)
|
|
neighbors(g, *first, result);
|
|
}
|
|
|
|
template < typename VertexListGraph, typename OutputIterator >
|
|
typename graph_traits < VertexListGraph >::degree_size_type
|
|
edge_connectivity(VertexListGraph & g, OutputIterator disconnecting_set)
|
|
{
|
|
typedef typename graph_traits <
|
|
VertexListGraph >::vertex_descriptor vertex_descriptor;
|
|
typedef typename graph_traits <
|
|
VertexListGraph >::degree_size_type degree_size_type;
|
|
typedef color_traits < default_color_type > Color;
|
|
typedef typename adjacency_list_traits < vecS, vecS,
|
|
directedS >::edge_descriptor edge_descriptor;
|
|
typedef adjacency_list < vecS, vecS, directedS, no_property,
|
|
property < edge_capacity_t, degree_size_type,
|
|
property < edge_residual_capacity_t, degree_size_type,
|
|
property < edge_reverse_t, edge_descriptor > > > > FlowGraph;
|
|
|
|
vertex_descriptor u, v, p, k;
|
|
edge_descriptor e1, e2;
|
|
bool inserted;
|
|
typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
|
|
degree_size_type delta, alpha_star, alpha_S_k;
|
|
std::set < vertex_descriptor > S, neighbor_S;
|
|
std::vector < vertex_descriptor > S_star, nonneighbor_S;
|
|
std::vector < default_color_type > color(num_vertices(g));
|
|
std::vector < edge_descriptor > pred(num_vertices(g));
|
|
|
|
FlowGraph flow_g(num_vertices(g));
|
|
typename property_map < FlowGraph, edge_capacity_t >::type
|
|
cap = get(edge_capacity, flow_g);
|
|
typename property_map < FlowGraph, edge_residual_capacity_t >::type
|
|
res_cap = get(edge_residual_capacity, flow_g);
|
|
typename property_map < FlowGraph, edge_reverse_t >::type
|
|
rev_edge = get(edge_reverse, flow_g);
|
|
|
|
typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
|
|
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
|
|
u = source(*ei, g), v = target(*ei, g);
|
|
boost::tie(e1, inserted) = add_edge(u, v, flow_g);
|
|
cap[e1] = 1;
|
|
boost::tie(e2, inserted) = add_edge(v, u, flow_g);
|
|
cap[e2] = 1;
|
|
rev_edge[e1] = e2;
|
|
rev_edge[e2] = e1;
|
|
}
|
|
|
|
boost::tie(p, delta) = min_degree_vertex(g);
|
|
S_star.push_back(p);
|
|
alpha_star = delta;
|
|
S.insert(p);
|
|
neighbor_S.insert(p);
|
|
neighbors(g, S.begin(), S.end(),
|
|
std::inserter(neighbor_S, neighbor_S.begin()));
|
|
std::set_difference(vertices(g).first, vertices(g).second,
|
|
neighbor_S.begin(), neighbor_S.end(),
|
|
std::back_inserter(nonneighbor_S));
|
|
|
|
while (!nonneighbor_S.empty()) {
|
|
k = nonneighbor_S.front();
|
|
alpha_S_k = edmonds_karp_max_flow
|
|
(flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
|
|
if (alpha_S_k < alpha_star) {
|
|
alpha_star = alpha_S_k;
|
|
S_star.clear();
|
|
for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
|
|
if (color[*vi] != Color::white())
|
|
S_star.push_back(*vi);
|
|
}
|
|
S.insert(k);
|
|
neighbor_S.insert(k);
|
|
neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
|
|
nonneighbor_S.clear();
|
|
std::set_difference(vertices(g).first, vertices(g).second,
|
|
neighbor_S.begin(), neighbor_S.end(),
|
|
std::back_inserter(nonneighbor_S));
|
|
}
|
|
|
|
std::vector < bool > in_S_star(num_vertices(g), false);
|
|
typename std::vector < vertex_descriptor >::iterator si;
|
|
for (si = S_star.begin(); si != S_star.end(); ++si)
|
|
in_S_star[*si] = true;
|
|
degree_size_type c = 0;
|
|
for (si = S_star.begin(); si != S_star.end(); ++si) {
|
|
typename graph_traits < VertexListGraph >::out_edge_iterator ei, ei_end;
|
|
for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
|
|
if (!in_S_star[target(*ei, g)]) {
|
|
*disconnecting_set++ = *ei;
|
|
++c;
|
|
}
|
|
}
|
|
|
|
return c;
|
|
}
|
|
|
|
}
|
|
|
|
int
|
|
main()
|
|
{
|
|
using namespace boost;
|
|
GraphvizGraph g;
|
|
read_graphviz("figs/edge-connectivity.dot", g);
|
|
|
|
typedef graph_traits < GraphvizGraph >::edge_descriptor edge_descriptor;
|
|
typedef graph_traits < GraphvizGraph >::degree_size_type degree_size_type;
|
|
std::vector < edge_descriptor > disconnecting_set;
|
|
degree_size_type c =
|
|
edge_connectivity(g, std::back_inserter(disconnecting_set));
|
|
|
|
std::cout << "The edge connectivity is " << c << "." << std::endl;
|
|
|
|
property_map < GraphvizGraph, vertex_attribute_t >::type
|
|
attr_map = get(vertex_attribute, g);
|
|
|
|
std::cout << "The disconnecting set is {";
|
|
for (std::vector < edge_descriptor >::iterator i =
|
|
disconnecting_set.begin(); i != disconnecting_set.end(); ++i)
|
|
std::
|
|
cout << "(" << attr_map[source(*i, g)]["label"] << "," <<
|
|
attr_map[target(*i, g)]["label"] << ") ";
|
|
std::cout << "}." << std::endl;
|
|
return EXIT_SUCCESS;
|
|
}
|