c++ - 检查顶点之间的平行边 : edge_range does not work with directed graph

Question

我不确定这是否与 boost graph library directed multigraph edge_range bug 但是我不能将 edge_range 与 directedS 一起使用，并且从上面的链接中得到了不同的错误。将 directedS 更改为 nondirectedS 可以使它工作，但这不是我想要的。

1. 如果这不起作用，除了使用 boost::out_edges

，我们还有其他方法来检查节点之间的平行边吗？

2. 当我的图允许平行边时，boost::edge(u, v, G) 返回给我的是什么？第一条边？

谢谢。

#include <boost/graph/adjacency_list.hpp>

typedef boost::adjacency_list<
    boost::multisetS,
    boost::vecS, 
    boost::directedS,
    boost::no_property,
    boost::no_property,
    boost::no_property,
    boost::setS 
    > Graph;

typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;

void test(Edge aE, const Graph &aG) {
    Vertex sv = boost::source(aE, aG);
    Vertex tv = boost::target(aE, aG);
    typename boost::graph_traits<Graph>::out_edge_iterator it, eit;
    for (boost::tie(it, eit) = boost::edge_range(sv, tv, aG);
        it != eit;
        ++it) {
    }
}

留言

   In file included from .../glnxa64/boost/include/boost/graph/adjacency_list.hpp:370:0,
                 from sl_execgraph/Test.cpp:2:
.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘std::pair<typename Config::out_edge_iterator, typename Config::out_edge_iterator> boost::edge_range(typename Config::vertex_descriptor, typename Config::vertex_descriptor, const boost::adj_list_helper<Config, Base>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::multisetS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>, boost::vecS, boost::multisetS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>::config; Base = boost::directed_graph_helper<boost::detail::adj_list_gen<boost::adjacency_list<boost::multisetS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>, boost::vecS, boost::multisetS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>::config>; typename Config::out_edge_iterator = boost::detail::out_edge_iter<std::_Rb_tree_const_iterator<boost::detail::sep_<long unsigned int, boost::no_property> >, long unsigned int, boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>, long int>; typename Config::vertex_descriptor = long unsigned int]’:

sl_execgraph/Test.cpp:21:60:   required from here

.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:1625:7: error: no matching function for call to ‘boost::detail::sep_<long unsigned int, boost::no_property>::sep_(boost::detail::adj_list_gen<boost::adjacency_list<boost::multisetS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>, boost::vecS, boost::multisetS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>::config::vertex_descriptor&, std::set<boost::list_edge<long unsigned int, boost::no_property>, std::less<boost::list_edge<long unsigned int, boost::no_property> >, std::allocator<boost::list_edge<long unsigned int, boost::no_property> > >::iterator, boost::detail::adj_list_gen<boost::adjacency_list<boost::multisetS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>, boost::vecS, boost::multisetS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::setS>::config::EdgeContainer*)’
.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:1625:7: 

note: candidates are:

In file included from .../glnxa64/boost/include/boost/graph/adjacency_list.hpp:370:0,

                 from sl_execgraph/Test.cpp:2:

.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:273:7: note: boost::detail::sep_<Vertex, Property>::sep_(const self&) [with Vertex = long unsigned int; Property = boost::no_property; boost::detail::sep_<Vertex, Property>::self = boost::detail::sep_<long unsigned int, boost::no_property>]

.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:273:7: note:   candidate expects 1 argument, 3 provided

.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:270:14: note: boost::detail::sep_<Vertex, Property>::sep_(Vertex, const Property&) [with Vertex = long unsigned int; Property = boost::no_property]

.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:270:14: note:   candidate expects 2 arguments, 3 provided

.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:269:14: note: boost::detail::sep_<Vertex, Property>::sep_() [with Vertex = long unsigned int; Property = boost::no_property]

.../glnxa64/boost/include/boost/graph/detail/adjacency_list.hpp:269:14: note:   candidate expects 0 arguments, 3 provided

.../Makefile.module: recipe for target 'Test.o' failed

Answer 1

您遇到的错误已在 Boost 1.56 中修复

修复提交可能是 4af6108

tree 21e89a6ae24b1d94cdc38e3e0219ae81f0ff52e9
parent 031ce8084b5ca6e79b359b3a3fee671115fffc41
author Jeremiah Willcock <jewillco@osl.iu.edu> Sat Oct 26 22:57:10 2013 +0000
committer Jeremiah Willcock <jewillco@osl.iu.edu> Sat Oct 26 22:57:10 2013 +0000

Fixed edge_range bug from http://stackoverflow.com/questions/19223692/boost-graph-library-directed-multigraph-edge-range-bug?rq=1

[SVN r86469]

diff --git a/include/boost/graph/detail/adjacency_list.hpp b/include/boost/graph/detail/adjacency_list.hpp
index 16cf026..87fd557 100644
--- a/include/boost/graph/detail/adjacency_list.hpp
+++ b/include/boost/graph/detail/adjacency_list.hpp
@@ -1610,8 +1610,7 @@ namespace boost {
    typename Config::OutEdgeList::iterator first, last;
    typename Config::EdgeContainer fake_edge_container;
    boost::tie(first, last) = graph_detail::
-        equal_range(el, StoredEdge(v, fake_edge_container.end(),
-                                   &fake_edge_container));
+        equal_range(el, StoredEdge(v));
    return std::make_pair(out_edge_iterator(first, u),
                            out_edge_iterator(last, u));
    }

可以看到 Live On Coliru (使用 Boost 1.57)