September 2005 - Boost - lists.boost.org

[filesystem] determine free space
by Simon Richter 09 Sep '05

09 Sep '05

Hi, I just ran across the problem of having to determine how much space was available for a new file that would end up at a certain path. I'd be willing to contribute such a function (convenience.hpp looks like a good place) for Unix, but it would have to be complemented by other OS dependent functions for the other architectures. Anyone interested? Simon

2 1

Re: [boost] [thread] Win32 call_once
by Greer, Joe 08 Sep '05

08 Sep '05

I have continued to think about the call_once() mechanism because many uses I can think of for it could require that it be called a lot. Therefore, I think we want the "normal" path to be as quick as possible. To that end, I was trying to come up with a way to use critical sections instead of named semaphores for the guard. I think I have managed that now, but it also occurs to me that we can test the flag up front to see if it has been set and if it has, we don't need to get any sort of guard. In the case that it hasn't, we can then acquire a guard (of some sort), re-test the flag (in case we have two threads running in parallel), and then execute the function. It looks a little uglier because of the double test, but it would execute faster because most of the time it would never have to get the guard. Hopefully there is something useful here. :) joe

2 1

Boost-Wiki: Hacked...
by Johannes Brunen 08 Sep '05

08 Sep '05

Hi, I just take a look at the Boost-Wiki: BoostGui. The links http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?TableViews http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?OutlineViews http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?TreeViews etc. are all hacked. With best regards Johannes ____________ Virus checked by G DATA AntiVirusKit Version: AVK 16.350 from 06.09.2005 Virus news: www.antiviruslab.com

6 6

[thread] synchronization objects of static storage duration
by Anthony Williams 08 Sep '05

08 Sep '05

Hi all, I've been thinking a lot about synchronization primitives, especially around call_once, but also around mutexes, semaphores and conditions. Ensuring that they are correctly initialized, safely, is a hard problem, especially if we try and allow them to be used both as objects with static storage duration, and with non-static storage duration, or as members of other classes. Firstly, objects with static storage duration must be completely initialized statically, and not require any dynamic initialization. This is because dynamic initialization is not thread safe in general, and exposes the object to potential race conditions on the initialization, unless an alternative synchronization mechanism is used to ensure thread safety. The POSIX spec gives a good example, relating to pthread_mutex_init: "Without static initialization, a self-initializing routine foo() might look as follows: static pthread_once_t foo_once = PTHREAD_ONCE_INIT; static pthread_mutex_t foo_mutex; void foo_init() { pthread_mutex_init(&foo_mutex, NULL); } void foo() { pthread_once(&foo_once, foo_init); pthread_mutex_lock(&foo_mutex); /* Do work. */ pthread_mutex_unlock(&foo_mutex); } With static initialization, the same routine could be coded as follows: static pthread_mutex_t foo_mutex = PTHREAD_MUTEX_INITIALIZER; void foo() { pthread_mutex_lock(&foo_mutex); /* Do work. */ pthread_mutex_unlock(&foo_mutex); }" This requires that the objects are PODs or aggregates of PODs, so that no constructors are run (which would be dynamic initialization); if zero-initialization is not satisfactory, then a static initializer akin to PTHREAD_MUTEX_INITIALIZER can then be used. Secondly, objects of non-static storage duration cannot assume anything about the underlying memory, so they must be initialized dynamically. If the same class type is to be used for both purposes, this cannot be with a constructor, so it must be with an initializer. Whether this is the same as the static initializer is another question. Thirdly, these requirements apply recursively to any class which contains a synchronization primitive as a member: if a class has a constructor, then it is not safe for static initialization. If it does not have a constructor, then it requires an initializer to ensure safe use as an object with non-static storage duration. For such a class with a constructor, the synchronization primitive member must therefore be initialized in the member-initialization list. This implies that there must be a suitable initializer provided, as an aggregate initializer which might suffice for standalone variables cannot be used for member initialization. This implies to me that we probably therefore want two versions of each synchronization primitive. The first is a POD, which is therefore safe for static initialization. The second is non-POD, and has an appropriate default constructor, which is therefore safe for non-static objects. Any object which contains a synchronization primitive as a member must therefore choose which version to use, and therefore limit its own use as a consequence. Section 3.6.2 of the C++ standard allows implementers leeway to statically initialize objects with the result of dynamic initialization if such initialization yields a constant value, and doesn't affect any other object. On specific compilers and platforms where we can be sure that the implementors have taken advantage of this leeway, we can possibly relax some of these guidelines. Also, some compilers and platforms guarantee that dynamic initialization of objects with static storage duration is thread-safe. On such platforms, it is therefore safe for synchronization primitives to be non-POD objects with appropriate constructors, under all circumstances. Anthony -- Anthony Williams Software Developer Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk

