- Boost - lists.boost.org

[BGL] Tarjan's offline LCA algorithm.
by Cromwell Enage 09 Apr '04

09 Apr '04

I know this was a couple of days overdue, but I'm still learning my way through CVS. If there's still an urgent need for the LCA algorithm, here it is: <http://groups.yahoo.com/group/boost/files/bgl_algo/tarjan_offline_lca.zip> The example program provides a straightforward way of using it. Known issues: * The graph needs to be directed or bidirectional, it must be a tree, and the user must provide the root. * I forgot to discuss what type of output was desired. As a "quick and dirty" approach I used a Boost.uBLAS matrix; if you have any ideas that could lead to better efficiency and genericity, please let me know. The documentation covers my approach in greater detail. * The disjoint sets parameter is available in the kitchen-sink version of the function but not in the default version; the object is strictly for utility purposes. The bgl_named_params class doesn't appear to provide the ability to include custom named parameters; for this reason, I haven't included a named-parameter variant. If you disagree, please let me know. * I tried implementing Tarjan's LCA using the builtin depth-first-search function and event visitor lists. The major stumbling block was my inability to execute any code during post-traversal of an edge. (The on_tree_edge event fires during pre-traversal, and neither the on_back_edge event nor the on_forward_or_cross_edge event would fire using DFS on the example graph.) So, in the future, I'd like to see an on_post_traversal event filter and a corresponding vis.post_traversal(edge,graph) function implemented, and I'm pretty sure other graph algorithms could use this feature, too. For the moment, the LCA algorithm runs its own recursive DFS, and the event visitor list parameter in the kitchen-sink function variant does nothing. BTW, one of the Java source files (the one with the Graph class) was missing, so it was necessary to restart from scratch. HTH Cromwell Enage __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

4 3

Regex ease-of-use ideas
by David Abrahams 09 Apr '04

09 Apr '04

I was just writing up a simple tutorial example; finding the subject in a set of email headers. Here's what I got: std::string line; boost::regex pat("^Subject: (Re: )?(.*)"); boost::smatch matches; while (std::cin) { std::getline(std::cin, line); if (boost::regex_match(line,matches, pat)) std::cout << matches[2]; } 1. There's no way to search a stream for a match because a regex requires bidirectional iterators, so I have to do this totally frustrating line-by-line search. I think Spirit has some kind of iterator that turns an input iterator into something forward by holding a cache of the data starting with the earliest copy of the original iterator. Could something like that be added? 2. Seems to me that if match objects could be converted to bool, we might be able to: std::string line; boost::regex pat("^Subject: (Re: )?(.*)"); while (std::cin) { std::getline(std::cin, line); if (boost::smatch m = boost::regex_match(line, pat)) std::cout << m[2]; } which would be much smoother to the touch. Are match objects expensive to construct? -- Dave Abrahams Boost Consulting www.boost-consulting.com

9 27

[boost-sandbox] [BGL] Random path and Tarjan's Offline LCA algorithms.
by Cromwell Enage 08 Apr '04

08 Apr '04

They're now in the Boost Sandbox CVS, hooray! Accordingly, I've deleted the corresponding archives from the Yahoogroups file vault. The loop_erased_random_paths function has been changed to take in a boost::random_number_generator (or equivalent class) rather than a random number generating engine. Unfortunately, the following bug prevents the example and test programs from working correctly: <http://sourceforge.net/tracker/index.php?func=detail&aid=911758&group_id=75…> In the meantime, I'll be studying an all-pairs LCA algorithm that I've recently stumbled upon for which matrix output may be better suited. Cromwell Enage __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

1 0

RE: [boost] Re: FC++ -- Formal Review Result
by Powell, Gary 08 Apr '04

08 Apr '04

>> Do you think there would be merit in starting over from scratch? >> With a new language, I mean. >Of course. But adoption and interoperability are difficult issues, >then. http://felix.sf.net has one interesting strategy. This is of course a similar approach that C++ did to usurp "C". Generate code in a language that the machine is likely to have a compiler for. Without doing this, the chances of a new language being adopted by businesses which have bizillions of euros invested an existing code base and trained engineers is nil, nada, squat. By doing this a small test project can be done on the side by a team and if the results are good, integrated into the rest of the company. (If poor those left on the project when its cancelled will be terminated and forced to look for employment under assumed names.) The key is having both a "compiler" and a "debugger" that understands both languages at the source level. The quotes are to indicate that an interpreted language is not ruled out. Anyone who tried to debug CFront with adb, understands what I'm referring to. Yours-who-nearly-started-programming-"C"-when-it-was-"B", -Gary-

1 0

[boost] [Boost-bugs] [ boost-Bugs-931852 ] in the config.hpp system, problem with macos.hpp
by SourceForge.net 08 Apr '04

08 Apr '04

