- Boost-users - lists.boost.org

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

Using boost::barrier dynamically
by Gonzalo Garramuño 23 Feb '08

23 Feb '08

I'm trying to have several threads synced with a boost::barrier. But I'm finding its design very limiting (or, more likely, my understanding of its use is too poor). I want to have a barrier created dynamically (based on some parameters that determine how many threads run). And I also want to be able to delete the barrier at any point in time (from a thread that does not wait on the barrier). I expect this to force all threads that are waiting on the barrier to continue (ie. send a notify_all). However, boost::barrier's destructor just does nothing, so I get a hang. What's the right way to achieve this? PS. On a separate note... is there any reason why all of boost primitives have their variables private? I really would find it pretty useful to sometimes be able to query, for example, the lock count of some objects. -- Gonzalo Garramuño ggarra(a)advancedsl.com.ar AMD4400 - ASUS48N-E GeForce7300GT Xubuntu Gutsy

1 0

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

23 Feb '08

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

1 0

All orderings of boost::graph::topological_sort()
by Matan Nassau 22 Feb '08

22 Feb '08

Hello, In implementing a dependency graph subsystem, one of the tasks is figuring out all the possible ways of traversing the graph with respect to the dependencies. boost::graph::topological_sort() looks like a reasonable place to start; however, topological_sort() only gives /one/ linear ordering, not all possible orderings. I digged into the code and found that the algorithm is in fact a call to depth_first_search with a custom visitor. The 0-in-degree vertices are not mentioned in the algorithm, and I suspect manipulating the order of these vertices would be a good start in generating different orderings. I also digged into the depth_first_search() code, but there too it doesn't seem to be straightforward to change the order in which those start-nodes are visited. I am also aware that even if I would find a way to change the order in which the 0-in-degree vertices are visited it will still not give me all the various orderings; I think that repeating the procedure with a bredth_first_search() will give me yet more different orderings, and with I'll have all the different orderings. I may have missed something obvious but I really don't know how to tackle the problem of generating various orderings. Any advice, please? Thank you! -- Matan

2 1