Re: [Boost-users] [BGL] Accelerating property value-retrieval

Subject: Re: [Boost-users] [BGL] Accelerating property value-retrieval
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-08 14:02:54

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

Best,

Cedric