boostorg / graph Goto Github PK
View Code? Open in Web Editor NEWBoost.org graph module
Home Page: http://boost.org/libs/graph
Boost.org graph module
Home Page: http://boost.org/libs/graph
We're running cycle_ratio_example.cpp in the tests, but it uses a non-deterministic random number generator which very occasionally results in the assertions failing. It's not clear if this is inevitable, or is showing up a deeper bug of some sort.
Observed failure is:
Vertices number: 1000
Edges number: 30000
Maximum cycle ratio is 9.32637
Minimum cycle ratio is -0.45058
Critical cycle:
(354,386) (386,354)
cycle_ratio_example: libs/graph/example/cycle_ratio_example.cpp:83: int main(int, char**): Assertion `std::abs(cr.first / cr.second - min_cr) < epsilon * 2' failed.
Aborted (core dumped)
Actually looking at the result, I suspect we just need to up the error tolerance slightly - 2 epsilon might be a bit hopeful?
breadth_first_visit ignores the visitor object passed in and uses a null one instead. To recreate:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
using namespace std;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, uint>, boost::property<boost::edge_index_t, uint>> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits<Graph>::edge_descriptor edge_t;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
struct CollectBFSVisitor : public boost::default_bfs_visitor
{
virtual void initialize_vertex(vertex_t v, Graph const& g) {cout << "init vertex\n";};
virtual void discover_vertex(vertex_t v, Graph const& g) {};
virtual void examine_vertex(vertex_t v, Graph const& g) {};
virtual void finish_vertex(vertex_t v, Graph const& g) {};
virtual void black_target(edge_t, Graph const& g) {};
virtual void gray_target(edge_t, Graph const& g) {};
virtual void tree_target(edge_t, Graph const& g) {};
virtual void tree_edge(edge_t, Graph const& g) {};
virtual void non_tree_edge(edge_t, Graph const& g) {};
};
struct VertBuffer : boost::queue<vertex_t>
{
};
int main()
{
Graph g;
vertex_t x = add_vertex(g);
auto indexmap = boost::get(boost::vertex_index, g);
auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);
VertBuffer q;
CollectBFSVisitor v;
breadth_first_visit(g, x, q, v, colormap); // the cout doesn't run, but if you change it to breadth_first_search it does
}
Problem line in boost/graph/breadth_first_search.hpp
breadth_first_visit
(ng, s,
choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
choose_param(get_param(params, graph_visitor),
make_bfs_visitor(null_visitor())),
choose_pmap(get_param(params, vertex_color), ng, vertex_color)
);
Including reverse_graph.hpp
defines a get
overload inside the boost::detail
namespace:
namespace detail {
template <class E>
struct underlying_edge_desc_map_type {
E operator[](const reverse_graph_edge_descriptor<E>& k) const {
return k.underlying_descx;
}
};
template <class E>
E
get(underlying_edge_desc_map_type<E> m,
const reverse_graph_edge_descriptor<E>& k)
{
return m[k];
}
}
If included before other algorithms it can mess up the ADL on get
calls from within that detail namespace. E.g. in strong_components.hpp
the Tarjan visitor does
if (get(comp, w) == (std::numeric_limits<comp_type>::max)())
This call fails to compile if reverse_graph.hpp
had been included before. In fact, the developers probably found this out when they decided to only include the transpose_graph.hpp
header /after/ the Tarjan implementation (and before the Kosaraju version that requires it).
The exact mechanics of the bug are not completely clear to me. But I guess it sits on the intersection of ADL and partial ordering. In fact using
using ::boost::get;
if (get(comp, w) == (std::numeric_limits<comp_type>::max)()) // ...
does enable ADL at instantiation time. But I suspect the structural fix would be to avoid declaring a get
overload inside the detail namespace.
The sample output provided for the code in filtered_graph_edge_range.cpp is wrong.
Is there a class for trees in BGL?
I'm looking at GraphQL, and they have a legitimate use case where vertices aren't local but are dynamically generated. It would be really powerful to support that use case, though it may need to wait for a whole new implementation. Anyways, an eye should be kept to supporting their use case.
I want to improve the isomorphism
documentation and discuss some improvements to the algorithm.
AdaptableUnaryFunction
concept, not UnaryFunction
as stated (argument_type
and result_type
typedefs)isomorphism
, the second vertex invariant functor additionally requires a max()
member function as an alternative if vertex_max_invariant
is not passed. vertex_max_invariant
and max()
here are misnomers, as it is demanded that they are upper exclusive bounds on the vertex invariant values (i.e. number of different values, not maximum values). Any added documentation of max()
should have this information too, though.vertex_max_invariant
and vertex_invariant2::max()
are unnecessary: test_isomorphism
immediately evaluates all invariants for all vertices of both graphs, sorts them, and lexicographically compares. The upper exclusive bound on the invariant values is then the maximum of the back of both invariant lists plus one. Yes, it is then less clear why invariants must be in a contiguous range with a reasonable upper bound - which, I assume, is purely for the efficiency and memory-compactness of the invariant multiplicity calculation here:
// isomorphism.hpp, line 156 onwards
std::vector<vertex1_t> V_mult;
BGL_FORALL_VERTICES_T(v, G1, Graph1)
V_mult.push_back(v);
{
std::vector<size_type> multiplicity(max_invariant, 0);
BGL_FORALL_VERTICES_T(v, G1, Graph1)
++multiplicity.at(invariant1(v));
sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0]));
}
vertex_invariant2
, without breaking existing code.unordered_map
to avoid wasting memory.test_isomorphism
, where all invariants are calculated for all vertices, does not reserve
.Thoughts?
breath_first_search appears to not be robust against degenerate graphs, such as a single vertex with no edges. Adding an edge connecting this single vertex to itself seems to be a workaround.
To reproduce:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/breadth_first_search.hpp>
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, uint>, boost::property<boost::edge_index_t, uint>> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
struct BFSVisitor : boost::default_bfs_visitor
{
};
int main()
{
Graph g;
vertex_t x;
add_vertex(x, g);
//add_edge(x, x, g); // uncomment this line for workaround
BFSVisitor v;
breadth_first_search(g, x, boost::visitor(v));
}
On Fedora this crashes with:
boostbug: /usr/local/boost/boost/graph/two_bit_color_map.hpp:87: void boost::put(const boost::two_bit_color_map&, typename boost::property_traits::key_type, boost::two_bit_color_type) [with IndexMap = boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_index_t, unsigned int>, long unsigned int>; typename boost::property_traits::key_type = long unsigned int]: Assertion `(std::size_t)i < pm.n' failed.
[1] 14139 abort (core dumped) ./boostbug
Headers were likely never supposed to live in boost/pending for a long time. At this point boost/pending should be retired and the headers moved into their rightful and normal place. Here are the pending headers for this repository:
graph/include/boost/pending/bucket_sorter.hpp
graph/include/boost/pending/container_traits.hpp
graph/include/boost/pending/detail/property.hpp
graph/include/boost/pending/fenced_priority_queue.hpp
graph/include/boost/pending/fibonacci_heap.hpp
graph/include/boost/pending/indirect_cmp.hpp
graph/include/boost/pending/is_heap.hpp
graph/include/boost/pending/mutable_heap.hpp
graph/include/boost/pending/mutable_queue.hpp
graph/include/boost/pending/property.hpp
graph/include/boost/pending/queue.hpp
graph/include/boost/pending/relaxed_heap.hpp
graph/include/boost/pending/stringtok.hpp
there might be a bug in
boost/graph/tiernan_all_cycles.hpp
which comes from tiernan_all_cycles.hpp, line 161:
BOOST_CONCEPT_ASSERT(( VertexIndexGraphConcept<Graph> ));
and then in graph_concepts.hpp on line 469/70
// This is relaxed
renumber_vertex_indices(g);
One way to make it compile is to just provide the renumber_vertex_indices the concept checks for, but since tiernan_all_cycles doesn't directly or indirectly call renumber_vertex_indices the check on line 161 in tiernan_all_cycles.hpp can also be commented out.
I don't understand why this concept check is used. Maybe it's fine and the "workaround" is the right way to deal with it?
(adapted from https://svn.boost.org/trac10/ticket/9826)
Looking at property_map, I noticed that boost::property is wasting space. property<tag,double> will typically have size 16 because of the no_property member. list_edge<Vertex,no_property> will also be too long for the same reason. A proper use of the empty base optimization (possibly through tuple or compressed_pair) should help with this. Partial specializations for no_property may be a simpler alternative. If you are lazy, [[no_unique_address]] would already be nice.
Graphs can grow large, and it seems quite important to avoid wasting memory.
This appears to be a regression caused by:
commit 616b9e7
Author: Jeremiah Willcock [email protected]
Date: Sat Jun 30 20:00:41 2012 +0000
Before that commit, property was implemented with derivation (which is still what the documentation shows...), and the empty base optimization avoided wasting so much space.
The repository disjoint_sets contains one non-detail header and it is in boost/pending. A search of boost shows that only Boost.Graph and Boost.GraphParallel use disjoint_sets. I would like to eliminate disjoint_sets as a separate repository to ease the burden on the CMT. The maintainer of Boost.Container did not feel that disjoint_sets belonged there. As such I would like to move this module into Boost.Graph and update Graph and GraphParallel appropriately.
Imagine we have a root graph g, and two sons of it g1 and g2.
If we use edges(g1)
to get two iterators and cycle from one to the other to find an edge with index i
,
we name its corresponding descriptor as ed_1 = *e1_i
.
We use the same method in g
, find an edge with index i
, and convert it to g1's local edge descriptor, we name it ed_2 = g1.global_to_local(*e_i)
.
And I found that their m_eproperty
are not the same. Shouldn't these two be the same descriptor?
When BOOST_DISABLE_ASSERTS or BOOST_ENABLE_ASSERT_HANDLER is defined, the nested switch on str[1]
can continue past the assert and will fallthrough to the default
case below.
This can cause warnings with static analysis tools, and if a user-defined boost::assertion_failed function that doesn't terminate the process is being used, that function will be called twice because the first assertion falls through to the second.
Inserting a break
avoids static analysis warnings and avoids potentially calling the assertion handler twice.
When calling remove_vertex
on a labeled_graph
the vertex is removed but the label is not.
A dangling reference to the vertex is left behind. Accessing it causes segfaults.
Minimal example:
#include <iostream>
#include <string>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/labeled_graph.hpp>
using namespace boost;
using namespace std;
int main() {
using namespace boost::graph_detail;
typedef directed_graph<> Digraph;
typedef labeled_graph<Digraph, string> Graph;
Graph g;
g.add_vertex("foo");
auto v = g.vertex("foo");
if(v != nullptr)
cout << "foo exists\n";
g.remove_vertex("foo");
auto v2 = g.vertex("foo");
if(v2 != nullptr)
std::cout << " BUG! vertex label still exists.\n";
return 0;
}
stored_edge_property
contains a std::unique_ptr<Property>
instead of the raw Property
. In my application, this doubles the memory use of the graph and more than doubles the running time. It comes with this explanation
// Holding the property by-value causes edge-descriptor
// invalidation for add_edge() with EdgeList=vecS. Instead we
// hold a pointer to the property. std::auto_ptr is not
// a perfect fit for the job, but it is darn close.
I tried to understand and couldn't make sense of what this is supposed to mean. In any case, my property is a (wrapper for a) double, and I strongly doubt that storing a double will invalidate anything. Or do people keep pointers/references to internal properties, do some insertions/removals, then expect the properties are still there? If so, I'd like this expensive feature to be optional please... The comment seems to indicate that this is only needed for vecS but it doesn't seem restricted to vecS (and even for vecS I want to be able to avoid it).
My code using boost::graph::isomorphism(g1, g2)
works with boost 1.70.0 but fails to compile with boost 1.71.0. I'm using clang 9.
For a reproducer, see https://godbolt.org/z/bysaYi
The following files:
kruskal-telephone.cpp ;
loops_dfs.cpp ;
scc.cpp ;
reachable-loop-head.cpp ;
cc-internet.cpp ;
reachable-loop-tail.cpp ;
prim-telephone.cpp ;
dfs-parenthesis.cpp ;
edge_connectivity.cpp ;
edge-connectivity.cpp ;
All use GraphvizGraph
and related interfaces which have been removed from the library - actually they are commented out with the note:
// This interface has not worked for a long time
So either we need to remove these examples altogether, or better, figure out what interface they should be using.
In addition strong_components.cpp calls an old Graphviz API whose meaning has changed - as a result it chokes interpreting a filename as Graphviz data. Replacing the filename with a std::ifstream just moves the error elsewhere :(
https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/incremental_components.html
The first example, from examples/incremental_components.cpp, was copy-pasted raw, without protecting special characters from HTML, so in particular all templates are invisible.
graph/include/boost/graph/isomorphism.hpp
Line 321 in 887e63d
There don't seem to be many instances of abort() in BGL code. Should it be replaced by a boost::throw_exception?
The example starts with:
#error "This example appears to be incorrect; it uses edge weights that are smaller than 0 using the comparison operator passed to Dijkstra's algorithm, which is not allowed."
igraph
has this degree_sequence_game
src/games.c method to randomly create a graph with a set of degrees.
I wonder if you know if there is any implementation of that stochastic algorithm using BGL. And if not, if there is any road map on implementing it. Thanks!
Using bron_kerbosch_all_cliques
results in an unused variable warning
/usr/local/include/boost/graph/bron_kerbosch_all_cliques.hpp:227:41: error: unused variable 'j' [-Werror,-Wunused-variable]
typename Container::iterator i, j;
^
/usr/local/include/boost/graph/bron_kerbosch_all_cliques.hpp:289:13: note: in instantiation of function template specialization 'boost::detail::extend_clique<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> >, std::__1::deque<unsigned long, std::__1::allocator<unsigned long> >, std::__1::vector<unsigned long, std::__1::allocator<unsigned long> >, octopus::MaxCliqueVisitor<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> > > >' requested here
detail::extend_clique(g, clique, cands, nots, vis, min);
^
/usr/local/include/boost/graph/bron_kerbosch_all_cliques.hpp:297:3: note: in instantiation of function template specialization 'boost::bron_kerbosch_all_cliques<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> >, octopus::MaxCliqueVisitor<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> > > >' requested here
{ bron_kerbosch_all_cliques(g, vis, 2); }
Looks like j
can simply be removed?
Hello dear team of Boostorg.
First, I am not sure wheter this is the right repository to post this issue, if not, I will grandly repost it somewhere else.
The error is pretty much the same as in the closed issue #9438 and I am not sure why it reappeared.
#include <boost/geometry.hpp>
#include <lemon/list_graph.h>
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
using Point = boost::geometry::model::point<double, 2, bg::cs::cartesian>;
using Graph = lemon::ListDigraph;
using Node = lemon::ListDigraph::Node;
typedef std::pair<Point, Node> Pair;
using BoostRTree = bgi::rtree<Pair, bgi::quadratic<16>>;
using BoostQueryResult = std::vector<Pair>;
int main()
{
Point one = Point(10, 51);
Point two = Point(10, 51);
BoostRTree rtreePair = BoostRTree();
Graph graph;
Node dummy1 = graph.addNode();
Node dummy2 = graph.addNode();
rtreePair.insert(std::make_pair(one, dummy1));
return 0;
}
The following two examples crash at runtime:
astar_maze.cpp
kevin-bacon2.cpp
Sorry but I don't see what the issue is off hand.
Boost documentation mentions Parallel Boost Graph Library but I cannot find the code anywhere here.
Does anyone know where i can find it?
Thanks.
Title says it all, msvc runtime checks catch this.
One thing which would be useful to add would be general support for reading from and writing to a number of graph file formats. antlr4 should be of help here. It looks like there shouldn't be any licensing conflicts. I'd like to coordinate with cwl and NetworkX about some of these to add or improve support for their use cases.
Here's a little reading:
https://github.com/antlr/antlr4/blob/master/doc/cpp-target.md
http://graphml.graphdrawing.org/
https://github.com/antlr/grammars-v4/tree/master/xml
https://github.com/antlr/grammars-v4/tree/master/gml
https://github.com/antlr/grammars-v4/tree/master/dot
https://github.com/common-workflow-language/common-workflow-language
Currently the vertices()
and edges()
functions in BGL return an std::pair
of iterators. To iterate over vertices, a code like following is usually written:
typename graph_traits<Graph>::vertices_size_type b = 0;
typename graph_traits<Graph>::vertex_iterator i, end;
for (boost::tie(i, end) = vertices(g); i != end; ++i)
do_something(*i);
If vertices()
and edges()
returned a boost::iterator_range, a cleaner code could be written:
for (auto v : vertices(g))
do_something(v);
I found the error when my editor uses clang-format
to format the code.
Example directory has a file topo-sort1.cpp
. It includes two header files from bgl library.
/* ommited */
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/topological_sort.hpp>
If I change the order to
/* ommited */
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/vector_as_graph.hpp>
gcc-8.2 compiler shows a error message shown below.
(The error message is also saved as a text file errorlog.txt, if you wish to read on your terminal.)
In file included from /usr/include/boost/graph/topological_sort.hpp:16,
from topo-sort1.cpp:12:
/usr/include/boost/graph/depth_first_search.hpp: In instantiation of โvoid boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]โ:
/usr/include/boost/graph/depth_first_search.hpp:335:36: required from โvoid boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]โ
/usr/include/boost/graph/depth_first_search.hpp:342:5: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]โ
/usr/include/boost/graph/depth_first_search.hpp:345:3: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]โ
/usr/include/boost/graph/topological_sort.hpp:65:23: required from โvoid boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]โ
topo-sort1.cpp:42:61: required from here
/usr/include/boost/graph/depth_first_search.hpp:232:43: error: no matching function for call to โvertices(const std::vector<std::__cxx11::list<int> >&)โ
for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
~~~~~~~~^~~
In file included from /usr/include/boost/graph/depth_first_search.hpp:18,
from /usr/include/boost/graph/topological_sort.hpp:16,
from topo-sort1.cpp:12:
/usr/include/boost/graph/graph_concepts.hpp:47:48: note: candidate: โtemplate<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&)โ
typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
^~~~~~~~
/usr/include/boost/graph/graph_concepts.hpp:47:48: note: template argument deduction/substitution failed:
/usr/include/boost/graph/graph_concepts.hpp: In substitution of โtemplate<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&) [with T = std::vector<std::__cxx11::list<int> >]โ:
/usr/include/boost/graph/depth_first_search.hpp:232:43: required from โvoid boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]โ
/usr/include/boost/graph/depth_first_search.hpp:335:36: required from โvoid boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]โ
/usr/include/boost/graph/depth_first_search.hpp:342:5: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]โ
/usr/include/boost/graph/depth_first_search.hpp:345:3: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]โ
/usr/include/boost/graph/topological_sort.hpp:65:23: required from โvoid boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]โ
topo-sort1.cpp:42:61: required from here
/usr/include/boost/graph/graph_concepts.hpp:47:48: error: no type named โThereReallyIsNoMemberByThisNameInTโ in โclass std::vector<std::__cxx11::list<int> >โ
In file included from /usr/include/boost/graph/topological_sort.hpp:16,
from topo-sort1.cpp:12:
/usr/include/boost/graph/depth_first_search.hpp: In instantiation of โvoid boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]โ:
/usr/include/boost/graph/depth_first_search.hpp:335:36: required from โvoid boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]โ
/usr/include/boost/graph/depth_first_search.hpp:342:5: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]โ
/usr/include/boost/graph/depth_first_search.hpp:345:3: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]โ
/usr/include/boost/graph/topological_sort.hpp:65:23: required from โvoid boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]โ
topo-sort1.cpp:42:61: required from here
/usr/include/boost/graph/depth_first_search.hpp:242:43: error: no matching function for call to โvertices(const std::vector<std::__cxx11::list<int> >&)โ
for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
~~~~~~~~^~~
In file included from /usr/include/boost/graph/depth_first_search.hpp:18,
from /usr/include/boost/graph/topological_sort.hpp:16,
from topo-sort1.cpp:12:
/usr/include/boost/graph/graph_concepts.hpp:47:48: note: candidate: โtemplate<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&)โ
typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
^~~~~~~~
/usr/include/boost/graph/graph_concepts.hpp:47:48: note: template argument deduction/substitution failed:
/usr/include/boost/graph/graph_concepts.hpp: In substitution of โtemplate<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&) [with T = std::vector<std::__cxx11::list<int> >]โ:
/usr/include/boost/graph/depth_first_search.hpp:242:43: required from โvoid boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]โ
/usr/include/boost/graph/depth_first_search.hpp:335:36: required from โvoid boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]โ
/usr/include/boost/graph/depth_first_search.hpp:342:5: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]โ
/usr/include/boost/graph/depth_first_search.hpp:345:3: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]โ
/usr/include/boost/graph/topological_sort.hpp:65:23: required from โvoid boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]โ
topo-sort1.cpp:42:61: required from here
/usr/include/boost/graph/graph_concepts.hpp:47:48: error: no type named โThereReallyIsNoMemberByThisNameInTโ in โclass std::vector<std::__cxx11::list<int> >โ
In file included from /usr/include/boost/graph/depth_first_search.hpp:21,
from /usr/include/boost/graph/topological_sort.hpp:16,
from topo-sort1.cpp:12:
/usr/include/boost/graph/named_function_params.hpp: In instantiation of โstatic boost::detail::map_maker_helper<false, Graph, ArgPack, Value, PM>::map_type boost::detail::map_maker_helper<false, Graph, ArgPack, Value, PM>::make_map(const Graph&, Value, const PM&, const ArgPack&) [with Graph = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Value = boost::default_color_type; PM = int; boost::detail::map_maker_helper<false, Graph, ArgPack, Value, PM>::map_type = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::remove_const<typename boost::detail::override_const_property_t<typename boost::parameter::value_type<ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type, boost::vertex_index_t, Graph, boost::detail::parameter_exists<ArgPack, boost::graph::keywords::tag::vertex_index_map>::value>::result_type>::type = boost::typed_identity_property_map<long unsigned int>]โ:
/usr/include/boost/graph/named_function_params.hpp:606:32: required from โstatic boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(const Graph&, const ArgPack&, ValueType) [with Graph = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; MapTag = boost::graph::keywords::tag::color_map; ValueType = boost::default_color_type; boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >]โ
/usr/include/boost/graph/named_function_params.hpp:621:70: required from โtypename boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type boost::detail::make_property_map_from_arg_pack_gen<MapTag, ValueType>::operator()(const Graph&, const ArgPack&) const [with Graph = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; MapTag = boost::graph::keywords::tag::color_map; ValueType = boost::default_color_type; typename boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >]โ
/usr/include/boost/graph/depth_first_search.hpp:337:80: required from โvoid boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]โ
/usr/include/boost/graph/depth_first_search.hpp:342:5: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]โ
/usr/include/boost/graph/depth_first_search.hpp:345:3: required from โtypename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]โ
/usr/include/boost/graph/topological_sort.hpp:65:23: required from โvoid boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]โ
topo-sort1.cpp:42:61: required from here
/usr/include/boost/graph/named_function_params.hpp:580:30: error: โnum_verticesโ was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
num_vertices(g),
~~~~~~~~~~~~^~~
In file included from topo-sort1.cpp:13:
/usr/include/boost/graph/vector_as_graph.hpp:188:3: note: โtemplate<class EdgeList, class Alloc> typename std::vector<_Tp, _Alloc>::size_type boost::num_vertices(const std::vector<_Tp, _Alloc>&)โ declared here, later in the translation unit
num_vertices(const std::vector<EdgeList, Alloc>& v)
^~~~~~~~~~~~
If you merge Graph to master, please let me know, as the changes include moving a header and so GraphParallel needs to be merged in tandem.
The BGL documentation says to see boost email discussions for further details. (https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/faq.html)
Does anyone know where I can find these discussions?
This line in two_bit_color_map.hpp
I believe should be changed to
std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, (unsigned char)0);
If my downstream project happens to include two_bit_color_map.hpp
I will have warning messages similar to the below, and it's because data
is unsigned char
yet it is being filled with 0, which is int
.
1>mycpp.cpp
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2903): error C2220: warning treated as error - no 'object' file generated
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2917): note: see reference to function template instantiation 'void std::_Fill_unchecked1<_FwdIt,_Ty>(_FwdIt,_FwdIt,const _Ty &,std::false_type)' being compiled
1> with
1> [
1> _FwdIt=unsigned char *,
1> _Ty=int
1> ]
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2925): note: see reference to function template instantiation 'void std::_Fill_unchecked<_Ty*,int>(_FwdIt,_FwdIt,const int &)' being compiled
1> with
1> [
1> _Ty=unsigned char,
1> _FwdIt=unsigned char *
1> ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/two_bit_color_map.hpp(61): note: see reference to function template instantiation 'void std::fill<T*,int>(_FwdIt,_FwdIt,const _Ty &)' being compiled
1> with
1> [
1> T=unsigned char,
1> _FwdIt=unsigned char *,
1> _Ty=int
1> ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/two_bit_color_map.hpp(57): note: while compiling class template member function 'boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<Property,unsigned __int64>>::two_bit_color_map(size_t,const IndexMap &)'
1> with
1> [
1> Property=CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,
1> IndexMap=boost::vec_adj_list_vertex_id_map<CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,unsigned __int64>
1> ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/two_bit_color_map.hpp(100): note: see reference to function template instantiation 'boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<Property,unsigned __int64>>::two_bit_color_map(size_t,const IndexMap &)' being compiled
1> with
1> [
1> Property=CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,
1> IndexMap=boost::vec_adj_list_vertex_id_map<CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,unsigned __int64>
1> ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/breadth_first_search.hpp(317): note: see reference to class template instantiation 'boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<Property,unsigned __int64>>' being compiled
1> with
1> [
1> Property=CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>
1> ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/breadth_first_search.hpp(345): note: see reference to function template instantiation 'void boost::detail::bfs_dispatch<boost::param_not_found>::apply<VertexListGraph,boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property>(VertexListGraph &,unsigned __int64,const boost::bgl_named_params<boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property> &,boost::param_not_found)' being compiled
1> with
1> [
1> VertexListGraph=MST_graph,
1> _Ty=PointVectorPair
1> ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\CGAL/mst_orient_normals.h(706): note: see reference to function template instantiation 'void boost::breadth_first_search<MST_graph,boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property>(const VertexListGraph &,unsigned __int64,const boost::bgl_named_params<boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property> &)' being compiled
1> with
1> [
1> _Ty=PointVectorPair,
1> VertexListGraph=MST_graph
1> ]
1>C:\Users\jasju\Desktop\test\mycpp.cpp(22): note: see reference to function template instantiation 'std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>> CGAL::mst_orient_normals<std::vector<_Ty,std::allocator<_Ty>>,CGAL::cgal_bgl_named_params<CGAL::Second_of_pair_property_map<PointVectorPair>,CGAL::internal_np::normal_t,CGAL::cgal_bgl_named_params<CGAL::First_of_pair_property_map<PointVectorPair>,CGAL::internal_np::point_t,boost::no_property>>>(PointRange &,unsigned int,const NamedParameters &)' being compiled
1> with
1> [
1> _Ty=PointVectorPair,
1> PointRange=std::vector<PointVectorPair,std::allocator<PointVectorPair>>,
1> NamedParameters=CGAL::cgal_bgl_named_params<CGAL::Second_of_pair_property_map<PointVectorPair>,CGAL::internal_np::normal_t,CGAL::cgal_bgl_named_params<CGAL::First_of_pair_property_map<PointVectorPair>,CGAL::internal_np::point_t,boost::no_property>>
1> ]
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2903): warning C4244: '=': conversion from 'const _Ty' to '_Ty', possible loss of data
1> with
1> [
1> _Ty=int
1> ]
1> and
1> [
1> _Ty=unsigned char
1> ]
1>Done building project "Example.vcxproj" -- FAILED.
For more details on how to recreate this see here
I see:
1>csr-example.cpp
1>d:\data\boost\boost\boost\graph\graphviz.hpp(265): error C2064: term does not evaluate to a function taking 1 arguments
1>d:\data\boost\boost\boost\graph\graphviz.hpp(291): note: see reference to function template instantiation 'void boost::write_graphviz<Graph,VertexPropertiesWriter,EdgePropertiesWriter,GraphPropertiesWriter,boost::typed_identity_property_map<size_t>>(std::ostream &,const Graph &,VertexPropertiesWriter,EdgePropertiesWriter,GraphPropertiesWriter,VertexID,boost::graph::detail::no_parameter)' being compiled
1> with
1> [
1> Graph=WebGraph,
1> VertexPropertiesWriter=boost::dynamic_properties,
1> EdgePropertiesWriter=std::string,
1> GraphPropertiesWriter=boost::typed_identity_property_map<size_t>,
1> VertexID=boost::typed_identity_property_map<size_t>
1> ]
1>d:\data\boost\boost\libs\graph\example\csr-example.cpp(58): note: see reference to function template instantiation 'void boost::write_graphviz<WebGraph,boost::dynamic_properties,std::string,boost::typed_identity_property_map<size_t>>(std::ostream &,const Graph &,VertexPropertiesWriter,EdgePropertiesWriter,GraphPropertiesWriter,boost::graph::detail::no_parameter)' being compiled
1> with
1> [
1> Graph=WebGraph,
1> VertexPropertiesWriter=boost::dynamic_properties,
1> EdgePropertiesWriter=std::string,
1> GraphPropertiesWriter=boost::typed_identity_property_map<size_t>
1> ]
1>d:\data\boost\boost\boost\graph\graphviz.hpp(271): error C2064: term does not evaluate to a function taking 2 arguments
1>d:\data\boost\boost\boost\graph\graphviz.hpp(277): error C2064: term does not evaluate to a function taking 2 arguments
Here is my code. My code is trying to find common subgraph between graph1 and graph2 with specific number of vertices.
#include <iostream>
#include <unordered_map>
#include <string>
#include <boost/algorithm/string.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp>
#include <boost/property_map/property_map.hpp>
using EdgeProperty = boost::property<boost::edge_name_t, unsigned int>;
using VertexProperty = boost::property<boost::vertex_name_t, unsigned int, boost::property<boost::vertex_index_t, int> >;
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperty, EdgeProperty>;
template<typename GraphFirst, typename GraphSecond>
struct generate_subgraph_callback {
generate_subgraph_callback(const GraphFirst &graph1, const GraphSecond &graph2,
std::vector <Graph> *result, int size) :
m_graph1(graph1), m_graph2(graph2), m_result(result), m_subgraph_size(size) {}
template<typename CorrespondenceMapFirstToSecond, typename CorrespondenceMapSecondToFirst>
bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
typename boost::graph_traits<GraphFirst>::vertices_size_type subgraph_size) {
// only when size equals input
if (subgraph_size != m_subgraph_size) {
return (true);
}
Graph subgraph;
std::vector<int> vertex_set; // vertex_set contains old graph id
std::unordered_map<int, int> map;
BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst){
// skip unmapped vertices
if (boost::get(correspondence_map_1_to_2, vertex1) != boost::graph_traits<GraphSecond>::null_vertex()) {
vertex_set.push_back(vertex1);
}
}
// reconstruct vertices
int index = 0;
for (auto it = vertex_set.begin(); it != vertex_set.end(); it++) {
boost::add_vertex(VertexProperty(boost::get(boost::vertex_name_t(), m_graph1, *it)), subgraph);
std::cout << *it << " " << get(boost::vertex_name_t(), m_graph1, *it) << " " << index << std::endl;
map[*it] = index;
index++;
}
// reconstruct edges
for (auto it = vertex_set.begin(); it != vertex_set.end(); it++) {
int index1 = map[*it];
for (auto _it = std::next(it); _it != vertex_set.end(); _it++) {
int index2 = map[*_it];
// check edge exists
if (boost::edge(*it, *_it, m_graph1).second) {
boost::add_edge(index1, index2,
boost::get(boost::edge_name_t(), m_graph1, boost::edge(*it, *_it, m_graph1).first), subgraph);
} else if(boost::edge(*_it, *it, m_graph1).second) {
boost::add_edge(index2, index1,
boost::get(boost::edge_name_t(), m_graph1, boost::edge(*_it, *it, m_graph1).first), subgraph);
}
}
}
(*m_result).push_back(subgraph);
return (true);
}
private:
const GraphFirst &m_graph1;
const GraphSecond &m_graph2;
std::vector <Graph> *m_result;
int m_subgraph_size;
};
std::vector <Graph> find_maximal_common_subgraphs_n_vertices(const Graph& g1, const Graph& g2, int n) {
// use boost::mcgregor_common_subgraphs
auto vertex_comp = boost::make_property_map_equivalent(boost::get(boost::vertex_name, g1), boost::get(boost::vertex_name, g2));
auto edge_comp = boost::make_property_map_equivalent(boost::get(boost::edge_name, g1), boost::get(boost::edge_name, g2));
std::vector <Graph> result;
// store each common subgraph into result
generate_subgraph_callback<Graph, Graph> callback(g1, g2, &result, n);
boost::mcgregor_common_subgraphs_maximum_unique(g1, g2, true, callback, boost::edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
return result;
}
int main(){
Graph graph1;
boost::add_vertex(VertexProperty(11), graph1);
boost::add_vertex(VertexProperty(12), graph1);
boost::add_vertex(VertexProperty(13), graph1);
boost::add_vertex(VertexProperty(10), graph1);
boost::add_edge(0, 1, EdgeProperty(1), graph1);
boost::add_edge(1, 2, EdgeProperty(1), graph1);
boost::add_edge(2, 3, EdgeProperty(1), graph1);
boost::add_edge(3, 1, EdgeProperty(1), graph1);
Graph graph2;
boost::add_vertex(VertexProperty(11), graph2);
boost::add_vertex(VertexProperty(12), graph2);
boost::add_vertex(VertexProperty(13), graph2);
boost::add_vertex(VertexProperty(10), graph2);
boost::add_edge(0, 1, EdgeProperty(1), graph2);
boost::add_edge(1, 2, EdgeProperty(1), graph2);
boost::add_edge(2, 3, EdgeProperty(1), graph2);
boost::add_edge(3, 0, EdgeProperty(1), graph2);
std::vector <Graph> result = find_maximal_common_subgraphs_n_vertices(graph1, graph2, 4);
std::cout << result.size() << std::endl;
return 0;
}
It is clear that 11->12->13->10 should be a common subgraph with 4 vertices while result size is 0. I looked at source code of function mcgregor_common_subgraphs and I believe the reason is in below code segment.
if (!is_undirected2)
{
// Search for edge from new to existing vertex (graph2)
BGL_FORALL_OUTEDGES_T(
new_vertex2, edge2, graph2, GraphSecond)
{
if (target(edge2, graph2) == existing_vertex2)
{
edge_from_new2 = edge2;
edge_from_new_exists2 = true;
break;
}
}
}
// Make sure edges from new to existing vertices are equivalent
if ((edge_from_new_exists1 != edge_from_new_exists2)
|| ((edge_from_new_exists1 && edge_from_new_exists2)
&& !edges_equivalent(edge_from_new1, edge_from_new2)))
{
return (false);
}
if ((edge_from_new_exists1 && edge_from_new_exists2)
|| (edge_to_new_exists1 && edge_to_new_exists2))
{
has_one_edge = true;
}
Here when subgraph is a graph containing nodes 11,12,13 and we want to extend node 10, mcgregor_common_subgraphs finds out there is an edge between 10 and 11 in subgraph2 while ther e is no edge between 10 and 11 in subgraph1. Hence can_extend_graph will return false. I believe the implementation of mcgregor_common_subgraphs now can only find subgraphs that appears "fully" in both graphs, which will miss many common subgraphs.
std::max_element contract required forward iterator. Graph library's uses this interface in betweenness_centrality_clustering on edge iterators, which according to boost iterator library are deduced as input iterators. This fails to build with libc++, which validates the category at compile time.
The easiest solution is to handcraft the for loop:
auto it = edges_iters.first;
auto it_max = it;
while (++it != edges_iters.second) {
if (cmp(*it_max, *it)) it_max = it;
}
// Here we assume graph is not empty and contains at least one edge.
edge_descriptor e = *it_max;
while trying to build the example labeled_graph.cpp I see:
1>d:\data\boost\boost\libs\graph\example\labeled_graph.cpp(61): error C2039: 'add_edge': is not a member of 'boost::labeled_graph<G,size_t,boost::defaultS>'
1>d:\data\boost\boost\libs\graph\example\labeled_graph.cpp(57): note: see declaration of 'boost::labeled_graph<G,size_t,boost::defaultS>'
I think it should be adjacent_vertices(), not adjacenct_vertices().
In file https://github.com/boostorg/graph/blob/develop/include/boost/graph/labeled_graph.hpp.
/** @name Adjacency Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::adjacency_iterator,
typename LABELED_GRAPH::adjacency_iterator >
adjacenct_vertices(
typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
return adjacent_vertices(v, g.graph());
}
//@}
Dijsktra's shortest paths takes as parameter UTIL/OUT a color_map. Which should be passed to and used by breadth first search.
However, the current implementation ignores the color_map, if provided, and always creates a default one.
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/dijkstra_shortest_paths.html
https://github.com/boostorg/graph/blob/develop/include/boost/graph/dijkstra_shortest_paths.hpp
Due to unclosed HTML tag the page reads: This graph is the undirected version(b,y))
I already fixed this and other errors on this page in #191
In order to keep track of which tests are taking how long, it'd be useful to see how long each one takes.
The following macros are missing a BOOST_ prefix, which is against Boost library guidelines:
./boost/graph/minimum_degree_ordering.hpp:#ifndef MINIMUM_DEGREE_ORDERING_HPP
./boost/graph/minimum_degree_ordering.hpp:#define MINIMUM_DEGREE_ORDERING_HPP
./boost/graph/minimum_degree_ordering.hpp:#endif // MINIMUM_DEGREE_ORDERING_HPP
./boost/graph/edmonds_karp_max_flow.hpp:#ifndef EDMONDS_KARP_MAX_FLOW_HPP
./boost/graph/edmonds_karp_max_flow.hpp:#define EDMONDS_KARP_MAX_FLOW_HPP
./boost/graph/edmonds_karp_max_flow.hpp:#endif // EDMONDS_KARP_MAX_FLOW_HPP
./boost/graph/adj_list_serialize.hpp:#ifndef ADJ_LIST_SERIALIZE_HPP
./boost/graph/adj_list_serialize.hpp:#define ADJ_LIST_SERIALIZE_HPP
./boost/graph/adj_list_serialize.hpp:#endif // ADJ_LIST_SERIALIZE_HPP
Expected outputs of graph/example/subgraph.expected and graph/example/subgraph.cpp is incorrect.
bidir_vec_remove_edge.cpp is currently not tested, and triggers a static assert if you try and build it. Any ideas anyone?
It appears that the basic template of the docs of edge_coloring
was taken from the docs of king_ordering
and modified accordingly. However, some parts of the docs still contain words from king_ordering
documentation, which must also be modified.
The following changes must be done:
In the Example section of the docs, the line See example/king_ordering.cpp
shall be changed to See example/edge_coloring.cpp
. The hypertext reference of the link is correct, though.
Also, there is the following comment in the HTML file of the docs:
<!-- King, I.P. An automatic reordering scheme for simultaneous equations derived from network analysis. Int. J. Numer. Methods Engrg. 2 (1970), 523-533 -->
which is also copied from king_ordering
. It should be replaced with the following comment:
<!-- Misra, J., & Gries, D. (1992). A constructive proof of Vizing's theorem. In Information Processing Letters. -->
The reference of this can be found here.
Some graphs cause maximum_weighted_matching() to segfault due to a stack overflow when unit weights are used.
Please see minimal example linked below which is a simple modification of the standard example from the library.
https://gist.github.com/count0/551867e10973d4b2dc047b8528908281
If I try to use a string as a label, the result is expected. If an integer, then the result is different than expected.
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
int main()
{
using namespace std;
cout << "add_vertex():\n";
{
using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, string>;
LabeledGraph g;
const auto vd1 = g.add_vertex("123");
const auto vd2 = g.add_vertex("123");
cout << " string:\n";
cout << " " << boolalpha << (vd1 == vd2) << endl;
}
{
using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, size_t>;
LabeledGraph g;
const auto vd1 = g.add_vertex(123);
const auto vd2 = g.add_vertex(123);
cout << " size_t:\n";
cout << " " << boolalpha << (vd1 == vd2) << endl;
}
cout << "insert_vertex():\n";
{
using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, string>;
LabeledGraph g;
cout << " string:\n";
cout << " " << boolalpha << g.insert_vertex("123").second << endl;
cout << " " << boolalpha << g.insert_vertex("123").second << endl;
}
{
using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, size_t>;
LabeledGraph g;
cout << " size_t:\n";
cout << " " << boolalpha << g.insert_vertex(123).second << endl;
cout << " " << boolalpha << g.insert_vertex(123).second << endl;
}
}
If I compile this code using the following command line, I get this result.
g++ prog.cc -Wall -Wextra -I/opt/wandbox/boost-1.71.0/gcc-head/include -std=gnu++2a
add_vertex():
string:
true
size_t:
false
insert_vertex():
string:
true
false
size_t:
true
true
In the lib documentation,
https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/boykov_kolmogorov_max_flow.html
the figure shows a white Source node and a black Sink node, whether it is previously written that:
the source and the sink are colored (source==black, sink==white)
This is confusing. Either change the picture or the code/doc.
IMO the source should be white and not black (i.e change the code and doc), but it would be too complicated to keep backward compatibility...
Prim's algorithm can NOT use Dijkstra' shortest paths algorithm to return the map of the predecessor, because Dijkstra's shortest path allows to create a shortest paths tree, that is a spanning tree (if all the nodes are connected) but not always a minimum spanning tree.
I suggest to do a new implementation of the algorithm.
In general, the two algorithms are different: Dijkstra minimizes the weights of the paths from the root to the other nodes, Prim minimizes the sum of the weights of the tree.
Here follow a simple example:
Consider a complete graph with 3 vertices: a, b, c
Now,
{a, b} = 2
{a, c} = 1
{b, c} = 1
A correct spanning tree, using Dijkstra, is:
The sum of the weights is {a, b} + {a, c} = 2 + 1 = 3.
However, Prim's algorthim (starting with a) would find this spanning tree, instead:
The sum of the weights this time is {a, c} + {b, c} = 1 + 1 = 2
The problem can be found in include/boost/graph/prim_minimum_spanning_tree.hpp.
Edit: there was a typo in the sum of the weights for Prim (wrong edge)
1>bucket_sorter.cpp
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(46): warning C4267: 'argument': conversion from 'size_t' to 'const int', possible loss of data
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(65): warning C4267: 'argument': conversion from 'size_t' to 'const int', possible loss of data
1>d:\data\boost\boost\boost\pending\bucket_sorter.hpp(58): error C3861: 'get': identifier not found
1>d:\data\boost\boost\boost\pending\bucket_sorter.hpp(58): note: 'get': function was not declared in the template definition context and can be found only via argument-dependent lookup in the instantiation context
1>d:\data\boost\boost\boost\pending\bucket_sorter.hpp(57): note: while compiling class template member function 'void boost::bucket_sorter<size_t,int,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,ID>::push(const int &)'
1> with
1> [
1> _Ty=size_t
1> ]
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(46): note: see reference to function template instantiation 'void boost::bucket_sorter<size_t,int,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,ID>::push(const int &)' being compiled
1> with
1> [
1> _Ty=size_t
1> ]
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(43): note: see reference to class template instantiation 'boost::bucket_sorter<size_t,int,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,ID>' being compiled
1> with
1> [
1> _Ty=size_t
1> ]
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.