February 2008 - Boost-users - lists.preview.boost.org

BGL: ColorMap for depth_first_search
by Christian Sturz 25 Feb '08

25 Feb '08

Hi, I want to use the depth_first_search algorithm. Since I need the DFS version where a start vertex is specified, I also have to define a ColorMap. That's the function I want to use: template <class Graph, class DFSVisitor, class ColorMap> void depth_first_search(const Graph& g, DFSVisitor vis, ColorMap color, typename graph_traits<Graph>::vertex_descriptor start) However, I'm not able to define a working ColorMap. Since the map is irrelevant for me, the default ColorMap would be fully sufficient. Could you give me a hint how to create it? And another short question. I want to iterate the graph backwards via DFS. Could I use the "reverse_graph adaptor" with: depth_first_search( boost::make_reverse_graph(G), visitor( vis ) ...)? Regards, Christian -- GMX startet ShortView.de. Hier findest Du Leute mit Deinen Interessen! Jetzt dabei sein: http://www.shortview.de/?mc=sv_ext_mf@gmx

1 0

Linking problem with read_graphviz
by Michaela Kedikova 25 Feb '08

25 Feb '08

Hello, I'm new to boost(I'm working with boost_1_34_1) and I have a problem with read_graphviz. I'm working with MSVC 8. I've already built all external libraries using bjam and link them to my project. I also built libbgl-viz.lib, which contains all the source files in libs/graph/src.(As it was suggested in a thread) But I still have a link-error when I try to compile the graphviz.cpp example. I've searched in the mailing-list for solutions of this problem, but I didn't find anything, which helped me. Now I hope that somebody could give me a hint, what the problem may be. (My suggestion is, whether there is a missing object in a library or there are some difficulties between boost1_34_1 and MSVC 8.0). I post the error message below: 1>test_graphviz.obj : error LNK2019: unresolved external symbol "void __cdecl boost::read_graphviz(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &,class boost::subgraph<class boost::adjacency_list<struct boost::vecS,struct boost::vecS,struct boost::undirectedS,struct boost::property<enum boost::vertex_attribute_t,class std::map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,struct std::less<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std::pair<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > > >,struct boost::no_property>,struct boost::property<enum boost::edge_attribute_t,class std::map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,struct std::less<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std::pair<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > > >,struct boost::property<enum boost::edge_index_t,int,struct boost::no_property> >,struct boost::property<enum boost::graph_graph_attribute_t,class std::map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,struct std::less<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std::pair<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > > >,struct boost::property<enum boost::graph_vertex_attribute_t,class std::map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,struct std::less<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std::pair<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > > >,struct boost::property<enum boost::graph_edge_attribute_t,class std::map<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,struct std::less<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >,class std::allocator<struct std::pair<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const ,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > > >,struct boost::property<enum boost::graph_name_t,class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,struct boost::no_property> > > >,struct boost::listS> > &)" (?read_graphviz@boost@@YAXABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@AAV?$subgraph@V?$adjacency_list@UvecS@boost@@U12@UundirectedS@2@U?$property@W4vertex_attribute_t@boost@@V?$map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@U?$less@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@@std@@@2@@std@@Uno_property@2@@2@U?$property@W4edge_attribute_t@boost@@V?$map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@U?$less@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@@std@@@2@@std@@U?$property@W4edge_index_t@boost@@HUno_property@2@@2@@2@U?$property@W4graph_graph_attribute_t@boost@@V?$map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@U?$less@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@ D@2@@std@@@2@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@@std@@@2@@std@@U?$property@W4graph_vertex_attribute_t@boost@@V?$map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@U?$less@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@@std@@@2@@std@@U?$property@W4graph_edge_attribute_t@boost@@V?$map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@U?$less@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V12@@std@@@2@@std@@U?$property@W4graph_name_t@boost@@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@Uno_property@2@@2@@2@@2@@2@UlistS@2@@boost@@@1@@Z) referenced in function _main 1>D:\Mihaela\Projects_Cpp\Test_Boost\Debug\Test_graphviz.exe : fatal error LNK1120: 1 unresolved externals Sorry for my bad english. Thanks in advance, Mishe __________________________________________________________ Sent from Yahoo! Mail. A Smarter Inbox. http://uk.docs.yahoo.com/nowyoucan.html

