- Boost-users - lists.boost.org

lexical_cast problem
by shams 04 Aug '06

04 Aug '06

Hi, Here is a sample custom string class that I am tring to get working with lexical_cast but it gives me compile errors. Can you please see what I am doing wrong here. More explanation below. OTOH if I use a custom lexical_cast using wstringstream it works fine. // main.cpp #include <string> #include <iostream> #include "boost_1_33_1/boost/lexical_cast.hpp" using namespace std; class String : public wstring { public: String() { } String(const wchar_t *str) : wstring(str) { } String& operator=(const String& Rhs) { return static_cast<String&>(wstring::operator=(Rhs)); } }; // This is commented cause lexical_cast wants bool return value. #if 0 template<class OutputStream> OutputStream& operator<<(OutputStream &o, const String &s) { return o << s.c_str(); } #endif template<class OutputStream> bool operator<<(OutputStream &o, const String &s) { o << s.c_str(); return true; } // This is commented cause lexical_cast wants bool return value. #if 0 template<class InputStream> InputStream& operator>>(InputStream &i, String &s) { wstring ws; i >> ws; s.assign(ws); return i; } #endif template<class InputStream> bool operator>>(InputStream &i, String &s) { wstring ws; i >> ws; s.assign(ws); return true; } int main() { // This line causes errors both on MSVC and GCC. wcout << boost::lexical_cast<String>(10); // These lines DONT cause errors and work ok. String s = L"hello"; wcout << s; wcout << endl; wcin >> s; wcout << s; wcout << endl; return 0; }

1 0

Subject: Serialization, text_Xarchive Why doesn't work?
by tkachenkok＠gmx.de 04 Aug '06

04 Aug '06

I've tried to write my first application with Boost.Serialization library. Here is the part of code, where the boost::text_iarchive throws an exception "boost::archive::archive_exception" "what(): stream error": [code] enum Origin { UNKNOWN=0, MEASURED, AVERAGE }; class OTCValue { friend class boost::serialization::access; template<class Archive> void serialize(Archive & ar, const unsigned int version) { ar & m_value; ar & m_orig; } double m_value; Origin m_orig; ... }; ... const OTCValue val1=(*loaded.second.begin())->get_row(0)[0]; { std::ofstream ofs("test_serial.txt"); boost::archive::text_oarchive oa(ofs); oa << val1; } OTCValue val; { std::ifstream ifs("test_serial.txt"); boost::archive::text_iarchive ia(ifs); ia >> val; // here is this exceptions thrown } ... [/code] And here is a little bit different code, which works great: [code] enum Origin { UNKNOWN=0, MEASURED, AVERAGE }; class OTCValue { friend class boost::serialization::access; template<class Archive> void serialize(Archive & ar, const unsigned int version) { ar & m_value; ar & m_orig; } double m_value; Origin m_orig; ... }; ... const OTCValue val1(5.5, MEASURED); { std::ofstream ofs("test_serial.txt"); boost::archive::text_oarchive oa(ofs); oa << val1; } OTCValue val; { std::ifstream ifs("test_serial.txt"); boost::archive::text_iarchive ia(ifs); ia >> val; } ... [/code] What is the problem? The construction (*loaded.second.begin())->get_row(0)[0] returns an OTCValue . I have compiled the boost-1.33.1 from the sources (www.boost.org) The project I've made is under KDevelop 3.2.2 (initially consol "Hello World" application) Operating System: SuSe Linux 10.0 Compiler: gcc version 4.0.2 I hope, that I've gave enouph information. If not, ask what aou need, you are welcome. Best regards, and thanks to all! -- Echte DSL-Flatrate dauerhaft für 0,- Euro*. Nur noch kurze Zeit! "Feel free" mit GMX DSL: http://www.gmx.net/de/go/dsl

4 4

tsp 2-approximation using triangle inequality
by Matyas W Egyhazy 04 Aug '06

04 Aug '06

