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

[BGL] algorithms, design
by Val Samko 05 Apr '04

05 Apr '04

Hi, I find BGL extremely useful and flexible, but I am surprised that only a small number of algorithms is included with the library, although, numerous useful algorithms are implemented and available in boost/libs/graph/example . For example, why is the edge_connectivity function only available in edge-connectivity.cpp, and is not present in the library itself? I understand that I can copy the implementation of this function into my program, but why not include it in BGL? Is there any particular reason for this? -- Val Samko http://val.digiways.com/

2 2

Spirit skip parser question.
by Jia Pu 05 Apr '04

05 Apr '04

I am trying to write a parser which skipps white space and C, Java style comments. To get familiar with spirit, I did some experiments, here is a question. First, I write a simple grammar to accept some non-white space chars. //////////////////////////////////////////////////////////////////////////// //// struct FOO_GRAMMAR : public grammar<FOO_GRAMMAR> { template <typename ScannerT> struct definition { typedef rule<ScannerT> rule_t; definition(ABNF_GRAMMAR const & self) { r_LETTER = range_p('a','z') | range_p('A','Z') | '.'; r = (+r_LETTER); } rule_t r, r_LETTER; rule_t const& start() const { return r; } }; }; //////////////////////////////////////////////////////////////////////////// //// I used FOO_GRAMMAR with space_p as skip parser: //////////////////////////////////////////////////////////////////////////// // FOO_GRAMMAR g; std::string line = "This is a test parser."; parse_info<> info = parse(line.begin(),line.end(), g, space_p); //////////////////////////////////////////////////////////////////////////// //// This works perfectly. Then, I tried to wrap the skip parser in a skip grammar, since eventually I need a more complicated parser. So I wrote the skip grammar as: //////////////////////////////////////////////////////////////////////////// /// struct SKIP_GRAMMAR : public grammar<SKIP_GRAMMAR> { template <typename ScannerT> struct definition { typedef rule<ScannerT> rule_t; definition(SKIP_GRAMMAR const & self) { rule_t r_SKIP = space_p; } rule_t r_SKIP; rule_t const& start() const { return r_SKIP; } }; }; ///////////////////////////////////////////////////////////////////////// I tried to parse the same sentence as before: /////////////////////////////////////////////////////////////////////////// FOO_GRAMMAR g; SKIP_GRAMMAR skip; std::string line = "This is a test parser."; parse_info<> info = parse(line.begin(),line.end(), g, skip); ////////////////////////////////////////////////////////////////////////// This time the parsing failed. Can anyone tell me why? I thought grammars are just like rules. And any suggestion on building a parser skipping certain pattern? I just can figure it out by reading the doc. Thank you. Jia (Jay) Pu Software Engineer LumenVox LLC ---------------------------------------------------------------------------- ------------ Anytime a linguist leaves the group the recognition rate goes up. --Fred Jelinek (then of the IBM speech group) (1988)

1 0

Unexpected behavior in filesystem
by Martin Merck 05 Apr '04

05 Apr '04

Hi, I was trying the demo code from the filesystem library (searching for a file using the directory iterator). I noticed a strange behavior of the code. In the path I was searching I had a symbolic link, which was pointing to an unexisting file. The program throws now a exception with the following reason: boost::filesystem::is_directory: "/home/merck/CVS/test": No such file or directory Here 'test' is a link to some non exisitng file. It seems logical that the exception is thrown, however I can't garantee that there will never be tangling sym-links on the system. I would prefer if the library would have a option not to follow symlinks or handel this situation by itself. Regards Martin oooooooooooooooooooooooooooooooooooooooooooooooooooooooo o Dr. Martin Merck o o Institut fuer Theoretische Physik und Astrophysik o o Am Hubland o o 97074 Wuerzburg o o Phone: +49 931 888 4933 Fax: +49 931 888 4603 o o Email: merck(a)astro.uni-wuerzburg.de o oooooooooooooooooooooooooooooooooooooooooooooooooooooooo

1 0

