- Boost-users - lists.boost.org

[BGL]: adjacency_list_io bug?
by Sebastian Weber 10 Apr '06

10 Apr '06

Hello everybody! I'm using adjacency_list_io to import my graphs from the disk: typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS > graph_t; graph_t wwwg; //string dataFile("www.bdat"); string dataFile("www_undirected.bdat"); cout << "importing www network from file \"" << dataFile << "\" ... "; ifstream wwwDatIn(dataFile.c_str()); wwwDatIn >> read( wwwg ); wwwDatIn.close(); This works nicely with g++ 3.3, but g++ 4.0 refuse to compile this code and chokes with an error message like /home/sebi/projects/diplom/src/boost_1_33_1/boost/graph/adjacency_list_io.hpp: In member function 'boost::GraphParser<Graph_t, VertexProperty, EdgeProperty, VertexPropertySubset, EdgePropertySubset>& boost::GraphParser<Graph_t, VertexProperty, EdgeProperty, VertexPropertySubset, EdgePropertySubset>::operator()(std::istream&) [with Graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, VertexProperty = boost::no_property, EdgeProperty = boost::no_property, VertexPropertySubset = boost::no_property, EdgePropertySubset = boost::no_property]': /home/sebi/projects/diplom/src/boost_1_33_1/boost/graph/adjacency_list_io.hpp:327: instantiated from 'std::istream& boost::operator>>(std::istream&, boost::GraphParser<Graph, VP, EP, VPS, EPS>) [with Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, VP = boost::no_property, EP = boost::no_property, VPS = boost::no_property, EPS = boost::no_property]' I have no clue where this comes from, but it seems to be some incompatibility between g++ 4.0 and adjacency_list_io. Would be nice if someone could enlighten me or fix it. Thanks! Sebastian My system: Ubuntu 5.10, Boost 1.33.1, anything else needed?

4 8

Regex Submatch Position Question
by admin＠geocodenet.com 10 Apr '06

10 Apr '06

Hi all, Quick question about the Boost::Regex library. Is there a way to identify, with sub-matches, where a match in the search string is made and the length of the match? For instance, with the following regular expression and search string: Regex ==> "(\d+)" Search String ==> "Give me 100 dollars or give me 2001 dollars." Is there a way to determine that the subexpression matched at positions 8 and 31 in the search string, and that the lengths of the matches were three and four characters? Thanks

4 5

[boost][bgl] kevin-bacon.cpp example
by Harsh Deshmane 10 Apr '06

10 Apr '06

