[BGL] Accelerating property value-retrieval
Hi, I would like to know if there is a way to accelerate the retrieval of properties of an edge or a vertex? Actually, I define a new vertex-property (vertex_properties) and this again uses a "struct VertexProperties { ... }" to specify the details of the properties. However, when I want to get the properties of say vertex v, I need to first get the properties-map from the graph and then get the property for v. This obviously suffers from the lookup in the property_map and I would like to know if there is a way to accelerate this? In particular, when using vecS as the vertex_container because the vertices could generally be used as indices... I would find this very convenient, especially in combination with filtered_graph when filtering only on vertices that have certain properties (e.g. a category) and one only wants to see those that have a specific character (e.g. color). Best, Cedric
On Fri, 8 Apr 2011, Cedric Laczny wrote:
Hi,
I would like to know if there is a way to accelerate the retrieval of properties of an edge or a vertex? Actually, I define a new vertex-property (vertex_properties) and this again uses a "struct VertexProperties { ... }" to specify the details of the properties. However, when I want to get the properties of say vertex v, I need to first get the properties-map from the graph and then get the property for v. This obviously suffers from the lookup in the property_map and I would like to know if there is a way to accelerate this?
You can save the property map in a variable to avoid repeated lookups, but I suspect they are not too expensive.
In particular, when using vecS as the vertex_container because the vertices could generally be used as indices... I would find this very convenient, especially in combination with filtered_graph when filtering only on vertices that have certain properties (e.g. a category) and one only wants to see those that have a specific character (e.g. color).
Fast lookups will probably require external properties, since those are much simpler and have fewer layers of indirection (no pointers to members, for example). Can you copy your properties to an iterator_property_map (built on a vector) before the high-performance parts of your code? -- Jeremiah Willcock
On Friday, 8. April 2011 16:33:23 Jeremiah Willcock wrote:
On Fri, 8 Apr 2011, Cedric Laczny wrote:
Hi,
I would like to know if there is a way to accelerate the retrieval of properties of an edge or a vertex? Actually, I define a new vertex-property (vertex_properties) and this again uses a "struct VertexProperties { ... }" to specify the details of the properties. However, when I want to get the properties of say vertex v, I need to first get the properties-map from the graph and then get the property for v. This obviously suffers from the lookup in the property_map and I would like to know if there is a way to accelerate this?
You can save the property map in a variable to avoid repeated lookups, but I suspect they are not too expensive.
I agree with you on that.
In particular, when using vecS as the vertex_container because the vertices could generally be used as indices... I would find this very convenient, especially in combination with filtered_graph when filtering only on vertices that have certain properties (e.g. a category) and one only wants to see those that have a specific character (e.g. color).
Fast lookups will probably require external properties, since those are much simpler and have fewer layers of indirection (no pointers to members, for example). Can you copy your properties to an iterator_property_map (built on a vector) before the high-performance parts of your code?
This is a nice idea. So if I am getting this right, in the case of vecS, get(vertex_index, g) should return the identity_property_map, thus resulting in linear lookup. At the same time, using the intermediate vertex_index map and an iterator_property_map would guarantee at least valid lookups in case of other vertex-containers, albeit they would then require the usual O(log n) lookup. This of course only if the graph also provides a vertex-index map. Or am I missing something here?
-- Jeremiah Willcock
Best, Cedric
On Friday, 8. April 2011 16:33:23 Jeremiah Willcock wrote:
On Fri, 8 Apr 2011, Cedric Laczny wrote:
Hi,
I would like to know if there is a way to accelerate the retrieval of properties of an edge or a vertex? Actually, I define a new vertex-property (vertex_properties) and this again uses a "struct VertexProperties { ... }" to specify the details of the properties. However, when I want to get the properties of say vertex v, I need to first get the properties-map from the graph and then get the property for v. This obviously suffers from the lookup in the property_map and I would like to know if there is a way to accelerate this?
You can save the property map in a variable to avoid repeated lookups, but I suspect they are not too expensive.
In particular, when using vecS as the vertex_container because the vertices could generally be used as indices... I would find this very convenient, especially in combination with filtered_graph when filtering only on vertices that have certain properties (e.g. a category) and one only wants to see those that have a specific character (e.g. color).
Fast lookups will probably require external properties, since those are much simpler and have fewer layers of indirection (no pointers to members, for example). Can you copy your properties to an iterator_property_map (built on a vector) before the high-performance parts of your code?
I ran across a problem here, that is the copying from the property_map to a vector. Because the property_map is lacking an iterator, I have to go over all vertices, performing the lookup to get their values and then assign it to the vector. While this works, it provides basically no big benefit for my scenario. Most of the vertices and looked-up only very few times (sometimes only once), so that it breaks down to the lookup again... Any ideas how to efficiently convert the values in the property_map into a vector? Actually, it looks like this: template< class G, class P> struct FilterOnP{ typedef typename property_map< typename G::GraphContainer, vertex_properties_t>::const_type VPM; typedef typename property_map< typename G::GraphContainer, edge_properties_t>::const_type EPM; // This represents the type of the vertex_properties typedef typename property_traits< VPM >::value_type VProps; typedef typename boost::identity_property_map VertexIndexMap; typedef typename boost::iterator_property_map< typename std::vector< VProps >::iterator, VertexIndexMap > VIPM; MRDiEdgeFilterOnPvalue( const G& g, const P& p ) : g_(g), p_(p) { // Initialize the edge-property member epm_ = g.getEdgePropertyMap(); // To retrieve the vertex properties VPM tmp_vpm = g.getVertexPropertyMap(); typename G::vertex_iter v_it, v_it_end; typename G::vertex_range_t all_vertices = g.getVertices(); v_it = all_vertices.first; v_it_end = all_vertices.second; // Copy the properties from the map into a vector // PROBLEM: Lookups necessary, so no linear processing! v_props_vec_.resize( g.getVertexCount() ); unsigned int cnt = 0; for( ; v_it != v_it_end; ++v_it ) { v_props_vec_[cnt] = tmp_vpm[*v_it]; ++cnt; } VertexIndexMap index; // Initialize the vertex-property member vpm_ = VIPM( v_props_vec_.begin(), index); } template< class E > bool operator() (const E& e) const { typename G::Vertex u, v; u = g_.getSource(e); v = g_.getTarget(e); std::string u_type, v_type; u_type = (vpm_[u]).type; v_type = (vpm_[v]).type; if( ((u_type == "x") && (v_type == "y")) || ((u_type == "y") && (v_type == "x")) ) { if ((epm_[ e ].pvalue) < p_ ) return true; else { return false; } } else return true; } G g_; VPropsVec v_props_vec_; VIPM vpm_; /// Map holding the properties of the edges EPM epm_; /// Threshold p P p_; }; As you can see, the filter is supposed to filter only on those edges having incident vertices of type x or y. For all this, it needs the properties from those vertices as well as the properties of the edge to finally decide if it should be visible or not.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric
participants (2)
-
Cedric Laczny -
Jeremiah Willcock