1 0

betweenness centrality
by ivanballatore＠libero.it 25 Feb '08

25 Feb '08

Hi, i'm an italian developper and i have a question about the function brandes_betweenness_centrality. I would know if it's possbile to run brandes_betweenness_centrality only on a subset of nodes of a graph, because the execution of the function on the entire graph is too long. I want to calculate the betweenness approximation starting from the value computed for this subset of vetexes. Sorry for my english(i'm italian...).

1 0

subgraph with vertex lists
by Boris Lau 25 Feb '08

25 Feb '08

Hello, I'm new to boost and a bit confused about how to choose the vertex list type. My graph has around 50.000, and will be pruned down to roughly 500, so I use clear_vertex and remove_vertex a lot. According to http://www.boost.org/libs/graph/doc/adjacency_list.html, this works well only with VL=listS, otherwise I cannot safely remove vertices. Is that true? Ok, let's assume for now I need to use VL=listS in order to be able to safely remove vertices. How can I use the subgraph adaptor? It seems to require the vertex_index property, so I tried this: typedef subgraph< adjacency_list<listS, listS, undirectedS, property<vertex_index_t, int>, property<edge_index_t, int> > > Graph; which gives me nasty errors. It does make sense, if adding vertex_index to listS does not work. I was surprised by this, because adding edge_index does do the job if I use EL=listS: typedef subgraph< adjacency_list<listS, vecS, undirectedS, property<vertex_index_t, int>, property<edge_index_t, int> > > Graph; So, back to the topic. I need to be able to remove vertices and edges, and I need to use subgraphs. What can I do? Thanks for any help, Boris

1 1

fusion library not in boost 1.34.1?
by Robert Dailey 25 Feb '08

25 Feb '08

Hi, I've been working out of the development branch for boost for a while and I always took for granted that fusion was part of the library. However, after downgrading back to 1.34.1, I notice it isn't in there. Is there a reason for this? How do I go about downloading a version of fusion that will work with 1.34.1? Thanks.

3 3

Building boost 1.34.1 with MSVC 8 (64-bit)
by Eric Woodruff 25 Feb '08

25 Feb '08

Hello, I hope John Maddock is reading this as he had some knowledge of the Intel compiler problem. Similar to the thread quoted below, I am getting the "Windows cannot open this file" dialog when trying to build boost using VC8 as 64-bit. (Doesn't have /this/ problem when I don't set address-model=64 or use the VC7.1 x86 compiler for 32-bit builds.) This is with boost-jam-3.1.16-1-ntx86. I've tried adding the full path to cl.exe in user-config.jam without success. For historical reasons, I am using an nmake Makefile (under a Cygwin environment) to fit the boost build into an existing build system. It essentially operates as follows: tar jxf boost_1_34_1.tar.bz2 echo using msvc : 8.0 : "C:/WINDDK/3790.1830/bin/win64/x86/amd64/cl.exe" ; > boost_1_34_1\tools\build\v2\user-config.jam echo using stlport : 5.1.5 : c:\cygwin\home\ewoodruff\build\trunk\winnt\amd64\x64-WINNT\TOOLS\usr\include\stlport c:\cygwin\home\ewoodruff\build\trunk\winnt\amd64\x64-WINNT\TOOLS\usr\lib ; >> boost_1_34_1\tools\build\v2\user-config.jam sed -ie 's,\\\\,/,g' boost_1_34_1\tools\build\v2\user-config.jam cd boost_1_34_1 && "c:\cygwin\home\ewoodruff\build\trunk\winnt\amd64\boost\boost-jam-3.1.16-1-ntx86\bjam.exe" "-q" "--toolset=msvc-8.0" "--prefix=c:\cygwin\home\ewoodruff\build\trunk\winnt\amd64\x64-WINNT\TOOLS" "runtime-link=shared" "link=static" "threading=multi" "stdlib=stlport-5.1.5" "address-model=64" "--without-python" "--without-wave" stage install Once the first directory leaf is created is when the .rcp file tries to get run. Here's the content of that file: $ cat bin.v2/libs/serialization/build/msvc-8.0/debug/address-model-64/link-static/stdlib-stlport-5.1.5/stdlib-stlport-5.1.5/threading-multi/basic_archive.obj.rsp "libs\serialization\src\basic_archive.cpp" -Fo"bin.v2\libs\serialization\build\msvc-8.0\debug\address-model-64\link-static\stdlib-stlport-5.1.5\stdlib-stlport-5.1.5\threading-multi\basic_archive.obj" -TP /Z7 /Od /Ob0 /W3 /GR /MDd /Zc:forScope /Zc:wchar_t /favor:blend /wd4675 /EHs /Gy -c -DBOOST_ALL_NO_LIB=1 -D_STLP_DEBUG=1 -D_STLP_DEBUG_UNINITIALIZED=1 -D_STLP_USE_DYNAMIC_LIB=1 "-I." "-Ic:\cygwin\home\ewoodruff\build\trunk\winnt\amd64\x64-WINNT\TOOLS\usr\include\stlport" I'm also curious, is stdlib-stlport-5.1.5 supposed to be in the path twice? Thanks in advance, Eric > > > *Subject:* [Boost-users] Building boost 1.34.1 > > > *From:* James Emerton > > > *Date:* 2007-08-31 18:08:46 > > ------------------------------------------------------------------------ > I'm having difficulties building boost 1.34.1 using the intel > toolchain. Once bjam tries to invoke the compiler, I get the "Windows > cannot open this file" dialog, where the file is an .obj.rsp file. > > It would appear that perhaps the compiler itself is not making it into > the command line, thus causing the system to try executing the .rsp > file directly. I am not having this problem if I use the msvc > toolchain. > > > Command to invoke the build: > bjam --toolset=intel-9.1 > Compiler: > Intel(R) C++ Compiler for 32-bit applications, Version 9.1 > Build 20060519Z > bjam: > Boost.Jam Version 3.1.14. OS=NT. > > > Some environment variables: > > ICPP_COMPILER91=C:\Program Files\Intel\Compiler\C++\9.1 > INTEL_BASE_MSVC_TOOLSET=vc-7_1 > INTEL_LICENSE_FILE=C:\Program Files\Common Files\Intel\Licenses > INTEL_PATH=C:\Program Files\Intel\Compiler\C++\9.1\Ia32 > INTEL_SHARED=C:\Program Files\Common Files\Intel\Shared Files > > I've run the iclvars batch script, icl.exe is on the path, and I've > used this environment to build boost 1.33 successfully. I've tried > various debug levels of bjam, and I haven't seen anything that makes a > problem obvious to me. > > Thanks > James > _______________________________________________ > Boost-users mailing list > Boost-<email removed> > http://lists.boost.org/mailman/listinfo.cgi/boost-users > > ------------------------------------------------------------------------ > > > *From:* John Maddock > > > *Date:* 2007-08-31 19:17:38 > > ------------------------------------------------------------------------ > James Emerton wrote: > /> I'm having difficulties building boost 1.34.1 using the intel/ > /> toolchain. Once bjam tries to invoke the compiler, I get the "Windows/ > /> cannot open this file" dialog, where the file is an .obj.rsp file./ > />/ > /> It would appear that perhaps the compiler itself is not making it into/ > /> the command line, thus causing the system to try executing the .rsp/ > /> file directly. I am not having this problem if I use the msvc/ > /> toolchain./ > > Yep, it's bug report already: http://zigzag.cs.msu.su/boost.build/ticket/137 > > It does work if you add an entry for intel to a user-config.jam in your HOME > directory, mine looks like: > > using intel-win : 9.1 : "c:/program > files/intel/compiler/c++/9.1/ia32/bin/icl.exe" ; > using intel-win : 10.0 : "c:/program > files/intel/compiler/c++/10.0.025/ia32/bin/icl.exe" ; > using intel-win : 8.1 : "c:/program > files/intel/cpp/compiler80/ia32/bin/icl.exe" ; > #using intel-win : 7 : "c:/program > files/intel/cpp/compiler70/ia32/bin/icl.exe" ; > #using intel-win : 6 : "c:/program > files/intel/cpp/compiler60/ia32/bin/icl.exe" ; > > See the Boost.Build docs for more info on setting this up. And of course in > most cases you can always build the source from your IDE should you prefer > :-) > > HTH, John. > > _______________________________________________ > Boost-users mailing list > Boost-<email removed> > http://lists.boost.org/mailman/listinfo.cgi/boost-users >

3 4

boost::crc32 - visual studio crt - bug?!
by gfsdgadas＠Safe-mail.net 24 Feb '08

24 Feb '08

I want to compute the Crc32 checksum of a bunch of bytes. To do so, I simply use crc_32_type and process_bytes. Unfortunately this does not work in debug mode. Visual Studio (2008) breaks at line 574 of crc.hpp. // Compare a byte to the remainder's highest byte static unsigned char index( value_type rem, unsigned char x ) { return x ^ rem; } Error message: Run-Time Check Failure #1 - A cast to a smaller data type has caused a loss of data. If this was intentional, you should mask the source of the cast with the appropriate bitmask. For example: char c = (i & 0xFF); Changing the code in this way will not affect the quality of the resulting optimized code. I do not like changing the boost source code, so what can I do to workaround this problem?

2 1

GPGPU
by Carlo Alberto Ferraris 24 Feb '08

24 Feb '08

Just a casual question: has anyone considered the possibility to write and include a GPGPU library in boost? CAF

3 3

[call_traits] call_traits<enum>::param_type is const reference
by Sergei Politov 23 Feb '08

23 Feb '08

As I can see, call_traits for enum types defines param_type as const reference. I cannot find a reason for it. It is possible to use is_enum to determine whether type is enum or not, and define param_type for enums similar to value_type. Could anybody describe the situation?

1 0

Re: [Boost-users] All orderings of boost::graph::topological_sort()
by Matan Nassau 23 Feb '08

23 Feb '08

Excuse me for the double-post: my previous post had a bad subject line... Thank you very much for your prompt reply, Stephen. On Fri, Feb 22, 2008 at 12:51, Stephen Nuchia wrote: > For any significant-sized input the number of orderings will be too > large to do anything useful with. At the moment my input consists of about 32 vertices, although I'd like not to count on it to remain this way. I can probably assume the number of nodes will remain in the order of magnitude of hundreds or less. I'm talking about a schedule generating program for an undergraduate student. It generates a schedule for a semester for a student, given some constraints (time of day, courses done already and so on) and the course dependency (this course must not be taken before that one and so on). I would very much like to support other complexities such as some courses may be taken while a certain dependent is being taken, while others must be taken before any of their dependents may be taken. But I leave such complexities as worries for future versions. For the time being, all I want is to be able to generate all the different schedules (i.e., all various topo sorts). Indeed, something like std::next_permutation() would make a lot of sense. It would be fast and flexible. My next task would then be to find an algorithm to quickly estimate the number of different orderings. :) > For an input small enough that the > set of feasible orderings will fit in memory I would simply generate all > permutations and screen for feasibility rather than attempting to create > an enumeration algorithm. I don't follow. Can I change the ordering of vertices without ruining the graph's integrity? How? Would this affect the toposort output? > Create a comparability matrix and use it to > prune the permutation tree, perhaps? N^2 bits doesn't sound > prohibitive. I don't follow... > This has probably been studied but I'm at work so I'll speculate. For > larger inputs with many constraints it may be worthwhile to create an > enumeration algorithm. > > For purposes of empirical testing of build-ordering systems it might be > sufficient to go into the algorithm and randomize the selection > processes whenever it makes arbitrary choices. This may or may not be > easily achieved by randomly pre-sorting the input, depending on the > internals of the algorithm. If the sort is stable that will work. That is the reason for my query on my OP in the first place. I don't quite understand how manipulate the input vertices of the depth_first_search(). For what I understand, depth_first_search() works on a set of start vertices (which have no incoming edges), and for each of these the algorith dives in to the depth of the vertex's tree. Permuting the order of these vertices would give me advance me a lot, but I don't know how to do that. > If there is enough interest to justify adding an efficient deterministic > enumerator for poset orders I'll write one. Graph-theoretical > algorithms are a fun way to spend the weekend :-) I personally think the topological_sort() algorithm begs for an algorithm that would allow iterating over all unique orderings. As I stated above, I think something of the sort of std::next_permutation() would make a lot of sense, especially because graph algorithms, and finding all different toposorts in particular, tend to be expensive operations. Simply asking for one ordering at a time gives a lot of flexibility to the user with the added benefit of efficiency and integration with the STL's way of doing things. -- Matan

2 1