RE: [Boost-users] Re: about license
by Darryl Green 05 Apr '04

05 Apr '04

> -----Original Message----- > From: boost-users-bounces(a)lists.boost.org > [mailto:boost-users-bounces@lists.boost.org] On Behalf Of > David Abrahams > Sent: Sunday, 4 April 2004 2:18 PM > To: boost-users(a)lists.boost.org > Subject: [Boost-users] Re: about license > > This has been sitting in my "to be dealt with" pile for quite some > time, because I couldn't figure out what to do with it. > > "Darryl Green" <Darryl.Green(a)unitab.com.au> writes: > > > I've been trying to educate myself about the law in this area, > > with some help from Alexander Terekhov. I'm not at all convinced > > now that there is any derivative work produced by the compilation > > step > > I bet that's open to legal interpretation. Precisely. Thats what makes a trivial faq Q/A hard! > > > however this seems to make no difference to the result. > > Good. The intention of the license wording is to say that even if you > consider the compiled code a copy or a derivative work, the > requirement to embed a copy of the license doesn't apply to it. > > > It seems the compiled code is a translation of both works, > > I guess you mean the boost code and whatever it's compiled along with. > The latter could be nothing: there might only be boost code involved. > Anyway, can you cite something authoritative that gives compiled code > the status of a "translation" and not a "derivative work"? Actually, I'm not being careful enough with my words here - I should have said "mechanical translation". To quote from http://www.ipmall.info/hosted_resources/CopyrightCompendium/chapter_0300 .asp <quote> 306.02(a) Translations. A translation is a ren- -dering of a work from one language to another, as, for example, a work trans- -lated from Russian into French, or from German into English. However, trans- -literations and similar processes by which letters or sounds from one alpha- -bet are converted to another are not copyrightable since the conversion is merely a mechanical act. Thus, merely changing a work from the Cyrillic to the Roman alphabet would not be copyright- -able. </quote> The question is whether comiling source code is "merely a mechanical act". However, it seems reasonable to think that it is. I don't know how authoritative an answer you are looking for (presumably, in law that would need to be some sort of precedent) however Alexander did point me to the following discussion: http://www.crynwr.com/cgi-bin/ezmlm-cgi?3:mss:7659 http://www.crynwr.com/cgi-bin/ezmlm-cgi?3:mss:7663 http://www.crynwr.com/cgi-bin/ezmlm-cgi?3:mss:7679 http://www.crynwr.com/cgi-bin/ezmlm-cgi?3:mss:7680 It seems Rod Dixon at least (and he does cite some relevant material re. tests for originality) thinks that compilation doesn't produce a derivative work. Also, apparently the US copyright office thinks source code and object code are one and the same in at least some contexts - see: http://digital-law-online.info/lpdi1.0/treatise26.html <quote> VI.B. Source Code and Object Code ... Every computer program copyright case treats the copyright in the source code and the object code as equivalent... Even though source code and object code are distinct, it is still useful to maintain the concept that the source code and the object code are just different forms of the same copyrighted work. The Copyright Office regards the source code and object code as equivalent for purposes of registration... Where an applicant is unable or unwilling to deposit source code, he/she must state in writing that the work as deposited in object code contains copyrightable authorship. The Office will send a letter stating that registration has been made under its rule of doubt and warning that it has not determined the existence of copyrightable authorship. </quote> > > > agregated (a compilation) in some way then. I think whoever > > produces the compilation can license it however they like, > > subject to permission being granted by the authors of the > > original works to include their work in the compilation. > > I think the intent to grant that permission is made sufficiently > clear by the license text, don't you? No. Not so much because of the Boost license, but because of various other more exotic open source licenses such as the GPL in particular, changing the/my perception of what is "normal" or "expected" when it comes to copyright over software. I think it would be better spelt out clearly. However, I think at the end of the day the lawyers would figure it out as is - so the license meets the needs of lawyers at least. > > > I don't know if this is sufficiently clearly allowed by > > the wording of the boost license, though I think "use" > > must surely allow this for software source libs as there > > is no other way to "use" them. > > There are actually lots of ways to use them, but that is certainly *a* > use. Ok. > > > So the final answer is the same > > good. > > > but some of the questions and answers in between may be wrong. > > I don't know what _that_ means. Sorry - my earlier proposed FAQ Q/A might well be incorrect on some ponts of law but reaches the correct conclusion. > > > Have you received any feedback from lawyers about this? > > What is "this"? My earlier post containing the FAQ items, which you cced to the lawyers. I now understand the license sufficiently to use the code. I was hopeful that boost developers' time could be saved with a simple faq addition - but it my first attempt at that turns out (I think) to be innaccurate. I'm happy to put some time into correcting it, but ianal. If there is some lawyerly feedback I can use in correcting the FAQ proposal, I'm happy to do it. Beyond that, I don't want to waste more of your or the lawyers time on this. Regards Darryl Green. ########################################################################## This e-mail is for the use of the intended recipient(s) only. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not use, disclose or distribute this e-mail without the author's prior permission. We have taken precautions to minimise the risk of transmitting software viruses, but we advise you to carry out your own virus checks on any attachment to this message. We cannot accept liability for any loss or damage caused by software viruses. ##########################################################################

