Boost Graph Concepts

Boost , ,

Graph Concepts

Сердцем библиотеки Boost Graph Library (BGL) является интерфейс или концепции (на языке общего программирования), которые определяют, как граф может быть изучен и обработан нейтральным образом. На самом деле интерфейс BGL даже не обязательно должен быть реализован с использованием структуры данных, так как для некоторых задач проще или эффективнее определить граф неявно на основе некоторых функций.

Интерфейс BGL не является единой концепцией графа. Вместо этого он разбит на гораздо меньшие части. Причина этого заключается в том, что целью концепции является обобщение требований к алгоритмам particular. Любой алгоритм не нуждается во всех видах графовых операций, как правило, только в небольшом подмножестве. Кроме того, существует множество графовых структур данных, которые не могут обеспечить эффективную реализацию всех операций, но обеспечивают высокоэффективную реализацию операций, необходимых для конкретного алгоритма. Путем разложения графического интерфейса на множество более мелких концепций мы предоставляем автору алгоритма графа хороший выбор, из которого можно выбрать концепцию, наиболее подходящую для их алгоритма. Обратите внимание, что из-за использования классов признаков, а не типов членов, небезопасно (и часто не будет работать) определять подклассы типов графов BGL; эти типы могут отсутствовать важные черты и свойства, которые были определены вне определения класса.

Обзор концепций структуры графа

Рисунок 1 показывает отношения уточнений между понятиями графа. Причина включения графического интерфейса во многие концепции заключается в том, чтобы поощрять алгоритмические интерфейсы требовать и использовать только минимальный интерфейс графа, тем самым увеличивая повторное использование алгоритма.

Figure 1: The graph concepts and refinement relationships.

Notation

Undirected Graphs

The interface that the BGL provides for accessing and manipulating an undirected graph is the same as the interface for directed graphs described in the following sections, however there are some differences in the behaviour and semantics. For example, in a directed graph we can talk about out-edges and in-edges of a vertex. In an undirected graph there is no ``in'' and ``out'', there are just edges incident to a vertex. Nevertheless, in the BGL we still use the out_edges() function (or in_edges()) to access the incident edges in an undirected graph. Similarly, an undirected edge has no ``source'' and ``target'' but merely an unordered pair of vertices, but in the BGL we still use source() and target() to access these vertices. The reason the BGL does not provide a separate interface for undirected graphs is that many algorithms on directed graphs also work on undirected graphs, and it would be inconvenient to have to duplicate the algorithms just because of an interface difference. When using undirected graphs just mentally disregard the directionality in the function names. The example below demonstrates using the out_edges(), source(), and target() with an undirected graph. The source code for this example and the following one can be found in example/undirected_adjacency_list.cpp.

  const int V = 2;
  typedef ... UndirectedGraph;
  UndirectedGraph undigraph(V);
  std::cout << "the edges incident to v: ";
  boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
  boost::graph_traits<UndirectedGraph>::vertex_descriptor 
    s = vertex(0, undigraph);
  for (boost::tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e)
    std::cout << "(" << source(*e, undigraph) 
              << "," << target(*e, undigraph) << ")" << endl;

Even though the interface is the same for undirected graphs, there are some behavioral differences because edge equality is defined differently. In a directed graph, edge (u,v) is never equal to edge (v,u), but in an undirected graph they may be equal. If the undirected graph is a multigraph then (u,v) and (v,u) might be parallel edges. If the graph is not a multigraph then (u,v) and (v,u) must be the same edge.

In the example below the edge equality test will return false for the directed graph and true for the undirected graph. The difference also affects the meaning of add_edge(). In the example below, if we had also written add_edge(v, u, undigraph), this would have added a parallel edge between u and v (provided the graph type allows parallel edges). The difference in edge equality also affects the association of edge properties. In the directed graph, the edges (u,v) and (v,u) can have distinct weight values, whereas in the undirected graph the weight of (u,v) is the same as the weight of (v,u) since they are the same edge.

  typedef ... DirectedGraph;
  DirectedGraph digraph(V);
  {
    boost::graph_traits<DirectedGraph>::vertex_descriptor u, v;
    u = vertex(0, digraph);
    v = vertex(1, digraph);
    add_edge(digraph, u, v, Weight(1.2));
    add_edge(digraph, v, u, Weight(2.4));
    boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;
    bool found;
    boost::tie(e1, found) = edge(u, v, digraph);
    boost::tie(e2, found) = edge(v, u, digraph);
    std::cout << "in a directed graph is ";
    std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
    property_map<DirectedGraph, edge_weight_t>::type
      weight = get(edge_weight, digraph);
    cout << "weight[(u,v)] = " << get(weight, e1) << endl;
    cout << "weight[(v,u)] = " << get(weight, e2) << endl;
  }
  {
    boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;
    u = vertex(0, undigraph);
    v = vertex(1, undigraph);
    add_edge(undigraph, u, v, Weight(3.1));
    boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;
    bool found;
    boost::tie(e1, found) = edge(u, v, undigraph);
    boost::tie(e2, found) = edge(v, u, undigraph);
    std::cout << "in an undirected graph is ";
    std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
    property_map<UndirectedGraph, edge_weight_t>::type
      weight = get(edge_weight, undigraph);
    cout << "weight[(u,v)] = " << get(weight, e1) << endl;
    cout << "weight[(v,u)] = " << get(weight, e2) << endl;
  }

in a directed graph is (u,v) == (v,u) ? 0
weight[(u,v)] = 1.2
weight[(v,u)] = 2.4
in an undirected graph is (u,v) == (v,u) ? 1
weight[(u,v)] = 3.1
weight[(v,u)] = 3.1

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

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