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

Johnsons BGL implementation for undirected graphs correct?
by Jan de Ruiter 29 Jul '02

29 Jul '02

When I use the BGL johnsons_all_pairs_shortest_paths example (source below)on an undirected graph, some results are quite wrong. For example, the output shows that the distance between node 1 and 6 equals 36. The SP however (1-4-5-8-9-6) = 4+4+4+12+2 = 26. Is there something wrong with me or is the BGL implementation incorrect? Any ideas? Jan de Ruiter //Output 0 1 2 3 4 5 6 7 8 9 0 0 99 111 123 103 107 135 105 111 123 1 -99 0 12 24 4 8 36 6 12 24 2 -111 -12 0 12 -8 -4 24 -6 0 12 3 -123 -24 -12 0 -20 -16 12 -18 -12 0 4 -103 -4 8 20 0 4 32 2 8 20 5 -107 -8 4 16 -4 0 28 -2 4 16 6 -135 -36 -24 -12 -32 -28 0 -30 -24 -12 7 -105 -6 6 18 -2 2 30 0 6 18 8 -111 -12 0 12 -8 -4 24 -6 0 12 9 -123 -24 -12 0 -20 -16 12 -18 -12 0 ------------------------------------------------------------------------- //Source #include <boost/config.hpp> #include <fstream> #include <iostream> #include <vector> #include <iomanip> #include <boost/property_map.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graphviz.hpp> #include <boost/graph/johnson_all_pairs_shortest.hpp> int main() { using namespace boost; typedef adjacency_list<vecS, vecS, undirectedS, no_property, property< edge_weight_t, int, property< edge_weight2_t, int > > > Graph; const int V = 10; typedef std::pair < int, int >Edge; Edge edge_array[] = { Edge(0,1), Edge(1,2), Edge(2,3), Edge(1,4), Edge(2,5), Edge(3,6), Edge(4,5), Edge(5,6), Edge(4,7), Edge(5,8), Edge(6,9), Edge(7,8), Edge(8,9) }; const std::size_t E = sizeof(edge_array) / sizeof(Edge); Graph g(edge_array, edge_array + E, V); property_map < Graph, edge_weight_t >::type w = get(edge_weight, g); int weights[] = { 99, 12, 12, 4, 99, 12, 4, 99, 2, 4, 2, 99, 12 }; int *wp = weights; graph_traits < Graph >::edge_iterator e, e_end; for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) w[*e] = *wp++; std::vector < int >d(V, std::numeric_limits < int >::max()); int D[V][V]; johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0])); std::cout << std::setw(5) <<" "; for (int k = 0; k < 10; ++k) std::cout << std::setw(5) << k ; std::cout << std::endl; for (int i = 0; i < 10; ++i) { std::cout <<std::setw(5) << i ; for (int j = 0; j < 10; ++j) { std::cout << std::setw(5) << D[i][j] ; } std::cout << std::endl; } return 0; }

4 4

[BGL] Detection of cycles in graphs
by Erik Arner 29 Jul '02

29 Jul '02

This is a repost - I sent it last friday but it hasn't shown up, so I'll try again: Is there an algorithm implemented in BGL that detects whether a directed graph contains cycles or not? If not, what would be the best way to implement such an algorithm? Thanks, Erik

2 1

Pass through buffer
by Tom Howard 29 Jul '02

29 Jul '02

