?????????? ????????? - ??????????????? - /home/agenciai/public_html/cd38d8/graph.zip
???????
PK L�[���:>! >! floyd_warshall_shortest.hppnu �[��� // Copyright 2002 Rensselaer Polytechnic Institute // 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) // Authors: Lauren Foutz // Scott Hill /* This file implements the functions template <class VertexListGraph, class DistanceMatrix, class P, class T, class R> bool floyd_warshall_initialized_all_pairs_shortest_paths( const VertexListGraph& g, DistanceMatrix& d, const bgl_named_params<P, T, R>& params) AND template <class VertexAndEdgeListGraph, class DistanceMatrix, class P, class T, class R> bool floyd_warshall_all_pairs_shortest_paths( const VertexAndEdgeListGraph& g, DistanceMatrix& d, const bgl_named_params<P, T, R>& params) */ #ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP #define BOOST_GRAPH_FLOYD_WARSHALL_HPP #include <boost/property_map/property_map.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/relax.hpp> #include <boost/concept/assert.hpp> namespace boost { namespace detail { template < typename T, typename BinaryPredicate > T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare) { if (compare(x, y)) return x; else return y; } template < typename VertexListGraph, typename DistanceMatrix, typename BinaryPredicate, typename BinaryFunction, typename Infinity, typename Zero > bool floyd_warshall_dispatch(const VertexListGraph& g, DistanceMatrix& d, const BinaryPredicate& compare, const BinaryFunction& combine, const Infinity& inf, const Zero& zero) { typename graph_traits< VertexListGraph >::vertex_iterator i, lasti, j, lastj, k, lastk; for (boost::tie(k, lastk) = vertices(g); k != lastk; k++) for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) if (d[*i][*k] != inf) for (boost::tie(j, lastj) = vertices(g); j != lastj; j++) if (d[*k][*j] != inf) d[*i][*j] = detail::min_with_compare(d[*i][*j], combine(d[*i][*k], d[*k][*j]), compare); for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) if (compare(d[*i][*i], zero)) return false; return true; } } template < typename VertexListGraph, typename DistanceMatrix, typename BinaryPredicate, typename BinaryFunction, typename Infinity, typename Zero > bool floyd_warshall_initialized_all_pairs_shortest_paths( const VertexListGraph& g, DistanceMatrix& d, const BinaryPredicate& compare, const BinaryFunction& combine, const Infinity& inf, const Zero& zero) { BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexListGraph >)); return detail::floyd_warshall_dispatch(g, d, compare, combine, inf, zero); } template < typename VertexAndEdgeListGraph, typename DistanceMatrix, typename WeightMap, typename BinaryPredicate, typename BinaryFunction, typename Infinity, typename Zero > bool floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph& g, DistanceMatrix& d, const WeightMap& w, const BinaryPredicate& compare, const BinaryFunction& combine, const Infinity& inf, const Zero& zero) { BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexAndEdgeListGraph >)); BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< VertexAndEdgeListGraph >)); BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< VertexAndEdgeListGraph >)); typename graph_traits< VertexAndEdgeListGraph >::vertex_iterator firstv, lastv, firstv2, lastv2; typename graph_traits< VertexAndEdgeListGraph >::edge_iterator first, last; for (boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) for (boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++) d[*firstv][*firstv2] = inf; for (boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) d[*firstv][*firstv] = zero; for (boost::tie(first, last) = edges(g); first != last; first++) { if (d[source(*first, g)][target(*first, g)] != inf) { d[source(*first, g)][target(*first, g)] = detail::min_with_compare(get(w, *first), d[source(*first, g)][target(*first, g)], compare); } else d[source(*first, g)][target(*first, g)] = get(w, *first); } bool is_undirected = is_same< typename graph_traits< VertexAndEdgeListGraph >::directed_category, undirected_tag >::value; if (is_undirected) { for (boost::tie(first, last) = edges(g); first != last; first++) { if (d[target(*first, g)][source(*first, g)] != inf) d[target(*first, g)][source(*first, g)] = detail::min_with_compare(get(w, *first), d[target(*first, g)][source(*first, g)], compare); else d[target(*first, g)][source(*first, g)] = get(w, *first); } } return detail::floyd_warshall_dispatch(g, d, compare, combine, inf, zero); } namespace detail { template < class VertexListGraph, class DistanceMatrix, class WeightMap, class P, class T, class R > bool floyd_warshall_init_dispatch(const VertexListGraph& g, DistanceMatrix& d, WeightMap /*w*/, const bgl_named_params< P, T, R >& params) { typedef typename property_traits< WeightMap >::value_type WM; WM inf = choose_param(get_param(params, distance_inf_t()), std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION()); return floyd_warshall_initialized_all_pairs_shortest_paths(g, d, choose_param( get_param(params, distance_compare_t()), std::less< WM >()), choose_param(get_param(params, distance_combine_t()), closed_plus< WM >(inf)), inf, choose_param(get_param(params, distance_zero_t()), WM())); } template < class VertexAndEdgeListGraph, class DistanceMatrix, class WeightMap, class P, class T, class R > bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g, DistanceMatrix& d, WeightMap w, const bgl_named_params< P, T, R >& params) { typedef typename property_traits< WeightMap >::value_type WM; WM inf = choose_param(get_param(params, distance_inf_t()), std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION()); return floyd_warshall_all_pairs_shortest_paths(g, d, w, choose_param( get_param(params, distance_compare_t()), std::less< WM >()), choose_param(get_param(params, distance_combine_t()), closed_plus< WM >(inf)), inf, choose_param(get_param(params, distance_zero_t()), WM())); } } // namespace detail template < class VertexListGraph, class DistanceMatrix, class P, class T, class R > bool floyd_warshall_initialized_all_pairs_shortest_paths( const VertexListGraph& g, DistanceMatrix& d, const bgl_named_params< P, T, R >& params) { return detail::floyd_warshall_init_dispatch(g, d, choose_const_pmap(get_param(params, edge_weight), g, edge_weight), params); } template < class VertexListGraph, class DistanceMatrix > bool floyd_warshall_initialized_all_pairs_shortest_paths( const VertexListGraph& g, DistanceMatrix& d) { bgl_named_params< int, int > params(0); return detail::floyd_warshall_init_dispatch( g, d, get(edge_weight, g), params); } template < class VertexAndEdgeListGraph, class DistanceMatrix, class P, class T, class R > bool floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph& g, DistanceMatrix& d, const bgl_named_params< P, T, R >& params) { return detail::floyd_warshall_noninit_dispatch(g, d, choose_const_pmap(get_param(params, edge_weight), g, edge_weight), params); } template < class VertexAndEdgeListGraph, class DistanceMatrix > bool floyd_warshall_all_pairs_shortest_paths( const VertexAndEdgeListGraph& g, DistanceMatrix& d) { bgl_named_params< int, int > params(0); return detail::floyd_warshall_noninit_dispatch( g, d, get(edge_weight, g), params); } } // namespace boost #endif PK L�[���. �. king_ordering.hppnu �[��� //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2004, 2005 Trustees of Indiana University // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, // Doug Gregor, D. Kevin McGrath // // 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) //=======================================================================// #ifndef BOOST_GRAPH_KING_HPP #define BOOST_GRAPH_KING_HPP #include <boost/config.hpp> #include <boost/graph/detail/sparse_ordering.hpp> #include <boost/graph/graph_utility.hpp> /* King Algorithm for matrix reordering */ namespace boost { namespace detail { template < typename OutputIterator, typename Buffer, typename Compare, typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap > class bfs_king_visitor : public default_bfs_visitor { public: bfs_king_visitor(OutputIterator* iter, Buffer* b, Compare compare, PseudoDegreeMap deg, std::vector< int > loc, VecMap color, VertexIndexMap vertices) : permutation(iter) , Qptr(b) , degree(deg) , comp(compare) , Qlocation(loc) , colors(color) , vertex_map(vertices) { } template < typename Vertex, typename Graph > void finish_vertex(Vertex, Graph& g) { typename graph_traits< Graph >::out_edge_iterator ei, ei_end; Vertex v, w; typedef typename std::deque< Vertex >::reverse_iterator reverse_iterator; reverse_iterator rend = Qptr->rend() - index_begin; reverse_iterator rbegin = Qptr->rbegin(); // heap the vertices already there std::make_heap(rbegin, rend, boost::bind< bool >(comp, _2, _1)); unsigned i = 0; for (i = index_begin; i != Qptr->size(); ++i) { colors[get(vertex_map, (*Qptr)[i])] = 1; Qlocation[get(vertex_map, (*Qptr)[i])] = i; } i = 0; for (; rbegin != rend; rend--) { percolate_down< Vertex >(i); w = (*Qptr)[index_begin + i]; for (boost::tie(ei, ei_end) = out_edges(w, g); ei != ei_end; ++ei) { v = target(*ei, g); put(degree, v, get(degree, v) - 1); if (colors[get(vertex_map, v)] == 1) { percolate_up< Vertex >(get(vertex_map, v), i); } } colors[get(vertex_map, w)] = 0; i++; } } template < typename Vertex, typename Graph > void examine_vertex(Vertex u, const Graph&) { *(*permutation)++ = u; index_begin = Qptr->size(); } protected: // this function replaces pop_heap, and tracks state information template < typename Vertex > void percolate_down(int offset) { int heap_last = index_begin + offset; int heap_first = Qptr->size() - 1; // pop_heap functionality: // swap first, last std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]); // swap in the location queue std::swap(Qlocation[heap_first], Qlocation[heap_last]); // set drifter, children int drifter = heap_first; int drifter_heap = Qptr->size() - drifter; int right_child_heap = drifter_heap * 2 + 1; int right_child = Qptr->size() - right_child_heap; int left_child_heap = drifter_heap * 2; int left_child = Qptr->size() - left_child_heap; // check that we are staying in the heap bool valid = (right_child < heap_last) ? false : true; // pick smallest child of drifter, and keep in mind there might only // be left child int smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree, (*Qptr)[right_child])) ? right_child : left_child; while (valid && smallest_child < heap_last && comp((*Qptr)[drifter], (*Qptr)[smallest_child])) { // if smallest child smaller than drifter, swap them std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]); std::swap(Qlocation[drifter], Qlocation[smallest_child]); // update the values, run again, as necessary drifter = smallest_child; drifter_heap = Qptr->size() - drifter; right_child_heap = drifter_heap * 2 + 1; right_child = Qptr->size() - right_child_heap; left_child_heap = drifter_heap * 2; left_child = Qptr->size() - left_child_heap; valid = (right_child < heap_last) ? false : true; smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree, (*Qptr)[right_child])) ? right_child : left_child; } } // this is like percolate down, but we always compare against the // parent, as there is only a single choice template < typename Vertex > void percolate_up(int vertex, int offset) { int child_location = Qlocation[vertex]; int heap_child_location = Qptr->size() - child_location; int heap_parent_location = (int)(heap_child_location / 2); unsigned parent_location = Qptr->size() - heap_parent_location; bool valid = (heap_parent_location != 0 && child_location > index_begin + offset && parent_location < Qptr->size()); while (valid && comp((*Qptr)[child_location], (*Qptr)[parent_location])) { // swap in the heap std::swap((*Qptr)[child_location], (*Qptr)[parent_location]); // swap in the location queue std::swap( Qlocation[child_location], Qlocation[parent_location]); child_location = parent_location; heap_child_location = heap_parent_location; heap_parent_location = (int)(heap_child_location / 2); parent_location = Qptr->size() - heap_parent_location; valid = (heap_parent_location != 0 && child_location > index_begin + offset); } } OutputIterator* permutation; int index_begin; Buffer* Qptr; PseudoDegreeMap degree; Compare comp; std::vector< int > Qlocation; VecMap colors; VertexIndexMap vertex_map; }; } // namespace detail template < class Graph, class OutputIterator, class ColorMap, class DegreeMap, typename VertexIndexMap > OutputIterator king_ordering(const Graph& g, std::deque< typename graph_traits< Graph >::vertex_descriptor > vertex_queue, OutputIterator permutation, ColorMap color, DegreeMap degree, VertexIndexMap index_map) { typedef typename property_traits< DegreeMap >::value_type ds_type; typedef typename property_traits< ColorMap >::value_type ColorValue; typedef color_traits< ColorValue > Color; typedef typename graph_traits< Graph >::vertex_descriptor Vertex; typedef iterator_property_map< typename std::vector< ds_type >::iterator, VertexIndexMap, ds_type, ds_type& > PseudoDegreeMap; typedef indirect_cmp< PseudoDegreeMap, std::less< ds_type > > Compare; typedef typename boost::sparse::sparse_ordering_queue< Vertex > queue; typedef typename detail::bfs_king_visitor< OutputIterator, queue, Compare, PseudoDegreeMap, std::vector< int >, VertexIndexMap > Visitor; typedef typename graph_traits< Graph >::vertices_size_type vertices_size_type; std::vector< ds_type > pseudo_degree_vec(num_vertices(g)); PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map); typename graph_traits< Graph >::vertex_iterator ui, ui_end; queue Q; // Copy degree to pseudo_degree // initialize the color map for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { put(pseudo_degree, *ui, get(degree, *ui)); put(color, *ui, Color::white()); } Compare comp(pseudo_degree); std::vector< int > colors(num_vertices(g)); for (vertices_size_type i = 0; i < num_vertices(g); i++) colors[i] = 0; std::vector< int > loc(num_vertices(g)); // create the visitor Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map); while (!vertex_queue.empty()) { Vertex s = vertex_queue.front(); vertex_queue.pop_front(); // call BFS with visitor breadth_first_visit(g, s, Q, vis, color); } return permutation; } // This is the case where only a single starting vertex is supplied. template < class Graph, class OutputIterator, class ColorMap, class DegreeMap, typename VertexIndexMap > OutputIterator king_ordering(const Graph& g, typename graph_traits< Graph >::vertex_descriptor s, OutputIterator permutation, ColorMap color, DegreeMap degree, VertexIndexMap index_map) { std::deque< typename graph_traits< Graph >::vertex_descriptor > vertex_queue; vertex_queue.push_front(s); return king_ordering( g, vertex_queue, permutation, color, degree, index_map); } template < class Graph, class OutputIterator, class ColorMap, class DegreeMap, class VertexIndexMap > OutputIterator king_ordering(const Graph& G, OutputIterator permutation, ColorMap color, DegreeMap degree, VertexIndexMap index_map) { if (has_no_vertices(G)) return permutation; typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex; typedef typename property_traits< ColorMap >::value_type ColorValue; typedef color_traits< ColorValue > Color; std::deque< Vertex > vertex_queue; // Mark everything white BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white()); // Find one vertex from each connected component BGL_FORALL_VERTICES_T(v, G, Graph) { if (get(color, v) == Color::white()) { depth_first_visit(G, v, dfs_visitor<>(), color); vertex_queue.push_back(v); } } // Find starting nodes for all vertices // TBD: How to do this with a directed graph? for (typename std::deque< Vertex >::iterator i = vertex_queue.begin(); i != vertex_queue.end(); ++i) *i = find_starting_node(G, *i, color, degree); return king_ordering( G, vertex_queue, permutation, color, degree, index_map); } template < typename Graph, typename OutputIterator, typename VertexIndexMap > OutputIterator king_ordering( const Graph& G, OutputIterator permutation, VertexIndexMap index_map) { if (has_no_vertices(G)) return permutation; std::vector< default_color_type > colors(num_vertices(G)); return king_ordering(G, permutation, make_iterator_property_map(&colors[0], index_map, colors[0]), make_out_degree_map(G), index_map); } template < typename Graph, typename OutputIterator > inline OutputIterator king_ordering(const Graph& G, OutputIterator permutation) { return king_ordering(G, permutation, get(vertex_index, G)); } } // namespace boost #endif // BOOST_GRAPH_KING_HPP PK L�[r-Y� � random_spanning_tree.hppnu �[��� // Copyright 2010 The Trustees of Indiana University. // 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) // Authors: Jeremiah Willcock // Andrew Lumsdaine #ifndef BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP #define BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP #include <vector> #include <boost/assert.hpp> #include <boost/graph/loop_erased_random_walk.hpp> #include <boost/graph/random.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/property_map/property_map.hpp> #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/named_function_params.hpp> namespace boost { namespace detail { // Use Wilson's algorithm (based on loop-free random walks) to generate a // random spanning tree. The distribution of edges used is controlled by // the next_edge() function, so this version allows either weighted or // unweighted selection of trees. // Algorithm is from http://en.wikipedia.org/wiki/Uniform_spanning_tree template < typename Graph, typename PredMap, typename ColorMap, typename NextEdge > void random_spanning_tree_internal(const Graph& g, typename graph_traits< Graph >::vertex_descriptor s, PredMap pred, ColorMap color, NextEdge next_edge) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; BOOST_ASSERT(num_vertices(g) >= 1); // g must also be undirected (or symmetric) and connected typedef color_traits< typename property_traits< ColorMap >::value_type > color_gen; BGL_FORALL_VERTICES_T(v, g, Graph) put(color, v, color_gen::white()); std::vector< vertex_descriptor > path; put(color, s, color_gen::black()); put(pred, s, graph_traits< Graph >::null_vertex()); BGL_FORALL_VERTICES_T(v, g, Graph) { if (get(color, v) != color_gen::white()) continue; loop_erased_random_walk(g, v, next_edge, color, path); for (typename std::vector< vertex_descriptor >::const_reverse_iterator i = path.rbegin(); boost::next(i) != (typename std::vector< vertex_descriptor >::const_reverse_iterator)path.rend(); ++i) { typename std::vector< vertex_descriptor >::const_reverse_iterator j = i; ++j; BOOST_ASSERT(get(color, *j) == color_gen::gray()); put(color, *j, color_gen::black()); put(pred, *j, *i); } } } } // Compute a uniformly-distributed spanning tree on a graph. Use Wilson's // algorithm: // @inproceedings{wilson96generating, // author = {Wilson, David Bruce}, // title = {Generating random spanning trees more quickly than the cover // time}, booktitle = {STOC '96: Proceedings of the twenty-eighth annual ACM // symposium on Theory of computing}, year = {1996}, isbn = {0-89791-785-5}, // pages = {296--303}, // location = {Philadelphia, Pennsylvania, United States}, // doi = {http://doi.acm.org/10.1145/237814.237880}, // publisher = {ACM}, // address = {New York, NY, USA}, // } // template < typename Graph, typename Gen, typename PredMap, typename ColorMap > void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits< Graph >::vertex_descriptor root, PredMap pred, static_property_map< double >, ColorMap color) { unweighted_random_out_edge_gen< Graph, Gen > random_oe(gen); detail::random_spanning_tree_internal(g, root, pred, color, random_oe); } // Compute a weight-distributed spanning tree on a graph. template < typename Graph, typename Gen, typename PredMap, typename WeightMap, typename ColorMap > void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits< Graph >::vertex_descriptor root, PredMap pred, WeightMap weight, ColorMap color) { weighted_random_out_edge_gen< Graph, WeightMap, Gen > random_oe( weight, gen); detail::random_spanning_tree_internal(g, root, pred, color, random_oe); } template < typename Graph, typename Gen, typename P, typename T, typename R > void random_spanning_tree( const Graph& g, Gen& gen, const bgl_named_params< P, T, R >& params) { using namespace boost::graph::keywords; typedef bgl_named_params< P, T, R > params_type; BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; vertex_descriptor default_vertex = *vertices(g).first; vertex_descriptor start_vertex = arg_pack[_root_vertex | default_vertex]; typename boost::parameter::binding< arg_pack_type, boost::graph::keywords::tag::predecessor_map >::type pred_map = arg_pack[_predecessor_map]; static_property_map< double > default_weight_map(1.); typename boost::parameter::value_type< arg_pack_type, boost::graph::keywords::tag::weight_map, static_property_map< double > >::type e_w_map = arg_pack[_weight_map | default_weight_map]; typename boost::detail::map_maker< Graph, arg_pack_type, boost::graph::keywords::tag::color_map, boost::default_color_type >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); random_spanning_tree(g, gen, start_vertex, pred_map, e_w_map, c_map); } } #include <boost/graph/iteration_macros_undef.hpp> #endif // BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP PK L�[���H% % bellman_ford_shortest_paths.hppnu �[��� // //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // 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) //======================================================================= // /* This file implements the function template <class EdgeListGraph, class Size, class P, class T, class R> bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N, const bgl_named_params<P, T, R>& params) */ #ifndef BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP #define BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/relax.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/concept/assert.hpp> namespace boost { template < class Visitor, class Graph > struct BellmanFordVisitorConcept { void constraints() { BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >)); vis.examine_edge(e, g); vis.edge_relaxed(e, g); vis.edge_not_relaxed(e, g); vis.edge_minimized(e, g); vis.edge_not_minimized(e, g); } Visitor vis; Graph g; typename graph_traits< Graph >::edge_descriptor e; }; template < class Visitors = null_visitor > class bellman_visitor { public: bellman_visitor() {} bellman_visitor(Visitors vis) : m_vis(vis) {} template < class Edge, class Graph > void examine_edge(Edge u, Graph& g) { invoke_visitors(m_vis, u, g, on_examine_edge()); } template < class Edge, class Graph > void edge_relaxed(Edge u, Graph& g) { invoke_visitors(m_vis, u, g, on_edge_relaxed()); } template < class Edge, class Graph > void edge_not_relaxed(Edge u, Graph& g) { invoke_visitors(m_vis, u, g, on_edge_not_relaxed()); } template < class Edge, class Graph > void edge_minimized(Edge u, Graph& g) { invoke_visitors(m_vis, u, g, on_edge_minimized()); } template < class Edge, class Graph > void edge_not_minimized(Edge u, Graph& g) { invoke_visitors(m_vis, u, g, on_edge_not_minimized()); } protected: Visitors m_vis; }; template < class Visitors > bellman_visitor< Visitors > make_bellman_visitor(Visitors vis) { return bellman_visitor< Visitors >(vis); } typedef bellman_visitor<> default_bellman_visitor; template < class EdgeListGraph, class Size, class WeightMap, class PredecessorMap, class DistanceMap, class BinaryFunction, class BinaryPredicate, class BellmanFordVisitor > bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance, BinaryFunction combine, BinaryPredicate compare, BellmanFordVisitor v) { BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< EdgeListGraph >)); typedef graph_traits< EdgeListGraph > GTraits; typedef typename GTraits::edge_descriptor Edge; typedef typename GTraits::vertex_descriptor Vertex; BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< DistanceMap, Vertex >)); BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< WeightMap, Edge >)); typename GTraits::edge_iterator i, end; for (Size k = 0; k < N; ++k) { bool at_least_one_edge_relaxed = false; for (boost::tie(i, end) = edges(g); i != end; ++i) { v.examine_edge(*i, g); if (relax(*i, g, weight, pred, distance, combine, compare)) { at_least_one_edge_relaxed = true; v.edge_relaxed(*i, g); } else v.edge_not_relaxed(*i, g); } if (!at_least_one_edge_relaxed) break; } for (boost::tie(i, end) = edges(g); i != end; ++i) if (compare(combine(get(distance, source(*i, g)), get(weight, *i)), get(distance, target(*i, g)))) { v.edge_not_minimized(*i, g); return false; } else v.edge_minimized(*i, g); return true; } namespace detail { template < typename VertexAndEdgeListGraph, typename Size, typename WeightMap, typename PredecessorMap, typename DistanceMap, typename P, typename T, typename R > bool bellman_dispatch2(VertexAndEdgeListGraph& g, typename graph_traits< VertexAndEdgeListGraph >::vertex_descriptor s, Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance, const bgl_named_params< P, T, R >& params) { typedef typename property_traits< DistanceMap >::value_type D; bellman_visitor<> null_vis; typedef typename property_traits< WeightMap >::value_type weight_type; typename graph_traits< VertexAndEdgeListGraph >::vertex_iterator v, v_end; for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) { put(distance, *v, (std::numeric_limits< weight_type >::max)()); put(pred, *v, *v); } put(distance, s, weight_type(0)); return bellman_ford_shortest_paths(g, N, weight, pred, distance, choose_param( get_param(params, distance_combine_t()), closed_plus< D >()), choose_param( get_param(params, distance_compare_t()), std::less< D >()), choose_param(get_param(params, graph_visitor), null_vis)); } template < typename VertexAndEdgeListGraph, typename Size, typename WeightMap, typename PredecessorMap, typename DistanceMap, typename P, typename T, typename R > bool bellman_dispatch2(VertexAndEdgeListGraph& g, param_not_found, Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance, const bgl_named_params< P, T, R >& params) { typedef typename property_traits< DistanceMap >::value_type D; bellman_visitor<> null_vis; return bellman_ford_shortest_paths(g, N, weight, pred, distance, choose_param( get_param(params, distance_combine_t()), closed_plus< D >()), choose_param( get_param(params, distance_compare_t()), std::less< D >()), choose_param(get_param(params, graph_visitor), null_vis)); } template < class EdgeListGraph, class Size, class WeightMap, class DistanceMap, class P, class T, class R > bool bellman_dispatch(EdgeListGraph& g, Size N, WeightMap weight, DistanceMap distance, const bgl_named_params< P, T, R >& params) { dummy_property_map dummy_pred; return detail::bellman_dispatch2(g, get_param(params, root_vertex_t()), N, weight, choose_param(get_param(params, vertex_predecessor), dummy_pred), distance, params); } } // namespace detail template < class EdgeListGraph, class Size, class P, class T, class R > bool bellman_ford_shortest_paths( EdgeListGraph& g, Size N, const bgl_named_params< P, T, R >& params) { return detail::bellman_dispatch(g, N, choose_const_pmap(get_param(params, edge_weight), g, edge_weight), choose_pmap(get_param(params, vertex_distance), g, vertex_distance), params); } template < class EdgeListGraph, class Size > bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N) { bgl_named_params< int, int > params(0); return bellman_ford_shortest_paths(g, N, params); } template < class VertexAndEdgeListGraph, class P, class T, class R > bool bellman_ford_shortest_paths( VertexAndEdgeListGraph& g, const bgl_named_params< P, T, R >& params) { BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexAndEdgeListGraph >)); return detail::bellman_dispatch(g, num_vertices(g), choose_const_pmap(get_param(params, edge_weight), g, edge_weight), choose_pmap(get_param(params, vertex_distance), g, vertex_distance), params); } } // namespace boost #endif // BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP PK L�[I�@0 0 relax.hppnu �[��� //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, // // 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) //======================================================================= #ifndef BOOST_GRAPH_RELAX_HPP #define BOOST_GRAPH_RELAX_HPP #include <functional> #include <boost/limits.hpp> // for numeric limits #include <boost/graph/graph_traits.hpp> #include <boost/property_map/property_map.hpp> namespace boost { // The following version of the plus functor prevents // problems due to overflow at positive infinity. template < class T > struct closed_plus { const T inf; closed_plus() : inf((std::numeric_limits< T >::max)()) {} closed_plus(T inf) : inf(inf) {} T operator()(const T& a, const T& b) const { using namespace std; if (a == inf) return inf; if (b == inf) return inf; return a + b; } }; template < class Graph, class WeightMap, class PredecessorMap, class DistanceMap, class BinaryFunction, class BinaryPredicate > bool relax(typename graph_traits< Graph >::edge_descriptor e, const Graph& g, const WeightMap& w, PredecessorMap& p, DistanceMap& d, const BinaryFunction& combine, const BinaryPredicate& compare) { typedef typename graph_traits< Graph >::directed_category DirCat; bool is_undirected = is_same< DirCat, undirected_tag >::value; typedef typename graph_traits< Graph >::vertex_descriptor Vertex; Vertex u = source(e, g), v = target(e, g); typedef typename property_traits< DistanceMap >::value_type D; typedef typename property_traits< WeightMap >::value_type W; const D d_u = get(d, u); const D d_v = get(d, v); const W& w_e = get(w, e); // The seemingly redundant comparisons after the distance puts are to // ensure that extra floating-point precision in x87 registers does not // lead to relax() returning true when the distance did not actually // change. if (compare(combine(d_u, w_e), d_v)) { put(d, v, combine(d_u, w_e)); if (compare(get(d, v), d_v)) { put(p, v, u); return true; } else { return false; } } else if (is_undirected && compare(combine(d_v, w_e), d_u)) { put(d, u, combine(d_v, w_e)); if (compare(get(d, u), d_u)) { put(p, u, v); return true; } else { return false; } } else return false; } template < class Graph, class WeightMap, class PredecessorMap, class DistanceMap, class BinaryFunction, class BinaryPredicate > bool relax_target(typename graph_traits< Graph >::edge_descriptor e, const Graph& g, const WeightMap& w, PredecessorMap& p, DistanceMap& d, const BinaryFunction& combine, const BinaryPredicate& compare) { typedef typename graph_traits< Graph >::vertex_descriptor Vertex; typedef typename property_traits< DistanceMap >::value_type D; typedef typename property_traits< WeightMap >::value_type W; const Vertex u = source(e, g); const Vertex v = target(e, g); const D d_u = get(d, u); const D d_v = get(d, v); const W& w_e = get(w, e); // The seemingly redundant comparisons after the distance puts are to // ensure that extra floating-point precision in x87 registers does not // lead to relax() returning true when the distance did not actually // change. if (compare(combine(d_u, w_e), d_v)) { put(d, v, combine(d_u, w_e)); if (compare(get(d, v), d_v)) { put(p, v, u); return true; } } return false; } template < class Graph, class WeightMap, class PredecessorMap, class DistanceMap > bool relax(typename graph_traits< Graph >::edge_descriptor e, const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d) { typedef typename property_traits< DistanceMap >::value_type D; typedef closed_plus< D > Combine; typedef std::less< D > Compare; return relax(e, g, w, p, d, Combine(), Compare()); } } // namespace boost #endif /* BOOST_GRAPH_RELAX_HPP */ PK L�[59�S( ( is_kuratowski_subgraph.hppnu �[��� //======================================================================= // Copyright 2007 Aaron Windsor // // 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) //======================================================================= #ifndef __IS_KURATOWSKI_SUBGRAPH_HPP__ #define __IS_KURATOWSKI_SUBGRAPH_HPP__ #include <boost/config.hpp> #include <boost/tuple/tuple.hpp> //for tie #include <boost/property_map/property_map.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/isomorphism.hpp> #include <boost/graph/adjacency_list.hpp> #include <algorithm> #include <vector> #include <set> namespace boost { namespace detail { template < typename Graph > Graph make_K_5() { typename graph_traits< Graph >::vertex_iterator vi, vi_end, inner_vi; Graph K_5(5); for (boost::tie(vi, vi_end) = vertices(K_5); vi != vi_end; ++vi) for (inner_vi = next(vi); inner_vi != vi_end; ++inner_vi) add_edge(*vi, *inner_vi, K_5); return K_5; } template < typename Graph > Graph make_K_3_3() { typename graph_traits< Graph >::vertex_iterator vi, vi_end, bipartition_start, inner_vi; Graph K_3_3(6); bipartition_start = next(next(next(vertices(K_3_3).first))); for (boost::tie(vi, vi_end) = vertices(K_3_3); vi != bipartition_start; ++vi) for (inner_vi = bipartition_start; inner_vi != vi_end; ++inner_vi) add_edge(*vi, *inner_vi, K_3_3); return K_3_3; } template < typename AdjacencyList, typename Vertex > void contract_edge(AdjacencyList& neighbors, Vertex u, Vertex v) { // Remove u from v's neighbor list neighbors[v].erase( std::remove(neighbors[v].begin(), neighbors[v].end(), u), neighbors[v].end()); // Replace any references to u with references to v typedef typename AdjacencyList::value_type::iterator adjacency_iterator_t; adjacency_iterator_t u_neighbor_end = neighbors[u].end(); for (adjacency_iterator_t u_neighbor_itr = neighbors[u].begin(); u_neighbor_itr != u_neighbor_end; ++u_neighbor_itr) { Vertex u_neighbor(*u_neighbor_itr); std::replace(neighbors[u_neighbor].begin(), neighbors[u_neighbor].end(), u, v); } // Remove v from u's neighbor list neighbors[u].erase( std::remove(neighbors[u].begin(), neighbors[u].end(), v), neighbors[u].end()); // Add everything in u's neighbor list to v's neighbor list std::copy(neighbors[u].begin(), neighbors[u].end(), std::back_inserter(neighbors[v])); // Clear u's neighbor list neighbors[u].clear(); } enum target_graph_t { tg_k_3_3, tg_k_5 }; } // namespace detail template < typename Graph, typename ForwardIterator, typename VertexIndexMap > bool is_kuratowski_subgraph(const Graph& g, ForwardIterator begin, ForwardIterator end, VertexIndexMap vm) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; typedef typename graph_traits< Graph >::edge_descriptor edge_t; typedef typename graph_traits< Graph >::edges_size_type e_size_t; typedef typename graph_traits< Graph >::vertices_size_type v_size_t; typedef typename std::vector< vertex_t > v_list_t; typedef typename v_list_t::iterator v_list_iterator_t; typedef iterator_property_map< typename std::vector< v_list_t >::iterator, VertexIndexMap > vertex_to_v_list_map_t; typedef adjacency_list< vecS, vecS, undirectedS > small_graph_t; detail::target_graph_t target_graph = detail::tg_k_3_3; // unless we decide otherwise later static small_graph_t K_5(detail::make_K_5< small_graph_t >()); static small_graph_t K_3_3(detail::make_K_3_3< small_graph_t >()); v_size_t n_vertices(num_vertices(g)); v_size_t max_num_edges(3 * n_vertices - 5); std::vector< v_list_t > neighbors_vector(n_vertices); vertex_to_v_list_map_t neighbors(neighbors_vector.begin(), vm); e_size_t count = 0; for (ForwardIterator itr = begin; itr != end; ++itr) { if (count++ > max_num_edges) return false; edge_t e(*itr); vertex_t u(source(e, g)); vertex_t v(target(e, g)); neighbors[u].push_back(v); neighbors[v].push_back(u); } for (v_size_t max_size = 2; max_size < 5; ++max_size) { vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { vertex_t v(*vi); // a hack to make sure we don't contract the middle edge of a path // of four degree-3 vertices if (max_size == 4 && neighbors[v].size() == 3) { if (neighbors[neighbors[v][0]].size() + neighbors[neighbors[v][1]].size() + neighbors[neighbors[v][2]].size() < 11 // so, it has two degree-3 neighbors ) continue; } while (neighbors[v].size() > 0 && neighbors[v].size() < max_size) { // Find one of v's neighbors u such that v and u // have no neighbors in common. We'll look for such a // neighbor with a naive cubic-time algorithm since the // max size of any of the neighbor sets we'll consider // merging is 3 bool neighbor_sets_intersect = false; vertex_t min_u = graph_traits< Graph >::null_vertex(); vertex_t u; v_list_iterator_t v_neighbor_end = neighbors[v].end(); for (v_list_iterator_t v_neighbor_itr = neighbors[v].begin(); v_neighbor_itr != v_neighbor_end; ++v_neighbor_itr) { neighbor_sets_intersect = false; u = *v_neighbor_itr; v_list_iterator_t u_neighbor_end = neighbors[u].end(); for (v_list_iterator_t u_neighbor_itr = neighbors[u].begin(); u_neighbor_itr != u_neighbor_end && !neighbor_sets_intersect; ++u_neighbor_itr) { for (v_list_iterator_t inner_v_neighbor_itr = neighbors[v].begin(); inner_v_neighbor_itr != v_neighbor_end; ++inner_v_neighbor_itr) { if (*u_neighbor_itr == *inner_v_neighbor_itr) { neighbor_sets_intersect = true; break; } } } if (!neighbor_sets_intersect && (min_u == graph_traits< Graph >::null_vertex() || neighbors[u].size() < neighbors[min_u].size())) { min_u = u; } } if (min_u == graph_traits< Graph >::null_vertex()) // Exited the loop without finding an appropriate neighbor // of v, so v must be a lost cause. Move on to other // vertices. break; else u = min_u; detail::contract_edge(neighbors, u, v); } // end iteration over v's neighbors } // end iteration through vertices v if (max_size == 3) { // check to see whether we should go on to find a K_5 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) if (neighbors[*vi].size() == 4) { target_graph = detail::tg_k_5; break; } if (target_graph == detail::tg_k_3_3) break; } } // end iteration through max degree 2,3, and 4 // Now, there should only be 5 or 6 vertices with any neighbors. Find them. v_list_t main_vertices; vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { if (!neighbors[*vi].empty()) main_vertices.push_back(*vi); } // create a graph isomorphic to the contracted graph to test // against K_5 and K_3_3 small_graph_t contracted_graph(main_vertices.size()); std::map< vertex_t, typename graph_traits< small_graph_t >::vertex_descriptor > contracted_vertex_map; typename v_list_t::iterator itr, itr_end; itr_end = main_vertices.end(); typename graph_traits< small_graph_t >::vertex_iterator si = vertices(contracted_graph).first; for (itr = main_vertices.begin(); itr != itr_end; ++itr, ++si) { contracted_vertex_map[*itr] = *si; } typename v_list_t::iterator jtr, jtr_end; for (itr = main_vertices.begin(); itr != itr_end; ++itr) { jtr_end = neighbors[*itr].end(); for (jtr = neighbors[*itr].begin(); jtr != jtr_end; ++jtr) { if (get(vm, *itr) < get(vm, *jtr)) { add_edge(contracted_vertex_map[*itr], contracted_vertex_map[*jtr], contracted_graph); } } } if (target_graph == detail::tg_k_5) { return boost::isomorphism(K_5, contracted_graph); } else // target_graph == tg_k_3_3 { return boost::isomorphism(K_3_3, contracted_graph); } } template < typename Graph, typename ForwardIterator > bool is_kuratowski_subgraph( const Graph& g, ForwardIterator begin, ForwardIterator end) { return is_kuratowski_subgraph(g, begin, end, get(vertex_index, g)); } } #endif //__IS_KURATOWSKI_SUBGRAPH_HPP__ PK L�[�p9^up up leda_graph.hppnu �[��� //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2004 The Trustees of Indiana University. // Copyright 2007 University of Karlsruhe // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor, // Jens Mueller // // 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) //======================================================================= #ifndef BOOST_GRAPH_LEDA_HPP #define BOOST_GRAPH_LEDA_HPP #include <boost/config.hpp> #include <boost/iterator/iterator_facade.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/properties.hpp> #include <LEDA/graph/graph.h> #include <LEDA/graph/node_array.h> #include <LEDA/graph/node_map.h> // The functions and classes in this file allows the user to // treat a LEDA GRAPH object as a boost graph "as is". No // wrapper is needed for the GRAPH object. // Warning: this implementation relies on partial specialization // for the graph_traits class (so it won't compile with Visual C++) // Warning: this implementation is in alpha and has not been tested namespace boost { struct leda_graph_traversal_category : public virtual bidirectional_graph_tag, public virtual adjacency_graph_tag, public virtual vertex_list_graph_tag { }; template < class vtype, class etype > struct graph_traits< leda::GRAPH< vtype, etype > > { typedef leda::node vertex_descriptor; typedef leda::edge edge_descriptor; class adjacency_iterator : public iterator_facade< adjacency_iterator, leda::node, bidirectional_traversal_tag, leda::node, const leda::node* > { public: adjacency_iterator( leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) : base(node), g(g) { } private: leda::node dereference() const { return leda::target(base); } bool equal(const adjacency_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::GRAPH< vtype, etype >* g; friend class iterator_core_access; }; class out_edge_iterator : public iterator_facade< out_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge* > { public: out_edge_iterator( leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) : base(node), g(g) { } private: const leda::edge& dereference() const { return base; } bool equal(const out_edge_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::GRAPH< vtype, etype >* g; friend class iterator_core_access; }; class in_edge_iterator : public iterator_facade< in_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge* > { public: in_edge_iterator( leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) : base(node), g(g) { } private: const leda::edge& dereference() const { return base; } bool equal(const in_edge_iterator& other) const { return base == other.base; } void increment() { base = g->in_succ(base); } void decrement() { base = g->in_pred(base); } leda::edge base; const leda::GRAPH< vtype, etype >* g; friend class iterator_core_access; }; class vertex_iterator : public iterator_facade< vertex_iterator, leda::node, bidirectional_traversal_tag, const leda::node&, const leda::node* > { public: vertex_iterator( leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) : base(node), g(g) { } private: const leda::node& dereference() const { return base; } bool equal(const vertex_iterator& other) const { return base == other.base; } void increment() { base = g->succ_node(base); } void decrement() { base = g->pred_node(base); } leda::node base; const leda::GRAPH< vtype, etype >* g; friend class iterator_core_access; }; class edge_iterator : public iterator_facade< edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge* > { public: edge_iterator( leda::edge edge = 0, const leda::GRAPH< vtype, etype >* g = 0) : base(edge), g(g) { } private: const leda::edge& dereference() const { return base; } bool equal(const edge_iterator& other) const { return base == other.base; } void increment() { base = g->succ_edge(base); } void decrement() { base = g->pred_edge(base); } leda::node base; const leda::GRAPH< vtype, etype >* g; friend class iterator_core_access; }; typedef directed_tag directed_category; typedef allow_parallel_edge_tag edge_parallel_category; // not sure here typedef leda_graph_traversal_category traversal_category; typedef int vertices_size_type; typedef int edges_size_type; typedef int degree_size_type; }; template <> struct graph_traits< leda::graph > { typedef leda::node vertex_descriptor; typedef leda::edge edge_descriptor; class adjacency_iterator : public iterator_facade< adjacency_iterator, leda::node, bidirectional_traversal_tag, leda::node, const leda::node* > { public: adjacency_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) { } private: leda::node dereference() const { return leda::target(base); } bool equal(const adjacency_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class out_edge_iterator : public iterator_facade< out_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge* > { public: out_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) { } private: const leda::edge& dereference() const { return base; } bool equal(const out_edge_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class in_edge_iterator : public iterator_facade< in_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge* > { public: in_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) { } private: const leda::edge& dereference() const { return base; } bool equal(const in_edge_iterator& other) const { return base == other.base; } void increment() { base = g->in_succ(base); } void decrement() { base = g->in_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class vertex_iterator : public iterator_facade< vertex_iterator, leda::node, bidirectional_traversal_tag, const leda::node&, const leda::node* > { public: vertex_iterator(leda::node node = 0, const leda::graph* g = 0) : base(node), g(g) { } private: const leda::node& dereference() const { return base; } bool equal(const vertex_iterator& other) const { return base == other.base; } void increment() { base = g->succ_node(base); } void decrement() { base = g->pred_node(base); } leda::node base; const leda::graph* g; friend class iterator_core_access; }; class edge_iterator : public iterator_facade< edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge* > { public: edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) { } private: const leda::edge& dereference() const { return base; } bool equal(const edge_iterator& other) const { return base == other.base; } void increment() { base = g->succ_edge(base); } void decrement() { base = g->pred_edge(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; typedef directed_tag directed_category; typedef allow_parallel_edge_tag edge_parallel_category; // not sure here typedef leda_graph_traversal_category traversal_category; typedef int vertices_size_type; typedef int edges_size_type; typedef int degree_size_type; }; } // namespace boost namespace boost { //=========================================================================== // functions for GRAPH<vtype,etype> template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor source( typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e, const leda::GRAPH< vtype, etype >& g) { return source(e); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor target( typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e, const leda::GRAPH< vtype, etype >& g) { return target(e); } template < class vtype, class etype > inline std::pair< typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator, typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator > vertices(const leda::GRAPH< vtype, etype >& g) { typedef typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator Iter; return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g)); } template < class vtype, class etype > inline std::pair< typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator, typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator > edges(const leda::GRAPH< vtype, etype >& g) { typedef typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator Iter; return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g)); } template < class vtype, class etype > inline std::pair< typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator, typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator > out_edges( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, const leda::GRAPH< vtype, etype >& g) { typedef typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator Iter; return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g)); } template < class vtype, class etype > inline std::pair< typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator, typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator > in_edges( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, const leda::GRAPH< vtype, etype >& g) { typedef typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator Iter; return std::make_pair(Iter(g.first_adj_edge(u, 1), &g), Iter(0, &g)); } template < class vtype, class etype > inline std::pair< typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator, typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator > adjacent_vertices( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, const leda::GRAPH< vtype, etype >& g) { typedef typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator Iter; return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g)); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::vertices_size_type num_vertices(const leda::GRAPH< vtype, etype >& g) { return g.number_of_nodes(); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::edges_size_type num_edges( const leda::GRAPH< vtype, etype >& g) { return g.number_of_edges(); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type out_degree( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, const leda::GRAPH< vtype, etype >& g) { return g.outdeg(u); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type in_degree( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, const leda::GRAPH< vtype, etype >& g) { return g.indeg(u); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type degree( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, const leda::GRAPH< vtype, etype >& g) { return g.outdeg(u) + g.indeg(u); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor add_vertex(leda::GRAPH< vtype, etype >& g) { return g.new_node(); } template < class vtype, class etype > typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor add_vertex(const vtype& vp, leda::GRAPH< vtype, etype >& g) { return g.new_node(vp); } template < class vtype, class etype > void clear_vertex( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, leda::GRAPH< vtype, etype >& g) { typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++) remove_edge(*ei); typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator iei, iei_end; for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++) remove_edge(*iei); } template < class vtype, class etype > void remove_vertex( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, leda::GRAPH< vtype, etype >& g) { g.del_node(u); } template < class vtype, class etype > std::pair< typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor, bool > add_edge( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v, leda::GRAPH< vtype, etype >& g) { return std::make_pair(g.new_edge(u, v), true); } template < class vtype, class etype > std::pair< typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor, bool > add_edge( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v, const etype& et, leda::GRAPH< vtype, etype >& g) { return std::make_pair(g.new_edge(u, v, et), true); } template < class vtype, class etype > void remove_edge( typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v, leda::GRAPH< vtype, etype >& g) { typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator i, iend; for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i) if (target(*i, g) == v) g.del_edge(*i); } template < class vtype, class etype > void remove_edge( typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e, leda::GRAPH< vtype, etype >& g) { g.del_edge(e); } //=========================================================================== // functions for graph (non-templated version) graph_traits< leda::graph >::vertex_descriptor source( graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g) { return source(e); } graph_traits< leda::graph >::vertex_descriptor target( graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g) { return target(e); } inline std::pair< graph_traits< leda::graph >::vertex_iterator, graph_traits< leda::graph >::vertex_iterator > vertices(const leda::graph& g) { typedef graph_traits< leda::graph >::vertex_iterator Iter; return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g)); } inline std::pair< graph_traits< leda::graph >::edge_iterator, graph_traits< leda::graph >::edge_iterator > edges(const leda::graph& g) { typedef graph_traits< leda::graph >::edge_iterator Iter; return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g)); } inline std::pair< graph_traits< leda::graph >::out_edge_iterator, graph_traits< leda::graph >::out_edge_iterator > out_edges( graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) { typedef graph_traits< leda::graph >::out_edge_iterator Iter; return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g)); } inline std::pair< graph_traits< leda::graph >::in_edge_iterator, graph_traits< leda::graph >::in_edge_iterator > in_edges(graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) { typedef graph_traits< leda::graph >::in_edge_iterator Iter; return std::make_pair(Iter(g.first_in_edge(u), &g), Iter(0, &g)); } inline std::pair< graph_traits< leda::graph >::adjacency_iterator, graph_traits< leda::graph >::adjacency_iterator > adjacent_vertices( graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) { typedef graph_traits< leda::graph >::adjacency_iterator Iter; return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g)); } graph_traits< leda::graph >::vertices_size_type num_vertices( const leda::graph& g) { return g.number_of_nodes(); } graph_traits< leda::graph >::edges_size_type num_edges(const leda::graph& g) { return g.number_of_edges(); } graph_traits< leda::graph >::degree_size_type out_degree( graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) { return g.outdeg(u); } graph_traits< leda::graph >::degree_size_type in_degree( graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) { return g.indeg(u); } graph_traits< leda::graph >::degree_size_type degree( graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) { return g.outdeg(u) + g.indeg(u); } graph_traits< leda::graph >::vertex_descriptor add_vertex(leda::graph& g) { return g.new_node(); } void remove_edge(graph_traits< leda::graph >::vertex_descriptor u, graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g) { graph_traits< leda::graph >::out_edge_iterator i, iend; for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i) if (target(*i, g) == v) g.del_edge(*i); } void remove_edge(graph_traits< leda::graph >::edge_descriptor e, leda::graph& g) { g.del_edge(e); } void clear_vertex( graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g) { graph_traits< leda::graph >::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++) remove_edge(*ei, g); graph_traits< leda::graph >::in_edge_iterator iei, iei_end; for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++) remove_edge(*iei, g); } void remove_vertex( graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g) { g.del_node(u); } std::pair< graph_traits< leda::graph >::edge_descriptor, bool > add_edge( graph_traits< leda::graph >::vertex_descriptor u, graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g) { return std::make_pair(g.new_edge(u, v), true); } //=========================================================================== // property maps for GRAPH<vtype,etype> class leda_graph_id_map : public put_get_helper< int, leda_graph_id_map > { public: typedef readable_property_map_tag category; typedef int value_type; typedef int reference; typedef leda::node key_type; leda_graph_id_map() {} template < class T > long operator[](T x) const { return x->id(); } }; template < class vtype, class etype > inline leda_graph_id_map get( vertex_index_t, const leda::GRAPH< vtype, etype >& g) { return leda_graph_id_map(); } template < class vtype, class etype > inline leda_graph_id_map get(edge_index_t, const leda::GRAPH< vtype, etype >& g) { return leda_graph_id_map(); } template < class Tag > struct leda_property_map { }; template <> struct leda_property_map< vertex_index_t > { template < class vtype, class etype > struct bind_ { typedef leda_graph_id_map type; typedef leda_graph_id_map const_type; }; }; template <> struct leda_property_map< edge_index_t > { template < class vtype, class etype > struct bind_ { typedef leda_graph_id_map type; typedef leda_graph_id_map const_type; }; }; template < class Data, class DataRef, class GraphPtr > class leda_graph_data_map : public put_get_helper< DataRef, leda_graph_data_map< Data, DataRef, GraphPtr > > { public: typedef Data value_type; typedef DataRef reference; typedef void key_type; typedef lvalue_property_map_tag category; leda_graph_data_map(GraphPtr g) : m_g(g) {} template < class NodeOrEdge > DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; } protected: GraphPtr m_g; }; template <> struct leda_property_map< vertex_all_t > { template < class vtype, class etype > struct bind_ { typedef leda_graph_data_map< vtype, vtype&, leda::GRAPH< vtype, etype >* > type; typedef leda_graph_data_map< vtype, const vtype&, const leda::GRAPH< vtype, etype >* > const_type; }; }; template < class vtype, class etype > inline typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::type get(vertex_all_t, leda::GRAPH< vtype, etype >& g) { typedef typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::type pmap_type; return pmap_type(&g); } template < class vtype, class etype > inline typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::const_type get(vertex_all_t, const leda::GRAPH< vtype, etype >& g) { typedef typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::const_type pmap_type; return pmap_type(&g); } template <> struct leda_property_map< edge_all_t > { template < class vtype, class etype > struct bind_ { typedef leda_graph_data_map< etype, etype&, leda::GRAPH< vtype, etype >* > type; typedef leda_graph_data_map< etype, const etype&, const leda::GRAPH< vtype, etype >* > const_type; }; }; template < class vtype, class etype > inline typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::type get(edge_all_t, leda::GRAPH< vtype, etype >& g) { typedef typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::type pmap_type; return pmap_type(&g); } template < class vtype, class etype > inline typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::const_type get(edge_all_t, const leda::GRAPH< vtype, etype >& g) { typedef typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::const_type pmap_type; return pmap_type(&g); } // property map interface to the LEDA node_array class template < class E, class ERef, class NodeMapPtr > class leda_node_property_map : public put_get_helper< ERef, leda_node_property_map< E, ERef, NodeMapPtr > > { public: typedef E value_type; typedef ERef reference; typedef leda::node key_type; typedef lvalue_property_map_tag category; leda_node_property_map(NodeMapPtr a) : m_array(a) {} ERef operator[](leda::node n) const { return (*m_array)[n]; } protected: NodeMapPtr m_array; }; template < class E > leda_node_property_map< E, const E&, const leda::node_array< E >* > make_leda_node_property_map(const leda::node_array< E >& a) { typedef leda_node_property_map< E, const E&, const leda::node_array< E >* > pmap_type; return pmap_type(&a); } template < class E > leda_node_property_map< E, E&, leda::node_array< E >* > make_leda_node_property_map(leda::node_array< E >& a) { typedef leda_node_property_map< E, E&, leda::node_array< E >* > pmap_type; return pmap_type(&a); } template < class E > leda_node_property_map< E, const E&, const leda::node_map< E >* > make_leda_node_property_map(const leda::node_map< E >& a) { typedef leda_node_property_map< E, const E&, const leda::node_map< E >* > pmap_type; return pmap_type(&a); } template < class E > leda_node_property_map< E, E&, leda::node_map< E >* > make_leda_node_property_map(leda::node_map< E >& a) { typedef leda_node_property_map< E, E&, leda::node_map< E >* > pmap_type; return pmap_type(&a); } // g++ 'enumeral_type' in template unification not implemented workaround template < class vtype, class etype, class Tag > struct property_map< leda::GRAPH< vtype, etype >, Tag > { typedef typename leda_property_map< Tag >::template bind_< vtype, etype > map_gen; typedef typename map_gen::type type; typedef typename map_gen::const_type const_type; }; template < class vtype, class etype, class PropertyTag, class Key > inline typename boost::property_traits< typename boost::property_map< leda::GRAPH< vtype, etype >, PropertyTag >::const_type >::value_type get(PropertyTag p, const leda::GRAPH< vtype, etype >& g, const Key& key) { return get(get(p, g), key); } template < class vtype, class etype, class PropertyTag, class Key, class Value > inline void put(PropertyTag p, leda::GRAPH< vtype, etype >& g, const Key& key, const Value& value) { typedef typename property_map< leda::GRAPH< vtype, etype >, PropertyTag >::type Map; Map pmap = get(p, g); put(pmap, key, value); } // property map interface to the LEDA edge_array class template < class E, class ERef, class EdgeMapPtr > class leda_edge_property_map : public put_get_helper< ERef, leda_edge_property_map< E, ERef, EdgeMapPtr > > { public: typedef E value_type; typedef ERef reference; typedef leda::edge key_type; typedef lvalue_property_map_tag category; leda_edge_property_map(EdgeMapPtr a) : m_array(a) {} ERef operator[](leda::edge n) const { return (*m_array)[n]; } protected: EdgeMapPtr m_array; }; template < class E > leda_edge_property_map< E, const E&, const leda::edge_array< E >* > make_leda_node_property_map(const leda::node_array< E >& a) { typedef leda_edge_property_map< E, const E&, const leda::node_array< E >* > pmap_type; return pmap_type(&a); } template < class E > leda_edge_property_map< E, E&, leda::edge_array< E >* > make_leda_edge_property_map(leda::edge_array< E >& a) { typedef leda_edge_property_map< E, E&, leda::edge_array< E >* > pmap_type; return pmap_type(&a); } template < class E > leda_edge_property_map< E, const E&, const leda::edge_map< E >* > make_leda_edge_property_map(const leda::edge_map< E >& a) { typedef leda_edge_property_map< E, const E&, const leda::edge_map< E >* > pmap_type; return pmap_type(&a); } template < class E > leda_edge_property_map< E, E&, leda::edge_map< E >* > make_leda_edge_property_map(leda::edge_map< E >& a) { typedef leda_edge_property_map< E, E&, leda::edge_map< E >* > pmap_type; return pmap_type(&a); } } // namespace boost #endif // BOOST_GRAPH_LEDA_HPP PK L�[酧�x x adjacency_iterator.hppnu �[��� //======================================================================= // Copyright 2002 Indiana University. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // 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) //======================================================================= #ifndef BOOST_ADJACENCY_ITERATOR_HPP #define BOOST_ADJACENCY_ITERATOR_HPP #include <boost/detail/iterator.hpp> #include <boost/iterator/iterator_adaptor.hpp> #include <boost/graph/graph_traits.hpp> namespace boost { template < class Graph, class Vertex, class OutEdgeIter, class Difference > struct adjacency_iterator : iterator_adaptor< adjacency_iterator< Graph, Vertex, OutEdgeIter, Difference >, OutEdgeIter, Vertex, use_default, Vertex, Difference > { typedef iterator_adaptor< adjacency_iterator< Graph, Vertex, OutEdgeIter, Difference >, OutEdgeIter, Vertex, use_default, Vertex, Difference > super_t; inline adjacency_iterator() {} inline adjacency_iterator(OutEdgeIter const& i, const Graph* g) : super_t(i), m_g(g) { } inline Vertex dereference() const { return target(*this->base(), *m_g); } const Graph* m_g; }; template < class Graph, class Vertex = typename graph_traits< Graph >::vertex_descriptor, class OutEdgeIter = typename graph_traits< Graph >::out_edge_iterator > class adjacency_iterator_generator { typedef typename boost::detail::iterator_traits< OutEdgeIter >::difference_type difference_type; public: typedef adjacency_iterator< Graph, Vertex, OutEdgeIter, difference_type > type; }; template < class Graph, class Vertex, class InEdgeIter, class Difference > struct inv_adjacency_iterator : iterator_adaptor< inv_adjacency_iterator< Graph, Vertex, InEdgeIter, Difference >, InEdgeIter, Vertex, use_default, Vertex, Difference > { typedef iterator_adaptor< inv_adjacency_iterator< Graph, Vertex, InEdgeIter, Difference >, InEdgeIter, Vertex, use_default, Vertex, Difference > super_t; inline inv_adjacency_iterator() {} inline inv_adjacency_iterator(InEdgeIter const& i, const Graph* g) : super_t(i), m_g(g) { } inline Vertex dereference() const { return source(*this->base(), *m_g); } const Graph* m_g; }; template < class Graph, class Vertex = typename graph_traits< Graph >::vertex_descriptor, class InEdgeIter = typename graph_traits< Graph >::in_edge_iterator > class inv_adjacency_iterator_generator { typedef typename boost::detail::iterator_traits< InEdgeIter >::difference_type difference_type; public: typedef inv_adjacency_iterator< Graph, Vertex, InEdgeIter, difference_type > type; }; } // namespace boost #endif // BOOST_DETAIL_ADJACENCY_ITERATOR_HPP PK L�[����� �� push_relabel_max_flow.hppnu �[��� //======================================================================= // Copyright 2000 University of Notre Dame. // Authors: 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) //======================================================================= #ifndef BOOST_PUSH_RELABEL_MAX_FLOW_HPP #define BOOST_PUSH_RELABEL_MAX_FLOW_HPP #include <boost/config.hpp> #include <boost/assert.hpp> #include <vector> #include <list> #include <iosfwd> #include <algorithm> // for std::min and std::max #include <boost/pending/queue.hpp> #include <boost/limits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/named_function_params.hpp> namespace boost { namespace detail { // This implementation is based on Goldberg's // "On Implementing Push-Relabel Method for the Maximum Flow Problem" // by B.V. Cherkassky and A.V. Goldberg, IPCO '95, pp. 157--171 // and on the h_prf.c and hi_pr.c code written by the above authors. // This implements the highest-label version of the push-relabel method // with the global relabeling and gap relabeling heuristics. // The terms "rank", "distance", "height" are synonyms in // Goldberg's implementation, paper and in the CLR. A "layer" is a // group of vertices with the same distance. The vertices in each // layer are categorized as active or inactive. An active vertex // has positive excess flow and its distance is less than n (it is // not blocked). template < class Vertex > struct preflow_layer { std::list< Vertex > active_vertices; std::list< Vertex > inactive_vertices; }; template < class Graph, class EdgeCapacityMap, // integer value type class ResidualCapacityEdgeMap, class ReverseEdgeMap, class VertexIndexMap, // vertex_descriptor -> integer class FlowValue > class push_relabel { public: typedef graph_traits< Graph > Traits; typedef typename Traits::vertex_descriptor vertex_descriptor; typedef typename Traits::edge_descriptor edge_descriptor; typedef typename Traits::vertex_iterator vertex_iterator; typedef typename Traits::out_edge_iterator out_edge_iterator; typedef typename Traits::vertices_size_type vertices_size_type; typedef typename Traits::edges_size_type edges_size_type; typedef preflow_layer< vertex_descriptor > Layer; typedef std::vector< Layer > LayerArray; typedef typename LayerArray::iterator layer_iterator; typedef typename LayerArray::size_type distance_size_type; typedef color_traits< default_color_type > ColorTraits; //======================================================================= // Some helper predicates inline bool is_admissible(vertex_descriptor u, vertex_descriptor v) { return get(distance, u) == get(distance, v) + 1; } inline bool is_residual_edge(edge_descriptor a) { return 0 < get(residual_capacity, a); } inline bool is_saturated(edge_descriptor a) { return get(residual_capacity, a) == 0; } //======================================================================= // Layer List Management Functions typedef typename std::list< vertex_descriptor >::iterator list_iterator; void add_to_active_list(vertex_descriptor u, Layer& layer) { BOOST_USING_STD_MIN(); BOOST_USING_STD_MAX(); layer.active_vertices.push_front(u); max_active = max BOOST_PREVENT_MACRO_SUBSTITUTION( get(distance, u), max_active); min_active = min BOOST_PREVENT_MACRO_SUBSTITUTION( get(distance, u), min_active); layer_list_ptr[u] = layer.active_vertices.begin(); } void remove_from_active_list(vertex_descriptor u) { layers[get(distance, u)].active_vertices.erase(layer_list_ptr[u]); } void add_to_inactive_list(vertex_descriptor u, Layer& layer) { layer.inactive_vertices.push_front(u); layer_list_ptr[u] = layer.inactive_vertices.begin(); } void remove_from_inactive_list(vertex_descriptor u) { layers[get(distance, u)].inactive_vertices.erase(layer_list_ptr[u]); } //======================================================================= // initialization push_relabel(Graph& g_, EdgeCapacityMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev, vertex_descriptor src_, vertex_descriptor sink_, VertexIndexMap idx) : g(g_) , n(num_vertices(g_)) , capacity(cap) , src(src_) , sink(sink_) , index(idx) , excess_flow_data(num_vertices(g_)) , excess_flow(excess_flow_data.begin(), idx) , current_data(num_vertices(g_), out_edges(*vertices(g_).first, g_)) , current(current_data.begin(), idx) , distance_data(num_vertices(g_)) , distance(distance_data.begin(), idx) , color_data(num_vertices(g_)) , color(color_data.begin(), idx) , reverse_edge(rev) , residual_capacity(res) , layers(num_vertices(g_)) , layer_list_ptr_data( num_vertices(g_), layers.front().inactive_vertices.end()) , layer_list_ptr(layer_list_ptr_data.begin(), idx) , push_count(0) , update_count(0) , relabel_count(0) , gap_count(0) , gap_node_count(0) , work_since_last_update(0) { vertex_iterator u_iter, u_end; // Don't count the reverse edges edges_size_type m = num_edges(g) / 2; nm = alpha() * n + m; // Initialize flow to zero which means initializing // the residual capacity to equal the capacity. out_edge_iterator ei, e_end; for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) { put(residual_capacity, *ei, get(capacity, *ei)); } for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { vertex_descriptor u = *u_iter; put(excess_flow, u, 0); current[u] = out_edges(u, g); } bool overflow_detected = false; FlowValue test_excess = 0; out_edge_iterator a_iter, a_end; for (boost::tie(a_iter, a_end) = out_edges(src, g); a_iter != a_end; ++a_iter) if (target(*a_iter, g) != src) test_excess += get(residual_capacity, *a_iter); if (test_excess > (std::numeric_limits< FlowValue >::max)()) overflow_detected = true; if (overflow_detected) put(excess_flow, src, (std::numeric_limits< FlowValue >::max)()); else { put(excess_flow, src, 0); for (boost::tie(a_iter, a_end) = out_edges(src, g); a_iter != a_end; ++a_iter) { edge_descriptor a = *a_iter; vertex_descriptor tgt = target(a, g); if (tgt != src) { ++push_count; FlowValue delta = get(residual_capacity, a); put(residual_capacity, a, get(residual_capacity, a) - delta); edge_descriptor rev = get(reverse_edge, a); put(residual_capacity, rev, get(residual_capacity, rev) + delta); put(excess_flow, tgt, get(excess_flow, tgt) + delta); } } } max_distance = num_vertices(g) - 1; max_active = 0; min_active = n; for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { vertex_descriptor u = *u_iter; if (u == sink) { put(distance, u, 0); continue; } else if (u == src && !overflow_detected) put(distance, u, n); else put(distance, u, 1); if (get(excess_flow, u) > 0) add_to_active_list(u, layers[1]); else if (get(distance, u) < n) add_to_inactive_list(u, layers[1]); } } // push_relabel constructor //======================================================================= // This is a breadth-first search over the residual graph // (well, actually the reverse of the residual graph). // Would be cool to have a graph view adaptor for hiding certain // edges, like the saturated (non-residual) edges in this case. // Goldberg's implementation abused "distance" for the coloring. void global_distance_update() { BOOST_USING_STD_MAX(); ++update_count; vertex_iterator u_iter, u_end; for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { put(color, *u_iter, ColorTraits::white()); put(distance, *u_iter, n); } put(color, sink, ColorTraits::gray()); put(distance, sink, 0); for (distance_size_type l = 0; l <= max_distance; ++l) { layers[l].active_vertices.clear(); layers[l].inactive_vertices.clear(); } max_distance = max_active = 0; min_active = n; Q.push(sink); while (!Q.empty()) { vertex_descriptor u = Q.top(); Q.pop(); distance_size_type d_v = get(distance, u) + 1; out_edge_iterator ai, a_end; for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) { edge_descriptor a = *ai; vertex_descriptor v = target(a, g); if (get(color, v) == ColorTraits::white() && is_residual_edge(get(reverse_edge, a))) { put(distance, v, d_v); put(color, v, ColorTraits::gray()); current[v] = out_edges(v, g); max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION( d_v, max_distance); if (get(excess_flow, v) > 0) add_to_active_list(v, layers[d_v]); else add_to_inactive_list(v, layers[d_v]); Q.push(v); } } } } // global_distance_update() //======================================================================= // This function is called "push" in Goldberg's h_prf implementation, // but it is called "discharge" in the paper and in hi_pr.c. void discharge(vertex_descriptor u) { BOOST_ASSERT(get(excess_flow, u) > 0); while (1) { out_edge_iterator ai, ai_end; for (boost::tie(ai, ai_end) = current[u]; ai != ai_end; ++ai) { edge_descriptor a = *ai; if (is_residual_edge(a)) { vertex_descriptor v = target(a, g); if (is_admissible(u, v)) { ++push_count; if (v != sink && get(excess_flow, v) == 0) { remove_from_inactive_list(v); add_to_active_list(v, layers[get(distance, v)]); } push_flow(a); if (get(excess_flow, u) == 0) break; } } } // for out_edges of i starting from current Layer& layer = layers[get(distance, u)]; distance_size_type du = get(distance, u); if (ai == ai_end) { // i must be relabeled relabel_distance(u); if (layer.active_vertices.empty() && layer.inactive_vertices.empty()) gap(du); if (get(distance, u) == n) break; } else { // i is no longer active current[u].first = ai; add_to_inactive_list(u, layer); break; } } // while (1) } // discharge() //======================================================================= // This corresponds to the "push" update operation of the paper, // not the "push" function in Goldberg's h_prf.c implementation. // The idea is to push the excess flow from from vertex u to v. void push_flow(edge_descriptor u_v) { vertex_descriptor u = source(u_v, g), v = target(u_v, g); BOOST_USING_STD_MIN(); FlowValue flow_delta = min BOOST_PREVENT_MACRO_SUBSTITUTION( get(excess_flow, u), get(residual_capacity, u_v)); put(residual_capacity, u_v, get(residual_capacity, u_v) - flow_delta); edge_descriptor rev = get(reverse_edge, u_v); put(residual_capacity, rev, get(residual_capacity, rev) + flow_delta); put(excess_flow, u, get(excess_flow, u) - flow_delta); put(excess_flow, v, get(excess_flow, v) + flow_delta); } // push_flow() //======================================================================= // The main purpose of this routine is to set distance[v] // to the smallest value allowed by the valid labeling constraints, // which are: // distance[t] = 0 // distance[u] <= distance[v] + 1 for every residual edge (u,v) // distance_size_type relabel_distance(vertex_descriptor u) { BOOST_USING_STD_MAX(); ++relabel_count; work_since_last_update += beta(); distance_size_type min_distance = num_vertices(g); put(distance, u, min_distance); // Examine the residual out-edges of vertex i, choosing the // edge whose target vertex has the minimal distance. out_edge_iterator ai, a_end, min_edge_iter; for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) { ++work_since_last_update; edge_descriptor a = *ai; vertex_descriptor v = target(a, g); if (is_residual_edge(a) && get(distance, v) < min_distance) { min_distance = get(distance, v); min_edge_iter = ai; } } ++min_distance; if (min_distance < n) { put(distance, u, min_distance); // this is the main action current[u].first = min_edge_iter; max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION( min_distance, max_distance); } return min_distance; } // relabel_distance() //======================================================================= // cleanup beyond the gap void gap(distance_size_type empty_distance) { ++gap_count; distance_size_type r; // distance of layer before the current layer r = empty_distance - 1; // Set the distance for the vertices beyond the gap to "infinity". for (layer_iterator l = layers.begin() + empty_distance + 1; l < layers.begin() + max_distance; ++l) { list_iterator i; for (i = l->inactive_vertices.begin(); i != l->inactive_vertices.end(); ++i) { put(distance, *i, n); ++gap_node_count; } l->inactive_vertices.clear(); } max_distance = r; max_active = r; } //======================================================================= // This is the core part of the algorithm, "phase one". FlowValue maximum_preflow() { work_since_last_update = 0; while (max_active >= min_active) { // "main" loop Layer& layer = layers[max_active]; list_iterator u_iter = layer.active_vertices.begin(); if (u_iter == layer.active_vertices.end()) --max_active; else { vertex_descriptor u = *u_iter; remove_from_active_list(u); discharge(u); if (work_since_last_update * global_update_frequency() > nm) { global_distance_update(); work_since_last_update = 0; } } } // while (max_active >= min_active) return get(excess_flow, sink); } // maximum_preflow() //======================================================================= // remove excess flow, the "second phase" // This does a DFS on the reverse flow graph of nodes with excess flow. // If a cycle is found, cancel it. // Return the nodes with excess flow in topological order. // // Unlike the prefl_to_flow() implementation, we use // "color" instead of "distance" for the DFS labels // "parent" instead of nl_prev for the DFS tree // "topo_next" instead of nl_next for the topological ordering void convert_preflow_to_flow() { vertex_iterator u_iter, u_end; out_edge_iterator ai, a_end; vertex_descriptor r, restart, u; std::vector< vertex_descriptor > parent(n); std::vector< vertex_descriptor > topo_next(n); vertex_descriptor tos(parent[0]), bos(parent[0]); // bogus initialization, just to avoid warning bool bos_null = true; // handle self-loops for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) for (boost::tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai) if (target(*ai, g) == *u_iter) put(residual_capacity, *ai, get(capacity, *ai)); // initialize for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { u = *u_iter; put(color, u, ColorTraits::white()); parent[get(index, u)] = u; current[u] = out_edges(u, g); } // eliminate flow cycles and topologically order the vertices for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { u = *u_iter; if (get(color, u) == ColorTraits::white() && get(excess_flow, u) > 0 && u != src && u != sink) { r = u; put(color, r, ColorTraits::gray()); while (1) { for (; current[u].first != current[u].second; ++current[u].first) { edge_descriptor a = *current[u].first; if (get(capacity, a) == 0 && is_residual_edge(a)) { vertex_descriptor v = target(a, g); if (get(color, v) == ColorTraits::white()) { put(color, v, ColorTraits::gray()); parent[get(index, v)] = u; u = v; break; } else if (get(color, v) == ColorTraits::gray()) { // find minimum flow on the cycle FlowValue delta = get(residual_capacity, a); while (1) { BOOST_USING_STD_MIN(); delta = min BOOST_PREVENT_MACRO_SUBSTITUTION( delta, get(residual_capacity, *current[v].first)); if (v == u) break; else v = target(*current[v].first, g); } // remove delta flow units v = u; while (1) { a = *current[v].first; put(residual_capacity, a, get(residual_capacity, a) - delta); edge_descriptor rev = get(reverse_edge, a); put(residual_capacity, rev, get(residual_capacity, rev) + delta); v = target(a, g); if (v == u) break; } // back-out of DFS to the first saturated // edge restart = u; for (v = target(*current[u].first, g); v != u; v = target(a, g)) { a = *current[v].first; if (get(color, v) == ColorTraits::white() || is_saturated(a)) { put(color, target(*current[v].first, g), ColorTraits::white()); if (get(color, v) != ColorTraits::white()) restart = v; } } if (restart != u) { u = restart; ++current[u].first; break; } } // else if (color[v] == ColorTraits::gray()) } // if (get(capacity, a) == 0 ... } // for out_edges(u, g) (though "u" changes during // loop) if (current[u].first == current[u].second) { // scan of i is complete put(color, u, ColorTraits::black()); if (u != src) { if (bos_null) { bos = u; bos_null = false; tos = u; } else { topo_next[get(index, u)] = tos; tos = u; } } if (u != r) { u = parent[get(index, u)]; ++current[u].first; } else break; } } // while (1) } // if (color[u] == white && excess_flow[u] > 0 & ...) } // for all vertices in g // return excess flows // note that the sink is not on the stack if (!bos_null) { for (u = tos; u != bos; u = topo_next[get(index, u)]) { boost::tie(ai, a_end) = out_edges(u, g); while (get(excess_flow, u) > 0 && ai != a_end) { if (get(capacity, *ai) == 0 && is_residual_edge(*ai)) push_flow(*ai); ++ai; } } // do the bottom u = bos; boost::tie(ai, a_end) = out_edges(u, g); while (get(excess_flow, u) > 0 && ai != a_end) { if (get(capacity, *ai) == 0 && is_residual_edge(*ai)) push_flow(*ai); ++ai; } } } // convert_preflow_to_flow() //======================================================================= inline bool is_flow() { vertex_iterator u_iter, u_end; out_edge_iterator ai, a_end; // check edge flow values for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { for (boost::tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai) { edge_descriptor a = *ai; if (get(capacity, a) > 0) if ((get(residual_capacity, a) + get( residual_capacity, get(reverse_edge, a)) != get(capacity, a) + get(capacity, get(reverse_edge, a))) || (get(residual_capacity, a) < 0) || (get(residual_capacity, get(reverse_edge, a)) < 0)) return false; } } // check conservation FlowValue sum; for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { vertex_descriptor u = *u_iter; if (u != src && u != sink) { if (get(excess_flow, u) != 0) return false; sum = 0; for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) if (get(capacity, *ai) > 0) sum -= get(capacity, *ai) - get(residual_capacity, *ai); else sum += get(residual_capacity, *ai); if (get(excess_flow, u) != sum) return false; } } return true; } // is_flow() bool is_optimal() { // check if mincut is saturated... global_distance_update(); return get(distance, src) >= n; } void print_statistics(std::ostream& os) const { os << "pushes: " << push_count << std::endl << "relabels: " << relabel_count << std::endl << "updates: " << update_count << std::endl << "gaps: " << gap_count << std::endl << "gap nodes: " << gap_node_count << std::endl << std::endl; } void print_flow_values(std::ostream& os) const { os << "flow values" << std::endl; vertex_iterator u_iter, u_end; out_edge_iterator ei, e_end; for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) if (get(capacity, *ei) > 0) os << *u_iter << " " << target(*ei, g) << " " << (get(capacity, *ei) - get(residual_capacity, *ei)) << std::endl; os << std::endl; } //======================================================================= Graph& g; vertices_size_type n; vertices_size_type nm; EdgeCapacityMap capacity; vertex_descriptor src; vertex_descriptor sink; VertexIndexMap index; // will need to use random_access_property_map with these std::vector< FlowValue > excess_flow_data; iterator_property_map< typename std::vector< FlowValue >::iterator, VertexIndexMap > excess_flow; std::vector< std::pair< out_edge_iterator, out_edge_iterator > > current_data; iterator_property_map< typename std::vector< std::pair< out_edge_iterator, out_edge_iterator > >::iterator, VertexIndexMap > current; std::vector< distance_size_type > distance_data; iterator_property_map< typename std::vector< distance_size_type >::iterator, VertexIndexMap > distance; std::vector< default_color_type > color_data; iterator_property_map< std::vector< default_color_type >::iterator, VertexIndexMap > color; // Edge Property Maps that must be interior to the graph ReverseEdgeMap reverse_edge; ResidualCapacityEdgeMap residual_capacity; LayerArray layers; std::vector< list_iterator > layer_list_ptr_data; iterator_property_map< typename std::vector< list_iterator >::iterator, VertexIndexMap > layer_list_ptr; distance_size_type max_distance; // maximal distance distance_size_type max_active; // maximal distance with active node distance_size_type min_active; // minimal distance with active node boost::queue< vertex_descriptor > Q; // Statistics counters long push_count; long update_count; long relabel_count; long gap_count; long gap_node_count; inline double global_update_frequency() { return 0.5; } inline vertices_size_type alpha() { return 6; } inline long beta() { return 12; } long work_since_last_update; }; } // namespace detail template < class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class VertexIndexMap > typename property_traits< CapacityEdgeMap >::value_type push_relabel_max_flow( Graph& g, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink, CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev, VertexIndexMap index_map) { typedef typename property_traits< CapacityEdgeMap >::value_type FlowValue; detail::push_relabel< Graph, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap, VertexIndexMap, FlowValue > algo(g, cap, res, rev, src, sink, index_map); FlowValue flow = algo.maximum_preflow(); algo.convert_preflow_to_flow(); BOOST_ASSERT(algo.is_flow()); BOOST_ASSERT(algo.is_optimal()); return flow; } // push_relabel_max_flow() template < class Graph, class P, class T, class R > typename detail::edge_capacity_value< Graph, P, T, R >::type push_relabel_max_flow(Graph& g, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink, const bgl_named_params< P, T, R >& params) { return push_relabel_max_flow(g, src, sink, choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity), choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity), choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)); } template < class Graph > typename property_traits< typename property_map< Graph, edge_capacity_t >::const_type >::value_type push_relabel_max_flow(Graph& g, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink) { bgl_named_params< int, buffer_param_t > params(0); // bogus empty param return push_relabel_max_flow(g, src, sink, params); } } // namespace boost #endif // BOOST_PUSH_RELABEL_MAX_FLOW_HPP PK L�[۠=�^ �^ directed_graph.hppnu �[��� // (C) Copyright 2007-2009 Andrew Sutton // // Use, modification and distribution are subject to the // Boost Software License, Version 1.0 (See accompanying file // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_GRAPH_DIRECTED_GRAPH_HPP #define BOOST_GRAPH_DIRECTED_GRAPH_HPP #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> #include <boost/pending/property.hpp> #include <boost/property_map/transform_value_property_map.hpp> #include <boost/type_traits.hpp> #include <boost/mpl/if.hpp> namespace boost { struct directed_graph_tag { }; /** * The directed_graph class template is a simplified version of the BGL * adjacency list. This class is provided for ease of use, but may not * perform as well as custom-defined adjacency list classes. Instances of * this template model the BidirectionalGraph, VertexIndexGraph, and * EdgeIndexGraph concepts. The graph is also fully mutable, supporting * both insertions and removals of vertices and edges. * * @note Special care must be taken when removing vertices or edges since * those operations can invalidate the numbering of vertices. */ template < typename VertexProp = no_property, typename EdgeProp = no_property, typename GraphProp = no_property > class directed_graph { public: typedef GraphProp graph_property_type; typedef VertexProp vertex_property_type; typedef EdgeProp edge_property_type; typedef typename lookup_one_property< GraphProp, graph_bundle_t >::type graph_bundled; typedef typename lookup_one_property< VertexProp, vertex_bundle_t >::type vertex_bundled; typedef typename lookup_one_property< EdgeProp, edge_bundle_t >::type edge_bundled; public: // Embed indices into the vertex type. typedef property< vertex_index_t, unsigned, vertex_property_type > internal_vertex_property; typedef property< edge_index_t, unsigned, edge_property_type > internal_edge_property; public: typedef adjacency_list< listS, listS, bidirectionalS, internal_vertex_property, internal_edge_property, GraphProp, listS > graph_type; private: // storage selectors typedef typename graph_type::vertex_list_selector vertex_list_selector; typedef typename graph_type::edge_list_selector edge_list_selector; typedef typename graph_type::out_edge_list_selector out_edge_list_selector; typedef typename graph_type::directed_selector directed_selector; public: // more commonly used graph types typedef typename graph_type::stored_vertex stored_vertex; typedef typename graph_type::vertices_size_type vertices_size_type; typedef typename graph_type::edges_size_type edges_size_type; typedef typename graph_type::degree_size_type degree_size_type; typedef typename graph_type::vertex_descriptor vertex_descriptor; typedef typename graph_type::edge_descriptor edge_descriptor; // iterator types typedef typename graph_type::vertex_iterator vertex_iterator; typedef typename graph_type::edge_iterator edge_iterator; typedef typename graph_type::out_edge_iterator out_edge_iterator; typedef typename graph_type::in_edge_iterator in_edge_iterator; typedef typename graph_type::adjacency_iterator adjacency_iterator; // miscellaneous types typedef directed_graph_tag graph_tag; typedef typename graph_type::directed_category directed_category; typedef typename graph_type::edge_parallel_category edge_parallel_category; typedef typename graph_type::traversal_category traversal_category; typedef std::size_t vertex_index_type; typedef std::size_t edge_index_type; directed_graph(GraphProp const& p = GraphProp()) : m_graph(p) , m_num_vertices(0) , m_num_edges(0) , m_max_vertex_index(0) , m_max_edge_index(0) { } directed_graph(directed_graph const& x) : m_graph(x.m_graph) , m_num_vertices(x.m_num_vertices) , m_num_edges(x.m_num_edges) , m_max_vertex_index(x.m_max_vertex_index) , m_max_edge_index(x.m_max_edge_index) { } directed_graph(vertices_size_type n, GraphProp const& p = GraphProp()) : m_graph(n, p) , m_num_vertices(n) , m_num_edges(0) , m_max_vertex_index(n) , m_max_edge_index(0) { renumber_vertex_indices(); } template < typename EdgeIterator > directed_graph(EdgeIterator f, EdgeIterator l, vertices_size_type n, edges_size_type m = 0, GraphProp const& p = GraphProp()) : m_graph(f, l, n, m, p) , m_num_vertices(n) , m_num_edges(0) , m_max_vertex_index(n) , m_max_edge_index(0) { // Unfortunately, we have to renumber the entire graph. renumber_indices(); // Can't always guarantee that the number of edges is actually // m if distance(f, l) != m (or is undefined). m_num_edges = m_max_edge_index = boost::num_edges(m_graph); } directed_graph& operator=(directed_graph const& g) { if (&g != this) { m_graph = g.m_graph; m_num_vertices = g.m_num_vertices; m_num_edges = g.m_num_edges; m_max_vertex_index = g.m_max_vertex_index; m_max_edge_index = g.m_max_edge_index; } return *this; } // The impl_() methods are not part of the public interface. graph_type& impl() { return m_graph; } graph_type const& impl() const { return m_graph; } // The following methods are not part of the public interface vertices_size_type num_vertices() const { return m_num_vertices; } private: // This helper function manages the attribution of vertex indices. vertex_descriptor make_index(vertex_descriptor v) { boost::put(vertex_index, m_graph, v, m_max_vertex_index); m_num_vertices++; m_max_vertex_index++; return v; } public: vertex_descriptor add_vertex() { return make_index(boost::add_vertex(m_graph)); } vertex_descriptor add_vertex(vertex_property_type const& p) { return make_index( boost::add_vertex(internal_vertex_property(0u, p), m_graph)); } void clear_vertex(vertex_descriptor v) { m_num_edges -= boost::degree(v, m_graph); boost::clear_vertex(v, m_graph); } void remove_vertex(vertex_descriptor v) { boost::remove_vertex(v, m_graph); --m_num_vertices; } edges_size_type num_edges() const { return m_num_edges; } private: // A helper function for managing edge index attributes. std::pair< edge_descriptor, bool > const& make_index( std::pair< edge_descriptor, bool > const& x) { if (x.second) { boost::put(edge_index, m_graph, x.first, m_max_edge_index); ++m_num_edges; ++m_max_edge_index; } return x; } public: std::pair< edge_descriptor, bool > add_edge( vertex_descriptor u, vertex_descriptor v) { return make_index(boost::add_edge(u, v, m_graph)); } std::pair< edge_descriptor, bool > add_edge( vertex_descriptor u, vertex_descriptor v, edge_property_type const& p) { return make_index( boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); } void remove_edge(vertex_descriptor u, vertex_descriptor v) { // find all edges, (u, v) std::vector< edge_descriptor > edges; out_edge_iterator i, i_end; for (boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) { if (boost::target(*i, m_graph) == v) { edges.push_back(*i); } } // remove all edges, (u, v) typename std::vector< edge_descriptor >::iterator j = edges.begin(), j_end = edges.end(); for (; j != j_end; ++j) { remove_edge(*j); } } void remove_edge(edge_iterator i) { remove_edge(*i); } void remove_edge(edge_descriptor e) { boost::remove_edge(e, m_graph); --m_num_edges; } vertex_index_type max_vertex_index() const { return m_max_vertex_index; } void renumber_vertex_indices() { vertex_iterator i, end; boost::tie(i, end) = vertices(m_graph); m_max_vertex_index = renumber_vertex_indices(i, end, 0); } void remove_vertex_and_renumber_indices(vertex_iterator i) { vertex_iterator j = next(i), end = vertices(m_graph).second; vertex_index_type n = get(vertex_index, m_graph, *i); // remove the offending vertex and renumber everything after remove_vertex(*i); m_max_vertex_index = renumber_vertex_indices(j, end, n); } edge_index_type max_edge_index() const { return m_max_edge_index; } void renumber_edge_indices() { edge_iterator i, end; boost::tie(i, end) = edges(m_graph); m_max_edge_index = renumber_edge_indices(i, end, 0); } void remove_edge_and_renumber_indices(edge_iterator i) { edge_iterator j = next(i), end = edges(m_graph).second; edge_index_type n = get(edge_index, m_graph, *i); // remove the offending edge and renumber everything after remove_edge(*i); m_max_edge_index = renumber_edge_indices(j, end, n); } void renumber_indices() { renumber_vertex_indices(); renumber_edge_indices(); } // bundled property support #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; } vertex_bundled const& operator[](vertex_descriptor v) const { return m_graph[v]; } edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; } edge_bundled const& operator[](edge_descriptor e) const { return m_graph[e]; } graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } graph_bundled const& operator[](graph_bundle_t) const { return get_property(*this); } #endif // Graph concepts static vertex_descriptor null_vertex() { return graph_type::null_vertex(); } void clear() { m_graph.clear(); m_num_vertices = m_max_vertex_index = 0; m_num_edges = m_max_edge_index = 0; } void swap(directed_graph& g) { m_graph.swap(g.m_graph); std::swap(m_num_vertices, g.m_num_vertices); std::swap(m_max_vertex_index, g.m_max_vertex_index); std::swap(m_num_edges, g.m_num_edges); std::swap(m_max_edge_index, g.m_max_edge_index); } private: vertices_size_type renumber_vertex_indices( vertex_iterator i, vertex_iterator end, vertices_size_type n) { typedef typename property_map< graph_type, vertex_index_t >::type IndexMap; IndexMap indices = get(vertex_index, m_graph); for (; i != end; ++i) { indices[*i] = n++; } return n; } vertices_size_type renumber_edge_indices( edge_iterator i, edge_iterator end, vertices_size_type n) { typedef typename property_map< graph_type, edge_index_t >::type IndexMap; IndexMap indices = get(edge_index, m_graph); for (; i != end; ++i) { indices[*i] = n++; } return n; } graph_type m_graph; vertices_size_type m_num_vertices; edges_size_type m_num_edges; vertex_index_type m_max_vertex_index; edge_index_type m_max_edge_index; }; #define DIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP #define DIRECTED_GRAPH directed_graph< VP, EP, GP > // IncidenceGraph concepts template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::vertex_descriptor source( typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g) { return source(e, g.impl()); } template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::vertex_descriptor target( typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g) { return target(e, g.impl()); } template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::degree_size_type out_degree( typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return out_degree(v, g.impl()); } template < DIRECTED_GRAPH_PARAMS > inline std::pair< typename DIRECTED_GRAPH::out_edge_iterator, typename DIRECTED_GRAPH::out_edge_iterator > out_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return out_edges(v, g.impl()); } // BidirectionalGraph concepts template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::degree_size_type in_degree( typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return in_degree(v, g.impl()); } template < DIRECTED_GRAPH_PARAMS > inline std::pair< typename DIRECTED_GRAPH::in_edge_iterator, typename DIRECTED_GRAPH::in_edge_iterator > in_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return in_edges(v, g.impl()); } template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::degree_size_type degree( typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return degree(v, g.impl()); } // AdjacencyGraph concepts template < DIRECTED_GRAPH_PARAMS > inline std::pair< typename DIRECTED_GRAPH::adjacency_iterator, typename DIRECTED_GRAPH::adjacency_iterator > adjacent_vertices( typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return adjacent_vertices(v, g.impl()); } template < DIRECTED_GRAPH_PARAMS > typename DIRECTED_GRAPH::vertex_descriptor vertex( typename DIRECTED_GRAPH::vertices_size_type n, DIRECTED_GRAPH const& g) { return vertex(n, g.impl()); } template < DIRECTED_GRAPH_PARAMS > std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > edge( typename DIRECTED_GRAPH::vertex_descriptor u, typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return edge(u, v, g.impl()); } // VertexListGraph concepts template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::vertices_size_type num_vertices( DIRECTED_GRAPH const& g) { return g.num_vertices(); } template < DIRECTED_GRAPH_PARAMS > inline std::pair< typename DIRECTED_GRAPH::vertex_iterator, typename DIRECTED_GRAPH::vertex_iterator > vertices(DIRECTED_GRAPH const& g) { return vertices(g.impl()); } // EdgeListGraph concepts template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::edges_size_type num_edges( DIRECTED_GRAPH const& g) { return g.num_edges(); } template < DIRECTED_GRAPH_PARAMS > inline std::pair< typename DIRECTED_GRAPH::edge_iterator, typename DIRECTED_GRAPH::edge_iterator > edges(DIRECTED_GRAPH const& g) { return edges(g.impl()); } // MutableGraph concepts template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::vertex_descriptor add_vertex(DIRECTED_GRAPH& g) { return g.add_vertex(); } template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::vertex_descriptor add_vertex( typename DIRECTED_GRAPH::vertex_property_type const& p, DIRECTED_GRAPH& g) { return g.add_vertex(p); } template < DIRECTED_GRAPH_PARAMS > inline void clear_vertex( typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) { return g.clear_vertex(v); } template < DIRECTED_GRAPH_PARAMS > inline void remove_vertex( typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) { return g.remove_vertex(v); } template < DIRECTED_GRAPH_PARAMS > inline std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > add_edge( typename DIRECTED_GRAPH::vertex_descriptor u, typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) { return g.add_edge(u, v); } template < DIRECTED_GRAPH_PARAMS > inline std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > add_edge( typename DIRECTED_GRAPH::vertex_descriptor u, typename DIRECTED_GRAPH::vertex_descriptor v, typename DIRECTED_GRAPH::edge_property_type const& p, DIRECTED_GRAPH& g) { return g.add_edge(u, v, p); } template < DIRECTED_GRAPH_PARAMS > inline void remove_edge(typename DIRECTED_GRAPH::vertex_descriptor u, typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) { return g.remove_edge(u, v); } template < DIRECTED_GRAPH_PARAMS > inline void remove_edge( typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH& g) { return g.remove_edge(e); } template < DIRECTED_GRAPH_PARAMS > inline void remove_edge( typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g) { return g.remove_edge(i); } template < DIRECTED_GRAPH_PARAMS, class Predicate > inline void remove_edge_if(Predicate pred, DIRECTED_GRAPH& g) { return remove_edge_if(pred, g.impl()); } template < DIRECTED_GRAPH_PARAMS, class Predicate > inline void remove_out_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v, Predicate pred, DIRECTED_GRAPH& g) { return remove_out_edge_if(v, pred, g.impl()); } template < DIRECTED_GRAPH_PARAMS, class Predicate > inline void remove_in_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v, Predicate pred, DIRECTED_GRAPH& g) { return remove_in_edge_if(v, pred, g.impl()); } template < DIRECTED_GRAPH_PARAMS, typename Property > struct property_map< DIRECTED_GRAPH, Property > : property_map< typename DIRECTED_GRAPH::graph_type, Property > { }; template < DIRECTED_GRAPH_PARAMS > struct property_map< DIRECTED_GRAPH, vertex_all_t > { typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename DIRECTED_GRAPH::graph_type, vertex_all_t >::const_type > const_type; typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename DIRECTED_GRAPH::graph_type, vertex_all_t >::type > type; }; template < DIRECTED_GRAPH_PARAMS > struct property_map< DIRECTED_GRAPH, edge_all_t > { typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename DIRECTED_GRAPH::graph_type, edge_all_t >::const_type > const_type; typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename DIRECTED_GRAPH::graph_type, edge_all_t >::type > type; }; // PropertyGraph concepts template < DIRECTED_GRAPH_PARAMS, typename Property > inline typename property_map< DIRECTED_GRAPH, Property >::type get( Property p, DIRECTED_GRAPH& g) { return get(p, g.impl()); } template < DIRECTED_GRAPH_PARAMS, typename Property > inline typename property_map< DIRECTED_GRAPH, Property >::const_type get( Property p, DIRECTED_GRAPH const& g) { return get(p, g.impl()); } template < DIRECTED_GRAPH_PARAMS > inline typename property_map< DIRECTED_GRAPH, vertex_all_t >::type get( vertex_all_t, DIRECTED_GRAPH& g) { return typename property_map< DIRECTED_GRAPH, vertex_all_t >::type( detail::remove_first_property(), get(vertex_all, g.impl())); } template < DIRECTED_GRAPH_PARAMS > inline typename property_map< DIRECTED_GRAPH, vertex_all_t >::const_type get( vertex_all_t, DIRECTED_GRAPH const& g) { return typename property_map< DIRECTED_GRAPH, vertex_all_t >::const_type( detail::remove_first_property(), get(vertex_all, g.impl())); } template < DIRECTED_GRAPH_PARAMS > inline typename property_map< DIRECTED_GRAPH, edge_all_t >::type get( edge_all_t, DIRECTED_GRAPH& g) { return typename property_map< DIRECTED_GRAPH, edge_all_t >::type( detail::remove_first_property(), get(edge_all, g.impl())); } template < DIRECTED_GRAPH_PARAMS > inline typename property_map< DIRECTED_GRAPH, edge_all_t >::const_type get( edge_all_t, DIRECTED_GRAPH const& g) { return typename property_map< DIRECTED_GRAPH, edge_all_t >::const_type( detail::remove_first_property(), get(edge_all, g.impl())); } template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key > inline typename property_traits< typename property_map< typename DIRECTED_GRAPH::graph_type, Property >::const_type >::value_type get(Property p, DIRECTED_GRAPH const& g, Key const& k) { return get(p, g.impl(), k); } template < DIRECTED_GRAPH_PARAMS, typename Key > inline typename property_traits< typename property_map< typename DIRECTED_GRAPH::graph_type, vertex_all_t >::const_type >::value_type get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k) { return get(vertex_all, g.impl(), k).m_base; } template < DIRECTED_GRAPH_PARAMS, typename Key > inline typename property_traits< typename property_map< typename DIRECTED_GRAPH::graph_type, edge_all_t >::const_type >::value_type get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k) { return get(edge_all, g.impl(), k).m_base; } template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value > inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v) { put(p, g.impl(), k, v); } template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value > inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v) { put(vertex_all, g.impl(), k, typename DIRECTED_GRAPH::internal_vertex_property( get(vertex_index, g.impl(), k), v)); } template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value > inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v) { put(edge_all, g.impl(), k, typename DIRECTED_GRAPH::internal_vertex_property( get(edge_index, g.impl(), k), v)); } template < DIRECTED_GRAPH_PARAMS, class Property > typename graph_property< DIRECTED_GRAPH, Property >::type& get_property( DIRECTED_GRAPH& g, Property p) { return get_property(g.impl(), p); } template < DIRECTED_GRAPH_PARAMS, class Property > typename graph_property< DIRECTED_GRAPH, Property >::type const& get_property( DIRECTED_GRAPH const& g, Property p) { return get_property(g.impl(), p); } template < DIRECTED_GRAPH_PARAMS, class Property, class Value > void set_property(DIRECTED_GRAPH& g, Property p, Value v) { return set_property(g.impl(), p, v); } // Vertex index management template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::vertex_index_type get_vertex_index( typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) { return get(vertex_index, g, v); } template < DIRECTED_GRAPH_PARAMS > typename DIRECTED_GRAPH::vertex_index_type max_vertex_index( DIRECTED_GRAPH const& g) { return g.max_vertex_index(); } template < DIRECTED_GRAPH_PARAMS > inline void renumber_vertex_indices(DIRECTED_GRAPH& g) { g.renumber_vertex_indices(); } template < DIRECTED_GRAPH_PARAMS > inline void remove_vertex_and_renumber_indices( typename DIRECTED_GRAPH::vertex_iterator i, DIRECTED_GRAPH& g) { g.remove_vertex_and_renumber_indices(i); } // Edge index management template < DIRECTED_GRAPH_PARAMS > inline typename DIRECTED_GRAPH::edge_index_type get_edge_index( typename DIRECTED_GRAPH::edge_descriptor v, DIRECTED_GRAPH const& g) { return get(edge_index, g, v); } template < DIRECTED_GRAPH_PARAMS > typename DIRECTED_GRAPH::edge_index_type max_edge_index(DIRECTED_GRAPH const& g) { return g.max_edge_index(); } template < DIRECTED_GRAPH_PARAMS > inline void renumber_edge_indices(DIRECTED_GRAPH& g) { g.renumber_edge_indices(); } template < DIRECTED_GRAPH_PARAMS > inline void remove_edge_and_renumber_indices( typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g) { g.remove_edge_and_renumber_indices(i); } // Index management template < DIRECTED_GRAPH_PARAMS > inline void renumber_indices(DIRECTED_GRAPH& g) { g.renumber_indices(); } // Mutability Traits template < DIRECTED_GRAPH_PARAMS > struct graph_mutability_traits< DIRECTED_GRAPH > { typedef mutable_property_graph_tag category; }; #undef DIRECTED_GRAPH_PARAMS #undef DIRECTED_GRAPH } /* namespace boost */ #endif PK L�[Y�!w�4 �4 bipartite.hppnu �[��� /** * * Copyright (c) 2010 Matthias Walter (xammy@xammy.homelinux.net) * * Authors: Matthias Walter * * 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) * */ #ifndef BOOST_GRAPH_BIPARTITE_HPP #define BOOST_GRAPH_BIPARTITE_HPP #include <utility> #include <vector> #include <exception> #include <boost/graph/properties.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/one_bit_color_map.hpp> #include <boost/bind.hpp> namespace boost { namespace detail { /** * The bipartite_visitor_error is thrown if an edge cannot be colored. * The witnesses are the edges incident vertices. */ template < typename Vertex > struct BOOST_SYMBOL_VISIBLE bipartite_visitor_error : std::exception { std::pair< Vertex, Vertex > witnesses; bipartite_visitor_error(Vertex a, Vertex b) : witnesses(a, b) {} const char* what() const throw() { return "Graph is not bipartite."; } }; /** * Functor which colors edges to be non-monochromatic. */ template < typename PartitionMap > struct bipartition_colorize { typedef on_tree_edge event_filter; bipartition_colorize(PartitionMap partition_map) : partition_map_(partition_map) { } template < typename Edge, typename Graph > void operator()(Edge e, const Graph& g) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef color_traits< typename property_traits< PartitionMap >::value_type > color_traits; vertex_descriptor_t source_vertex = source(e, g); vertex_descriptor_t target_vertex = target(e, g); if (get(partition_map_, source_vertex) == color_traits::white()) put(partition_map_, target_vertex, color_traits::black()); else put(partition_map_, target_vertex, color_traits::white()); } private: PartitionMap partition_map_; }; /** * Creates a bipartition_colorize functor which colors edges * to be non-monochromatic. * * @param partition_map Color map for the bipartition * @return The functor. */ template < typename PartitionMap > inline bipartition_colorize< PartitionMap > colorize_bipartition( PartitionMap partition_map) { return bipartition_colorize< PartitionMap >(partition_map); } /** * Functor which tests an edge to be monochromatic. */ template < typename PartitionMap > struct bipartition_check { typedef on_back_edge event_filter; bipartition_check(PartitionMap partition_map) : partition_map_(partition_map) { } template < typename Edge, typename Graph > void operator()(Edge e, const Graph& g) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; vertex_descriptor_t source_vertex = source(e, g); vertex_descriptor_t target_vertex = target(e, g); if (get(partition_map_, source_vertex) == get(partition_map_, target_vertex)) throw bipartite_visitor_error< vertex_descriptor_t >( source_vertex, target_vertex); } private: PartitionMap partition_map_; }; /** * Creates a bipartition_check functor which raises an error if a * monochromatic edge is found. * * @param partition_map The map for a bipartition. * @return The functor. */ template < typename PartitionMap > inline bipartition_check< PartitionMap > check_bipartition( PartitionMap partition_map) { return bipartition_check< PartitionMap >(partition_map); } /** * Find the beginning of a common suffix of two sequences * * @param sequence1 Pair of bidirectional iterators defining the first * sequence. * @param sequence2 Pair of bidirectional iterators defining the second * sequence. * @return Pair of iterators pointing to the beginning of the common suffix. */ template < typename BiDirectionalIterator1, typename BiDirectionalIterator2 > inline std::pair< BiDirectionalIterator1, BiDirectionalIterator2 > reverse_mismatch( std::pair< BiDirectionalIterator1, BiDirectionalIterator1 > sequence1, std::pair< BiDirectionalIterator2, BiDirectionalIterator2 > sequence2) { if (sequence1.first == sequence1.second || sequence2.first == sequence2.second) return std::make_pair(sequence1.first, sequence2.first); BiDirectionalIterator1 iter1 = sequence1.second; BiDirectionalIterator2 iter2 = sequence2.second; while (true) { --iter1; --iter2; if (*iter1 != *iter2) { ++iter1; ++iter2; break; } if (iter1 == sequence1.first) break; if (iter2 == sequence2.first) break; } return std::make_pair(iter1, iter2); } } /** * Checks a given graph for bipartiteness and fills the given color map with * white and black according to the bipartition. If the graph is not * bipartite, the contents of the color map are undefined. Runs in linear * time in the size of the graph, if access to the property maps is in * constant time. * * @param graph The given graph. * @param index_map An index map associating vertices with an index. * @param partition_map A color map to fill with the bipartition. * @return true if and only if the given graph is bipartite. */ template < typename Graph, typename IndexMap, typename PartitionMap > bool is_bipartite( const Graph& graph, const IndexMap index_map, PartitionMap partition_map) { /// General types and variables typedef typename property_traits< PartitionMap >::value_type partition_color_t; typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; /// Declare dfs visitor // detail::empty_recorder recorder; // typedef detail::bipartite_visitor <PartitionMap, // detail::empty_recorder> dfs_visitor_t; dfs_visitor_t dfs_visitor // (partition_map, recorder); /// Call dfs try { depth_first_search(graph, vertex_index_map(index_map).visitor(make_dfs_visitor( std::make_pair(detail::colorize_bipartition(partition_map), std::make_pair(detail::check_bipartition(partition_map), put_property(partition_map, color_traits< partition_color_t >::white(), on_start_vertex())))))); } catch (const detail::bipartite_visitor_error< vertex_descriptor_t >&) { return false; } return true; } /** * Checks a given graph for bipartiteness. * * @param graph The given graph. * @param index_map An index map associating vertices with an index. * @return true if and only if the given graph is bipartite. */ template < typename Graph, typename IndexMap > bool is_bipartite(const Graph& graph, const IndexMap index_map) { typedef one_bit_color_map< IndexMap > partition_map_t; partition_map_t partition_map(num_vertices(graph), index_map); return is_bipartite(graph, index_map, partition_map); } /** * Checks a given graph for bipartiteness. The graph must * have an internal vertex_index property. Runs in linear time in the * size of the graph, if access to the property maps is in constant time. * * @param graph The given graph. * @return true if and only if the given graph is bipartite. */ template < typename Graph > bool is_bipartite(const Graph& graph) { return is_bipartite(graph, get(vertex_index, graph)); } /** * Checks a given graph for bipartiteness and fills a given color map with * white and black according to the bipartition. If the graph is not * bipartite, a sequence of vertices, producing an odd-cycle, is written to * the output iterator. The final iterator value is returned. Runs in linear * time in the size of the graph, if access to the property maps is in * constant time. * * @param graph The given graph. * @param index_map An index map associating vertices with an index. * @param partition_map A color map to fill with the bipartition. * @param result An iterator to write the odd-cycle vertices to. * @return The final iterator value after writing. */ template < typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator > OutputIterator find_odd_cycle(const Graph& graph, const IndexMap index_map, PartitionMap partition_map, OutputIterator result) { /// General types and variables typedef typename property_traits< PartitionMap >::value_type partition_color_t; typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; vertex_iterator_t vertex_iter, vertex_end; /// Declare predecessor map typedef std::vector< vertex_descriptor_t > predecessors_t; typedef iterator_property_map< typename predecessors_t::iterator, IndexMap, vertex_descriptor_t, vertex_descriptor_t& > predecessor_map_t; predecessors_t predecessors( num_vertices(graph), graph_traits< Graph >::null_vertex()); predecessor_map_t predecessor_map(predecessors.begin(), index_map); /// Initialize predecessor map for (boost::tie(vertex_iter, vertex_end) = vertices(graph); vertex_iter != vertex_end; ++vertex_iter) { put(predecessor_map, *vertex_iter, *vertex_iter); } /// Call dfs try { depth_first_search(graph, vertex_index_map(index_map).visitor(make_dfs_visitor( std::make_pair(detail::colorize_bipartition(partition_map), std::make_pair(detail::check_bipartition(partition_map), std::make_pair( put_property(partition_map, color_traits< partition_color_t >::white(), on_start_vertex()), record_predecessors( predecessor_map, on_tree_edge()))))))); } catch (const detail::bipartite_visitor_error< vertex_descriptor_t >& error) { typedef std::vector< vertex_descriptor_t > path_t; path_t path1, path2; vertex_descriptor_t next, current; /// First path next = error.witnesses.first; do { current = next; path1.push_back(current); next = predecessor_map[current]; } while (current != next); /// Second path next = error.witnesses.second; do { current = next; path2.push_back(current); next = predecessor_map[current]; } while (current != next); /// Find beginning of common suffix std::pair< typename path_t::iterator, typename path_t::iterator > mismatch = detail::reverse_mismatch( std::make_pair(path1.begin(), path1.end()), std::make_pair(path2.begin(), path2.end())); /// Copy the odd-length cycle result = std::copy(path1.begin(), mismatch.first + 1, result); return std::reverse_copy(path2.begin(), mismatch.second, result); } return result; } /** * Checks a given graph for bipartiteness. If the graph is not bipartite, a * sequence of vertices, producing an odd-cycle, is written to the output * iterator. The final iterator value is returned. Runs in linear time in the * size of the graph, if access to the property maps is in constant time. * * @param graph The given graph. * @param index_map An index map associating vertices with an index. * @param result An iterator to write the odd-cycle vertices to. * @return The final iterator value after writing. */ template < typename Graph, typename IndexMap, typename OutputIterator > OutputIterator find_odd_cycle( const Graph& graph, const IndexMap index_map, OutputIterator result) { typedef one_bit_color_map< IndexMap > partition_map_t; partition_map_t partition_map(num_vertices(graph), index_map); return find_odd_cycle(graph, index_map, partition_map, result); } /** * Checks a given graph for bipartiteness. If the graph is not bipartite, a * sequence of vertices, producing an odd-cycle, is written to the output * iterator. The final iterator value is returned. The graph must have an * internal vertex_index property. Runs in linear time in the size of the * graph, if access to the property maps is in constant time. * * @param graph The given graph. * @param result An iterator to write the odd-cycle vertices to. * @return The final iterator value after writing. */ template < typename Graph, typename OutputIterator > OutputIterator find_odd_cycle(const Graph& graph, OutputIterator result) { return find_odd_cycle(graph, get(vertex_index, graph), result); } } #endif /// BOOST_GRAPH_BIPARTITE_HPP PK L�[�s5�0 0 stoer_wagner_min_cut.hppnu �[��� // Copyright Daniel Trebbien 2010. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or the copy at // http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP #define BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP 1 #include <boost/assert.hpp> #include <set> #include <vector> #include <boost/concept_check.hpp> #include <boost/concept/assert.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/buffer_concepts.hpp> #include <boost/graph/exception.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/maximum_adjacency_search.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/graph/one_bit_color_map.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/property_map/property_map.hpp> #include <boost/tuple/tuple.hpp> #include <boost/utility/result_of.hpp> #include <boost/graph/iteration_macros.hpp> namespace boost { namespace detail { template < typename ParityMap, typename WeightMap, typename IndexMap > class mas_min_cut_visitor : public boost::default_mas_visitor { typedef one_bit_color_map< IndexMap > InternalParityMap; typedef typename boost::property_traits< WeightMap >::value_type weight_type; public: template < typename Graph > mas_min_cut_visitor(const Graph& g, ParityMap parity, weight_type& cutweight, const WeightMap& weight_map, IndexMap index_map) : m_bestParity(parity) , m_parity(make_one_bit_color_map(num_vertices(g), index_map)) , m_bestWeight(cutweight) , m_cutweight(0) , m_visited(0) , m_weightMap(weight_map) { // set here since the init list sets the reference m_bestWeight = (std::numeric_limits< weight_type >::max)(); } template < typename Vertex, typename Graph > void initialize_vertex(Vertex u, const Graph& g) { typedef typename boost::property_traits< ParityMap >::value_type parity_type; typedef typename boost::property_traits< InternalParityMap >::value_type internal_parity_type; put(m_parity, u, internal_parity_type(0)); put(m_bestParity, u, parity_type(0)); } template < typename Edge, typename Graph > void examine_edge(Edge e, const Graph& g) { weight_type w = get(m_weightMap, e); // if the target of e is already marked then decrease cutweight // otherwise, increase it if (get(m_parity, boost::target(e, g))) { m_cutweight -= w; } else { m_cutweight += w; } } template < typename Vertex, typename Graph > void finish_vertex(Vertex u, const Graph& g) { typedef typename boost::property_traits< InternalParityMap >::value_type internal_parity_type; ++m_visited; put(m_parity, u, internal_parity_type(1)); if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) { m_bestWeight = m_cutweight; BGL_FORALL_VERTICES_T(i, g, Graph) { put(m_bestParity, i, get(m_parity, i)); } } } inline void clear() { m_bestWeight = (std::numeric_limits< weight_type >::max)(); m_visited = 0; m_cutweight = 0; } private: ParityMap m_bestParity; InternalParityMap m_parity; weight_type& m_bestWeight; weight_type m_cutweight; unsigned m_visited; const WeightMap& m_weightMap; }; /** * \brief Computes a min-cut of the input graph * * Computes a min-cut of the input graph using the Stoer-Wagner algorithm. * * \pre \p g is a connected, undirected graph * \pre <code>pq.empty()</code> * \param[in] g the input graph * \param[in] weights a readable property map from each edge to its weight * (a non-negative value) \param[out] parities a writable property map from * each vertex to a bool type object for distinguishing the two vertex sets * of the min-cut \param[out] assignments a read/write property map from * each vertex to a \c vertex_descriptor object. This map serves as work * space, and no particular meaning should be derived from property values * after completion of the algorithm. * \param[out] pq a keyed, updatable max-priority queue * \returns the cut weight of the min-cut * \see * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf * \see * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf * * \author Daniel Trebbien * \date 2010-09-11 */ template < class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap > typename boost::property_traits< WeightMap >::value_type stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) { typedef typename boost::graph_traits< UndirectedGraph >::vertex_descriptor vertex_descriptor; typedef typename boost::property_traits< WeightMap >::value_type weight_type; typename graph_traits< UndirectedGraph >::vertex_iterator u_iter, u_end; weight_type bestW = (std::numeric_limits< weight_type >::max)(); weight_type bestThisTime = (std::numeric_limits< weight_type >::max)(); vertex_descriptor bestStart = boost::graph_traits< UndirectedGraph >::null_vertex(); detail::mas_min_cut_visitor< ParityMap, WeightMap, IndexMap > vis( g, parities, bestThisTime, weights, index_map); // for each node in the graph, for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) { // run the MAS and find the min cut vis.clear(); boost::maximum_adjacency_search(g, boost::weight_map(weights) .visitor(vis) .root_vertex(*u_iter) .vertex_assignment_map(assignments) .max_priority_queue(pq)); if (bestThisTime < bestW) { bestW = bestThisTime; bestStart = *u_iter; } } // Run one more time, starting from the best start location, to // ensure the visitor has the best values. vis.clear(); boost::maximum_adjacency_search(g, boost::vertex_assignment_map(assignments) .weight_map(weights) .visitor(vis) .root_vertex(bestStart) .max_priority_queue(pq)); return bestW; } } // end `namespace detail` within `namespace boost` template < class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap > typename boost::property_traits< WeightMap >::value_type stoer_wagner_min_cut( const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) { BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept< UndirectedGraph >)); BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept< UndirectedGraph >)); typedef typename boost::graph_traits< UndirectedGraph >::vertex_descriptor vertex_descriptor; typedef typename boost::graph_traits< UndirectedGraph >::vertices_size_type vertices_size_type; typedef typename boost::graph_traits< UndirectedGraph >::edge_descriptor edge_descriptor; BOOST_CONCEPT_ASSERT((boost::Convertible< typename boost::graph_traits< UndirectedGraph >::directed_category, boost::undirected_tag >)); BOOST_CONCEPT_ASSERT( (boost::ReadablePropertyMapConcept< WeightMap, edge_descriptor >)); // typedef typename boost::property_traits<WeightMap>::value_type // weight_type; BOOST_CONCEPT_ASSERT( (boost::WritablePropertyMapConcept< ParityMap, vertex_descriptor >)); // typedef typename boost::property_traits<ParityMap>::value_type // parity_type; BOOST_CONCEPT_ASSERT( (boost::ReadWritePropertyMapConcept< VertexAssignmentMap, vertex_descriptor >)); BOOST_CONCEPT_ASSERT((boost::Convertible< vertex_descriptor, typename boost::property_traits< VertexAssignmentMap >::value_type >)); BOOST_CONCEPT_ASSERT( (boost::KeyedUpdatableQueueConcept< KeyedUpdatablePriorityQueue >)); vertices_size_type n = num_vertices(g); if (n < 2) throw boost::bad_graph( "the input graph must have at least two vertices."); else if (!pq.empty()) throw std::invalid_argument( "the max-priority queue must be empty initially."); return detail::stoer_wagner_min_cut( g, weights, parities, assignments, pq, index_map); } namespace graph { namespace detail { template < class UndirectedGraph, class WeightMap > struct stoer_wagner_min_cut_impl { typedef typename boost::property_traits< WeightMap >::value_type result_type; template < typename ArgPack > result_type operator()(const UndirectedGraph& g, WeightMap weights, const ArgPack& arg_pack) const { using namespace boost::graph::keywords; typedef typename boost::graph_traits< UndirectedGraph >::vertex_descriptor vertex_descriptor; typedef typename boost::property_traits< WeightMap >::value_type weight_type; typedef boost::detail::make_priority_queue_from_arg_pack_gen< boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater< weight_type > > gen_type; gen_type gen( choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0))); typename boost::result_of< gen_type( const UndirectedGraph&, const ArgPack&) >::type pq = gen(g, arg_pack); boost::dummy_property_map dummy_prop; return boost::stoer_wagner_min_cut(g, weights, arg_pack[_parity_map | dummy_prop], boost::detail::make_property_map_from_arg_pack_gen< tag::vertex_assignment_map, vertex_descriptor >( vertex_descriptor())(g, arg_pack), pq, boost::detail::override_const_property( arg_pack, _vertex_index_map, g, vertex_index)); } }; } BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut, 2, 4) } // Named parameter interface BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2) namespace graph { // version without IndexMap kept for backwards compatibility // (but requires vertex_index_t to be defined in the graph) // Place after the macro to avoid compilation errors template < class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue > typename boost::property_traits< WeightMap >::value_type stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) { return stoer_wagner_min_cut( g, weights, parities, assignments, pq, get(vertex_index, g)); } } // end `namespace graph` } // end `namespace boost` #include <boost/graph/iteration_macros_undef.hpp> #endif // !BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP PK L�[����0 0 overloading.hppnu �[��� // Copyright 2004 The Trustees of Indiana University. // Use, modification and distribution is subject to 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) // Authors: Douglas Gregor // Andrew Lumsdaine // // This file contains helps that enable concept-based overloading // within the Boost Graph Library. // #ifndef BOOST_GRAPH_OVERLOADING_HPP #define BOOST_GRAPH_OVERLOADING_HPP #include <boost/type_traits/is_base_and_derived.hpp> #include <boost/utility/enable_if.hpp> namespace boost { namespace graph { namespace detail { struct no_parameter { }; } } } // end namespace boost::graph::detail #ifndef BOOST_NO_SFINAE #define BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag, Type) \ typename enable_if_c< \ (is_base_and_derived< Tag, \ typename graph_traits< Graph >::traversal_category >::value), \ Type >::type #define BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, Tag) \ , \ BOOST_GRAPH_ENABLE_IF_MODELS( \ Graph, Tag, ::boost::graph::detail::no_parameter) \ = ::boost::graph::detail::no_parameter() #else #define BOOST_GRAPH_ENABLE_IF_MODELS(Graph, Tag, Type) Type #define BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, Tag) #endif // no SFINAE support #endif // BOOST_GRAPH_OVERLOADING_HPP PK L�[�G7� � exterior_property.hppnu �[��� // (C) Copyright 2007-2009 Andrew Sutton // // Use, modification and distribution are subject to the // Boost Software License, Version 1.0 (See accompanying file // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_GRAPH_EXTERIOR_PROPERTY_HPP #define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP #include <vector> #include <boost/graph/property_maps/container_property_map.hpp> #include <boost/graph/property_maps/matrix_property_map.hpp> namespace boost { namespace detail { // The vector matrix provides a little abstraction over vector // types that makes matrices easier to work with. template < typename Value > struct vector_matrix { typedef std::vector< Value > container_type; typedef std::vector< container_type > matrix_type; typedef container_type value_type; typedef container_type& reference; typedef const container_type const_reference; typedef container_type* pointer; typedef typename matrix_type::size_type size_type; // Instantiate the matrix over n elements (creates an n by n matrix). // The graph has to be passed in order to ensure the index maps // are constructed correctly when returning indexible elements. inline vector_matrix(size_type n) : m_matrix(n, container_type(n)) {} inline reference operator[](size_type n) { return m_matrix[n]; } inline const_reference operator[](size_type n) const { return m_matrix[n]; } matrix_type m_matrix; }; } /* namespace detail */ /** * The exterior_property metafunction defines an appropriate set of types for * creating an exterior property. An exterior property is comprised of a both * a container and a property map that acts as its abstraction. An extension * of this metafunction will select an appropriate "matrix" property that * records values for pairs of vertices. * * @todo This does not currently support the ability to define exterior * properties for graph types that do not model the IndexGraph concepts. A * solution should not be especially difficult, but will require an extension * of type traits to affect the type selection. */ template < typename Graph, typename Key, typename Value > struct exterior_property { typedef Key key_type; typedef Value value_type; typedef std::vector< Value > container_type; typedef container_property_map< Graph, Key, container_type > map_type; typedef detail::vector_matrix< Value > matrix_type; typedef matrix_property_map< Graph, Key, matrix_type > matrix_map_type; private: exterior_property() {} exterior_property(const exterior_property&) {} }; /** * Define a the container and property map types requried to create an exterior * vertex property for the given value type. The Graph parameter is required to * model the VertexIndexGraph concept. */ template < typename Graph, typename Value > struct exterior_vertex_property { typedef exterior_property< Graph, typename graph_traits< Graph >::vertex_descriptor, Value > property_type; typedef typename property_type::key_type key_type; typedef typename property_type::value_type value_type; typedef typename property_type::container_type container_type; typedef typename property_type::map_type map_type; typedef typename property_type::matrix_type matrix_type; typedef typename property_type::matrix_map_type matrix_map_type; }; /** * Define a the container and property map types requried to create an exterior * edge property for the given value type. The Graph parameter is required to * model the EdgeIndexGraph concept. */ template < typename Graph, typename Value > struct exterior_edge_property { typedef exterior_property< Graph, typename graph_traits< Graph >::edge_descriptor, Value > property_type; typedef typename property_type::key_type key_type; typedef typename property_type::value_type value_type; typedef typename property_type::container_type container_type; typedef typename property_type::map_type map_type; typedef typename property_type::matrix_type matrix_type; typedef typename property_type::matrix_map_type matrix_map_type; }; } /* namespace boost */ #endif PK L�[��z�7 �7 transitive_closure.hppnu �[��� // Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su> // Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu> // 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) // NOTE: this final is generated by libs/graph/doc/transitive_closure.w #ifndef BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP #define BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP #include <vector> #include <algorithm> // for std::min and std::max #include <functional> #include <boost/config.hpp> #include <boost/bind.hpp> #include <boost/graph/strong_components.hpp> #include <boost/graph/topological_sort.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/concept/assert.hpp> namespace boost { namespace detail { inline void union_successor_sets(const std::vector< std::size_t >& s1, const std::vector< std::size_t >& s2, std::vector< std::size_t >& s3) { BOOST_USING_STD_MIN(); for (std::size_t k = 0; k < s1.size(); ++k) s3[k] = min BOOST_PREVENT_MACRO_SUBSTITUTION(s1[k], s2[k]); } } // namespace detail namespace detail { template < typename TheContainer, typename ST = std::size_t, typename VT = typename TheContainer::value_type > struct subscript_t { typedef ST argument_type; typedef VT& result_type; subscript_t(TheContainer& c) : container(&c) {} VT& operator()(const ST& i) const { return (*container)[i]; } protected: TheContainer* container; }; template < typename TheContainer > subscript_t< TheContainer > subscript(TheContainer& c) { return subscript_t< TheContainer >(c); } } // namespace detail template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap, typename VertexIndexMap > void transitive_closure(const Graph& g, GraphTC& tc, G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map) { if (num_vertices(g) == 0) return; typedef typename graph_traits< Graph >::vertex_descriptor vertex; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; typedef typename property_traits< VertexIndexMap >::value_type size_type; typedef typename graph_traits< Graph >::adjacency_iterator adjacency_iterator; BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >)); BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept< Graph >)); BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept< GraphTC >)); BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< GraphTC >)); BOOST_CONCEPT_ASSERT( (ReadablePropertyMapConcept< VertexIndexMap, vertex >)); typedef size_type cg_vertex; std::vector< cg_vertex > component_number_vec(num_vertices(g)); iterator_property_map< cg_vertex*, VertexIndexMap, cg_vertex, cg_vertex& > component_number(&component_number_vec[0], index_map); int num_scc = strong_components(g, component_number, vertex_index_map(index_map)); std::vector< std::vector< vertex > > components; build_component_lists(g, num_scc, component_number, components); typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS > CG_t; CG_t CG(num_scc); for (cg_vertex s = 0; s < components.size(); ++s) { std::vector< cg_vertex > adj; for (size_type i = 0; i < components[s].size(); ++i) { vertex u = components[s][i]; adjacency_iterator v, v_end; for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end; ++v) { cg_vertex t = component_number[*v]; if (s != t) // Avoid loops in the condensation graph adj.push_back(t); } } std::sort(adj.begin(), adj.end()); typename std::vector< cg_vertex >::iterator di = std::unique(adj.begin(), adj.end()); if (di != adj.end()) adj.erase(di, adj.end()); for (typename std::vector< cg_vertex >::const_iterator i = adj.begin(); i != adj.end(); ++i) { add_edge(s, *i, CG); } } std::vector< cg_vertex > topo_order; std::vector< cg_vertex > topo_number(num_vertices(CG)); topological_sort(CG, std::back_inserter(topo_order), vertex_index_map(identity_property_map())); std::reverse(topo_order.begin(), topo_order.end()); size_type n = 0; for (typename std::vector< cg_vertex >::iterator iter = topo_order.begin(); iter != topo_order.end(); ++iter) topo_number[*iter] = n++; std::vector< std::vector< cg_vertex > > CG_vec(num_vertices(CG)); for (size_type i = 0; i < num_vertices(CG); ++i) { typedef typename boost::graph_traits< CG_t >::adjacency_iterator cg_adj_iter; std::pair< cg_adj_iter, cg_adj_iter > pr = adjacent_vertices(i, CG); CG_vec[i].assign(pr.first, pr.second); std::sort(CG_vec[i].begin(), CG_vec[i].end(), boost::bind(std::less< cg_vertex >(), boost::bind(detail::subscript(topo_number), _1), boost::bind(detail::subscript(topo_number), _2))); } std::vector< std::vector< cg_vertex > > chains; { std::vector< cg_vertex > in_a_chain(CG_vec.size()); for (typename std::vector< cg_vertex >::iterator i = topo_order.begin(); i != topo_order.end(); ++i) { cg_vertex v = *i; if (!in_a_chain[v]) { chains.resize(chains.size() + 1); std::vector< cg_vertex >& chain = chains.back(); for (;;) { chain.push_back(v); in_a_chain[v] = true; typename std::vector< cg_vertex >::const_iterator next = std::find_if(CG_vec[v].begin(), CG_vec[v].end(), std::not1(detail::subscript(in_a_chain))); if (next != CG_vec[v].end()) v = *next; else break; // end of chain, dead-end } } } } std::vector< size_type > chain_number(CG_vec.size()); std::vector< size_type > pos_in_chain(CG_vec.size()); for (size_type i = 0; i < chains.size(); ++i) for (size_type j = 0; j < chains[i].size(); ++j) { cg_vertex v = chains[i][j]; chain_number[v] = i; pos_in_chain[v] = j; } cg_vertex inf = (std::numeric_limits< cg_vertex >::max)(); std::vector< std::vector< cg_vertex > > successors( CG_vec.size(), std::vector< cg_vertex >(chains.size(), inf)); for (typename std::vector< cg_vertex >::reverse_iterator i = topo_order.rbegin(); i != topo_order.rend(); ++i) { cg_vertex u = *i; typename std::vector< cg_vertex >::const_iterator adj, adj_last; for (adj = CG_vec[u].begin(), adj_last = CG_vec[u].end(); adj != adj_last; ++adj) { cg_vertex v = *adj; if (topo_number[v] < successors[u][chain_number[v]]) { // Succ(u) = Succ(u) U Succ(v) detail::union_successor_sets( successors[u], successors[v], successors[u]); // Succ(u) = Succ(u) U {v} successors[u][chain_number[v]] = topo_number[v]; } } } for (size_type i = 0; i < CG_vec.size(); ++i) CG_vec[i].clear(); for (size_type i = 0; i < CG_vec.size(); ++i) for (size_type j = 0; j < chains.size(); ++j) { size_type topo_num = successors[i][j]; if (topo_num < inf) { cg_vertex v = topo_order[topo_num]; for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k) CG_vec[i].push_back(chains[j][k]); } } // Add vertices to the transitive closure graph { vertex_iterator i, i_end; for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) g_to_tc_map[*i] = add_vertex(tc); } // Add edges between all the vertices in two adjacent SCCs typename std::vector< std::vector< cg_vertex > >::const_iterator si, si_end; for (si = CG_vec.begin(), si_end = CG_vec.end(); si != si_end; ++si) { cg_vertex s = si - CG_vec.begin(); typename std::vector< cg_vertex >::const_iterator i, i_end; for (i = CG_vec[s].begin(), i_end = CG_vec[s].end(); i != i_end; ++i) { cg_vertex t = *i; for (size_type k = 0; k < components[s].size(); ++k) for (size_type l = 0; l < components[t].size(); ++l) add_edge(g_to_tc_map[components[s][k]], g_to_tc_map[components[t][l]], tc); } } // Add edges connecting all vertices in a SCC for (size_type i = 0; i < components.size(); ++i) if (components[i].size() > 1) for (size_type k = 0; k < components[i].size(); ++k) for (size_type l = 0; l < components[i].size(); ++l) { vertex u = components[i][k], v = components[i][l]; add_edge(g_to_tc_map[u], g_to_tc_map[v], tc); } // Find loopbacks in the original graph. // Need to add it to transitive closure. { vertex_iterator i, i_end; for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) { adjacency_iterator ab, ae; for (boost::tie(ab, ae) = adjacent_vertices(*i, g); ab != ae; ++ab) { if (*ab == *i) if (components[component_number[*i]].size() == 1) add_edge(g_to_tc_map[*i], g_to_tc_map[*i], tc); } } } } template < typename Graph, typename GraphTC > void transitive_closure(const Graph& g, GraphTC& tc) { if (num_vertices(g) == 0) return; typedef typename property_map< Graph, vertex_index_t >::const_type VertexIndexMap; VertexIndexMap index_map = get(vertex_index, g); typedef typename graph_traits< GraphTC >::vertex_descriptor tc_vertex; std::vector< tc_vertex > to_tc_vec(num_vertices(g)); iterator_property_map< tc_vertex*, VertexIndexMap, tc_vertex, tc_vertex& > g_to_tc_map(&to_tc_vec[0], index_map); transitive_closure(g, tc, g_to_tc_map, index_map); } namespace detail { template < typename Graph, typename GraphTC, typename G_to_TC_VertexMap, typename VertexIndexMap > void transitive_closure_dispatch(const Graph& g, GraphTC& tc, G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map) { typedef typename graph_traits< GraphTC >::vertex_descriptor tc_vertex; typename std::vector< tc_vertex >::size_type n = is_default_param(g_to_tc_map) ? num_vertices(g) : 1; std::vector< tc_vertex > to_tc_vec(n); transitive_closure(g, tc, choose_param(g_to_tc_map, make_iterator_property_map( to_tc_vec.begin(), index_map, to_tc_vec[0])), index_map); } } // namespace detail template < typename Graph, typename GraphTC, typename P, typename T, typename R > void transitive_closure( const Graph& g, GraphTC& tc, const bgl_named_params< P, T, R >& params) { if (num_vertices(g) == 0) return; detail::transitive_closure_dispatch(g, tc, get_param(params, orig_to_copy_t()), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)); } template < typename G > void warshall_transitive_closure(G& g) { typedef typename graph_traits< G >::vertex_iterator vertex_iterator; BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< G >)); BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< G >)); // Matrix form: // for k // for i // if A[i,k] // for j // A[i,j] = A[i,j] | A[k,j] vertex_iterator ki, ke, ii, ie, ji, je; for (boost::tie(ki, ke) = vertices(g); ki != ke; ++ki) for (boost::tie(ii, ie) = vertices(g); ii != ie; ++ii) if (edge(*ii, *ki, g).second) for (boost::tie(ji, je) = vertices(g); ji != je; ++ji) if (!edge(*ii, *ji, g).second && edge(*ki, *ji, g).second) { add_edge(*ii, *ji, g); } } template < typename G > void warren_transitive_closure(G& g) { using namespace boost; typedef typename graph_traits< G >::vertex_iterator vertex_iterator; BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< G >)); BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept< G >)); // Make sure second loop will work if (num_vertices(g) == 0) return; // for i = 2 to n // for k = 1 to i - 1 // if A[i,k] // for j = 1 to n // A[i,j] = A[i,j] | A[k,j] vertex_iterator ic, ie, jc, je, kc, ke; for (boost::tie(ic, ie) = vertices(g), ++ic; ic != ie; ++ic) for (boost::tie(kc, ke) = vertices(g); *kc != *ic; ++kc) if (edge(*ic, *kc, g).second) for (boost::tie(jc, je) = vertices(g); jc != je; ++jc) if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) { add_edge(*ic, *jc, g); } // for i = 1 to n - 1 // for k = i + 1 to n // if A[i,k] // for j = 1 to n // A[i,j] = A[i,j] | A[k,j] for (boost::tie(ic, ie) = vertices(g), --ie; ic != ie; ++ic) for (kc = ic, ke = ie, ++kc; kc != ke; ++kc) if (edge(*ic, *kc, g).second) for (boost::tie(jc, je) = vertices(g); jc != je; ++jc) if (!edge(*ic, *jc, g).second && edge(*kc, *jc, g).second) { add_edge(*ic, *jc, g); } } } // namespace boost #endif // BOOST_GRAPH_TRANSITIVE_CLOSURE_HPP PK L�[���* �* metis.hppnu �[��� // Copyright 2005 The Trustees of Indiana University. // Use, modification and distribution is subject to 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) // Authors: Douglas Gregor // Andrew Lumsdaine #ifndef BOOST_GRAPH_METIS_HPP #define BOOST_GRAPH_METIS_HPP #ifdef BOOST_GRAPH_METIS_NO_INLINE #define BOOST_GRAPH_METIS_INLINE_KEYWORD #else #define BOOST_GRAPH_METIS_INLINE_KEYWORD inline #endif #include <string> #include <iostream> #include <iterator> #include <utility> #include <sstream> #include <exception> #include <vector> #include <algorithm> namespace boost { namespace graph { class BOOST_SYMBOL_VISIBLE metis_exception : public std::exception { }; class BOOST_SYMBOL_VISIBLE metis_input_exception : public metis_exception { }; class metis_reader { public: typedef std::size_t vertices_size_type; typedef std::size_t edges_size_type; typedef double vertex_weight_type; typedef double edge_weight_type; class edge_iterator { public: typedef std::input_iterator_tag iterator_category; typedef std::pair< vertices_size_type, vertices_size_type > value_type; typedef const value_type& reference; typedef const value_type* pointer; typedef std::ptrdiff_t difference_type; private: class postincrement_proxy { postincrement_proxy(const value_type& value) : value(value) {} public: reference operator*() const { return value; } private: value_type value; friend class edge_iterator; }; public: edge_iterator& operator++(); postincrement_proxy operator++(int); reference operator*() const { return self->edge; } pointer operator->() const { return &self->edge; } // Default copy constructor and assignment operator are okay private: edge_iterator(metis_reader* self); void advance(bool skip_initial_read); metis_reader* self; friend class metis_reader; friend bool operator==(edge_iterator, edge_iterator); friend bool operator!=(edge_iterator, edge_iterator); }; friend class edge_iterator; class edge_weight_iterator { public: typedef std::input_iterator_tag iterator_category; typedef edge_weight_type value_type; typedef const value_type& reference; typedef const value_type* pointer; // Default copy constructor and assignment operator are okay reference operator*() const { return self->edge_weight; } pointer operator->() const { return &self->edge_weight; } edge_weight_iterator& operator++() { return *this; } edge_weight_iterator operator++(int) { return *this; } private: edge_weight_iterator(metis_reader* self) : self(self) {} metis_reader* self; friend class metis_reader; }; metis_reader(std::istream& in) : in(in), edge_weight(1.0) { start(); } edge_iterator begin(); edge_iterator end(); edge_weight_iterator weight_begin(); vertices_size_type num_vertices() const { return n_vertices; } edges_size_type num_edges() const { return n_edges; } std::size_t num_vertex_weights() const { return n_vertex_weights; } vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n) { return vertex_weights[v * num_vertex_weights() + n]; } bool has_edge_weights() const { return edge_weights; } private: void start(); // Configuration information std::istream& in; // Information about the current METIS file vertices_size_type n_vertices; edges_size_type n_edges; std::size_t n_vertex_weights; bool edge_weights; // Information about the current edge/vertex std::istringstream line_in; std::pair< vertices_size_type, vertices_size_type > edge; std::vector< vertex_weight_type > vertex_weights; edge_weight_type edge_weight; friend bool operator==(edge_iterator, edge_iterator); friend bool operator!=(edge_iterator, edge_iterator); }; class metis_distribution { public: typedef int process_id_type; typedef std::size_t size_type; typedef std::vector< process_id_type >::iterator iterator; metis_distribution(std::istream& in, process_id_type my_id); size_type block_size(process_id_type id, size_type) const; process_id_type operator()(size_type n) const { return vertices[n]; } size_type local(size_type n) const; size_type global(size_type n) const { return global(my_id, n); } size_type global(process_id_type id, size_type n) const; iterator begin() { return vertices.begin(); } iterator end() { return vertices.end(); } private: process_id_type my_id; std::vector< process_id_type > vertices; }; #if !defined(BOOST_GRAPH_METIS_NO_INLINE) || defined(BOOST_GRAPH_METIS_SOURCE) BOOST_GRAPH_METIS_INLINE_KEYWORD bool operator==( metis_reader::edge_iterator x, metis_reader::edge_iterator y) { return (x.self == y.self || (x.self && x.self->edge.first == x.self->num_vertices()) || (y.self && y.self->edge.first == y.self->num_vertices())); } BOOST_GRAPH_METIS_INLINE_KEYWORD bool operator!=( metis_reader::edge_iterator x, metis_reader::edge_iterator y) { return !(x == y); } BOOST_GRAPH_METIS_INLINE_KEYWORD metis_reader::edge_iterator::edge_iterator(metis_reader* self) : self(self) { if (self) advance(true); } BOOST_GRAPH_METIS_INLINE_KEYWORD metis_reader::edge_iterator& metis_reader::edge_iterator::operator++() { advance(false); return *this; } BOOST_GRAPH_METIS_INLINE_KEYWORD void metis_reader::edge_iterator::advance(bool skip_initial_read) { do { if (!skip_initial_read) { // Try to read the next edge if (self->line_in >> std::ws >> self->edge.second) { --self->edge.second; if (self->has_edge_weights()) { if (!(self->line_in >> self->edge_weight)) boost::throw_exception(metis_input_exception()); } return; } // Check if we're done ++self->edge.first; if (self->edge.first == self->num_vertices()) return; } // Find the next line std::string line; while (getline(self->in, line) && !line.empty() && line[0] == '%') { /* Keep reading lines in the loop header... */ } if (!self->in) boost::throw_exception(metis_input_exception()); self->line_in.str(line); self->line_in.clear(); // Read the next line std::size_t weights_left = self->n_vertex_weights; vertex_weight_type weight; while (weights_left > 0) { if (self->line_in >> weight) self->vertex_weights.push_back(weight); else boost::throw_exception(metis_input_exception()); --weights_left; } // Successive iterations will pick up edges for this vertex. skip_initial_read = false; } while (true); } BOOST_GRAPH_METIS_INLINE_KEYWORD metis_reader::edge_iterator::postincrement_proxy metis_reader::edge_iterator::operator++(int) { postincrement_proxy result(**this); ++(*this); return result; } BOOST_GRAPH_METIS_INLINE_KEYWORD metis_reader::edge_iterator metis_reader::begin() { if (edge.first != 0) start(); return edge_iterator(this); } BOOST_GRAPH_METIS_INLINE_KEYWORD metis_reader::edge_iterator metis_reader::end() { return edge_iterator(0); } BOOST_GRAPH_METIS_INLINE_KEYWORD metis_reader::edge_weight_iterator metis_reader::weight_begin() { return edge_weight_iterator(this); } BOOST_GRAPH_METIS_INLINE_KEYWORD void metis_reader::start() { in.seekg(0, std::ios::beg); std::string line; while (getline(in, line) && !line.empty() && line[0] == '%') { /* Keep getting lines in loop header. */ } if (!in || line.empty()) boost::throw_exception(metis_input_exception()); // Determine number of vertices and edges in the graph line_in.str(line); if (!(line_in >> n_vertices >> n_edges)) boost::throw_exception(metis_input_exception()); // Determine whether vertex or edge weights are included in the graph int fmt = 0; line_in >> fmt; n_vertex_weights = fmt / 10; edge_weights = (fmt % 10 == 1); // Determine how many (if any!) vertex weights are included if (n_vertex_weights) line_in >> n_vertex_weights; // Setup the iteration data structures edge_weight = 1.0; edge.first = 0; edge.second = 0; vertex_weights.reserve(n_vertex_weights * num_vertices()); } metis_distribution::metis_distribution( std::istream& in, process_id_type my_id) : my_id(my_id) , vertices(std::istream_iterator< process_id_type >(in), std::istream_iterator< process_id_type >()) { } metis_distribution::size_type metis_distribution::block_size( process_id_type id, size_type) const { return std::count(vertices.begin(), vertices.end(), id); } metis_distribution::size_type metis_distribution::local(size_type n) const { return std::count(vertices.begin(), vertices.begin() + n, vertices[n]); } metis_distribution::size_type metis_distribution::global( process_id_type id, size_type n) const { std::vector< process_id_type >::const_iterator i = vertices.begin(); while (*i != id) ++i; while (n > 0) { do { ++i; } while (*i != id); --n; } return i - vertices.begin(); } #endif } } // end namespace boost::graph #endif // BOOST_GRAPH_METIS_HPP PK L�[f�� � use_mpi.hppnu �[��� // Copyright (C) 2004-2009 The Trustees of Indiana University. // Use, modification and distribution is subject to 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) // Authors: Nick Edmonds // Andrew Lumsdaine #ifndef BOOST_GRAPH_USE_MPI_HPP #define BOOST_GRAPH_USE_MPI_HPP #define BOOST_GRAPH_USE_MPI #endif // BOOST_GRAPH_USE_MPI_HPP PK L�[Q(*�C �C fruchterman_reingold.hppnu �[��� // Copyright 2004, 2005 The Trustees of Indiana University. // 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) // Authors: Douglas Gregor // Andrew Lumsdaine #ifndef BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP #define BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP #include <boost/config/no_tr1/cmath.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/topology.hpp> // For topology concepts #include <boost/graph/detail/mpi_include.hpp> #include <vector> #include <list> #include <algorithm> // for std::min and std::max #include <numeric> // for std::accumulate #include <cmath> // for std::sqrt and std::fabs #include <functional> namespace boost { struct square_distance_attractive_force { template < typename Graph, typename T > T operator()(typename graph_traits< Graph >::edge_descriptor, T k, T d, const Graph&) const { return d * d / k; } }; struct square_distance_repulsive_force { template < typename Graph, typename T > T operator()(typename graph_traits< Graph >::vertex_descriptor, typename graph_traits< Graph >::vertex_descriptor, T k, T d, const Graph&) const { return k * k / d; } }; template < typename T > struct linear_cooling { typedef T result_type; linear_cooling(std::size_t iterations) : temp(T(iterations) / T(10)), step(0.1) { } linear_cooling(std::size_t iterations, T temp) : temp(temp), step(temp / T(iterations)) { } T operator()() { T old_temp = temp; temp -= step; if (temp < T(0)) temp = T(0); return old_temp; } private: T temp; T step; }; struct all_force_pairs { template < typename Graph, typename ApplyForce > void operator()(const Graph& g, ApplyForce apply_force) { typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; vertex_iterator v, end; for (boost::tie(v, end) = vertices(g); v != end; ++v) { vertex_iterator u = v; for (++u; u != end; ++u) { apply_force(*u, *v); apply_force(*v, *u); } } } }; template < typename Topology, typename PositionMap > struct grid_force_pairs { typedef typename property_traits< PositionMap >::value_type Point; BOOST_STATIC_ASSERT(Point::dimensions == 2); typedef typename Topology::point_difference_type point_difference_type; template < typename Graph > explicit grid_force_pairs( const Topology& topology, PositionMap position, const Graph& g) : topology(topology), position(position) { two_k = 2. * this->topology.volume(this->topology.extent()) / std::sqrt((double)num_vertices(g)); } template < typename Graph, typename ApplyForce > void operator()(const Graph& g, ApplyForce apply_force) { typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; typedef std::list< vertex_descriptor > bucket_t; typedef std::vector< bucket_t > buckets_t; std::size_t columns = std::size_t(topology.extent()[0] / two_k + 1.); std::size_t rows = std::size_t(topology.extent()[1] / two_k + 1.); buckets_t buckets(rows * columns); vertex_iterator v, v_end; for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) { std::size_t column = std::size_t( (get(position, *v)[0] + topology.extent()[0] / 2) / two_k); std::size_t row = std::size_t( (get(position, *v)[1] + topology.extent()[1] / 2) / two_k); if (column >= columns) column = columns - 1; if (row >= rows) row = rows - 1; buckets[row * columns + column].push_back(*v); } for (std::size_t row = 0; row < rows; ++row) for (std::size_t column = 0; column < columns; ++column) { bucket_t& bucket = buckets[row * columns + column]; typedef typename bucket_t::iterator bucket_iterator; for (bucket_iterator u = bucket.begin(); u != bucket.end(); ++u) { // Repulse vertices in this bucket bucket_iterator v = u; for (++v; v != bucket.end(); ++v) { apply_force(*u, *v); apply_force(*v, *u); } std::size_t adj_start_row = row == 0 ? 0 : row - 1; std::size_t adj_end_row = row == rows - 1 ? row : row + 1; std::size_t adj_start_column = column == 0 ? 0 : column - 1; std::size_t adj_end_column = column == columns - 1 ? column : column + 1; for (std::size_t other_row = adj_start_row; other_row <= adj_end_row; ++other_row) for (std::size_t other_column = adj_start_column; other_column <= adj_end_column; ++other_column) if (other_row != row || other_column != column) { // Repulse vertices in this bucket bucket_t& other_bucket = buckets[other_row * columns + other_column]; for (v = other_bucket.begin(); v != other_bucket.end(); ++v) { double dist = topology.distance( get(position, *u), get(position, *v)); if (dist < two_k) apply_force(*u, *v); } } } } } private: const Topology& topology; PositionMap position; double two_k; }; template < typename PositionMap, typename Topology, typename Graph > inline grid_force_pairs< Topology, PositionMap > make_grid_force_pairs( const Topology& topology, const PositionMap& position, const Graph& g) { return grid_force_pairs< Topology, PositionMap >(topology, position, g); } template < typename Graph, typename PositionMap, typename Topology > void scale_graph(const Graph& g, PositionMap position, const Topology& topology, typename Topology::point_type upper_left, typename Topology::point_type lower_right) { if (num_vertices(g) == 0) return; typedef typename Topology::point_type Point; typedef typename Topology::point_difference_type point_difference_type; // Find min/max ranges Point min_point = get(position, *vertices(g).first), max_point = min_point; BGL_FORALL_VERTICES_T(v, g, Graph) { min_point = topology.pointwise_min(min_point, get(position, v)); max_point = topology.pointwise_max(max_point, get(position, v)); } Point old_origin = topology.move_position_toward(min_point, 0.5, max_point); Point new_origin = topology.move_position_toward(upper_left, 0.5, lower_right); point_difference_type old_size = topology.difference(max_point, min_point); point_difference_type new_size = topology.difference(lower_right, upper_left); // Scale to bounding box provided BGL_FORALL_VERTICES_T(v, g, Graph) { point_difference_type relative_loc = topology.difference(get(position, v), old_origin); relative_loc = (relative_loc / old_size) * new_size; put(position, v, topology.adjust(new_origin, relative_loc)); } } namespace detail { template < typename Topology, typename PropMap, typename Vertex > void maybe_jitter_point(const Topology& topology, const PropMap& pm, Vertex v, const typename Topology::point_type& p2) { double too_close = topology.norm(topology.extent()) / 10000.; if (topology.distance(get(pm, v), p2) < too_close) { put(pm, v, topology.move_position_toward( get(pm, v), 1. / 200, topology.random_point())); } } template < typename Topology, typename PositionMap, typename DisplacementMap, typename RepulsiveForce, typename Graph > struct fr_apply_force { typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; typedef typename Topology::point_type Point; typedef typename Topology::point_difference_type PointDiff; fr_apply_force(const Topology& topology, const PositionMap& position, const DisplacementMap& displacement, RepulsiveForce repulsive_force, double k, const Graph& g) : topology(topology) , position(position) , displacement(displacement) , repulsive_force(repulsive_force) , k(k) , g(g) { } void operator()(vertex_descriptor u, vertex_descriptor v) { if (u != v) { // When the vertices land on top of each other, move the // first vertex away from the boundaries. maybe_jitter_point(topology, position, u, get(position, v)); double dist = topology.distance(get(position, u), get(position, v)); typename Topology::point_difference_type dispv = get(displacement, v); if (dist == 0.) { for (std::size_t i = 0; i < Point::dimensions; ++i) { dispv[i] += 0.01; } } else { double fr = repulsive_force(u, v, k, dist, g); dispv += (fr / dist) * topology.difference( get(position, v), get(position, u)); } put(displacement, v, dispv); } } private: const Topology& topology; PositionMap position; DisplacementMap displacement; RepulsiveForce repulsive_force; double k; const Graph& g; }; } // end namespace detail template < typename Topology, typename Graph, typename PositionMap, typename AttractiveForce, typename RepulsiveForce, typename ForcePairs, typename Cooling, typename DisplacementMap > void fruchterman_reingold_force_directed_layout(const Graph& g, PositionMap position, const Topology& topology, AttractiveForce attractive_force, RepulsiveForce repulsive_force, ForcePairs force_pairs, Cooling cool, DisplacementMap displacement) { typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; typedef typename graph_traits< Graph >::edge_iterator edge_iterator; double volume = topology.volume(topology.extent()); // assume positions are initialized randomly double k = pow(volume / num_vertices(g), 1. / (double)(Topology::point_difference_type::dimensions)); detail::fr_apply_force< Topology, PositionMap, DisplacementMap, RepulsiveForce, Graph > apply_force(topology, position, displacement, repulsive_force, k, g); do { // Calculate repulsive forces vertex_iterator v, v_end; for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) put(displacement, *v, typename Topology::point_difference_type()); force_pairs(g, apply_force); // Calculate attractive forces edge_iterator e, e_end; for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) { vertex_descriptor v = source(*e, g); vertex_descriptor u = target(*e, g); // When the vertices land on top of each other, move the // first vertex away from the boundaries. ::boost::detail::maybe_jitter_point( topology, position, u, get(position, v)); typename Topology::point_difference_type delta = topology.difference(get(position, v), get(position, u)); double dist = topology.distance(get(position, u), get(position, v)); double fa = attractive_force(*e, k, dist, g); put(displacement, v, get(displacement, v) - (fa / dist) * delta); put(displacement, u, get(displacement, u) + (fa / dist) * delta); } if (double temp = cool()) { // Update positions BGL_FORALL_VERTICES_T(v, g, Graph) { BOOST_USING_STD_MIN(); BOOST_USING_STD_MAX(); double disp_size = topology.norm(get(displacement, v)); put(position, v, topology.adjust(get(position, v), get(displacement, v) * (min BOOST_PREVENT_MACRO_SUBSTITUTION( disp_size, temp) / disp_size))); put(position, v, topology.bound(get(position, v))); } } else { break; } } while (true); } namespace detail { template < typename DisplacementMap > struct fr_force_directed_layout { template < typename Topology, typename Graph, typename PositionMap, typename AttractiveForce, typename RepulsiveForce, typename ForcePairs, typename Cooling, typename Param, typename Tag, typename Rest > static void run(const Graph& g, PositionMap position, const Topology& topology, AttractiveForce attractive_force, RepulsiveForce repulsive_force, ForcePairs force_pairs, Cooling cool, DisplacementMap displacement, const bgl_named_params< Param, Tag, Rest >&) { fruchterman_reingold_force_directed_layout(g, position, topology, attractive_force, repulsive_force, force_pairs, cool, displacement); } }; template <> struct fr_force_directed_layout< param_not_found > { template < typename Topology, typename Graph, typename PositionMap, typename AttractiveForce, typename RepulsiveForce, typename ForcePairs, typename Cooling, typename Param, typename Tag, typename Rest > static void run(const Graph& g, PositionMap position, const Topology& topology, AttractiveForce attractive_force, RepulsiveForce repulsive_force, ForcePairs force_pairs, Cooling cool, param_not_found, const bgl_named_params< Param, Tag, Rest >& params) { typedef typename Topology::point_difference_type PointDiff; std::vector< PointDiff > displacements(num_vertices(g)); fruchterman_reingold_force_directed_layout(g, position, topology, attractive_force, repulsive_force, force_pairs, cool, make_iterator_property_map(displacements.begin(), choose_const_pmap( get_param(params, vertex_index), g, vertex_index), PointDiff())); } }; } // end namespace detail template < typename Topology, typename Graph, typename PositionMap, typename Param, typename Tag, typename Rest > void fruchterman_reingold_force_directed_layout(const Graph& g, PositionMap position, const Topology& topology, const bgl_named_params< Param, Tag, Rest >& params) { typedef typename get_param_type< vertex_displacement_t, bgl_named_params< Param, Tag, Rest > >::type D; detail::fr_force_directed_layout< D >::run(g, position, topology, choose_param(get_param(params, attractive_force_t()), square_distance_attractive_force()), choose_param(get_param(params, repulsive_force_t()), square_distance_repulsive_force()), choose_param(get_param(params, force_pairs_t()), make_grid_force_pairs(topology, position, g)), choose_param( get_param(params, cooling_t()), linear_cooling< double >(100)), get_param(params, vertex_displacement_t()), params); } template < typename Topology, typename Graph, typename PositionMap > void fruchterman_reingold_force_directed_layout( const Graph& g, PositionMap position, const Topology& topology) { fruchterman_reingold_force_directed_layout(g, position, topology, attractive_force(square_distance_attractive_force())); } } // end namespace boost #include BOOST_GRAPH_MPI_INCLUDE(< boost / graph / distributed / fruchterman_reingold.hpp >) #endif // BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP PK L�[V�\� � circle_layout.hppnu �[��� // Copyright 2004 The Trustees of Indiana University. // 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) // Authors: Douglas Gregor // Andrew Lumsdaine #ifndef BOOST_GRAPH_CIRCLE_LAYOUT_HPP #define BOOST_GRAPH_CIRCLE_LAYOUT_HPP #include <boost/config/no_tr1/cmath.hpp> #include <boost/math/constants/constants.hpp> #include <utility> #include <boost/graph/graph_traits.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/topology.hpp> #include <boost/static_assert.hpp> namespace boost { /** * \brief Layout the graph with the vertices at the points of a regular * n-polygon. * * The distance from the center of the polygon to each point is * determined by the @p radius parameter. The @p position parameter * must be an Lvalue Property Map whose value type is a class type * containing @c x and @c y members that will be set to the @c x and * @c y coordinates. */ template < typename VertexListGraph, typename PositionMap, typename Radius > void circle_graph_layout( const VertexListGraph& g, PositionMap position, Radius radius) { BOOST_STATIC_ASSERT( property_traits< PositionMap >::value_type::dimensions >= 2); const double pi = boost::math::constants::pi< double >(); #ifndef BOOST_NO_STDC_NAMESPACE using std::cos; using std::sin; #endif // BOOST_NO_STDC_NAMESPACE typedef typename graph_traits< VertexListGraph >::vertices_size_type vertices_size_type; vertices_size_type n = num_vertices(g); vertices_size_type i = 0; double two_pi_over_n = 2. * pi / n; BGL_FORALL_VERTICES_T(v, g, VertexListGraph) { position[v][0] = radius * cos(i * two_pi_over_n); position[v][1] = radius * sin(i * two_pi_over_n); ++i; } } } // end namespace boost #endif // BOOST_GRAPH_CIRCLE_LAYOUT_HPP PK L�[�`+w�b �b undirected_graph.hppnu �[��� // (C) Copyright 2007-2009 Andrew Sutton // // Use, modification and distribution are subject to the // Boost Software License, Version 1.0 (See accompanying file // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_GRAPH_UNDIRECTED_GRAPH_HPP #define BOOST_GRAPH_UNDIRECTED_GRAPH_HPP #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> #include <boost/pending/property.hpp> #include <boost/property_map/transform_value_property_map.hpp> #include <boost/type_traits.hpp> #include <boost/mpl/if.hpp> namespace boost { struct undirected_graph_tag { }; /** * The undirected_graph class template is a simplified version of the BGL * adjacency list. This class is provided for ease of use, but may not * perform as well as custom-defined adjacency list classes. Instances of * this template model the VertexIndexGraph, and EdgeIndexGraph concepts. The * graph is also fully mutable, supporting both insertions and removals of * vertices and edges. * * @note Special care must be taken when removing vertices or edges since * those operations can invalidate the numbering of vertices. */ template < typename VertexProp = no_property, typename EdgeProp = no_property, typename GraphProp = no_property > class undirected_graph { public: typedef GraphProp graph_property_type; typedef VertexProp vertex_property_type; typedef EdgeProp edge_property_type; typedef typename lookup_one_property< GraphProp, graph_bundle_t >::type graph_bundled; typedef typename lookup_one_property< VertexProp, vertex_bundle_t >::type vertex_bundled; typedef typename lookup_one_property< EdgeProp, edge_bundle_t >::type edge_bundled; public: // Embed indices into the vertex type. typedef property< vertex_index_t, unsigned, vertex_property_type > internal_vertex_property; typedef property< edge_index_t, unsigned, edge_property_type > internal_edge_property; public: typedef adjacency_list< listS, listS, undirectedS, internal_vertex_property, internal_edge_property, GraphProp, listS > graph_type; private: // storage selectors typedef typename graph_type::vertex_list_selector vertex_list_selector; typedef typename graph_type::edge_list_selector edge_list_selector; typedef typename graph_type::out_edge_list_selector out_edge_list_selector; typedef typename graph_type::directed_selector directed_selector; public: // more commonly used graph types typedef typename graph_type::stored_vertex stored_vertex; typedef typename graph_type::vertices_size_type vertices_size_type; typedef typename graph_type::edges_size_type edges_size_type; typedef typename graph_type::degree_size_type degree_size_type; typedef typename graph_type::vertex_descriptor vertex_descriptor; typedef typename graph_type::edge_descriptor edge_descriptor; // iterator types typedef typename graph_type::vertex_iterator vertex_iterator; typedef typename graph_type::edge_iterator edge_iterator; typedef typename graph_type::out_edge_iterator out_edge_iterator; typedef typename graph_type::in_edge_iterator in_edge_iterator; typedef typename graph_type::adjacency_iterator adjacency_iterator; // miscellaneous types typedef undirected_graph_tag graph_tag; typedef typename graph_type::directed_category directed_category; typedef typename graph_type::edge_parallel_category edge_parallel_category; typedef typename graph_type::traversal_category traversal_category; typedef std::size_t vertex_index_type; typedef std::size_t edge_index_type; inline undirected_graph(GraphProp const& p = GraphProp()) : m_graph(p) , m_num_vertices(0) , m_num_edges(0) , m_max_vertex_index(0) , m_max_edge_index(0) { } inline undirected_graph(undirected_graph const& x) : m_graph(x.m_graph) , m_num_vertices(x.m_num_vertices) , m_num_edges(x.m_num_edges) , m_max_vertex_index(x.m_max_vertex_index) , m_max_edge_index(x.m_max_edge_index) { } inline undirected_graph( vertices_size_type n, GraphProp const& p = GraphProp()) : m_graph(n, p) , m_num_vertices(n) , m_num_edges(0) , m_max_vertex_index(n) , m_max_edge_index(0) { renumber_vertex_indices(); } template < typename EdgeIterator > inline undirected_graph(EdgeIterator f, EdgeIterator l, vertices_size_type n, edges_size_type m = 0, GraphProp const& p = GraphProp()) : m_graph(f, l, n, m, p) , m_num_vertices(n) , m_num_edges(0) , m_max_vertex_index(n) , m_max_edge_index(0) { // Unfortunately, we have to renumber to ensure correct indexing. renumber_indices(); // Can't always guarantee that the number of edges is actually // m if distance(f, l) != m (or is undefined). m_num_edges = m_max_edge_index = boost::num_edges(m_graph); } undirected_graph& operator=(undirected_graph const& g) { if (&g != this) { m_graph = g.m_graph; m_num_vertices = g.m_num_vertices; m_num_edges = g.m_num_edges; m_max_vertex_index = g.m_max_vertex_index; } return *this; } // The impl_() methods are not part of the public interface. graph_type& impl() { return m_graph; } graph_type const& impl() const { return m_graph; } // The following methods are not part of the public interface vertices_size_type num_vertices() const { return m_num_vertices; } private: // This helper function manages the attribution of vertex indices. vertex_descriptor make_index(vertex_descriptor v) { boost::put(vertex_index, m_graph, v, m_max_vertex_index); m_num_vertices++; m_max_vertex_index++; return v; } public: vertex_descriptor add_vertex() { return make_index(boost::add_vertex(m_graph)); } vertex_descriptor add_vertex(vertex_property_type const& p) { return make_index( boost::add_vertex(internal_vertex_property(0u, p), m_graph)); } void clear_vertex(vertex_descriptor v) { std::pair< out_edge_iterator, out_edge_iterator > p = boost::out_edges(v, m_graph); m_num_edges -= std::distance(p.first, p.second); boost::clear_vertex(v, m_graph); } void remove_vertex(vertex_descriptor v) { boost::remove_vertex(v, m_graph); --m_num_vertices; } edges_size_type num_edges() const { return m_num_edges; } private: // A helper fucntion for managing edge index attributes. std::pair< edge_descriptor, bool > const& make_index( std::pair< edge_descriptor, bool > const& x) { if (x.second) { boost::put(edge_index, m_graph, x.first, m_max_edge_index); ++m_num_edges; ++m_max_edge_index; } return x; } public: std::pair< edge_descriptor, bool > add_edge( vertex_descriptor u, vertex_descriptor v) { return make_index(boost::add_edge(u, v, m_graph)); } std::pair< edge_descriptor, bool > add_edge( vertex_descriptor u, vertex_descriptor v, edge_property_type const& p) { return make_index( boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); } void remove_edge(vertex_descriptor u, vertex_descriptor v) { // find all edges, (u, v) std::vector< edge_descriptor > edges; out_edge_iterator i, i_end; for (boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) { if (boost::target(*i, m_graph) == v) { edges.push_back(*i); } } // remove all edges, (u, v) typename std::vector< edge_descriptor >::iterator j = edges.begin(), j_end = edges.end(); for (; j != j_end; ++j) { remove_edge(*j); } } void remove_edge(edge_iterator i) { remove_edge(*i); } void remove_edge(edge_descriptor e) { boost::remove_edge(e, m_graph); --m_num_edges; } vertex_index_type max_vertex_index() const { return m_max_vertex_index; } void renumber_vertex_indices() { vertex_iterator i, i_end; boost::tie(i, i_end) = vertices(m_graph); m_max_vertex_index = renumber_vertex_indices(i, i_end, 0); } void remove_vertex_and_renumber_indices(vertex_iterator i) { vertex_iterator j = next(i), end = vertices(m_graph).second; vertex_index_type n = get(vertex_index, m_graph, *i); // remove the offending vertex and renumber everything after remove_vertex(*i); m_max_vertex_index = renumber_vertex_indices(j, end, n); } edge_index_type max_edge_index() const { return m_max_edge_index; } void renumber_edge_indices() { edge_iterator i, end; boost::tie(i, end) = edges(m_graph); m_max_edge_index = renumber_edge_indices(i, end, 0); } void remove_edge_and_renumber_indices(edge_iterator i) { edge_iterator j = next(i), end = edges(m_graph.second); edge_index_type n = get(edge_index, m_graph, *i); // remove the edge and renumber everything after it remove_edge(*i); m_max_edge_index = renumber_edge_indices(j, end, n); } void renumber_indices() { renumber_vertex_indices(); renumber_edge_indices(); } // bundled property support #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; } vertex_bundled const& operator[](vertex_descriptor v) const { return m_graph[v]; } edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; } edge_bundled const& operator[](edge_descriptor e) const { return m_graph[e]; } graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } graph_bundled const& operator[](graph_bundle_t) const { return get_property(*this); } #endif // Graph concepts static vertex_descriptor null_vertex() { return graph_type::null_vertex(); } void clear() { m_graph.clear(); m_num_vertices = m_max_vertex_index = 0; m_num_edges = m_max_edge_index = 0; } void swap(undirected_graph& g) { m_graph.swap(g.m_graph); std::swap(m_num_vertices, g.m_num_vertices); std::swap(m_max_vertex_index, g.m_max_vertex_index); std::swap(m_num_edges, g.m_num_edges); std::swap(m_max_edge_index, g.m_max_edge_index); } private: vertices_size_type renumber_vertex_indices( vertex_iterator i, vertex_iterator end, vertices_size_type n) { typedef typename property_map< graph_type, vertex_index_t >::type IndexMap; IndexMap indices = get(vertex_index, m_graph); for (; i != end; ++i) { indices[*i] = n++; } return n; } edges_size_type renumber_edge_indices( edge_iterator i, edge_iterator end, edges_size_type n) { typedef typename property_map< graph_type, edge_index_t >::type IndexMap; IndexMap indices = get(edge_index, m_graph); for (; i != end; ++i) { indices[*i] = n++; } return n; } graph_type m_graph; vertices_size_type m_num_vertices; edges_size_type m_num_edges; vertex_index_type m_max_vertex_index; edge_index_type m_max_edge_index; }; #define UNDIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP #define UNDIRECTED_GRAPH undirected_graph< VP, EP, GP > // IncidenceGraph concepts template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::vertex_descriptor source( typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g) { return source(e, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::vertex_descriptor target( typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g) { return target(e, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::degree_size_type out_degree( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return out_degree(v, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator, typename UNDIRECTED_GRAPH::out_edge_iterator > out_edges( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return out_edges(v, g.impl()); } // BidirectionalGraph concepts template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::degree_size_type in_degree( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return in_degree(v, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::in_edge_iterator, typename UNDIRECTED_GRAPH::in_edge_iterator > in_edges( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return in_edges(v, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator, typename UNDIRECTED_GRAPH::out_edge_iterator > incident_edges( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return out_edges(v, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::degree_size_type degree( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return degree(v, g.impl()); } // AdjacencyGraph concepts template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::adjacency_iterator, typename UNDIRECTED_GRAPH::adjacency_iterator > adjacent_vertices( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return adjacent_vertices(v, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > typename UNDIRECTED_GRAPH::vertex_descriptor vertex( typename UNDIRECTED_GRAPH::vertices_size_type n, UNDIRECTED_GRAPH const& g) { return vertex(n, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > edge( typename UNDIRECTED_GRAPH::vertex_descriptor u, typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return edge(u, v, g.impl()); } // VertexListGraph concepts template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::vertices_size_type num_vertices( UNDIRECTED_GRAPH const& g) { return g.num_vertices(); } template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::vertex_iterator, typename UNDIRECTED_GRAPH::vertex_iterator > vertices(UNDIRECTED_GRAPH const& g) { return vertices(g.impl()); } // EdgeListGraph concepts template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::edges_size_type num_edges( UNDIRECTED_GRAPH const& g) { return g.num_edges(); } template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::edge_iterator, typename UNDIRECTED_GRAPH::edge_iterator > edges(UNDIRECTED_GRAPH const& g) { return edges(g.impl()); } // MutableGraph concepts template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex( UNDIRECTED_GRAPH& g) { return g.add_vertex(); } template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex( typename UNDIRECTED_GRAPH::vertex_property_type const& p, UNDIRECTED_GRAPH& g) { return g.add_vertex(p); } template < UNDIRECTED_GRAPH_PARAMS > inline void clear_vertex( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) { return g.clear_vertex(v); } template < UNDIRECTED_GRAPH_PARAMS > inline void remove_vertex( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) { return g.remove_vertex(v); } template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge( typename UNDIRECTED_GRAPH::vertex_descriptor u, typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) { return g.add_edge(u, v); } template < UNDIRECTED_GRAPH_PARAMS > inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge( typename UNDIRECTED_GRAPH::vertex_descriptor u, typename UNDIRECTED_GRAPH::vertex_descriptor v, typename UNDIRECTED_GRAPH::edge_property_type const& p, UNDIRECTED_GRAPH& g) { return g.add_edge(u, v, p); } template < UNDIRECTED_GRAPH_PARAMS > inline void remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u, typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) { return g.remove_edge(u, v); } template < UNDIRECTED_GRAPH_PARAMS > inline void remove_edge( typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH& g) { return g.remove_edge(e); } template < UNDIRECTED_GRAPH_PARAMS > inline void remove_edge( typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g) { return g.remove_edge(i); } template < UNDIRECTED_GRAPH_PARAMS, class Predicate > inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g) { return remove_edge_if(pred, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS, class Predicate > inline void remove_incident_edge_if( typename UNDIRECTED_GRAPH::vertex_descriptor v, Predicate pred, UNDIRECTED_GRAPH& g) { return remove_out_edge_if(v, pred, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS, class Predicate > inline void remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v, Predicate pred, UNDIRECTED_GRAPH& g) { return remove_out_edge_if(v, pred, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS, class Predicate > inline void remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v, Predicate pred, UNDIRECTED_GRAPH& g) { return remove_in_edge_if(v, pred, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS, typename Property > struct property_map< UNDIRECTED_GRAPH, Property > : property_map< typename UNDIRECTED_GRAPH::graph_type, Property > { }; template < UNDIRECTED_GRAPH_PARAMS > struct property_map< UNDIRECTED_GRAPH, vertex_all_t > { typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename UNDIRECTED_GRAPH::graph_type, vertex_all_t >::const_type > const_type; typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename UNDIRECTED_GRAPH::graph_type, vertex_all_t >::type > type; }; template < UNDIRECTED_GRAPH_PARAMS > struct property_map< UNDIRECTED_GRAPH, edge_all_t > { typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename UNDIRECTED_GRAPH::graph_type, edge_all_t >::const_type > const_type; typedef transform_value_property_map< detail::remove_first_property, typename property_map< typename UNDIRECTED_GRAPH::graph_type, edge_all_t >::type > type; }; // PropertyGraph concepts template < UNDIRECTED_GRAPH_PARAMS, typename Property > inline typename property_map< UNDIRECTED_GRAPH, Property >::type get( Property p, UNDIRECTED_GRAPH& g) { return get(p, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS, typename Property > inline typename property_map< UNDIRECTED_GRAPH, Property >::const_type get( Property p, UNDIRECTED_GRAPH const& g) { return get(p, g.impl()); } template < UNDIRECTED_GRAPH_PARAMS > inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type get( vertex_all_t, UNDIRECTED_GRAPH& g) { return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type( detail::remove_first_property(), get(vertex_all, g.impl())); } template < UNDIRECTED_GRAPH_PARAMS > inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type get( vertex_all_t, UNDIRECTED_GRAPH const& g) { return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type( detail::remove_first_property(), get(vertex_all, g.impl())); } template < UNDIRECTED_GRAPH_PARAMS > inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type get( edge_all_t, UNDIRECTED_GRAPH& g) { return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type( detail::remove_first_property(), get(edge_all, g.impl())); } template < UNDIRECTED_GRAPH_PARAMS > inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type get( edge_all_t, UNDIRECTED_GRAPH const& g) { return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type( detail::remove_first_property(), get(edge_all, g.impl())); } template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key > inline typename property_traits< typename property_map< typename UNDIRECTED_GRAPH::graph_type, Property >::const_type >::value_type get(Property p, UNDIRECTED_GRAPH const& g, Key const& k) { return get(p, g.impl(), k); } template < UNDIRECTED_GRAPH_PARAMS, typename Key > inline typename property_traits< typename property_map< typename UNDIRECTED_GRAPH::graph_type, vertex_all_t >::const_type >::value_type get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k) { return get(vertex_all, g.impl(), k).m_base; } template < UNDIRECTED_GRAPH_PARAMS, typename Key > inline typename property_traits< typename property_map< typename UNDIRECTED_GRAPH::graph_type, edge_all_t >::const_type >::value_type get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k) { return get(edge_all, g.impl(), k).m_base; } template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value > inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) { put(p, g.impl(), k, v); } template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) { put(vertex_all, g.impl(), k, typename UNDIRECTED_GRAPH::internal_vertex_property( get(vertex_index, g.impl(), k), v)); } template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) { put(edge_all, g.impl(), k, typename UNDIRECTED_GRAPH::internal_vertex_property( get(edge_index, g.impl(), k), v)); } template < UNDIRECTED_GRAPH_PARAMS, class Property > inline typename graph_property< UNDIRECTED_GRAPH, Property >::type& get_property(UNDIRECTED_GRAPH& g, Property p) { return get_property(g.impl(), p); } template < UNDIRECTED_GRAPH_PARAMS, class Property > inline typename graph_property< UNDIRECTED_GRAPH, Property >::type const& get_property(UNDIRECTED_GRAPH const& g, Property p) { return get_property(g.impl(), p); } template < UNDIRECTED_GRAPH_PARAMS, class Property, class Value > inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v) { return set_property(g.impl(), p, v); } // Indexed Vertex graph template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::vertex_index_type get_vertex_index( typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) { return get(vertex_index, g, v); } template < UNDIRECTED_GRAPH_PARAMS > typename UNDIRECTED_GRAPH::vertex_index_type max_vertex_index( UNDIRECTED_GRAPH const& g) { return g.max_vertex_index(); } template < UNDIRECTED_GRAPH_PARAMS > inline void renumber_vertex_indices(UNDIRECTED_GRAPH& g) { g.renumber_vertex_indices(); } template < UNDIRECTED_GRAPH_PARAMS > inline void remove_vertex_and_renumber_indices( typename UNDIRECTED_GRAPH::vertex_iterator i, UNDIRECTED_GRAPH& g) { g.remove_vertex_and_renumber_indices(i); } // Edge index management template < UNDIRECTED_GRAPH_PARAMS > inline typename UNDIRECTED_GRAPH::edge_index_type get_edge_index( typename UNDIRECTED_GRAPH::edge_descriptor v, UNDIRECTED_GRAPH const& g) { return get(edge_index, g, v); } template < UNDIRECTED_GRAPH_PARAMS > typename UNDIRECTED_GRAPH::edge_index_type max_edge_index( UNDIRECTED_GRAPH const& g) { return g.max_edge_index(); } template < UNDIRECTED_GRAPH_PARAMS > inline void renumber_edge_indices(UNDIRECTED_GRAPH& g) { g.renumber_edge_indices(); } template < UNDIRECTED_GRAPH_PARAMS > inline void remove_edge_and_renumber_indices( typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g) { g.remove_edge_and_renumber_indices(i); } // Index management template < UNDIRECTED_GRAPH_PARAMS > inline void renumber_indices(UNDIRECTED_GRAPH& g) { g.renumber_indices(); } // Mutability Traits template < UNDIRECTED_GRAPH_PARAMS > struct graph_mutability_traits< UNDIRECTED_GRAPH > { typedef mutable_property_graph_tag category; }; #undef UNDIRECTED_GRAPH_PARAMS #undef UNDIRECTED_GRAPH } /* namespace boost */ #endif PK L�[d���&