August 2005 - Boost-users - lists.stage.boost.cppalliance.org

Boost Graph Library and Boehm Garbage Collector
by FBSL 08 Sep '08

08 Sep '08

Hello I am having trouble to garbage-collect adjacency_list<>. I have instanciated it with correctly garbage-collected vectors and lists (I have copied vecS and listS definitions, and added Boehm GC's default allocator so that they are garbage-collected). In my application I need to dynamically allocate many graphs, but it does not work, there is a (big) memory leak. Unfortunately, there is no template argument in adjacency_list<> to specify Boehm GC's allocator. Does anyone have a hint ? Snippet code "main.cpp" follows, compiled with Boost Graph Library 1.32, Boehm GC 6.4 and G++ 3.3.5, with command line : $ g++ -o main main.cpp -lgc -lgccpp -- #include <boost/graph/adjacency_list.hpp> #include <gc/gc_allocator.h> #include <gc/gc_cpp.h> #include <iostream> #include <vector> #include <list> using namespace std; using namespace boost; namespace boost { struct collected_vecS {}; struct collected_listS {}; template <class ValueType> struct container_gen<collected_vecS, ValueType> { typedef vector<ValueType,gc_allocator<ValueType> > type; }; template <class ValueType> struct container_gen<collected_listS, ValueType> { typedef list<ValueType,gc_allocator<ValueType> > type; }; template <> struct parallel_edge_traits<collected_vecS> { typedef allow_parallel_edge_tag type; }; template <> struct parallel_edge_traits<collected_listS> { typedef allow_parallel_edge_tag type; }; namespace detail { template <> struct is_random_access<collected_vecS> { enum { value = true }; typedef true_type type; }; } } typedef adjacency_list<collected_vecS, collected_vecS, directedS, no_property, no_property, no_property, collected_listS> graph; int main() { // leaks... while(true){ graph * g=new (UseGC) graph; for(unsigned int i=0; i<100; ++i){ add_vertex(*g); } for(unsigned int i=0; i<100; ++i){ for(unsigned int j=0; j<100; ++j){ add_edge(i,j,*g); } } } }

3 4

BGL: INTERNAL COMPILER ERROR in VC7.1
by Yariv Tal 10 Jun '07

10 Jun '07

This one was already posted by Nicholas Burlett awhile back (see http://lists.boost.org/MailArchives/boost-users/msg06534.php) but I have some new info that may help. The problem: ========= When compiling code that uses the boost.graph library the VC7.1 compiler shouts: c:\boost_1_32_0\boost\mpl\aux_\preprocessed\plain\apply_wrap.hpp(48) : fatal error C1001: INTERNAL COMPILER ERROR As Nicholas already noted, this seems to be due to some compiler problem with the boost.graph out_edge_iterators since it is caused by the following lines in my code: (FilteredGraphGenerator::FilteredGraph is a typedef of a boost::filtered_graph) typedef boost::graph_traits<FilteredGraphGenerator::FilteredGraph> ::out_edge_iterator oedge_iterator; oedge_iterator edgesItr, edgesEnd; boost::tie(edgesItr, edgesEnd) = boost::out_edges(itr->first, m_g.m_filteredGraph); while (edgesItr != edgesEnd) { // do anything! } In fact, it seems to be related to the operator!= between iterators (if the while loop is commented out it compiles). How ever, the error persists even after changing the operator!= to operator== : while (edgesItr == edgesEnd) { // do anything! } ========================================================================== Some findings: =========== * We used to use boost_1_30_0 and the code used to compile PERFECTLY. The problem only appeared after migrating to boost_1_32_0. * Calling directly to the "equal" function in iterator_core_access instead of the operator== works. typedef boost::graph_traits<FilteredGraphGenerator::FilteredGraph> ::out_edge_iterator oedge_iterator; oedge_iterator edgesItr, edgesEnd; boost::tie(edgesItr, edgesEnd) = boost::out_edges(itr->first,m_g.m_filteredGraph); while (boost::iterator_core_access::equal(edgesItr, edgesEnd, boost::mpl::true_())) { // do somthing } * The error message location is at the mpl::apply_wrap2 function. Any relation to the mpl::apply2 function used for declaring the operator== in the BOOST_ITERATOR_FACADE_INTEROP_HEAD macro? Have these functions changed since v1.30.0?

9 8

[BGL] how to actually search with DFS/BFS?
by martin f krafft 22 Nov '06

22 Nov '06

This may seem like a silly question, but how does one actually search with DFS or BFS? Say I want to find the first node for which a predicate returns true in a BFS traversal starting at node N... The function signatures don't have a parameter for "criteria" or "predicate", so I guess it's up for a Visitor to implement such a check. What is not clear to me is how the visitor functions can break out of the search once a condition is true. Thanks, -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus(a)madduck.net "information superhighway" is just an anagram for "i'm on a huge wispy rhino fart".

9 12

Building boost for 64-bit on AIX
by Patrik Jonsson 17 Aug '06

17 Aug '06

Hi, I'm trying to build boost (1.32.0) on an IBM SP2 under AIX5, using the 64-bit ABI. This is troublesome. I do: bjam "-sTOOLS=gcc" "-sGXX=g++ -maix64 -pthread" --prefix=$HOME --libdir=$HOME/lib64-gcc --includedir=$HOME/include-gcc install But it doesn't work. I get loads of errors like: gcc-Link-action bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true/libboost_date_time-gcc-d-1_32.so ld: 0711-738 ERROR: Input file bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true/greg_month.o: XCOFF32 object files are not allowed in 64-bit mode. collect2: ld returned 8 exit status set -e LIBPATH=bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true:$LIBPATH export LIBPATH "g++" -maix64 -pthread -g -fPIC -shared -o "bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true/libboost_date_time-gcc-d-1_32.so" "bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true/greg_month.o" "bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true/greg_weekday.o" "bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true/date_generators.o" ...failed gcc-Link-action bin/boost/libs/date_time/build/libboost_date_time.so/gcc/debug/shared-linkable-true/libboost_date_time-gcc-d-1_32.so... ...skipped <@boost!lib64-gcc>libboost_date_time-gcc-d-1_32.so for lack of <@boost!libs!date_time!build/libboost_date_time.so/gcc/debug/shared-linkable-true>libboost_date_time-gcc-d-1_32.so... It seems it's using -maix64 ok when trying to build the library, but not when compiling... Can anyone tell me what the proper way of building boost under these conditions are? Thanks, /Patrik Jonsson

5 16

case insensitive less_than string comparison
by Matthias Kaeppler 07 Mar '06

07 Mar '06

Hi, I am aware that string_algo has an if_iequal functor. Is there also an equivalent for a less-than comparison? I have to compare strings ignoring the case but taking locales into account. Right now I'm calling boost::algorithm::to_lower on two copies of the original strings. I'm not so sure if this is very efficient when I'm comparing thousands of strings. Here's the functor as it is now: struct FileLessNameA : std::binary_function<const File&,const File&,bool> { bool operator() (const File& lhs, const File& rhs) const { std::string path1( lhs.get_name().c_str() ); std::string path2( rhs.get_name().c_str() ); boost::algorithm::to_lower( path1 ); boost::algorithm::to_lower( path2 ); return path1 < path2; } }; Any suggestions for improvements appreciated :) Regards, Matthias -- Matthias Kaeppler

7 17

[date_time] problem adding negative number of months
by Guido Spahn 24 Oct '05

24 Oct '05

Hello, when adding a negative number of months to a date(y, m, d), an exception "Month number is out of range 1..12" is raised if the resulting month m2 belongs to a year y2 < y and m2 > m. For example date(2005, Jan, 1) + months(-1) fails date(2005, Feb, 1) + months(-1) doesn't fail date(2005, Feb, 1) + months(-2) fails date(2005, Feb, 1) + months(-12) doesn't fail date(2005, Feb, 1) + months(-13) doesn't fail date(2005, Feb, 1) + months(-14) fails I checked it only with release 1.33 using the appended code. There is no problem adding or substracting any positive number of months. Hopefully I didn't miss this topic in the mailing list archive. Thanks in advance, Guido #include <boost/date_time/gregorian/gregorian.hpp> int main() { using namespace boost::gregorian; date d(2005, May, 1); for (long m = 0; m >= -40; --m) { try { std::cerr << d << " + (" << m << "): "; std::cerr << d + months(m) << std::endl; } catch (std::exception& e) { std::cerr << "FAILED: " << e.what() << std::endl; } } return 0; }

3 3

[BGL] Help with Brandes' Betweenness
by Rui Carvalho 09 Sep '05

09 Sep '05

Hi, I'm trying to write code to compute Brandes' Betweenness Centrality for a very simple graph: a star. I'm doing this, as I haven't been able to find simple examples in the documentation [hint :)] for vecS,vecS graphs and still haven't grasped how edge property maps work. I've got it running if all I want is to compute vertex BC (see below, also attached), but can't get it to compute both vertex and edge BC. I'd appreciate any suggestions -perhaps my example (or something similar) could be corrected and included in the BGL? Thanks, Rui #include <iostream> // for std::dataout #include <utility> // for std::pair #include <boost/utility.hpp> // for boost::tie #include <boost/graph/graph_traits.hpp> // for boost::graph_traits #include <boost/graph/graph_utility.hpp> #include <boost/graph/betweenness_centrality.hpp>//for boost::brandes_betweenness_centrality #include <boost/graph/adjacency_list.hpp> using namespace boost; using namespace std; typedef adjacency_list < vecS, //Store out-edges vecS, //Store vertex set undirectedS, //the graph is undirected property<edge_index_t, int> > Graph; typedef graph_traits<Graph>::vertex_descriptor Vertex; typedef graph_traits<Graph>::vertex_iterator Vertex_Iter; typedef graph_traits<Graph>::edge_descriptor Edge; typedef graph_traits<Graph>::edge_iterator Edge_Iter; typedef property_map<Graph, vertex_name_t>::type Name_Map_t; typedef property_map<Graph, edge_index_t>::type Edge_Map_t; int main(int,char*[]) { int n_vrtx = 5; //Builds graph with vertices, but no edges Graph g_star(n_vrtx); //Add edges. Graph g_star is a star add_edge(vertex(0, g_star), vertex(4, g_star), g_star); add_edge(vertex(1, g_star), vertex(4, g_star), g_star); add_edge(vertex(2, g_star), vertex(4, g_star), g_star); add_edge(vertex(3, g_star), vertex(4, g_star), g_star); Vertex_Iter vertex_iterator_begin, vertex_iterator_end; std::vector<double> centrality(n_vrtx); brandes_betweenness_centrality(g_star, centrality_map(make_iterator_property_map(centrality.begin(), get(vertex_index, g_star),double())).vertex_index_map(get(vertex_index, g_star))); for ( tie(vertex_iterator_begin, vertex_iterator_end) = vertices(g_star); vertex_iterator_begin != vertex_iterator_end; ++vertex_iterator_begin) { cout << "Vertex: " << *vertex_iterator_begin <<"\tBC: "<< centrality[*vertex_iterator_begin] << endl; } }

