1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/edge_connectivity.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,181 @@
1.4 +//=======================================================================
1.5 +// Copyright 2000 University of Notre Dame.
1.6 +// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +
1.13 +#ifndef BOOST_EDGE_CONNECTIVITY
1.14 +#define BOOST_EDGE_CONNECTIVITY
1.15 +
1.16 +// WARNING: not-yet fully tested!
1.17 +
1.18 +#include <boost/config.hpp>
1.19 +#include <vector>
1.20 +#include <set>
1.21 +#include <algorithm>
1.22 +#include <boost/graph/edmunds_karp_max_flow.hpp>
1.23 +
1.24 +namespace boost {
1.25 +
1.26 + namespace detail {
1.27 +
1.28 + template <class Graph>
1.29 + inline
1.30 + std::pair<typename graph_traits<Graph>::vertex_descriptor,
1.31 + typename graph_traits<Graph>::degree_size_type>
1.32 + min_degree_vertex(Graph& g)
1.33 + {
1.34 + typedef graph_traits<Graph> Traits;
1.35 + typename Traits::vertex_descriptor p;
1.36 + typedef typename Traits::degree_size_type size_type;
1.37 + size_type delta = (std::numeric_limits<size_type>::max)();
1.38 +
1.39 + typename Traits::vertex_iterator i, iend;
1.40 + for (tie(i, iend) = vertices(g); i != iend; ++i)
1.41 + if (degree(*i, g) < delta) {
1.42 + delta = degree(*i, g);
1.43 + p = *i;
1.44 + }
1.45 + return std::make_pair(p, delta);
1.46 + }
1.47 +
1.48 + template <class Graph, class OutputIterator>
1.49 + void neighbors(const Graph& g,
1.50 + typename graph_traits<Graph>::vertex_descriptor u,
1.51 + OutputIterator result)
1.52 + {
1.53 + typename graph_traits<Graph>::adjacency_iterator ai, aend;
1.54 + for (tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
1.55 + *result++ = *ai;
1.56 + }
1.57 +
1.58 + template <class Graph, class VertexIterator, class OutputIterator>
1.59 + void neighbors(const Graph& g,
1.60 + VertexIterator first, VertexIterator last,
1.61 + OutputIterator result)
1.62 + {
1.63 + for (; first != last; ++first)
1.64 + neighbors(g, *first, result);
1.65 + }
1.66 +
1.67 + } // namespace detail
1.68 +
1.69 + // O(m n)
1.70 + template <class VertexListGraph, class OutputIterator>
1.71 + typename graph_traits<VertexListGraph>::degree_size_type
1.72 + edge_connectivity(VertexListGraph& g, OutputIterator disconnecting_set)
1.73 + {
1.74 + //-------------------------------------------------------------------------
1.75 + // Type Definitions
1.76 + typedef graph_traits<VertexListGraph> Traits;
1.77 + typedef typename Traits::vertex_iterator vertex_iterator;
1.78 + typedef typename Traits::edge_iterator edge_iterator;
1.79 + typedef typename Traits::out_edge_iterator out_edge_iterator;
1.80 + typedef typename Traits::vertex_descriptor vertex_descriptor;
1.81 + typedef typename Traits::degree_size_type degree_size_type;
1.82 + typedef color_traits<default_color_type> Color;
1.83 +
1.84 + typedef adjacency_list_traits<vecS, vecS, directedS> Tr;
1.85 + typedef typename Tr::edge_descriptor Tr_edge_desc;
1.86 + typedef adjacency_list<vecS, vecS, directedS, no_property,
1.87 + property<edge_capacity_t, degree_size_type,
1.88 + property<edge_residual_capacity_t, degree_size_type,
1.89 + property<edge_reverse_t, Tr_edge_desc> > > >
1.90 + FlowGraph;
1.91 + typedef typename graph_traits<FlowGraph>::edge_descriptor edge_descriptor;
1.92 +
1.93 + //-------------------------------------------------------------------------
1.94 + // Variable Declarations
1.95 + vertex_descriptor u, v, p, k;
1.96 + edge_descriptor e1, e2;
1.97 + bool inserted;
1.98 + vertex_iterator vi, vi_end;
1.99 + edge_iterator ei, ei_end;
1.100 + degree_size_type delta, alpha_star, alpha_S_k;
1.101 + std::set<vertex_descriptor> S, neighbor_S;
1.102 + std::vector<vertex_descriptor> S_star, non_neighbor_S;
1.103 + std::vector<default_color_type> color(num_vertices(g));
1.104 + std::vector<edge_descriptor> pred(num_vertices(g));
1.105 +
1.106 + //-------------------------------------------------------------------------
1.107 + // Create a network flow graph out of the undirected graph
1.108 + FlowGraph flow_g(num_vertices(g));
1.109 +
1.110 + typename property_map<FlowGraph, edge_capacity_t>::type
1.111 + cap = get(edge_capacity, flow_g);
1.112 + typename property_map<FlowGraph, edge_residual_capacity_t>::type
1.113 + res_cap = get(edge_residual_capacity, flow_g);
1.114 + typename property_map<FlowGraph, edge_reverse_t>::type
1.115 + rev_edge = get(edge_reverse, flow_g);
1.116 +
1.117 + for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
1.118 + u = source(*ei, g), v = target(*ei, g);
1.119 + tie(e1, inserted) = add_edge(u, v, flow_g);
1.120 + cap[e1] = 1;
1.121 + tie(e2, inserted) = add_edge(v, u, flow_g);
1.122 + cap[e2] = 1; // not sure about this
1.123 + rev_edge[e1] = e2;
1.124 + rev_edge[e2] = e1;
1.125 + }
1.126 +
1.127 + //-------------------------------------------------------------------------
1.128 + // The Algorithm
1.129 +
1.130 + tie(p, delta) = detail::min_degree_vertex(g);
1.131 + S_star.push_back(p);
1.132 + alpha_star = delta;
1.133 + S.insert(p);
1.134 + neighbor_S.insert(p);
1.135 + detail::neighbors(g, S.begin(), S.end(),
1.136 + std::inserter(neighbor_S, neighbor_S.begin()));
1.137 +
1.138 + std::set_difference(vertices(g).first, vertices(g).second,
1.139 + neighbor_S.begin(), neighbor_S.end(),
1.140 + std::back_inserter(non_neighbor_S));
1.141 +
1.142 + while (!non_neighbor_S.empty()) { // at most n - 1 times
1.143 + k = non_neighbor_S.front();
1.144 +
1.145 + alpha_S_k = edmunds_karp_max_flow
1.146 + (flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
1.147 +
1.148 + if (alpha_S_k < alpha_star) {
1.149 + alpha_star = alpha_S_k;
1.150 + S_star.clear();
1.151 + for (tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
1.152 + if (color[*vi] != Color::white())
1.153 + S_star.push_back(*vi);
1.154 + }
1.155 + S.insert(k);
1.156 + neighbor_S.insert(k);
1.157 + detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
1.158 + non_neighbor_S.clear();
1.159 + std::set_difference(vertices(g).first, vertices(g).second,
1.160 + neighbor_S.begin(), neighbor_S.end(),
1.161 + std::back_inserter(non_neighbor_S));
1.162 + }
1.163 + //-------------------------------------------------------------------------
1.164 + // Compute edges of the cut [S*, ~S*]
1.165 + std::vector<bool> in_S_star(num_vertices(g), false);
1.166 + typename std::vector<vertex_descriptor>::iterator si;
1.167 + for (si = S_star.begin(); si != S_star.end(); ++si)
1.168 + in_S_star[*si] = true;
1.169 +
1.170 + degree_size_type c = 0;
1.171 + for (si = S_star.begin(); si != S_star.end(); ++si) {
1.172 + out_edge_iterator ei, ei_end;
1.173 + for (tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
1.174 + if (!in_S_star[target(*ei, g)]) {
1.175 + *disconnecting_set++ = *ei;
1.176 + ++c;
1.177 + }
1.178 + }
1.179 + return c;
1.180 + }
1.181 +
1.182 +} // namespace boost
1.183 +
1.184 +#endif // BOOST_EDGE_CONNECTIVITY