Hello, I recently implemented an approximation for the traveling salesperson using the boost graph library. The interface as well as the implementation are not polished and they require improvement, mostly due to the work being part of a school homework assignment. If anyone is interested, I would like outside comments before spending (or wasting, if no one is interested) effort to fix it up. I have attached the .h,a driver .cpp, and a sample input file. The driver program will produce output files that are viewable in a neato dot renderer. I have tested this only on VC++ 2005 (8.0) although I cannot think of any specific reason why it would not compile on other compilers. The approximation algorithm runs in polynomial time and solves the TSP problem with the worst possible solution producing a path twice as long as the optimal solution. More information can be found regarding the algorithm/heuristic on page 1028 in "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. A slightly different description can be found on Wikipedia: http://en.wikipedia.org/wiki/Traveling_salesperson_problem#Triangle_inequal… My implementation matches the Introduction to Algorithms description as I use a preorder walk of the MST without bothering to create an Euler tour. I believe the Euler tour part of the algorithm is only used to prove the limit on the length of the produced solution. Regards, Matt //tsp_2_approximation //Takes a sequence of simple_points and performs 2-approximation triangle inequality to //generate a solution for the traveling salesperson problem. //Outputs the graphs in dot format to passed ostream objects //Also returns the MST generated as part of the approximation and a predecessor map //for a tour #include <algorithm> #include <vector> #include <map> #include <string> #include <iostream> #include <complex> #include <boost/graph/graph_as_tree.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> #include <boost/graph/simple_point.hpp> #include <boost/graph/graphviz.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/graph_traits.hpp> template<typename Pt> std::istream& operator >> (std::istream& is, const boost::simple_point<Pt>& p) { return is >> boost::lexical_cast<std::string>(p.x) >> std::string(", ") >> boost::lexical_cast<std::string>(p.y); } template<typename Pt> std::ostream& operator << (std::ostream& os, const boost::simple_point<Pt>& p) { return os << boost::lexical_cast<std::string>(p.x) << std::string(",") << boost::lexical_cast<std::string>(p.y) << "!"; } //g is returned as the MST //preds is the predecessor map for the TSP approximation tour //the PositionMap is a coordinate map of the vertices represented as simple_points //the ostreams are optional, if they are provided the dot graphs are printed to them template<typename Graph, typename PositionMap, typename PredecessorMap> void tsp_2_approximation(Graph& g, const PositionMap& pos, PredecessorMap preds, std::ostream& pts_out = std::ostream(), std::ostream& mst_out = std::ostream(), std::ostream& tour_out = std::ostream()) { using namespace boost; using namespace std; typedef graph_traits<Graph>::vertex_iterator VertexItr; typedef graph_traits<Graph> GraphTraits; typedef property_map<Graph, vertex_index_t>::type IndexMap; typedef graph_traits<Graph>::vertex_descriptor Vertex; typedef iterator_property_map<vector<Vertex>::iterator, property_map<Graph, vertex_index_t>::type> ParentMap; typedef graph_as_tree<Graph, ParentMap> Tree; typedef tree_traits<Tree>::node_descriptor Node; typedef graph_traits <Graph>::edge_descriptor Edge; typedef vector<simple_point<double> > PositionVec; typedef iterator_property_map<PositionVec::iterator, property_map<Graph, vertex_index_t>::type> PositionMap; int cnt(0); property_map<Graph, vertex_name_t>::type name_map(get(vertex_name, g)); //setup name map for the vertices IndexMap index(get(vertex_index, g)); for (pair<VertexItr, VertexItr> vp(vertices(g)); vp.first != vp.second; ++vp.first) { cnt++; name_map[*(vp.first)] = lexical_cast<string>(index[*(vp.first)]); } //print point layout to dot format if (pts_out) { dynamic_properties dp; dp.property("pos", pos); dp.property("id", get(vertex_name, g)); write_graphviz(pts_out, g, dp, string("id")); } property_map<Graph, edge_weight_t>::type weight_map(get(edge_weight, g)); graph_traits<Graph>::edge_iterator ei, ei_end; for (int q(0); q < cnt; ++q) { for (int i(q); i < cnt; ++i) { if (q != i) { //Calculate distance double weight(sqrt(pow(static_cast<double>(pos[q].x - pos[i].x), 2.0) + pow(static_cast<double>(pos[i].y - pos[q].y), 2.0))); graph_traits<Graph>::edge_descriptor e; bool inserted; tie(e, inserted) = add_edge(q, i, g); weight_map[e] = weight; } } } index = get(vertex_index, g); //extract the mst using prim's minimum spanning tree algorithm vector<Vertex> p(num_vertices(g)); prim_minimum_spanning_tree(g, &p[0]); Graph mst(cnt); vector<Vertex> parent(num_vertices(mst)); Tree t(mst, 0, make_iterator_property_map(parent.begin(), get(vertex_index, mst))); property_map<Graph, edge_weight_t>::type mst_weight_map(get(edge_weight, mst)); //build mst graph using the predecessor map from prim's mst algorithm for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { Edge e(*ei); Vertex u(source(e, g)); Vertex v(target(e, g)); if (p[v] == u || p[u] == v) { add_edge(u, v, mst); } } name_map = get(vertex_name, mst); for (tie(ei, ei_end) = edges(mst); ei != ei_end; ++ei) { Edge e(*ei); Vertex u(source(e, g)); Vertex v(target(e, g)); double weight(sqrt(pow(static_cast<double>(pos[u].x - pos[v].x), 2.0) + pow(static_cast<double>(pos[u].y - pos[v].y), 2.0))); mst_weight_map[e] = weight; preds[v] = u; name_map[u] = lexical_cast<string>(u); name_map[v] = lexical_cast<string>(v); } //print mst in dot format if (mst_out) { dynamic_properties dp; dp.property("pos", pos); dp.property("label", get(edge_weight, mst)); dp.property("id", get(vertex_name, mst)); write_graphviz(mst_out, mst, dp, string("id")); } //create tour using a preorder traversal of the mst property_map<Graph, edge_weight_t>::type tour_weight_map(get(edge_weight, mst)); PreorderTraverser<Node, Tree> vis; traverse_tree_ref(0, t, vis); const vector<Node>& v(vis.getPath()); Graph tour(cnt); //print out tour in dot format for (vector<Node>::const_iterator itr(v.begin()); itr != v.end() - 1; ++itr) { Node s(*itr); Node d(*(itr + 1)); add_edge(s, d, tour); } add_edge(*(v.end() - 1), *(v.begin()), tour); name_map = get(vertex_name, tour); for (tie(ei, ei_end) = edges(tour); ei != ei_end; ++ei) { Edge e(*ei); Vertex u(source(e, g)); Vertex v(target(e, g)); double weight(sqrt(pow(static_cast<double>(pos[u].x - pos[v].x), 2.0) + pow(static_cast<double>(pos[u].y - pos[v].y), 2.0))); tour_weight_map[e] = weight; name_map[u] = lexical_cast<string>(u); name_map[v] = lexical_cast<string>(v); } if (tour_out) { dynamic_properties dp; dp.property("pos", pos); dp.property("label", get(edge_weight, tour)); dp.property("id", get(vertex_name, tour)); write_graphviz(tour_out, tour, dp, string("id")); } g = mst; } //Recursive function that traverses a tree with a custom visttor template <class Tree, class TreeVisitor> void traverse_tree_ref(typename boost::tree_traits<Tree>::node_descriptor v, Tree& t, TreeVisitor& visitor) { visitor.preorder(v, t); typename boost::tree_traits<Tree>::children_iterator i, end; tie(i, end) = children(v, t); if (i != end) { traverse_tree_ref(*i++, t, visitor); visitor.inorder(v, t); while (i != end) { traverse_tree_ref(*i++, t, visitor); } } else { visitor.inorder(v, t); } visitor.postorder(v, t); } //Keeps track of a preorder traversal of a tree template<typename Node, typename Tree> class PreorderTraverser { private: std::vector<Node> path_; public: void preorder(Node n, Tree& t) { path_.push_back(n); } void inorder(Node n, Tree& t) {} void postorder(Node, Tree& t) {} const std::vector<Node>& getPath() { return path_; } }; //Main test harness for the tsp_2_approximation solution generator #include <iostream> #include <utility> #include <vector> #include <fstream> #include <boost/lexical_cast.hpp> #include "tsp_2_approximation.h" int main(int,char*[]) { using namespace boost; using namespace std; typedef adjacency_list<vecS, vecS, directedS, property <vertex_name_t, string>, property <edge_weight_t, double > > Graph; typedef vector<simple_point<double> > PositionVec; typedef iterator_property_map<PositionVec::iterator, property_map<Graph, vertex_index_t>::type> PositionMap; ifstream fin("graph.txt"); if (!fin) { cerr << "To run this program properly please place a file called graph.txt" << endl << "into the current working directory." << endl << "Each line of this file should be a coordinate specifying the" << endl << "location of a vertex" << endl << "For example: " << endl << "1,2" << endl << "20,4" << endl << "15,7" << endl << endl << "The output of the program will be three DOT formatted files in the" << endl << "current working directory: " << endl << "pts.dot - Only displays the points as described in graph.txt" << endl << "mst.dot - Displays an MST for the points in graph.txt" << endl << "tour.dot - Displays the TSP 2-approximation triangle inequality tour " << endl << "for the points in graph.txt" << endl << endl << "These files should be viewed with a 'neato'" << "DOT graph viewer" << endl << "as it can handle forced coordinates" << endl; return -1; } ofstream ptsOut("pts.dot"); ofstream mstOut("mst.dot"); ofstream tourOut("tour.dot"); string line; PositionVec position_vec; int n(0); while (getline(fin, line)) { simple_point<double> vertex; size_t idx(line.find(",")); string xStr(line.substr(0, idx)); string yStr(line.substr(idx + 1, line.size() - idx)); vertex.x = lexical_cast<double>(xStr); vertex.y = lexical_cast<double>(yStr); position_vec.push_back(vertex); n++; } fin.close(); Graph g(n); PositionMap pos(position_vec.begin(), get(vertex_index, g)); vector<graph_traits<Graph>::vertex_descriptor> preds(n); tsp_2_approximation(g, pos, &preds.front(), ptsOut, mstOut, tourOut); return 0; } 1,2 2,4 10,20 45,20 15,1 17,20 20,25 30,20