Hi, I'm wondering if someone can help me with the pass through buffer (basic_passthrubuf) that is part of more_io. >From what I can understand the pass though buffer passes 1 character at a time to (and from) the underlying stream buffer and I'm wondering what happens with flushes. In the code I'm working on (gzostreambuf which writes to an ostream) I need to know is overflow() is being called because there is no more room in the buffer I'm using or because of an explicit flush. In the later case I need to also flush the compression (Z_SYNC_FLUSH), but doing so all the time will degrade the compression performance plus increase the number of flushes to the underlying stream. This is particularly bad as the underlying stream in my case is a socket stream an the increased flushes breaks up the data into many small packets. Because of the software at the other end of the socket, data must be sent as one message unless it's over 8096 bytes. So basically I only want to flush the underlying stream if the gzostreambuf has been flushed (either by endl or flush). is this possible? My current workaround is to make sure the buffersize of my gzostreambuf is greater than or equal to the buffersize of the underlying stream, but I was hoping there was a neater solution and thats why I was looking at the pass through buffer. >From what I unbderstand, If I use the pass through buffer as part of my gzostreambuf, then flushing will not be passed to the underling streambuf at all. This means that data sent to the stream may be compressed, but result in no output for quite some time later and this sort of latency would be unacceptable in the software I'm working on (client-server multi-agent simulation). Cheers, Tom Howard

1 0

regex_search matches correctly but memory holder contains wrong value
by Anibal Jodorcovsky 29 Jul '02

29 Jul '02

Hi all, I have a small problem when trying out a regex that works ok with both jakarta (java code) and Perl. However, in boost::regex I get an extra space that's very weird. This is the code: #include <iostream> #include <string> #include <boost/regex.hpp> main() { static const boost::regex infileRedirection( "\\[(.+?)\\s*=\\s*(.+?)\\]" ); const string input = "[IN_FILE_REDIRECTION = STARTS_3]"; boost::cmatch what; if ( boost::regex_search( input, what, infileRedirection, boost::regbase::perl ) ) { cerr << "Matched! == input is (" << input << ")" << endl; string mySection; mySection.assign( what[1].first, what[1].second ); string newSectionName; newSectionName.assign( what[2].first, what[2].second ); cerr << "mySection is: --" << mySection << "--" << endl; cerr << "newSection is: --" << newSectionName << "--" << endl; } else { cerr << "Didn't match" << endl; } return 0; } And this is the output: [anibal@anibal ControlFile]$ ./a.out Matched! == input is ([IN_FILE_REDIRECTION = STARTS_3]) mySection is: --IN_FILE_REDIRECTION-- newSection is: -- STARTS_3-- Please note the extra space in the newSection. That should be STARTS_3 and not " STARTS_3". Why is it taking that space if the space itself is not in the () expression? Any help greatly appreciated, -Anibal

2 1

Compilation problem
by Sergey Belovolov 29 Jul '02

29 Jul '02

gcc version 2.95.3 20010315 (release). It came with OS (SunOS 5.8 x86). After when I compiled & installed bjam I came into boost root dir and give (as it suggessted in docs): bjam "-sTOOLS=gcc". It builds 3 library: libboost_regex.a, libboost_regex.so, libboost_thread.a (while bjam builds library libboost_thread.a it throws messages: " g++: unrecognized option '-pthreads' "). Then I copy them into some dir that included in LD_LIBRARY_PATH environment varyable and copy dir boost to /usr/include. Then I create file with contents: #include <boost/thread/mutex.hpp> main() { return 0; } and compile it with: g++ test.cpp. Results: In file included from /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/uti lity:31, from /usr/include/boost/config/select_stdlib_config.hpp:18, from /usr/include/boost/config.hpp:40, from /usr/include/boost/thread/mutex.hpp:15, from test.cpp:1: /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h: In function `bool rel_ops::operator !=(const _Tp &, const _Tp &)': /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h:37: template with C linkage /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h: In function `bool rel_ops::operator >(const _Tp &, const _Tp &)': /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h:42: template with C linkage /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h: In function `bool rel_ops::operator <=(const _Tp &, const _Tp &)': /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h:47: template with C linkage /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h: In function `bool rel_ops::operator >=(const _Tp &, const _Tp &)': /opt/sfw/lib/gcc-lib/i386-pc-solaris2.8/2.95.3/../../../../include/g++-3/stl _relops.h:52: template with C linkage and so on and so on... What's wrong? Why it says that STL templates use C linkage? Thanks for help in advance. Sergey Belovolov. b_sv(a)mail.ru SBelovolov(a)algorithm.aelita.com