1 0

[BGL] johnson_all_pairs_shortest problem compiling
by Val Samko 04 Apr '04

04 Apr '04

Hi, Why doesn't the following code compile (VC++ 7.1, g++ 3.3.3, boost 1.31.0) ? ======================================================================== #include <boost/graph/adjacency_list.hpp> #include <boost/graph/johnson_all_pairs_shortest.hpp> int main() { using namespace boost; typedef adjacency_list<vecS, vecS, bidirectionalS, boost::property<boost::vertex_index_t, int, boost::property<boost::edge_weight_t, int> > > Graph; Graph g; int distance_matrix[100][100]; johnson_all_pairs_shortest_paths(g, distance_matrix); } ======================================================================== but it compiles, if we pass the edge weight map (composed from std::map<edge_descriptor, int>) as a named parameter to johnson_all_pairs_shortest_paths ? Also, why do johnson_all_pairs_shortest_paths(g, distance_matrix); and johnson_all_pairs_shortest_paths(g, distance_matrix, weight_map(get(vertex_index, g))); produce completely different compile time errors? Finally, is it possible to use johnson_all_pairs_shortest_paths with adjacency_list<mapS, mapS, ...> ? According to the documentation, this should be possible, but this just does not compile. -- Val Samko http://val.digiways.com/

2 2

[BGL] documentation problem
by Val Samko 04 Apr '04

04 Apr '04

Hi, Is it required for a readable property map to have operator[]? At least, that is not mentioned at http://www.boost.org/libs/property_map/ReadablePropertyMap.html , so I assume, operator[] is not required. At http://www.boost.org/libs/graph/doc/johnson_all_pairs_shortest.html it is documented that weight_map named parameter must be a model of a readable property map. At johnson_all_pairs_shortest.hpp, line 101 we have w[e2] = w1[*e]; which assumes that weight_map has operator []. Is the problem in the readable property map documentation, or in the johnson_all_pairs_shortest, or I am doing something wrong? -- Val Samko http://val.digiways.com

2 2

RE: [Boost-users] Re: about license
by Darryl Green 04 Apr '04

04 Apr '04