3 2

[program_options] very long default values make formatting go nuts
by Andy Schlaikjer 03 Aug '06

03 Aug '06

Hi all, I have an option in my options_description which has a very long default value (an absolute pathname to a data file). When I print out the usage info via: cout << desc << endl; ..the formatting of the message is really bad; The long default value makes the option description text get squished to the far right: Allowed options: -h [ --help ] produce help message -v [ --version ] print version string -D [ --database-file ] arg (=/very/long/path) specify databas e filen ame Is there any way to affect the formatting of the description? Perhaps force any default value to be printed underneath the option itself, or not require the description text for all options align on the same column? Thanks, Andy

1 0

[Graph] float/double weights and brandes_betweenness_centrality
by Ioannis Filippis 03 Aug '06

03 Aug '06

Hi, I wonder whether float/double weights may cause a bug in brandes_betweenness_centrality. In the brandes_dijkstra_visitor, in the case where edge is not relaxed, there is an equality check if (d_w == combine(d_v, w_e)) in order to find if there is equally-short path from v to w. If d_w, d_v, w_e are float/doubles, isn't there gonna be a problem with the "=="? Thanks Ioannis

2 1

filtered graph with bundled properties
by moritz Hilger 03 Aug '06

03 Aug '06

hi, i hava a problem using bundled properties with filtered graph. i've modified the example from the filtered-graph page ( http://www.boost.org/libs/graph/doc/filtered_graph.html) to use edge properties and woul like to create a filter using these bundled properties, but am experiencing problems with the types of the property_map and/or filter. since i'm quite new to c++ and boost i would aprectiate any suggestin, thanks in advance i'm using gcc-3.3.5 and boost-1.34 moritz modified code: struct myEdge { int id; int weight; }; template <typename EdgeWeightMap> struct positive_edge_weight { positive_edge_weight() { } positive_edge_weight(EdgeWeightMap weight) : m_weight(weight) { } template <typename Edge> bool operator()(const Edge& e) const { return 0 < boost::get(m_weight, e); } EdgeWeightMap m_weight; }; int main() { using namespace boost; typedef adjacency_list<vecS, vecS, directedS, //no_property, property<edge_weight_t, int> > Graph; no_property, myEdge > Graph; typedef property_map<Graph, int myEdge::*>::type EdgeWeightMap; typedef graph_traits<Graph>::edge_iterator edge_iter_t; typedef filtered_graph<Graph,positive_edge_weight<EdgeWeightMap> > f_graph_t; typedef graph_traits<Graph>::edge_descriptor Edge; enum { A, B, C, D, E, N }; const char* name = "ABCDE"; Graph g(N); Edge e; bool ins; tie(e,ins)=add_edge(A, B, g); /.../ positive_edge_weight<EdgeWeightMap> filter(get(&myEdge::weight, g)); f_graph_t fg(g, filter); std::cout << "filtered edge set: "; print_edges(fg, name); std::cout << "filtered out-edges:" << std::endl; print_graph(fg, name); return 0; } g++ output: error: no matching function for call to ` boost::bundle_property_map<main()::Graph, boost::detail::edge_desc_impl<boost::directed_tag, size_t>, myEdge, int>:: bundle_property_map()' /homes/combi/Software/Boost/boost/graph/properties.hpp:330: error: candidates are: boost::bundle_property_map<main()::Graph, boost::detail::edge_desc_impl<boost::directed_tag, size_t>, myEdge, int>::bundle_property_map(const boost::bundle_property_map<main()::Graph, boost::detail::edge_desc_impl<boost::directed_tag, size_t>, myEdge, int>&) /homes/combi/Software/Boost/boost/graph/properties.hpp:336: error: boost::bundle_property_map<Graph, Descriptor, Bundle, T>::bundle_property_map(Graph*, T Bundle::*) [with Graph = main()::Graph, Descriptor = boost::detail::edge_desc_impl<boost::directed_tag, size_t>, Bundle = myEdge, T = int] -- /* ICQ 291996214 */ /* MSN moritz.hilger(a)gmail.com */ /* moe1234(a)jabber.ccc.de */ /* del.icio.us/new/moritz.hilger */