Hello Doug, I am trying to create a custom visitor class, for bfs, which accumulates all predecessors (based on Doug Gregor's suggestion for finding all paths between 2 vertices) I compiled and ran this example from the examples dir. However, the output is not consistent with kevin_bacon.expected in the example dir. Output I get is listed below (top lines) $ a.out William Shatner has a Bacon number of 0 has a Bacon number of 1 Denise Richards has a Bacon number of 0 has a Bacon number of 0 Patrick Stewart has a Bacon number of 0 has a Bacon number of 0 Steve Martin has a Bacon number of 0 Gerard Depardieu has a Bacon number of 0 has a Bacon number of 0 Clint Howard has a Bacon number of 0 Sean Astin has a Bacon number of 0 ..... (basically, all values are zero) except the first. http://www.boost.org/libs/graph/example/kevin-bacon.cpp I am using boost version 1.33.0/x86_64/include/boost-1_33 gcc version 3.2.3 20030502 (Red Hat Linux 3.2.3-52) If possible, can someone please check whether the output you get is the correct one ? regards, -harsh

2 1

[iterator] joint_iterator?
by Shunsuke Sogame 10 Apr '06

10 Apr '06

Hi gurus, I compared Boost.MPL Views... http://www.boost.org/libs/mpl/doc/refmanual/views.html with Boost.Iterator adaptors... http://www.boost.org/libs/iterator/doc/index.html#specialized-adaptors I think joint_iterator seems missing from Boost.Iterator. Is such iterator impossible or prohibited by STL? -- Shunsuke Sogame

2 2

[BGL] bug in PLOD algorithm
by Johan Oudinet 10 Apr '06

10 Apr '06

Hi, I'm using Parrallel Boost Graph Library to generate some graphs and compute their pagerank. I found the PLOD algorithm and I'd like using it with bidirected graphs. But, the PLOD algorithm generates self_edges whereas I put allow_self_edges to false. I look at the code in plod_generator.hpp and found that the next(directed_tag) function never uses allow_self_edges boolean ! I think it's a bug... I suggest replace: current.second = x(*gen); with: do { current.second = x(*gen); } while (current.first == current.second && !allow_self_loops); Regards, -- Johan

2 1

[Graph] How to free memory allocated when constructing a graph?
by Olivier Delalleau 10 Apr '06

10 Apr '06

I am constructing a graph exactly the same way as in the spanning tree example here: http://www.boost.org/libs/graph/example/prim-example.cpp i.e. using a constructor of the kind Graph g(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes); where Graph is some kind of adjacency_list. In my application, edges is rather big (on the order of 1e7 elements). Problem: when this constructor is called, it allocates a huge amount of memory (I see this when I do a 'top' to monitor the memory usage while in gdb). And this memory is not freed when the graph is deleted (when it gets out of the scope, or, if I use a pointer instead, when I delete it explicitely). Is there a way to recover this memory? Any hint on how to make it use less memory? Thank you, Olivier

2 1

Re: [Boost-users] FW: adjacency_list remove_edge
by Sean Kelly 10 Apr '06

10 Apr '06

Hi Doug, here is the example code that works - XFlatGraph is a listS, listS adjacency_list. Note if I replace the remove edge expression with remove_edge(*iter, _graph) the edge is intermittently not removed thanks Sean XFlatGraph& graph = _flat_view->get_graph(); XFlatEdgePMap& edge_pmap = get(kFlatGraphEdgeProperty, graph); std::list<XFlatView::edge_descriptor> scheduled_for_removal; XFlatView::edge_iterator current, end; tie(current, end) = edges(graph); for(;current!=end;++current) { if(edge_pmap[*current]->get_impl()->isSimulationOnly()) { scheduled_for_removal.push_back(*current); } } // Remove edges marked as simualtion only scheduled_for_removal.unique(); for(std::list<XFlatView::edge_descriptor>::iterator iter = scheduled_for_removal.begin(); iter != scheduled_for_removal.end(); ++iter) { remove_edge(source(*iter, graph), target(*iter,graph), graph); } System Information: compiler info: Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86 Copyright (C) Microsoft Corporation 1984-2002. All rights reserved. Boost version 1-32 -----Original Message----- From: boost-users-bounces(a)lists.boost.org [ mailto:boost-users-bounces@lists.boost.org] On Behalf Of Doug Gregor Sent: Thursday, March 02, 2006 12:42 PM To: boost-users(a)lists.boost.org Subject: Re: [Boost-users] FW: adjacency_list remove_edge On Mar 1, 2006, at 6:33 PM, Sean Kelly wrote: > I have observed the following behavior using the remove_edge function > and am curious if anyone else has seen this. > > remove_edge(edge_descriptor, graph) // occasionally fails in a > seemingly indeterminant way > > remove_edge(source(edge_descriptor, graph), > target(edge_descriptor, graph), > graph) // works fine It sounds like either the edge_descriptor is getting invalidated or there is a bug somewhere in remove_edge. > The adjacency list I am using is listS listS, and this is not an issue > with invalid edge_iterators, i.e. I collect all the edge_descriptors > to be removed before removing them. Are you sure that there are no duplicate edge descriptors? > I can provide more detailed info upon request. We won't be able to help without more detailed information. Doug _______________________________________________ Boost-users mailing list Boost-users(a)lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

2 1

Shortest Path City map
by Jeroen Vanattenhoven 10 Apr '06

10 Apr '06

Hello, I'm just learning and reading about the graph theory and shortest path algorithms. For graph representation there are 3 possibilities: adjacency matrix for dense graphs, adjacency lists for sparse graphs and edge lists. The road network of a city map belongs to which category? I've also been reading that Dijkstra is applied to a directed graph. Calculating the shortest route in a city map implies an undirected graph (am I wrong?). So how can I do shortest path calculation of a city map the best way? Jeroen

2 1

[Graph] Very minor typo/doc-bug in bellman-ford example
by Greg Link 10 Apr '06

10 Apr '06

I'm not quite sure where to submit this, but the main boost.org site noted that bug reports are often best reported to mailing lists, so here goes. In the documentation for the Bellman-Ford algorithm, there is an example program (bellman-example.cpp) that contains the following 'main' function (snippet): main() { enum { u, v, x, y, z, N }; char name[] = { 'u', 'v', 'x', 'y', 'z' }; typedef std::pair < int, int >E; const int n_edges = 10; E edge_array[] = { E(u, y), E(u, x), E(u, v), E(v, u), E(x, y), E(x, v), E(y, v), E(y, z), E(z, u), E(z,x) }; ... Note that edge_array[] is of type "E", which of course, should be "Edge". The example doesn't work as listed, as such. - Greg Link

2 1

Using raph algorithm
by David Zweigenhaft 10 Apr '06

10 Apr '06

Does anyone know how to achieve the following: * find all the paths between 2 nodes ? Or, find the first N shortest paths between 2 nodes ? * find the shortest path using include/exclude constraints (passing through list of nodes) * BWY - am I using the correct mailing list ?

2 1