Bugs item #931852, was opened at 2004-04-08 10:06 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=931852&group_i… Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Nobody/Anonymous (nobody) Assigned to: Nobody/Anonymous (nobody) Summary: in the config.hpp system, problem with macos.hpp Initial Comment: on MacOSX with a ProjectBuilder, the line # ifndef TARGET_CARBON # include <boost/config/posix_features.hpp> # endif does not work, because the posix_features are always activated, even with carbon targets. the guy probably wanted to do something like # ifndef __MACHO__ # include <boost/config/posix_features.hpp> # endif or something like that. that bug prevents the boost library to be used with ProjectBuilder's projects that uses Carbon. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=931852&group_i… ------------------------------------------------------- This SF.Net email is sponsored by: IBM Linux Tutorials Free Linux tutorial presented by Daniel Robbins, President and CEO of GenToo technologies. Learn everything from fundamentals to system administration.http://ads.osdn.com/?ad_id=1470&alloc_id=3638&op=click _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

Auto_link and BOOST_DYN_LINK
by Edward Diener 08 Apr '04

08 Apr '04

I know it is late to suggest a change but I think that the default when one links to the dynamic RTL should be that a dynamic link library is created, not a static library. My own experience is that creating a dynamic link library is the norm when linking to the dynamic RTL, creating a static library is the norm when linking to the static lib version of the RTL, and that following any other mixed setup seems to lead to problems at run-time, particularly when memory management is involved. Now I know that auto-link specifies it is an #error if one tries to create a dynamic link library, using BOOST_DYN_LINK, when one is using the static version of the RTL. I am wondering why this is any less of a problem than if one attempts to create a static library using the DLL version of the RTL. Despite the fact that I don't like either mixture, I would welcome an explanation of why one is allowable, and safe, and the other is not. But given that the latter is considered allowable and the former not, I would suggest, along with my beginning suggestion, that BOOST_DYN_LINK be removed and that BOOST_STATIC_LINK be added to coerce the creation of a static library when linking to the DLL version of the RTL.

3 4

regex lib: non-greedy repeats w/ match_posix
by Benzinger, Ralph 08 Apr '04

08 Apr '04

I noticed that the newest regex version no longer supports non-greedy repeats "+?" in match_posix mode. What was the rationale for this? Is it possible to re-enable non-greedy repeats? As far as I could test, it's not sufficient to modify the syntax check around regex_compile.hpp:1794; regex "a+?" would be valid but matches "aaa" on string "-aaa-" instead of "a". Ralph

2 1

Documentation improvement for boost::bind
by Edward Diener 07 Apr '04

07 Apr '04

In the first line of the next to last paragraph of the boost::bind deocumentation under the heading of "Using nested binds for function composition", it is stated: "Sometimes it is necessary not to evaluate the first argument, but not to evaluate some of the other arguments, even when they are nested bind subexpressions. " I believe this is confusing and that a much clearer explanation of what is meant would be: "Although the first argument is, by default, not evaluated, all other arguments are. Sometimes it is necessary not to evaluate arguments subsequent to the first, even when they are nested bind subexpressions."

2 3

Date-Time documentation link
by Edward Diener 07 Apr '04

07 Apr '04

In the Date-Time library documentation for 1.31, the link from Class day_clock takes me to the Construction From Clock section of the class Date. Is that correct ? I was expecting to be taken to documentation for class day_clock's constructors and member functions. Is this a way of saying that day_clock has only a default constructor and the member functions local_day() and universal_day() ?

2 3

Re: Tokenizer doc problems/confusion (?)
by David Abrahams 07 Apr '04

07 Apr '04

"John R. Bandela" <jbandela(a)ufl.edu> writes: > Thanks for the e-mail. > > The problem the char_separators not giving you the correct words and > counts is a bug. It was caused by the latest changes to > token_functions to speed up tokenizing non-input iterators. The > version in the boost 1.31 should work (it is the one prior to the > changes). I have also just fixed it in the CVS. Thanks! All the docs still show char_delimiters_separator as the default, though. > Having char_delimiters_separator as the default tokenizing function > was unintentional (ie it never got changed). OK. > As to simplifying the interface, I would really like to hear your ideas. 1. Allow "boost::use_default" for any of the template parameters 2. Supply a templated 1-argument ctor that constructs the start iterator from the argument and default constructs the end iterator then I could write: boost::tokenizer< boost::use_default, std::istreambuf_iterator<char> > t(std::cin); > As to why char_delimiters_separator was deprecated, char_delimiters ^^^^^^^^^^^^^^^ What's that? It's not in the doc. Do you mean char_separator? > was supposed to be a replacement for it, doing everything it did, > but providing the user with more control in dealing with empty > tokens. However, as you have brought up, it also has the unfortunate > problem that in its default construction of returning punctuation as > well as words and thus is not as simple to use. Why not just change that. > Perhaps the solution would be making a separate words_delimiter that > is hard-wired to return only words (ie characters separated by > either a space or a punctuation mark) and making that the default. That'd be OK with me. > As to why the mention of std::isspace and ispunct, I needed a default > behavior when the user does not want to provide all the space and > punctuation (it can be a somewhat long string). I also did not what to > hard-code it as a string so I used those functions instead. That doesn't demystify things for me. If you have an internal way to use functions to determine kept and dropped, why don't you give me a way to supply functions, too? -- Dave Abrahams Boost Consulting www.boost-consulting.com

2 4