Bidirectional

Boost , ,

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

BidirectionalGraph

The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient access to the in-edges of each vertex. This concept is separated from IncidenceGraph because for directed graphs efficient access to in-edges typically requires more storage space, and many algorithms do not require access to in-edges. For undirected graphs this is not an issue, since the in_edges() and out_edges() functions are the same, they both return the edges incident to the vertex.

Refinement of

IncidenceGraph

Notation

`G`	Тип, который является моделью графа.
`г`	Объект типа`G`.
`против`	Объект типа`boost::graph_traits::vertex_descriptor`.

Associated Types

boost::graph_traits::traversal_category

Этот тип тега должен быть конвертируемым вbidirectional_graph_tag.

boost::graph_traits<G>::in_edge_iterator

>Передний итератор для вершиныvобеспечивает доступ к краямv. Таким образом, тип значения в переднем итераторе является типом дескриптора края его графика. Итератор должен соответствовать требованиямMultiPassInputIterator.

Valid Expressions

`in_edges(v, g)`	Возвращает итератор-диапазон, обеспечивающий доступ к выступам (для направленных графов) или краям инцидента (для ненаправленных графов) вершины`v`в графе`g`. Для как направленных, так и ненаправленных графов, целью края должна быть вершина`v`, а источником должна быть вершина, прилегающая к`v`. Тип возврата:`std::pair`
`in_degree (v, g)`	Возвращает число краев (для направленных графов) или число краев (для ненаправленных графов) вершины`v`в графе`g`. Тип возврата:`Степень_size_type`
`степень (v, g)`	Возвращает число in-edges plus out-edges (для направленных графов) или число краев инцидента (для ненаправленных графов) вершины`v`в графе`g`. Тип возврата:`Степень_size_type`

Models

adjacency_listсDirected=bidirectionalS
adjacency_listсDirected=undirectedS

Complexity guarantees

The in_edges() function is required to be constant time. The in_degree() and degree() functions must be linear in the number of in-edges (for directed graphs) or incident edges (for undirected graphs).

Concept Checking Class

  template <class G>
  struct BidirectionalGraphConcept
  {
    typedef typename boost::graph_traits<G>::in_edge_iterator
      in_edge_iterator;
    void constraints() {
      BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> ));
      BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<in_edge_iterator> ));
      p = in_edges(v, g);
      n = in_degree(v, g);
      n = degree(v, g);
      e = *p.first;
      const_constraints(g);
    }
    void const_constraints(const G& g) {
      p = in_edges(v, g);
      n = in_degree(v, g);
      n = degree(v, g);
      e = *p.first;
    }
    std::pair<in_edge_iterator, in_edge_iterator> p;
    typename boost::graph_traits<G>::vertex_descriptor v;
    typename boost::graph_traits<G>::edge_descriptor e;
    typename boost::graph_traits<G>::degree_size_type n;
    G g;
  };

Джереми Сик, Университет Индианыjsiek@osl.iu.edu

Статья Bidirectional раздела может быть полезна для разработчиков на c++ и boost.

Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.

:: Главная :: ::

Время компиляции файла: 2024-08-30 11:47:00
2025-07-05 00:27:05/0.0032570362091064/0