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

[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

cvs activity
by Serge Skorokhodov 10 Apr '06

10 Apr '06

Hi, Whenever I try to update boost source tree from sf.net, I see no changes. Is it just a low activity period or I missed the change of the settings? TIA -- Serge

2 1

(no subject)
by Karim Bakir 10 Apr '06

10 Apr '06

Hi , I have a problem, I can' use boost multi array as private member, I have the mistake: "unexpected extents" I can only return a boost multi array in my function Thanks // KOKO.h: interface for the KOKO class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_KOKO_H__3E4A2230_0446_43C2_BD69_6FF9C2614C02__INCLUDED_) #define AFX_KOKO_H__3E4A2230_0446_43C2_BD69_6FF9C2614C02__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "boost/multi_array.hpp" #include <cassert> using namespace std; using namespace boost; class KOKO { typedef boost::multi_array<double,3> array_type_3dd; public: KOKO(); virtual ~KOKO(); boost::multi_array<double,3>MiseEnFormeMatrice3D(vector<double>data,int nbJourSimule, int na, int nbEnergie); private: int d1; int d2; int d3; array_type_3d myvector(boost::extents[d1][d2][d3]); }; #endif // !defined(AFX_KOKO_H__3E4A2230_0446_43C2_BD69_6FF9C2614C02__INCLUDED_) --------------------------------- Nouveau : téléphonez moins cher avec Yahoo! Messenger ! Découvez les tarifs exceptionnels pour appeler la France et l'international.Téléchargez la version beta.

6 6

[BGL] Survivability Network Design Problem
by Alejandro Aragón 10 Apr '06

10 Apr '06

Hello everybody, I was wondering if anybody had to implement the SNDP problem using graphs. Is there anything in the boost library that deals with this problem? In the SNDP we have to design a graph having certain degree of redundancy (cycles in the graph) so if you remove one edge, then you can still reach every part in the graph. Stated in a different way, you should be able to have different paths between two vertices in the graph. So far I have seen only algorithms to deal with minimum spanning trees. I appreciate anything related to this problem. Alejandro Aragon

2 1

Selective depth-first search in a graph
by Anatoli Sakhnik 10 Apr '06

10 Apr '06

Hello, boost users! Is there a simple way to perform a selective depth-first search in a graph, so that I could choose edges to traverse the graph? For example, let's assume I can walk through an edge, only if its weight is greater than 0. How could I reveal all reachable vertices? It worth pointing out that the real availability condition is a little bit more complicated, but easity can be revealed from edge's inner properties. Thank you in advance! -- Anatoli Sakhnik

2 1

Boost and CPAN and CodeProject
by Lynn Allan 10 Apr '06

10 Apr '06

From: "Eric Niebler" <eric(a)boost-consulting.com> > evening, and he asked why C++ didn't have the equivalent of Perl's CPAN > -- that is, a huge repository of useful code to which anybody can > submit. No releases. No quality assurance. No reviews. Survival of the > fittest. Here's a wacky thought: can we turn boost-sandbox into CBAN > (the Comprehensive Boost Archive Network), and cherry-pick the best > libraries from CBAN for inclusion in boost? If anybody could make > something like this fly, it's boost. We'd need to look closely at the > CPAN model to find out why it's successful. Something this boost newbie would find valuable would be the equivalent of codeproject.com (or a Boost section within codeproject ... there is a section for STL). http://www.codeproject.com/vcpp/stl/ This might be yet another repository for code examples and "best practices" that are "peer reviewed" ... and there is certainly as element of "survival of the fittest".

1 0