1 0

[ptr_container] Patch for iterator_test
by Markus Schöpflin 08 Sep '05

08 Sep '05

Attached is a patch which skips some tests for Tru64/CXX which does not yet conform to the resolution for DR#179. (See http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#179 for details.) Ok to commit? Markus Index: iterator_test.cpp =================================================================== RCS file: /cvsroot/boost/boost/libs/ptr_container/test/iterator_test.cpp,v retrieving revision 1.8 diff -u -w -r1.8 iterator_test.cpp --- iterator_test.cpp 15 Jun 2005 19:32:58 -0000 1.8 +++ iterator_test.cpp 8 Sep 2005 08:41:56 -0000 @@ -47,10 +47,15 @@ ptr_map<int,int>::iterator map_mutable_i = map.begin(); ptr_map<int,int>::const_iterator map_const_i = map.begin(); +#if !BOOST_WORKAROUND(__DECCXX_VER, BOOST_TESTED_AT(70190006)) + // This only works for library implementations which conform to the + // proposed resolution of the C++ Standard Library DR#179. See + // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#179. BOOST_CHECK( map_mutable_i == map_const_i ); BOOST_CHECK( ! ( map_mutable_i != map_const_i ) ); BOOST_CHECK( map_const_i == map_mutable_i ); BOOST_CHECK( ! ( map_const_i != map_mutable_i ) ); +#endif const ptr_map<int,int>& rmap = map; map_const_i = rmap.begin();

2 2

problem with modifying checked out files
by Arkadiy Vertleyb 08 Sep '05

08 Sep '05

Hi All, I am experiencing a strange problem with files checked out from the Boost CVS. The files are checked out as read-only, and even if I remove the read-only flag (attrib -R afile.hpp), I am not able to modify them -- access denied. Does this ring any bell or does it sound like some glitch related to my PC? Thanks, Arkadiy

4 8

[Boost-bugs] [ boost-Bugs-1284336 ] dijkstra_shortest_path doesn't scan the whole component
by SourceForge.net 08 Sep '05

08 Sep '05

Bugs item #1284336, was opened at 2005-09-07 22:24 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1284336&group_… Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Grégoire Dooms (dooms) Assigned to: Jeremy Siek (jsiek) Summary: dijkstra_shortest_path doesn't scan the whole component Initial Comment: Disjkstra Shortest path stops in the middle of the graph. I think this is because of a bug in relaxed_heap. This bug is present in boost 1.33 and boost cvs HEAD. It is however not present in debian boost-graph-dev version 1.32.0-6. I attach a source code which demonstrates the bug. It produces a dot file with the nodes labeled with distances from the source and the arcs labeled with their weight. The bug is present if some nodes have a 2147483647 label. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1284336&group_… ------------------------------------------------------- SF.Net email is Sponsored by the Better Software Conference & EXPO September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[BGL] brandes_betweenness_centrality failed on medium-size graphs
by Yu Huang 07 Sep '05

07 Sep '05

