c++ - pseudografo - grafo orientado

Booster gráfico biblioteca dirigida multigrafo edge_range error

Question

Tengo un multigrafo dirigido con vértices A..C y bordes E1..E4

A ---E1--> B
A ---E2--> B
A ---E3--> B
B ---E4--> C

Quería iterar sobre los bordes que conectan A y B.

En BGL, expresé esto como:

#include <boost/graph/adjacency_list.hpp>

struct Vertex
{
  std::string code;
};

struct Edge
{
  double distance;
  std::string code;
};

int main()
{
  using namespace boost;
  typedef adjacency_list<listS, vecS, directedS, Vertex, Edge> Graph;
  Graph g;
  auto a= add_vertex(Vertex{ "A" }, g);
  auto b= add_vertex(Vertex{ "B" }, g);
  auto c= add_vertex(Vertex{ "C" }, g);
  add_edge(a, b, Edge{ 10, "E1" }, g);
  add_edge(a, b, Edge{ 10, "E2" }, g);
  add_edge(a, b, Edge{ 10, "E3" }, g);
  add_edge(a, c, Edge{ 10, "E4" }, g);

  // checking number of edges
  std::cout<< num_edges(g)<< std::endl;

  // printing edges branching from A
  auto erange= out_edges(a, g);
  for(auto i= erange.first; i!= erange.second; ++ i)
    std::cout<< g[*i].code<< std::endl;

  // now we want to iterate over edges that connect A and B
  auto wtf= boost::edge_range(a, b, g);
}

Lo que resulta en un error de compilación:

In file included from /usr/include/boost/graph/adjacency_list.hpp:246:
/usr/include/boost/graph/detail/adjacency_list.hpp:1617:25: error: no matching constructor for initialization of ''StoredEdge'' (aka
      ''boost::detail::stored_edge_property<unsigned long, Edge>'')
        equal_range(el, StoredEdge(v, fake_edge_container.end(),
                    ^          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

He leído la documentación:

std::pair<out_edge_iterator, out_edge_iterator> edge_range(vertex_descriptor u, vertex_descriptor v, const adjacency_list& g) Returns a pair of out-edge iterators that give the range for all the parallel edges from u to v. This function only works when the OutEdgeList for the adjacency_list is a container that sorts the out edges according to target vertex, and allows for parallel edges. The multisetS selector chooses such a container.

( http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/adjacency_list.html )

Modificado el gráfico:

typedef adjacency_list<multisetS, vecS, directedS, Vertex, Edge> Graph;

Pero el error no cambió.

Entonces, ¿cómo se enumeran los bordes entre dos vértices (de -> a) en un multigrafo dirigido usando BGL?

Encontré una manera rápida y sucia:

auto erange= out_edges(a, g);$
for(auto i= erange.first; i!= erange.second; ++ i)$
  std::cout<< g[*i].code<< " -> "<< g[target(*i, g)].code<< std::endl;$

Lo cual me permitirá filtrar borde por vértice objetivo. ¿Pero cómo usas boost::edge_range ?

Answer 1

Esta falla ha sido reportada anteriormente en la lista de correo de Boost .

no se puede compilar cuando el argumento de la plantilla del Selector Dirigido a la lista_de_adjancia se establece en dirigidoS, pero funciona si el argumento es S no dirigido o bidireccional. A continuación se adjunta un breve programa que ilustra el problema. El problema es que edge_range () crea una instancia de StoredEdge a través de un constructor que toma 3 argumentos, pero cuando se dirige el SelectorS StoredEdge se digita como datado a stored_edge_property, que no tiene dicho constructor. Una solución podría ser crear funciones sobrecargadas edge_range_dispatch () y enviarlas en
Config :: on_edge_storage.

Cambiar las directedS a undirectedS en su programa funciona. Ejemplo en vivo Pero puede que eso no sea lo que necesita para su aplicación, por lo que el filtro simple que mencionó anteriormente podría ser mejor. Puede volver a publicar esto en la lista de correo de Boost para obtener más atención.