2 1

astar-cities.cpp internal compile error
by bringiton bringiton 03 Aug '06

03 Aug '06

Hi, I'm trying to compile the sample from astar-cities.cpp. I however get a INTERNAL COMPILER ERROR. I'm using ms vc++ 6. Can I assume the sample does not run on the old vc++ version? Anything I can do to get around this? Test5.cpp xxx\boost\random\lagged_fibonacci.hpp(81) : fatal error C1001: INTERNAL COMPILER ERROR (compiler file 'msc1.cpp', line 1794) Please choose the Technical Support command on the Visual C++ Help menu, or open the Technical Support help file for more information Generating Code... Error executing cl.exe. Test2.exe - 1 error(s), 1 warning(s)

3 2

[bgl documentation] corrections (?) and improvements to help new users
by David Baird 03 Aug '06

03 Aug '06

Hi! I'm a new user of the BGL. I've attached a couple patches to the BGL documentaion which I think will be very helpful to new users. For example, one of the websites, http://www.boost.org/libs/graph/doc/file_dependency_example.html seems to contain a simple, but confusing (for new users) error: Graph g(N, used_by, used_by + sizeof(used_by) / sizeof(Edge)); In boost-1.33.0, the correct line AFAICT is, Graph g(used_by, used_by + sizeof(used_by) / sizeof(Edge), N); I successfully tested the new instructions in the documentation (which the attached patches apply to) with boost-1.33.0 under Gentoo Linux. If this is the wrong list to post this, please direct me toward the correct place. -David

2 1

[BGL] traversing edges in the graph
by Alejandro Aragón 03 Aug '06

03 Aug '06

Hello, I'm working with undirected graphs and I was wondering if there is an algorithm that traverses all the edges in the graph in such a way that this task is optimized. That is, if you draw a graph with a pencil, the number of times that you should lift the tip of the pencil is minimized. Can anyone give me a hint on this? Thanks, Alex

2 1

[bgl] user defined vertex_descriptor?
by timblech 03 Aug '06

03 Aug '06

hi all, i'm curious, if it's possible to change the type, that a graph uses as vertex_descriptor... i went through the examples, where usually int values are used, which seems to be the default ... for my application, i'd like to use a class pointer as vertex_descriptor, though... the problem i had with property map is, that i was only able to look up a property by vertex_descriptor, but not the other way round... it's possibly only a problem caused by my limited knowledge of the bgl, but it would be very nice, if someone could enlighten me. thanks in advance ... tim -- View this message in context: http://www.nabble.com/-bgl--user-defined-vertex_descriptor--tf2008709.html#… Sent from the Boost - Users forum at Nabble.com.

2 1