2 2

[BGL] filtered_graph and null_vertex()
by Tiago de Paula Peixoto 06 Sep '05

06 Sep '05

Hello. Is the function graph_traits<G>::null_vertex() defined for G = filtered_graph? When I try to compile the following simple program: -------------------------------------------------------------- #include <boost/graph/adjacency_list.hpp> #include <boost/graph/filtered_graph.hpp> using namespace boost; int main() { typedef adjacency_list<vecS> graph_t; typedef filtered_graph<graph_t,keep_all> f_graph_t; graph_traits<f_graph_t>::vertex_descriptor v = graph_traits<f_graph_t>::null_vertex(); return 0; } -------------------------------------------------------------- I get the following error with GCC 4.0.1 and boost 1.33.0: /usr/include/boost/graph/graph_traits.hpp: In static member function ‘static typename boost::graph_traits<G>::vertex_descriptor boost::graph_traits<G>::null_vertex() [with G = main()::f_graph_t]’: filtered_test.cc:10: instantiated from here /usr/include/boost/graph/graph_traits.hpp:49: error: ‘null_vertex’ is not a member of ‘main()::f_graph_t’ Shouldn't null_vertex() just be defined to return the null_vertex() for the underlying graph, since the vertex descriptors are the same? Do I miss something? -- Tiago de Paula Peixoto <tiago(a)forked.de>