> -----Original Message----- > From: David Abrahams [mailto:dave@boost-consulting.com] > Sent: Tuesday, 2 March 2004 12:43 AM > > "Darryl Green" <Darryl.Green(a)unitab.com.au> writes: > > > I'm happy to provide a patch once I'm reasonably sure I > understand the > > license. I'm assuming an email discussion will be more > productive than > > patches in the meantime. I have one more question that I > have a proposed > > FAQ answer for, but my "answer" is based purely on what I think it > > should be, not an understanding of the law. I've been trying to educate myself about the law in this area, with some help from Alexander Terekhov. I'm not at all convinced now that there is any derivative work produced by the compilation step, however this seems to make no difference to the result. It seems the compiled code is a translation of both works, agregated (a compilation) in some way then. I think whoever produces the compilation can license it however they like, subject to permission being granted by the authors of the original works to include their work in the compilation. I don't know if this is sufficiently clearly allowed by the wording of the boost license, though I think "use" must surely allow this for software source libs as there is no other way to "use" them. So the final answer is the same - but some of the questions and answers in between may be wrong. Have you received any feedback from lawyers about this? Regards Darryl Green. ########################################################################## This e-mail is for the use of the intended recipient(s) only. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not use, disclose or distribute this e-mail without the author's prior permission. We have taken precautions to minimise the risk of transmitting software viruses, but we advise you to carry out your own virus checks on any attachment to this message. We cannot accept liability for any loss or damage caused by software viruses. ##########################################################################

2 1

[BGL] truncating dijkstra_shortest_paths
by Sven de Vries 03 Apr '04

03 Apr '04

Hi, in a given graph I want to determine whether between one (!) pair (u,v) of vertices there exists an u-v-path of length at most some given threshold and that path. I use dijkstra_shortest_paths(g,u, but to accelerate matters I would like to stop the computation as soon as the key of v becomes smaller than the threshold or v turns black. I couldn't find a hook of the dijkstra algorithm that could be used to achieve this. Do I really have to change the implementation of the dijkstra algorithm for this, or is there a better way? Thanks sven

2 1

how to package graph related data ???
by Gustavo Sánchez 02 Apr '04

02 Apr '04

Hi all, I'm developing a hardware test program with some class abstractions like resistor, diode, relay ... which I stick to the BGL graph structure in the edge properties. I so have some information associated with vertices, and the result is a set of data composed of the graph itself - an ajacency_list - the graph properties for edges and vertices and a couple of vectors for the abstractions. My problem is how can I manage all these data in an OO program. The method used in BGL examples (just declare all these in main ) is right just for that, but in a more complex object colaboration society I consider it to be simple and useless. I just use a class named GraphContainer to package all the elements, but I wonder if there is any other better aproach... class GraphContainer{ int nVertices; public: UGraph g; property_map<UGraph, vertex_index_t>::type id; property_map<UGraph, edge_name_t>::type name; property_map<UGraph, vertex_name_t>::type vname; std::map<string,boost::graph_traits<UGraph>::vertex_descriptor> vertx; // mapa vertices(string)--vertex_descriptor vector<Lampara> Lamparas; vector<Diodo> Diodos; vector<Switch> Switches; vector<Resistencia> Resistencias; vector<Bobina> Bobinas; // ---------- GraphContainer(); }; Thanks a lot... --------------------------------- Antivirus Filtros antispam 6 MB gratis ¿Todavía no tienes un correo inteligente?

1 0

Re: [boost] [BGL] forced client complexity
by Jeremy Siek 02 Apr '04

02 Apr '04

Hi, I too am dissatisfied with the complexity of many parts of the BGL... On Mar 31, 2004, at 4:48 AM, Provisional Dissonance wrote: > Is there any particular reason that a > simplified interface is not made available? Just a lack of time. The priority was placed on providing flexibility and efficiency so that the BGL components could handle any situation... that flexibility came at the price of complexity. I think a good next step would be to provide more special purpose components that are easier to use. > Perhaps a > container adapter could be packaged with the library > allowing a compromise of functionality and flexibility > for simplicity? Could you explain this "container adaptor" idea more. > #include <less_than_10_graph_headers> > ... > digraph<some_node_type,some_edge_context_type> g; > g << "vertex" << make_pair("vertex", > "implicit_vertex"); > g.add_edge("brother", "sister", "sibling"); > if(g.find(make_pair("brother", "sister"))) > related = true; Perhaps this is a good place to start. Could you explain each of the above lines of code. Then we can compare to an implementation in the current BGL and pinpoint problem areas. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek(a)osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________

3 6