Hi all, I coded a program recursively cutting graphs based on brandes_betweenness_centrality. But the weird thing is that it succeeds on small graphs(<=8 vertices, <=15 edges) and large graphs(~3500 vertices, ~138,000edges). But failed on medium-size (~37-200 vertices, ~42-350 edges). The failed output is like this: no_of_vertices: 203 no_of_edges: 368 connectivity: 0.0179486 running brandes_betweenness_centrality... *** glibc detected *** double free or corruption (out): 0x080942d8 *** Aborted Actually, I can't say the it succeeds on large graph. I stopped it after ~45 brandes_betweenness_centrality() calls(because it took too long, over-night). But on medium-size ones, the first brandes_betweenness_centrality() is always ok. But failed quickly, mostly 2nd loop, some 3rd, even 5th. Only 0x080942d8 changed from run to run. Others remain same(Am i stupid to say this? of course it won't change). Well, i paste my core function here. The main idea is I remove the edge with max centrality and form a vector of clusters(graphs) from the ancestor graph's components (if after cut, the ancestor has >=2 components, otherwise keep cutting on the ancestor graph). void ClusterByEBC::cut_by_betweenness_centrality(Graph &graph, const int &size_cutoff, const float &conn_cutoff) /* *09-04-05 * cut the graph with the edge of maximum betweenness_centrality */ { int no_of_vertices = num_vertices(graph); int no_of_edges = num_edges(graph); #ifdef DEBUG std::cerr<<"no_of_vertices: "<<no_of_vertices<<std::endl; std::cerr<<"no_of_edges: "<<no_of_edges<<std::endl; #endif if (no_of_vertices>=size_cutoff) { float connectivity = 2.0*no_of_edges/(no_of_vertices*(no_of_vertices-1)); #ifdef DEBUG std::cerr<<"connectivity: "<<connectivity<<std::endl; #endif if (connectivity>=conn_cutoff) { #ifdef DEBUG std::cerr<<"good subgraph "<<std::endl; #endif good_subgraph_vector.push_back(graph); } else { vector<double> edge_centrality(no_of_edges); EdgeCentralityMap ec_map(edge_centrality.begin(), get(edge_index, graph)); //"make_iterator_property_map(edge_centrality.begin(), get(edge_index, subgraph), double())" also works. indirect_cmp<EdgeCentralityMap, std::less<centrality_type> > cmp(ec_map); #ifdef DEBUG std::cerr<<"running brandes_betweenness_centrality... "; #endif brandes_betweenness_centrality(graph, edge_centrality_map(ec_map)); #ifdef DEBUG std::cerr<<"done."<<std::endl; #endif edgeDescriptor e = *max_element(edges(graph).first, edges(graph).second, cmp); centrality_type max_centrality = get(ec_map, e); #ifdef DEBUG std::cerr<<"max_centrality is "<<max_centrality<<std::endl; #endif remove_edge(e, graph); #ifdef DEBUG std::cerr<<"after removal the subgraph has "<<num_edges(graph)<<" edges."<<std::endl; #endif std::vector<int> component(num_vertices(graph)); int no_of_components = connected_components(graph, &component[0]); if (no_of_components==1) //keep cutting { #ifdef DEBUG std::cerr<<"only one component, keep cutting "<<std::endl; #endif cut_by_betweenness_centrality(graph, size_cutoff, conn_cutoff); } else //first get the connected_components into a vector_sub_subgraph and cut them separately { #ifdef DEBUG std::cerr<<"get the connected_components into a vector_graph and cut them separately "<<std::endl; #endif std::vector<Graph> vector_graph = graph_components(graph, component, no_of_components); std::vector<Graph>::iterator g_iterator; for(g_iterator=vector_graph.begin();g_iterator!=vector_graph.end();++g_iterator) { cut_by_betweenness_centrality(*g_iterator, size_cutoff, conn_cutoff); } } } } #ifdef DEBUG else std::cerr<<"Bad graph, too small,"<<no_of_vertices<<"vertices"<<std::endl; #endif } This looks like a hard issue. I searched the mailing list and found one similar message, http://lists.boost.org/MailArchives/ublas/2005/08/0657.php (no one replied). Thanks, Yu

2 3

[BGL] maximum cardinality matching
by Aaron Windsor 07 Sep '05

07 Sep '05

Hello all, I've implemented an algorithm for computing a maximum cardinality matching in an undirected graph for the BGL. A matching in an undirected graph is a set of edges such that no two meet in a common vertex. A maximum cardinality matching has the maximum number of edges over all matchings in the graph. I uploaded the source, some tests, and documentation to the boost sandbox file vault under the directory "maximum_cardinality_matching." Any feedback would be appreciated. I developed and tested under gcc 3.3.3 on cygwin and currently don't have access to any other C++ compilers, so I'd be particularly interested in feedback about whether the tests compile and run correctly under other compilers. Thanks, Aaron Windsor

2 3

Re: [boost] [binary-int] pre-release available
by Scott Schurr 07 Sep '05

07 Sep '05

Greetings, Thanks for all the comments and ideas: Dave Gomboc suggests: nybbles<0011,1010,1100,0100>::value David Abrahams and Jeff Flinn noted that 'nibbles' is the common spelling they have seen. And, personally, I've always seen a 4-bit entity written as nibble. So possible syntaxes for the template based solution, in the order they have been suggested, might be: binary_int<0011,1010,1100,0100>::value bits<0011,1010,1100,0100>::value nybbles<0011,1010,1100,0100>::value nibbles<0011,1010,1100,0100>::value On a different note, Matt Calabrese lofted a preprocessor-based library: BOOST_BINARY_LITERAL( 101 0111 1010 0110 ) This looks way cool. I personally like the way the '::value' is not required. So, how does the boost community decide which of the proposals (template-based or preprocessor-based) to pursue? Thanks for your consideration. Scott Schurr

3 2