3 3

Multipartite or layered graph
by Nicola Vitacolonna 06 Sep '05

06 Sep '05

Hi, I need to implement a graph whose set of vertices is partitioned into a certain number of ordered subsets (called layers). Edges join vertices from a layer to the next one(s). A critical operation is the iteration over the nodes of a given layer. I think this can be implemented by adding a vertex property to each vertex, that specifies the layer each vertex belongs to. But this does not seem to me the most (time and space) efficient solution: in particular, how can I iterate over the nodes of a given layer without checking every node? I was wondering whether there is a better way to do the job: maybe, using a custom VertexList implemented using a vector for each layer (in this case, should I write my own functions to add/remove vertices? And should I write my own iterators?). Any other idea, or pointer to existing code (I am new to Boost)? Best regards Nicola Vitacolonna

2 1

[BGL] using biconnected_components with an exterior property map
by Greg Landrum 06 Sep '05

06 Sep '05

Hi, I'm trying to use the biconnected_components algorithm from v1.33 of the BGL in some code and I've encountered a problem that I just can't seem to get past. The algorithm requires a property map argument that's used to output which component each edge maps to; this is the argument that's giving me fits. I started with a simple-ish case derived from an example in the BGL docs: //------------------------------------------------------------------ namespace boost { struct edge_component_t { enum { num = 555 }; typedef edge_property_tag kind; } edge_component; typedef property< edge_component_t, std::size_t > edge_prop_t; } int main() { using namespace boost; typedef adjacency_list < vecS, vecS, undirectedS, no_property, edge_prop_t >graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_t; graph_t g(5); add_edge(0, 1, edge_prop_t(3), g); add_edge(1, 2, edge_prop_t(3), g); add_edge(0, 2, edge_prop_t(3), g); add_edge(2, 3, edge_prop_t(1), g); add_edge(3, 5, edge_prop_t(1), g); typedef property_map < graph_t, edge_component_t >::type edge_map_t; edge_map_t edge_map = get(edge_component, g); graph_traits<graph_t>::edge_iterator edge,endEdges; for(tie(edge,endEdges)=boost::edges(g); edge!=endEdges;++edge){ std::cout << " >Edge1: " << source(*edge,g) << "-" << target(*edge,g) << " <- " << edge_map[*edge] << std::endl; } edge_map_t components = get(edge_component, g); std::size_t num_comps = biconnected_components(g, components); for(tie(edge,endEdges)=boost::edges(g); edge!=endEdges;++edge){ std::cout << " >Edge2: " << source(*edge,g) << "-" << target(*edge,g) << " <- " << edge_map[*edge] << std::endl; } return 0; } //------------------------------------------------------------------ When I run this, I get reasonable results for the connected components, but here's what prints: >Edge1: 0-1 <- 3 >Edge1: 1-2 <- 3 >Edge1: 0-2 <- 3 >Edge1: 2-3 <- 1 >Edge1: 3-5 <- 1 >Edge2: 0-1 <- 2 >Edge2: 1-2 <- 2 >Edge2: 0-2 <- 2 >Edge2: 2-3 <- 1 >Edge2: 3-5 <- 0 Note that the graph's property map values for the edges have changed (Edge2 values vs Edge1 values). So calling biconnected_components() has modified the graph, even though the graph argument is const. This made me sad, but I figured that I should be able to work around it using an exterior property map. According to the docs: "The ComponentMap type must be a model of Writable Property Map. The value type shouch be an integer type, preferably the same as the edges_size_type of the graph. The key type must be the graph's edge descriptor type." So as my next experiment, I decided to attempt to use an associative property map matching these requirements. I tried to define components like this: //------------ typedef std::map< graph_traits<graph_t>::edge_descriptor, int > map_t; map_t base_map; associative_property_map< map_t > components(base_map); //------------ That doesn't compile, the definition of base_map generates an error whose explanation begins with: //---------------- C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\functional(139) : error C2784: 'bool std::operator <(const std::stack<_Ty,_Container> &,const std::stack<_Ty,_Container> &)' : could not deduce template argument for 'const std::stack<_Ty,_Container> &' from 'const boost::graph_traits<G>::edge_descriptor' with [ G=graph_t ] //---------------- My apologies for the horrible interaction between this message and gmail's line wrapping. If it's useful, I can send the entire error message as an attachment. I next tried to create some other kind of exterior property map, but the documentation for how to do this seems to be out of date. There's an explanation of this in the boost wiki at URL: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Documentatio… search for "random_access_iterator_property_map" So my question is: how can I make a call to biconnected_components in a manner that doesn't modify my graph (or any of its associated property maps)? In the event that it matters, I'm building these tests under win2k using visual c++ 7.1 and boost v1.33. -greg

4 7