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
stanford_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\stanford_graph.hpp
Girar
Efecto
Propiedad
Historial
//======================================================================= // Copyright 1997-2001 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_SGB_GRAPH_HPP #define BOOST_GRAPH_SGB_GRAPH_HPP #include
#include
#include
#include
#include
#include
// Thanks to Andreas Scherer for numerous suggestions and fixes! // This file adapts a Stanford GraphBase (SGB) Graph pointer into a // VertexListGraph. Note that a graph adaptor class is not needed, // SGB's Graph* is used as is. The VertexListGraph concept is fulfilled by // defining the appropriate non-member functions for Graph*. // // The PROTOTYPES change file extensions to SGB must be applied so // that the SGB functions have real prototypes which are necessary for // the C++ compiler. To apply the PROTOTYPES extensions, before you do // "make tests install" for SGB do "ln -s PROTOTYPES/* ." to the SGB // root directory (or just copy all the files from the PROTOTYPES // directory to the SGB root directory). // extern "C" { // We include all global definitions for the general stuff // of The Stanford GraphBase and its various graph generator // functions by reading all SGB headerfiles as in section 2 of // the "test_sample" program. #include
/* SGB data structures */ #include
/* SGB input/output routines */ #include
/* random number generator */ #include
/* routines for shortest paths */ #include
/* the basic graph operations */ #undef empty /* avoid name clash with C++ standard library */ inline Graph* empty( long n ) /* and provide workaround */ { return board(n,0L,0L,0L,2L,0L,0L); } #include
/* graphs based on literature */ #include
/* graphs based on economic data */ #include
/* graphs based on football scores */ #include
/* graphs based on logic circuits */ #undef val /* avoid name clash with g++ headerfile stl_tempbuf.h */ // val ==> Vertex::x.I #include
/* graphs based on Mona Lisa */ #include
/* graphs based on mileage data */ #include
/* planar graphs */ #include
/* Ramanujan graphs */ #include
/* random graphs */ #include
/* graphs based on Roget's Thesaurus */ #include
/* we save results in ASCII format */ #include
/* five-letter-word graphs */ #undef weight /* avoid name clash with BGL parameter */ // weight ==> Vertex::u.I } namespace boost { class sgb_edge; } class sgb_out_edge_iterator; class sgb_adj_iterator; class sgb_vertex_iterator; namespace boost { typedef Graph* sgb_graph_ptr; typedef const Graph* sgb_const_graph_ptr; struct sgb_traversal_tag : public virtual vertex_list_graph_tag, public virtual incidence_graph_tag, public virtual adjacency_graph_tag { }; template <> struct graph_traits
{ typedef Vertex* vertex_descriptor; typedef boost::sgb_edge edge_descriptor; typedef sgb_out_edge_iterator out_edge_iterator; typedef void in_edge_iterator; typedef sgb_adj_iterator adjacency_iterator; typedef sgb_vertex_iterator vertex_iterator; typedef void edge_iterator; typedef long vertices_size_type; typedef long edge_size_type; typedef long degree_size_type; typedef directed_tag directed_category; typedef sgb_traversal_tag traversal_category; typedef allow_parallel_edge_tag edge_parallel_category; }; template <> struct graph_traits
{ typedef Vertex* vertex_descriptor; typedef boost::sgb_edge edge_descriptor; typedef sgb_out_edge_iterator out_edge_iterator; typedef void in_edge_iterator; typedef sgb_adj_iterator adjacency_iterator; typedef sgb_vertex_iterator vertex_iterator; typedef void edge_iterator; typedef long vertices_size_type; typedef long edge_size_type; typedef long degree_size_type; typedef directed_tag directed_category; typedef sgb_traversal_tag traversal_category; typedef allow_parallel_edge_tag edge_parallel_category; }; } namespace boost { struct edge_length_t { typedef edge_property_tag kind; }; // We could just use Arc* as the edge descriptor type, but // we want to add the source(e,g) function which requires // that we carry along a pointer to the source vertex. class sgb_edge { typedef sgb_edge self; public: sgb_edge() : _arc(0), _src(0) { } sgb_edge(Arc* a, Vertex* s) : _arc(a), _src(s) { } friend Vertex* source(self e, sgb_const_graph_ptr) { return e._src; } friend Vertex* target(self e, sgb_const_graph_ptr) { return e._arc->tip; } friend bool operator==(const self& a, const self& b) { return a._arc == b._arc; } friend bool operator!=(const self& a, const self& b) { return a._arc != b._arc; } #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) template
friend class sgb_edge_length_map; template
friend class sgb_edge_util_map; friend long get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key); friend long get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key); friend void put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value); protected: #endif Arc* _arc; Vertex* _src; }; } // namespace boost class sgb_out_edge_iterator : public boost::forward_iterator_helper< sgb_out_edge_iterator, boost::sgb_edge, std::ptrdiff_t, boost::sgb_edge*, boost::sgb_edge> { typedef sgb_out_edge_iterator self; public: sgb_out_edge_iterator() : _src(0), _arc(0) {} sgb_out_edge_iterator(Vertex* s, Arc* d) : _src(s), _arc(d) {} boost::sgb_edge operator*() { return boost::sgb_edge(_arc, _src); } self& operator++() { _arc = _arc->next; return *this; } friend bool operator==(const self& x, const self& y) { return x._arc == y._arc; } protected: Vertex* _src; Arc* _arc; }; class sgb_adj_iterator : public boost::forward_iterator_helper< sgb_adj_iterator, Vertex*, std::ptrdiff_t, Vertex**,Vertex*> { typedef sgb_adj_iterator self; public: sgb_adj_iterator() : _arc(0) {} sgb_adj_iterator(Arc* d) : _arc(d) {} Vertex* operator*() { return _arc->tip; } self& operator++() { _arc = _arc->next; return *this; } friend bool operator==(const self& x, const self& y) { return x._arc == y._arc; } protected: Arc* _arc; }; // The reason we have this instead of just using Vertex* is that we // want to use Vertex* as the vertex_descriptor instead of just // Vertex, which avoids problems with boost passing vertex descriptors // by value and how that interacts with the sgb_vertex_id_map. class sgb_vertex_iterator : public boost::forward_iterator_helper< sgb_vertex_iterator, Vertex*, std::ptrdiff_t, Vertex**, Vertex*> { typedef sgb_vertex_iterator self; public: sgb_vertex_iterator() : _v(0) { } sgb_vertex_iterator(Vertex* v) : _v(v) { } Vertex* operator*() { return _v; } self& operator++() { ++_v; return *this; } friend bool operator==(const self& x, const self& y) { return x._v == y._v; } protected: Vertex* _v; }; namespace boost { inline std::pair
vertices(sgb_const_graph_ptr g) { return std::make_pair(sgb_vertex_iterator(g->vertices), sgb_vertex_iterator(g->vertices + g->n)); } inline std::pair
out_edges(Vertex* u, sgb_const_graph_ptr) { return std::make_pair( sgb_out_edge_iterator(u, u->arcs), sgb_out_edge_iterator(u, 0) ); } inline boost::graph_traits
::degree_size_type out_degree(Vertex* u, sgb_const_graph_ptr g) { boost::graph_traits
::out_edge_iterator i, i_end; boost::tie(i, i_end) = out_edges(u, g); return std::distance(i, i_end); } // in_edges? inline std::pair
adjacent_vertices(Vertex* u, sgb_const_graph_ptr) { return std::make_pair( sgb_adj_iterator(u->arcs), sgb_adj_iterator(0) ); } inline long num_vertices(sgb_const_graph_ptr g) { return g->n; } inline long num_edges(sgb_const_graph_ptr g) { return g->m; } inline Vertex* vertex(long v, sgb_const_graph_ptr g) { return g->vertices + v; } // Various Property Maps // Vertex ID class sgb_vertex_id_map : public boost::put_get_helper
{ public: typedef boost::readable_property_map_tag category; typedef long value_type; typedef long reference; typedef Vertex* key_type; sgb_vertex_id_map() : _g(0) { } sgb_vertex_id_map(sgb_graph_ptr g) : _g(g) { } long operator[](Vertex* v) const { return v - _g->vertices; } protected: sgb_graph_ptr _g; }; inline sgb_vertex_id_map get(vertex_index_t, sgb_graph_ptr g) { return sgb_vertex_id_map(g); } // Vertex Name class sgb_vertex_name_map : public boost::put_get_helper
{ public: typedef boost::readable_property_map_tag category; typedef char* value_type; typedef char* reference; typedef Vertex* key_type; char* operator[](Vertex* v) const { return v->name; } }; inline sgb_vertex_name_map get(vertex_name_t, sgb_graph_ptr) { return sgb_vertex_name_map(); } // Vertex Property Tags #define SGB_PROPERTY_TAG(KIND,TAG) \ template
struct TAG##_property { \ typedef KIND##_property_tag kind; \ typedef T type; \ }; SGB_PROPERTY_TAG(vertex, u) SGB_PROPERTY_TAG(vertex, v) SGB_PROPERTY_TAG(vertex, w) SGB_PROPERTY_TAG(vertex, x) SGB_PROPERTY_TAG(vertex, y) SGB_PROPERTY_TAG(vertex, z) // Edge Property Tags SGB_PROPERTY_TAG(edge, a) SGB_PROPERTY_TAG(edge, b) // Various Utility Maps // helpers inline Vertex*& get_util(util& u, Vertex*) { return u.V; } inline Arc*& get_util(util& u, Arc*) { return u.A; } inline sgb_graph_ptr& get_util(util& u, sgb_graph_ptr) { return u.G; } inline char*& get_util(util& u, char*) { return u.S; } inline long& get_util(util& u, long) { return u.I; } #define SGB_GET_UTIL_FIELD(KIND,X) \ template
\ inline T& get_util_field(KIND* k, X##_property
) { \ return get_util(k->X, T()); } SGB_GET_UTIL_FIELD(Vertex, u) SGB_GET_UTIL_FIELD(Vertex, v) SGB_GET_UTIL_FIELD(Vertex, w) SGB_GET_UTIL_FIELD(Vertex, x) SGB_GET_UTIL_FIELD(Vertex, y) SGB_GET_UTIL_FIELD(Vertex, z) SGB_GET_UTIL_FIELD(Arc, a) SGB_GET_UTIL_FIELD(Arc, b) // Vertex Utility Map template
class sgb_vertex_util_map : public boost::put_get_helper
> { public: typedef boost::lvalue_property_map_tag category; typedef typename Tag::type value_type; typedef Vertex* key_type; typedef Ref reference; reference operator[](Vertex* v) const { return get_util_field(v, Tag()); } }; // Edge Utility Map template
class sgb_edge_util_map : public boost::put_get_helper
> { public: typedef boost::lvalue_property_map_tag category; typedef typename Tag::type value_type; typedef Vertex* key_type; typedef Ref reference; reference operator[](const sgb_edge& e) const { return get_util_field(e._arc, Tag()); } }; #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION template
inline sgb_vertex_util_map
get_property_map(Tag, const sgb_graph_ptr& g, vertex_property_tag) { return sgb_vertex_util_map
(); } template
inline sgb_vertex_util_map
get_property_map(Tag, sgb_graph_ptr& g, vertex_property_tag) { return sgb_vertex_util_map
(); } template
inline sgb_edge_util_map
get_property_map(Tag, const sgb_graph_ptr& g, edge_property_tag) { return sgb_edge_util_map
(); } template
inline sgb_edge_util_map
get_property_map(Tag, sgb_graph_ptr& g, edge_property_tag) { return sgb_edge_util_map
(); } #endif // ! BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION // Edge Length Access template
class sgb_edge_length_map : public boost::put_get_helper
> { public: typedef boost::lvalue_property_map_tag category; typedef long value_type; typedef sgb_edge key_type; typedef Ref reference; reference operator[](const sgb_edge& e) const { return e._arc->len; } }; inline sgb_edge_length_map
get(edge_length_t, const sgb_graph_ptr&) { return sgb_edge_length_map
(); } inline sgb_edge_length_map
get(edge_length_t, const sgb_const_graph_ptr&) { return sgb_edge_length_map
(); } inline sgb_edge_length_map
get(edge_length_t, sgb_graph_ptr&) { return sgb_edge_length_map
(); } inline long get(edge_length_t, const sgb_graph_ptr&, const sgb_edge& key) { return key._arc->len; } inline long get(edge_length_t, const sgb_const_graph_ptr&, const sgb_edge& key) { return key._arc->len; } inline void put(edge_length_t, sgb_graph_ptr&, const sgb_edge& key, long value) { key._arc->len = value; } // Property Map Traits Classes template <> struct property_map
{ typedef sgb_edge_length_map
type; typedef sgb_edge_length_map
const_type; }; template <> struct property_map
{ typedef sgb_vertex_id_map type; typedef sgb_vertex_id_map const_type; }; template <> struct property_map
{ typedef sgb_vertex_name_map type; typedef sgb_vertex_name_map const_type; }; template <> struct property_map
{ typedef sgb_edge_length_map
const_type; }; template <> struct property_map
{ typedef sgb_vertex_id_map const_type; }; template <> struct property_map
{ typedef sgb_vertex_name_map const_type; }; #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) namespace detail { template
struct sgb_choose_property_map { }; template
struct sgb_choose_property_map
{ typedef typename PropertyTag::type value_type; typedef sgb_vertex_util_map
type; typedef sgb_vertex_util_map
const_type; }; template
struct sgb_choose_property_map
{ typedef typename PropertyTag::type value_type; typedef sgb_edge_util_map
type; typedef sgb_edge_util_map
const_type; }; } // namespace detail template
struct property_map
{ typedef typename property_kind
::type Kind; typedef detail::sgb_choose_property_map
Choice; typedef typename Choice::type type; typedef typename Choice::const_type const_type; }; template
struct property_map
{ typedef typename property_kind
::type Kind; typedef detail::sgb_choose_property_map
Choice; typedef typename Choice::const_type const_type; }; #define SGB_UTIL_ACCESSOR(KIND,X) \ template
\ inline sgb_##KIND##_util_map< X##_property
, T&> \ get(X##_property
, sgb_graph_ptr&) { \ return sgb_##KIND##_util_map< X##_property
, T&>(); \ } \ template
\ inline sgb_##KIND##_util_map< X##_property
, const T&> \ get(X##_property
, const sgb_graph_ptr&) { \ return sgb_##KIND##_util_map< X##_property
, const T&>(); \ } \ template
\ inline sgb_##KIND##_util_map< X##_property
, const T&> \ get(X##_property
, const sgb_const_graph_ptr&) { \ return sgb_##KIND##_util_map< X##_property
, const T&>(); \ } \ template
\ inline typename \ sgb_##KIND##_util_map< X##_property
, const T&>::value_type \ get(X##_property
, const sgb_graph_ptr&, const Key& key) { \ return sgb_##KIND##_util_map< X##_property
, const T&>()[key]; \ } \ template
\ inline typename \ sgb_##KIND##_util_map< X##_property
, const T&>::value_type \ get(X##_property
, const sgb_const_graph_ptr&, const Key& key) { \ return sgb_##KIND##_util_map< X##_property
, const T&>()[key]; \ } \ template
\ inline void \ put(X##_property
, sgb_graph_ptr&, const Key& key, const Value& value) { \ sgb_##KIND##_util_map< X##_property
, T&>()[key] = value; \ } #else // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION #define SGB_UTIL_ACCESSOR_TYPE(KIND,TAG,TYPE) \ inline sgb_##KIND##_util_map< TAG
, TYPE& > \ get(TAG
, sgb_graph_ptr&) { \ return sgb_##KIND##_util_map< TAG
, TYPE& >(); \ } \ inline sgb_##KIND##_util_map< TAG
, const TYPE& > \ get(TAG
, const sgb_graph_ptr&) { \ return sgb_##KIND##_util_map< TAG
, const TYPE& >(); \ } \ inline sgb_##KIND##_util_map< TAG
, const TYPE& > \ get(TAG
, const sgb_const_graph_ptr&) { \ return sgb_##KIND##_util_map< TAG
, const TYPE& >(); \ } \ template
\ inline typename sgb_##KIND##_util_map< TAG
, const TYPE& >::value_type \ get(TAG
, const sgb_graph_ptr&, const Key& key) { \ return sgb_##KIND##_util_map< TAG
, const TYPE& >()[key]; \ } \ template
\ inline typename sgb_##KIND##_util_map< TAG
, const TYPE& >::value_type \ get(TAG
, const sgb_const_graph_ptr&, const Key& key) { \ return sgb_##KIND##_util_map< TAG
, const TYPE& >()[key]; \ } \ template
\ inline void \ put(TAG
, sgb_graph_ptr&, const Key& key, const Value& value) { \ sgb_##KIND##_util_map< TAG
, TYPE& >()[key] = value; \ } \ template <> struct property_map
> { \ typedef sgb_##KIND##_util_map< TAG
, TYPE&> type; \ typedef sgb_##KIND##_util_map< TAG
, const TYPE&> const_type; \ } #define SGB_UTIL_ACCESSOR(KIND,TAG) \ SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, Vertex*); \ SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, Arc*); \ SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, sgb_graph_ptr); \ SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, long); \ SGB_UTIL_ACCESSOR_TYPE(KIND, TAG##_property, char*); #endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION SGB_UTIL_ACCESSOR(vertex, u) SGB_UTIL_ACCESSOR(vertex, v) SGB_UTIL_ACCESSOR(vertex, w) SGB_UTIL_ACCESSOR(vertex, x) SGB_UTIL_ACCESSOR(vertex, y) SGB_UTIL_ACCESSOR(vertex, z) SGB_UTIL_ACCESSOR(edge, a) SGB_UTIL_ACCESSOR(edge, b) } // namespace boost #endif // BOOST_GRAPH_SGB_GRAPH_HPP
stanford_graph.hpp
Dirección de la página
Dirección del archivo
Anterior
83/95
Siguiente
Descargar
( 20 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.