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

performance issue with graph edge removal
by Feldman, Yulik 22 Jul '05

22 Jul '05

Hi, Our project has recently run into severe performance issue with remove_edge() function of Boost graph. In our particular case, we use adjacency list specialized as: typedef adjacency_list< listS, vecS, bidirectionalS, CdfgNodeProperty, CdfgEdgeProperty> CdfgType; At some point in the flow, we need to remove great amount of edges from the graph, an amount comparable to the total number of edges in the graph. Unfortunately, since the complexity of removal of each edge is about O(E/V) the complexity of removal of all edges is about O(E * E/V). This appears to be too much, when the number of edges is big. What is actually interesting about this situation, is that I see no way to remove all edges (let's say we need to remove all edges) with any Boost function and with any adjacency list specialization in O(E) complexity, not necessarily the one we're currently using. The O(E/V) complexity of the remove_edge() comes from the fact that there is a need to remove the edge from in/out edge lists of the vertices connected by the edge. Even though I know I will not need any of these lists after all edges are removed, remove_edge() doesn't know that, so it is doing the "extra" work of updating the lists one-by-one. Moreover, in case of edge lists such as vector/list/multiset, i.e. containers that allow parallel edges in the graph, the search is linear in the size of containers (resulting in O(E/V) complexity of the operation). The question is what can be done, in any way, to do this "simple" operation of removing all edges of the graph in "more reasonable" complexity O(E) instead of O(E * E/V)? It doesn't help to try to remove many edges at once, such as using clear_in_edges() function to remove all in-edges of the given node, or clear_vertex() to remove all edges of the given node, because these functions still have to remove all the edges being removed from the edge list of the connected nodes. This results in the same complexity of the operation, as with using repetitive remove_edge() calls. It also doesn't help using other containers for storing in/out edge lists, such as list or multiset, instead of vector. Although the removal operation is faster in these containers, the search operation that looks for the edge to be removed is still in the order of the size of the container. For containers such as set or hash set, the search operation is faster, but such containers do not allow parallel edges, since the edges are indexed by the node identifier on the other side of the edge. The search operation that looks for the edge to be removed is in the order of the size of the container because it is necessary to find all the parallel edges. Therefore, for implementations allowing parallel edges, the implementation goes over all edges stored in the container and checks whether the edge connects to the node whose edges are being removed (in case of clear_in_edges()/clear_vertex()). If it is, the edge is removed from the in/out edge list. In our graph implementation, we need to support parallel edges. Even without parallel edges, the total complexity of removal of all edges still can't be brought down to O(E) (only to O(E * log(E/V))). If I would be free to change Boost's graph implementation, one possible solution could be to store in each edge two iterators pointing to the position of this edge in the corresponding in/out edge lists. This would allow removal of the edge from "list" container in O(1). However, it doesn't seem to be possible to do with current Boost implementation. Still, even if it would be possible, the memory consumption would increase due to the storage of the two iterators (at least two additional extra pointers per edge). Another approach could be to index the edges in in/out edge lists by edge identifier (which is not a part of Boost graph infrastructure), instead of indexing them by node identifier. This would allow using "multiset" container to find the edges to remove faster (in logarithmic time). But this still doesn't seem to be possible to do with current Boost implementation and it will also incur a memory overhead (due to usage of complex container as multiset). And still the complexity will be more than O(E). Is there a way to remove all edges in O(E) complexity? Do I miss something, or there is an inherent performance issue in current Boost graph implementation with regard to the edge removal? Even if the current situation is by design due to memory consumption trade offs, I wish the graph implementation would be flexible enough to let the user control performance/memory balance, instead of requiring the performance hit. Or, at least, to provide an atomic function for removal of all edges of the graph, which can be easily implemented to work fast and without incurring any memory overhead with all underlying in/out edge container implementations (just clear all edge-related containers). Any thoughts are welcome. Thanks, Yulik.

3 2

Subgraph problem
by odisseo＠despammed.com 22 Jul '05

22 Jul '05

Look at the following code, as you it print out: ----------- name: graph name sg1: subgraph 3 name sg2: subgraph 3 name sg3: subgraph 3 ----------- when I waiting for ----------- name: graph name sg1: subgraph 1 name sg2: subgraph 2 name sg3: subgraph 3 ----------- WHY? Is this a bug in the library? #include <string> #include <iostream> using namespace std; #include <boost/config.hpp> #include <boost/graph/graphviz.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_utility.hpp> int main() { boost::GraphvizDigraph gr; boost::get_property(gr, boost::graph_name) = "graph"; std::cout << "name: " << get_property(gr, boost::graph_name) << std::endl; boost::subgraph<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::GraphvizVertexProperty, boost::GraphvizEdgeProperty, boost::GraphvizGraphProperty, boost::listS> > sg1 = gr.create_subgraph(); get_property(sg1, boost::graph_name) = "subgraph 1"; boost::subgraph<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::GraphvizVertexProperty, boost::GraphvizEdgeProperty, boost::GraphvizGraphProperty, boost::listS> > sg2 = gr.create_subgraph(); get_property(sg2, boost::graph_name) = "subgraph 2"; boost::subgraph<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::GraphvizVertexProperty, boost::GraphvizEdgeProperty, boost::GraphvizGraphProperty, boost::listS> > sg3 = gr.create_subgraph(); get_property(sg3, boost::graph_name) = "subgraph 3"; std::cout << "name sg1: " << get_property(sg1, boost::graph_name) << std::endl; std::cout << "name sg2: " << get_property(sg2, boost::graph_name) << std::endl; std::cout << "name sg3: " << get_property(sg3, boost::graph_name) << std::endl; }

2 1

question on property tags and bundled properties.
by sr kumar 22 Jul '05

22 Jul '05

Hi, I am attempting use bundled properties for my graph processing. My attempt to 'write_graphviz' fails because of a lack of an vertex_index as an internal property. But how does one specify this? Named params do not seem to be an option. Being new to the template meta programming game, I am having some trouble figuring out how to make this work. Code snippet below is the simplest that would reproduce my problem. Thanks in advance for any clues/hints on how to proceed. -sr #include <boost/graph/adjacency_list.hpp> #include <boost/graph/topological_sort.hpp> #include <boost/graph/graphviz.hpp> using namespace boost; using namespace std; class A { public: // dummy class }; typedef struct VertexProperties { A* a; std::size_t index; boost::default_color_type color; } VertexProperties; typedef struct EdgeProperties { A* a; } EdgeProperties; int main(void) { typedef adjacency_list<vecS, listS, directedS, VertexProperties, EdgeProperties> Graph; Graph g(3); property_map<Graph, std::size_t VertexProperties::*>::type id = get(&VertexProperties::index, g); property_map<Graph, boost::default_color_type VertexProperties::*>::type color = get(&VertexProperties::color, g); boost::graph_traits<Graph>::vertex_iterator vi, viend; int vnum = 0; for (boost::tie(vi,viend) = vertices(g); vi != viend; ++vi) { id[*vi] = vnum++; } add_edge(vertex(0, g), vertex(1, g), g); add_edge(vertex(2, g), vertex(1, g), g); typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; std::vector< vertex_descriptor > c; // Just check to ensure that all is ok. topological_sort(g, std::back_inserter(c), color_map(color). vertex_index_map(id)); // See error below... property_map<Graph, vertex_index_t>::const_type ver_idx = get(vertex_index_t(),g); remove_edge(vertex(0, g), vertex(1, g), g); remove_edge(vertex(2, g), vertex(1, g), g); return 0; }; // ------------- C:\test>cl /EHsc /IC:\CheckMate\boost\boost_1_32_0 btest.cpp Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50215.44 for 80x86 Copyright (C) Microsoft Corporation. All rights reserved. btest.cpp btest.cpp(53) : error C2440: 'initializing' : cannot convert from 'boost::adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>' to 'boost::adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>' with [ Graph=Graph, ValueType=boost::detail::error_property_not_found, Reference=boost::detail::error_property_not_found &, Tag=boost::vertex_index_t ] and [ Graph=Graph, ValueType=boost::detail::error_property_not_found, Reference=const boost::detail::error_property_not_found &, Tag=boost::vertex_index_t ] No constructor could take the source type, or constructor overload resolution was ambiguous

2 1

BGL: EdgeIterator construction of graphs
by Sebastian Weber 22 Jul '05

22 Jul '05

Hi everybody! I'm trying to initialize my adjacency_list graph via an EdgeIterator. Since I do not want parallel edges to be present in my graph, but still use vecS as EdgeList-storage because of memory considerations, my EdgeIterator needs somehow a reference to the graph under construction. Some code might explain it better: typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS > graph_t; typedef boost::my_edge_iterator<base_rand_gen_t, graph_t> SFGen; graph_t bg = graph_t(SFGen(bg, base_rand, 100), SFGen(), 100); This code compiles fine, but seg-faults immediatly since bg does not seem to be defined when my iterator gets constructed. A solution would be to provide a add_edge_range-function which gets as input the EdgeIterator and the corresponding empty boost graph. This function would then build up the graph or is there a better way to do this? Thanks a lot in advance for your help. Greetings, Sebastian

2 2

Re: [Boost-users] compiler warnings using date_time library onVS.NET2003
by Sean Rohead 22 Jul '05

22 Jul '05

Yes, I am using boost 1.32 and have /W3 as the warning level. Thanks, Sean -----Original Message----- From: boost-users-bounces(a)lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Bart Sent: Friday, July 22, 2005 7:06 AM To: boost-users(a)lists.boost.org Subject: Re: [Boost-users] compiler warnings using date_time library onVS.NET2003 "Sean Rohead" <sean.rohead(a)nextpage.com> wrote in message news:dbpf56$hig$1@sea.gmane.org... >I am using VS.NET 2003 and have a simple program which merely includes the > Boost date_time library. When compiling, I get 4 warning messages about > unsafe conversions. Is there some compiler setting that I can change to > get > rid of this warning? Shouldn't I be able to include a Boost library > without > getting warnings? > > Thanks! Could you please tell me, what warning level are you using and are you using boost 1.32 or current cvs? Thanks, Bart _______________________________________________ Boost-users mailing list Boost-users(a)lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

2 1

Building Boost for Comeau
by Edward Diener 22 Jul '05

22 Jul '05

In the explanation for como-win32 toolset configuration variables, the variable COMO_BACKEND_PATH, which says "Path to backend compiler" has a default value of $(VC7_TOOLS). Running vcvars32.bat for vc7 does not set any such environment variable. To what does the COMO_BACKEND_PATH need to be set ? Is it the path to the backend compiler executable itself or is it the path to the entire installation ? If I had Vc7 installed in c:\vsnet, would COMO_BACKEND_PATH be c:\vsnet or would it be c:\vsnet\vc7\bin ?

2 2

BGL: Average path distance implementation
by P.Saffrey 22 Jul '05

22 Jul '05

I am writing a graph application using BGL where a key component is cycle detection. I need to know how long a cycle is. I can use breadth first search, but that gives me the shortest path. What I want is the average path length. I have an idea for an algorithm for this: basically do a breadth first search, disallowing any edge if it's been used before in this path and then take the mean of all the complete paths from the node to itself. Can anybody give me some clues as to how I can implement this? I would prefer to use the pucker event visitor approach, but I'm not sure whether I can use this to alter the search process. I'll need to cull a path from the search if it encounters a node with no outgoing edges that haven't been used already. I'm also not sure how to collect all the path lengths at the end. Peter -- P.Saffrey(a)ucl.ac.uk http://www.cs.ucl.ac.uk/staff/P.Saffrey/ Beacon Project http://www.grid.ucl.ac.uk/biobeacon/

2 1

[bjam] How does one pass a compiler define
by Edward Diener 22 Jul '05

22 Jul '05

Is there a way to pass a compiler define when invoking bjam ? I want to build my libraries with by defining BOOST_ALL_DYN_LINK when linking to the dynamic run-time library. How do I do this ?

3 9

compiler warnings using date_time library on VS.NET 2003
by Sean Rohead 22 Jul '05

22 Jul '05

I am using VS.NET 2003 and have a simple program which merely includes the Boost date_time library. When compiling, I get 4 warning messages about unsafe conversions. Is there some compiler setting that I can change to get rid of this warning? Shouldn't I be able to include a Boost library without getting warnings? Thanks! >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> // main.cpp #include "boost/date_time/posix_time/posix_time.hpp" void main() { } >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ------ Build started: Project: boost, Configuration: Debug Win32 ------ Compiling... main.cpp c:\lib\boost_1_32_0\boost\date_time\posix_time\conversion.hpp(27) : warning C4244: 'argument' : conversion from 'time_t' to 'long', possible loss of data c:\lib\boost_1_32_0\boost\date_time\time_system_counted.hpp(57) : warning C4244: 'initializing' : conversion from 'boost::date_time::counted_time_rep<config>::int_type' to 'boost::date_time::gregorian_calendar_base<ymd_type_,date_int_type_>::date_int_type', possible loss of data with [ config=boost::posix_time::millisec_posix_time_system_config ] and [ ymd_type_=boost::gregorian::greg_year_month_day, date_int_type_=boost::date_time::int_adapter<unsigned long>::int_type ] c:\lib\boost_1_32_0\boost\date_time\time_system_counted.hpp(52) : while compiling class-template member function 'boost::date_time::counted_time_rep<config>::date_type boost::date_time::counted_time_rep<config>::date(void) const' with [ config=boost::posix_time::millisec_posix_time_system_config ] c:\lib\boost_1_32_0\boost\date_time\time_system_counted.hpp(111) : see reference to class template instantiation 'boost::date_time::counted_time_rep<config>' being compiled with [ config=boost::posix_time::millisec_posix_time_system_config ] c:\lib\boost_1_32_0\boost\date_time\time.hpp(52) : see reference to class template instantiation 'boost::date_time::counted_time_system<time_rep>' being compiled with [ time_rep=boost::posix_time::int64_time_rep ] c:\lib\boost_1_32_0\boost\date_time\posix_time\ptime.hpp(32) : see reference to class template instantiation 'boost::date_time::base_time<T,time_system>' being compiled with [ T=boost::posix_time::ptime, time_system=boost::posix_time::posix_time_system ] c:\lib\boost_1_32_0\boost\date_time\time_parsing.hpp(81) : warning C4267: 'initializing' : conversion from 'size_t' to 'int', possible loss of data c:\lib\boost_1_32_0\boost\date_time\posix_time\time_parsers.hpp(27) : see reference to function template instantiation 'time_duration boost::date_time::parse_delimited_time_duration<boost::posix_time::time_duration>(const std::string &)' being compiled with [ time_duration=boost::posix_time::time_duration ] c:\lib\boost_1_32_0\boost\date_time\date_parsing.hpp(211) : warning C4244: 'argument' : conversion from 'std::allocator<_Ty>::value_type' to 'char', possible loss of data with [ _Ty=wchar_t ] c:\lib\boost_1_32_0\boost\date_time\date_parsing.hpp(253) : see reference to function template instantiation 'date_type boost::date_time::from_stream_type<date_type,std::basic_string<_Elem,_Traits,_Ax>::iterator>(iterator_type &,iterator_type &,wchar_t)' being compiled with [ date_type=boost::gregorian::date, _Elem=wchar_t, _Traits=std::char_traits<wchar_t>, _Ax=std::allocator<wchar_t>, iterator_type=std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t>>::iterator ] c:\lib\boost_1_32_0\boost\date_time\gregorian\parsers.hpp(78) : see reference to function template instantiation 'boost::date_time::period<point_rep,duration_rep> boost::date_time::from_simple_string_type<boost::gregorian::date,wchar_t>(const std::basic_string<_Elem,_Traits,_Ax> &)' being compiled with [ point_rep=boost::gregorian::date, duration_rep=boost::gregorian::date_duration, _Elem=wchar_t, _Traits=std::char_traits<wchar_t>, _Ax=std::allocator<wchar_t> ]

4 3

Re: [Boost-users] [bjam] How does one pass a compiler define
by Foster, Gareth 22 Jul '05

22 Jul '05

> Nobody -- other than that rhinoceros over there behind you -- > considers it adequate. > I hate to clutter the mailing list with redundant comments, but that really deserves a "lol". Lol. Gaz

1 0