1 0

Installation problems
by fauzia_sharmeen 28 Jul '02

28 Jul '02

Hi, After downloading and unzipping the Regex library with the -d option, I ran nmake -fvc6.mak on the command prompt.However, I am getting an error message saying "Variable MSVCDIR not set". I checked the VcVars32.bat file to verify that the variable MSVCDIR has been set properly. Any ideas/suggestions about what I am doing wrong would be most appreciated. Thanks, Fauzia

4 3

Iterator problem with adjacent_vertices
by EJ van Eijk 28 Jul '02

28 Jul '02

Hello, I'm currently implementing some algorithms for drawing graphs, using boost::graph. PropertyMaps e.a. are working like a charm, but for my algorithm I need to find the adjacent vertices. Now I've become stuck on the following: typedef boost::adjacency_list < boost::mapS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph; typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; class functor { ... void operator()(Vertex& v) { ... }; }; for_each(adjacent_vertices(u,g).first, adjacent_vertices(u,g).second, functor<Graph>(g)); complains about foo.cc:30: initialization of non-const reference type `Vertex &' foo.cc:30: from rvalue of type `unsigned int' But, when using vertices(g) instead of adjacent_vertices(v,g), the code compiles, and applies functor to each vertex. What am I missing? The documentation is quite thorough, but I'm lost at the moment... EJ

1 0

Re: [Boost-Users] XML
by dick.bridges＠tais.com 26 Jul '02

26 Jul '02

What you say is true. In fact, it's *STILL* true. In the meantime, Xerces has released version 1.7.0 and, most recently, version 2.0. I've been following the Xalan mail lists and comments from some of the developers suggest that co-ordination between the two groups could be better. This "thread" probably belongs on xalan-c-users(a)xml.apache.org. Mail me direct to continue. Albrecht Fritzsche <albrecht.fritzsche@tisc To: Boost-Users(a)yahoogroups.com ali-dsl.de> cc: Subject: Re: [Boost-Users] XML 07/26/2002 11:33 AM Please respond to Boost-Users dick.bridges(a)tais.com wrote: > Unfortunately, the Xerces and Xalan projects don't appear to > be all that well co-ordinated. Makes it difficult to stay both > current and compatible. Huh - why do you think that? Simply reading the FAQ gives me "The Xalan-C++ release notes includes information about the Xerces-C++ release with which the Xalan-C++ release has been coordinated and tested." and even the Readme says "Xalan-C++ version 1.3 has been tested with Xerces-C++ version 1.6.0. Each Xalan-C++ version 1.3 download includes the Xerces-C++ distribution for the specified platform." Curious Ali Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

1 0

RE: [Boost-Users] XML
by dick.bridges＠tais.com 26 Jul '02

26 Jul '02

Xerces is ok for xml+namespaces but if you want to use additional facilities (e.g., XPath, XSLT, etc.) you'll have to go to other packages like Xalan. Unfortunately, the Xerces and Xalan projects don't appear to be all that well co-ordinated. Makes it difficult to stay both current and compatible. It sure would be nice to have a "boost-level" C++ library for xml but I'm not sure we could sell the idea that it should be "part of" C++. Hope I'm wrong. schalk_cronje@na i.com To: Boost-Users(a)yahoogroups.com cc: 07/26/2002 10:14 Subject: RE: [Boost-Users] XML AM Please respond to Boost-Users > I'm writing an XML based project right now. I haven't been > able to find > any good, open source XML parser to incorporate into my > application, so I What's wrong with Xerces? Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

3 2

RE: [Boost-Users] Re: [boost] Iterator Adaptor Poll
by Mark Storer 26 Jul '02

26 Jul '02

May i recommend providing both the "hello world" grade example, and something more real-world... like that path token iterator you mentioned? --Mark Storer Software Engineer Cardiff Software #include <disclaimer> typedef std::disclaimer<Cardiff> Discard;

1 0