x
Yes
No
Do you want to visit DriveHQ English website?
Inicio
Características
Precios
Prueba gratuita
Software cliente
Acerca de nosotros
Servidor de archivos
|
Solución de copias de seguridad
|
Servidor FTP
|
Servidor de correo electrónico
|
Alojamiento web
|
Software cliente
Servidor de archivos
Solución de copia de seguridad
Servidor FTP
Servidor de correo electrónico
Alojamiento web
Software cliente
filtered_graph.hpp - Hosted on DriveHQ Cloud IT Platform
Arriba
Subir
Descargar
Compartir
Publicar
Nueva carpeta
Nuevo archivo
Copiar
Cortar
Eliminar
Pegar
Clasificación
Actualizar
Ruta de la carpeta: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\graph\filtered_graph.hpp
Girar
Efecto
Propiedad
Historial
//======================================================================= // 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_FILTERED_GRAPH_HPP #define BOOST_FILTERED_GRAPH_HPP #include
#include
#include
#include
namespace boost { //========================================================================= // Some predicate classes. struct keep_all { template
bool operator()(const T&) const { return true; } }; // Keep residual edges (used in maximum-flow algorithms). template
struct is_residual_edge { is_residual_edge() { } is_residual_edge(ResidualCapacityEdgeMap rcap) : m_rcap(rcap) { } template
bool operator()(const Edge& e) const { return 0 < get(m_rcap, e); } ResidualCapacityEdgeMap m_rcap; }; template
struct is_in_subset { is_in_subset() : m_s(0) { } is_in_subset(const Set& s) : m_s(&s) { } template
bool operator()(const Elt& x) const { return set_contains(*m_s, x); } const Set* m_s; }; template
struct is_not_in_subset { is_not_in_subset() : m_s(0) { } is_not_in_subset(const Set& s) : m_s(&s) { } template
bool operator()(const Elt& x) const { return !set_contains(*m_s, x); } const Set* m_s; }; namespace detail { template
struct out_edge_predicate { out_edge_predicate() { } out_edge_predicate(EdgePredicate ep, VertexPredicate vp, const Graph& g) : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } template
bool operator()(const Edge& e) const { return m_edge_pred(e) && m_vertex_pred(target(e, *m_g)); } EdgePredicate m_edge_pred; VertexPredicate m_vertex_pred; const Graph* m_g; }; template
struct in_edge_predicate { in_edge_predicate() { } in_edge_predicate(EdgePredicate ep, VertexPredicate vp, const Graph& g) : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } template
bool operator()(const Edge& e) const { return m_edge_pred(e) && m_vertex_pred(source(e, *m_g)); } EdgePredicate m_edge_pred; VertexPredicate m_vertex_pred; const Graph* m_g; }; template
struct edge_predicate { edge_predicate() { } edge_predicate(EdgePredicate ep, VertexPredicate vp, const Graph& g) : m_edge_pred(ep), m_vertex_pred(vp), m_g(&g) { } template
bool operator()(const Edge& e) const { return m_edge_pred(e) && m_vertex_pred(source(e, *m_g)) && m_vertex_pred(target(e, *m_g)); } EdgePredicate m_edge_pred; VertexPredicate m_vertex_pred; const Graph* m_g; }; } // namespace detail //=========================================================================== // Filtered Graph struct filtered_graph_tag { }; // This base class is a stupid hack to change overload resolution // rules for the source and target functions so that they are a // worse match than the source and target functions defined for // pairs in graph_traits.hpp. I feel dirty. -JGS template
struct filtered_graph_base { typedef graph_traits
Traits; typedef typename Traits::vertex_descriptor vertex_descriptor; typedef typename Traits::edge_descriptor edge_descriptor; filtered_graph_base(const G& g) : m_g(g) { } //protected: const G& m_g; }; template
class filtered_graph : public filtered_graph_base
{ typedef filtered_graph_base
Base; typedef graph_traits
Traits; typedef filtered_graph self; public: typedef Graph graph_type; typedef detail::out_edge_predicate
OutEdgePred; typedef detail::in_edge_predicate
InEdgePred; typedef detail::edge_predicate
EdgePred; // Constructors filtered_graph(const Graph& g, EdgePredicate ep) : Base(g), m_edge_pred(ep) { } filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp) : Base(g), m_edge_pred(ep), m_vertex_pred(vp) { } // Graph requirements typedef typename Traits::vertex_descriptor vertex_descriptor; typedef typename Traits::edge_descriptor edge_descriptor; typedef typename Traits::directed_category directed_category; typedef typename Traits::edge_parallel_category edge_parallel_category; typedef typename Traits::traversal_category traversal_category; // IncidenceGraph requirements typedef filter_iterator< OutEdgePred, typename Traits::out_edge_iterator > out_edge_iterator; typedef typename Traits::degree_size_type degree_size_type; // AdjacencyGraph requirements typedef typename adjacency_iterator_generator
::type adjacency_iterator; // BidirectionalGraph requirements typedef filter_iterator< InEdgePred, typename Traits::in_edge_iterator > in_edge_iterator; // VertexListGraph requirements typedef filter_iterator< VertexPredicate, typename Traits::vertex_iterator > vertex_iterator; typedef typename Traits::vertices_size_type vertices_size_type; // EdgeListGraph requirements typedef filter_iterator< EdgePred, typename Traits::edge_iterator > edge_iterator; typedef typename Traits::edges_size_type edges_size_type; typedef typename ::boost::edge_property_type
::type edge_property_type; typedef typename ::boost::vertex_property_type
::type vertex_property_type; typedef filtered_graph_tag graph_tag; #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES // Bundled properties support template
typename graph::detail::bundled_result
::type& operator[](Descriptor x) { return const_cast
(this->m_g)[x]; } template
typename graph::detail::bundled_result
::type const& operator[](Descriptor x) const { return this->m_g[x]; } #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES static vertex_descriptor null_vertex() { return Graph::null_vertex(); } //private: EdgePredicate m_edge_pred; VertexPredicate m_vertex_pred; }; #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES template
struct vertex_bundle_type
> : vertex_bundle_type
{ }; template
struct edge_bundle_type
> : edge_bundle_type
{ }; #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES //=========================================================================== // Non-member functions for the Filtered Edge Graph // Helper functions template
inline filtered_graph
make_filtered_graph(Graph& g, EdgePredicate ep) { return filtered_graph
(g, ep); } template
inline filtered_graph
make_filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp) { return filtered_graph
(g, ep, vp); } template
inline filtered_graph
make_filtered_graph(const Graph& g, EdgePredicate ep) { return filtered_graph
(g, ep); } template
inline filtered_graph
make_filtered_graph(const Graph& g, EdgePredicate ep, VertexPredicate vp) { return filtered_graph
(g, ep, vp); } template
std::pair
::vertex_iterator, typename filtered_graph
::vertex_iterator> vertices(const filtered_graph
& g) { typedef filtered_graph
Graph; typename graph_traits
::vertex_iterator f, l; tie(f, l) = vertices(g.m_g); typedef typename Graph::vertex_iterator iter; return std::make_pair(iter(g.m_vertex_pred, f, l), iter(g.m_vertex_pred, l, l)); } template
std::pair
::edge_iterator, typename filtered_graph
::edge_iterator> edges(const filtered_graph
& g) { typedef filtered_graph
Graph; typename Graph::EdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); typename graph_traits
::edge_iterator f, l; tie(f, l) = edges(g.m_g); typedef typename Graph::edge_iterator iter; return std::make_pair(iter(pred, f, l), iter(pred, l, l)); } // An alternative for num_vertices() and num_edges() would be to // count the number in the filtered graph. This is problematic // because of the interaction with the vertex indices... they would // no longer go from 0 to num_vertices(), which would cause trouble // for algorithms allocating property storage in an array. We could // try to create a mapping to new recalibrated indices, but I don't // see an efficient way to do this. // // However, the current solution is still unsatisfactory because // the following semantic constraints no longer hold: // tie(vi, viend) = vertices(g); // assert(std::distance(vi, viend) == num_vertices(g)); template
typename filtered_graph
::vertices_size_type num_vertices(const filtered_graph
& g) { return num_vertices(g.m_g); } template
typename filtered_graph
::edges_size_type num_edges(const filtered_graph
& g) { return num_edges(g.m_g); } template
typename filtered_graph_base
::vertex_descriptor source(typename filtered_graph_base
::edge_descriptor e, const filtered_graph_base
& g) { return source(e, g.m_g); } template
typename filtered_graph_base
::vertex_descriptor target(typename filtered_graph_base
::edge_descriptor e, const filtered_graph_base
& g) { return target(e, g.m_g); } template
std::pair
::out_edge_iterator, typename filtered_graph
::out_edge_iterator> out_edges(typename filtered_graph
::vertex_descriptor u, const filtered_graph
& g) { typedef filtered_graph
Graph; typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); typedef typename Graph::out_edge_iterator iter; typename graph_traits
::out_edge_iterator f, l; tie(f, l) = out_edges(u, g.m_g); return std::make_pair(iter(pred, f, l), iter(pred, l, l)); } template
typename filtered_graph
::degree_size_type out_degree(typename filtered_graph
::vertex_descriptor u, const filtered_graph
& g) { typename filtered_graph
::degree_size_type n = 0; typename filtered_graph
::out_edge_iterator f, l; for (tie(f, l) = out_edges(u, g); f != l; ++f) ++n; return n; } template
std::pair
::adjacency_iterator, typename filtered_graph
::adjacency_iterator> adjacent_vertices(typename filtered_graph
::vertex_descriptor u, const filtered_graph
& g) { typedef filtered_graph
Graph; typedef typename Graph::adjacency_iterator adjacency_iterator; typename Graph::out_edge_iterator f, l; tie(f, l) = out_edges(u, g); return std::make_pair(adjacency_iterator(f, const_cast
(&g)), adjacency_iterator(l, const_cast
(&g))); } template
std::pair
::in_edge_iterator, typename filtered_graph
::in_edge_iterator> in_edges(typename filtered_graph
::vertex_descriptor u, const filtered_graph
& g) { typedef filtered_graph
Graph; typename Graph::InEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); typedef typename Graph::in_edge_iterator iter; typename graph_traits
::in_edge_iterator f, l; tie(f, l) = in_edges(u, g.m_g); return std::make_pair(iter(pred, f, l), iter(pred, l, l)); } template
typename filtered_graph
::degree_size_type in_degree(typename filtered_graph
::vertex_descriptor u, const filtered_graph
& g) { typename filtered_graph
::degree_size_type n = 0; typename filtered_graph
::in_edge_iterator f, l; for (tie(f, l) = in_edges(u, g); f != l; ++f) ++n; return n; } template
std::pair
::edge_descriptor, bool> edge(typename filtered_graph
::vertex_descriptor u, typename filtered_graph
::vertex_descriptor v, const filtered_graph
& g) { typename graph_traits
::edge_descriptor e; bool exists; tie(e, exists) = edge(u, v, g.m_g); return std::make_pair(e, exists && g.m_edge_pred(e)); } template
std::pair
::out_edge_iterator, typename filtered_graph
::out_edge_iterator> edge_range(typename filtered_graph
::vertex_descriptor u, typename filtered_graph
::vertex_descriptor v, const filtered_graph
& g) { typedef filtered_graph
Graph; typename Graph::OutEdgePred pred(g.m_edge_pred, g.m_vertex_pred, g); typedef typename Graph::out_edge_iterator iter; typename graph_traits
::out_edge_iterator f, l; tie(f, l) = edge_range(u, v, g.m_g); return std::make_pair(iter(pred, f, l), iter(pred, l, l)); } //=========================================================================== // Property map namespace detail { struct filtered_graph_property_selector { template
struct bind_ { typedef typename FilteredGraph::graph_type Graph; typedef property_map
Map; typedef typename Map::type type; typedef typename Map::const_type const_type; }; }; } // namespace detail template <> struct vertex_property_selector
{ typedef detail::filtered_graph_property_selector type; }; template <> struct edge_property_selector
{ typedef detail::filtered_graph_property_selector type; }; template
typename property_map
::type get(Property p, filtered_graph
& g) { return get(p, const_cast
(g.m_g)); } template
typename property_map
::const_type get(Property p, const filtered_graph
& g) { return get(p, (const G&)g.m_g); } template
typename property_map_value
::type get(Property p, const filtered_graph
& g, const Key& k) { return get(p, (const G&)g.m_g, k); } template
void put(Property p, const filtered_graph
& g, const Key& k, const Value& val) { put(p, const_cast
(g.m_g), k, val); } //=========================================================================== // Some filtered subgraph specializations template
struct vertex_subset_filter { typedef filtered_graph
> type; }; template
inline typename vertex_subset_filter
::type make_vertex_subset_filter(Graph& g, const Set& s) { typedef typename vertex_subset_filter
::type Filter; is_in_subset
p(s); return Filter(g, keep_all(), p); } template
struct vertex_subset_compliment_filter { typedef filtered_graph
> type; }; template
inline typename vertex_subset_compliment_filter
::type make_vertex_subset_compliment_filter(Graph& g, const Set& s) { typedef typename vertex_subset_compliment_filter
::type Filter; is_not_in_subset
p(s); return Filter(g, keep_all(), p); } } // namespace boost #endif // BOOST_FILTERED_GRAPH_HPP
filtered_graph.hpp
Dirección de la página
Dirección del archivo
Anterior
30/95
Siguiente
Descargar
( 18 KB )
Comments
Total ratings:
0
Average rating:
No clasificado
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.