Boost logo

Boost Users :

Subject: [Boost-users] [Graph] filters and subgraphs?
From: The Maschine (justthemaschine_at_[hidden])
Date: 2013-11-27 07:18:58


Hi all,

What Im trying to do is the get a filtered or subgraph that holds the
properties of the original graph (vertex and edge bundles).
Ill use the 'subgraph' in other algorithms but from time to time I'd like
to be able to trace the original vertex_descriptor and push data back to
the original graph.
(that might be able to happen via the original_vertex_d below but lets
see..)

Below is an attempt to use graph filters to do it but for reasons that can
be found in topics by others, I think this is not going to work. (filtered
graph are too simple.. etc)

Is it possible to use the 'distance map', that I use to produce a filtered
graph, for producing a subgraph that all info from the original (minus the
filtered vertexes that we dont want of course) data are there and can be
also further used in algorithms?

Thanks

/////////////////////////////
struct VertexProperties
{
boost::graph_traits<unGraph>::vertex_descriptor original_vertex_d; // might
be needed for the question above
double m_bc; // for betweenness
..... ....
};

struct EdgeProperties
{
    double m_weight1;
    double m_weight2;
};

typedef double Weight;
typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
VertexProperties, EdgeProperties> unGraph;

typedef boost::graph_traits < unGraph >::vertex_descriptor Vertex;
typedef boost::property_map < unGraph, boost::vertex_index_t >::type
IndexMap;
typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& >
PredecessorMap;
typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& >
DistanceMap;

struct vertex_distance_filter
{
    vertex_distance_filter() { }
    vertex_distance_filter(std::vector<Weight> distance_map, double radius)
: m_dist_map(distance_map), m_radius(radius) { }
    bool operator()(const typename
boost::graph_traits<unGraph>::vertex_descriptor& v) const
    {
        return m_radius > m_dist_map[v];
    }
    double m_radius;
    std::vector<Weight> m_dist_map;
};

//////
int i = 0; // simplified
        boost::graph_traits<unGraph>::vertex_descriptor s_vertex =
boost::vertex(i, m_ugraph);

        // Filter
        std::vector<Vertex> predecessors(boost::num_vertices(m_ugraph));
        std::vector<Weight> distances(boost::num_vertices(m_ugraph),
std::numeric_limits<double>::max() );
        IndexMap indexMap = boost::get(boost::vertex_index, m_ugraph);
        PredecessorMap predecessorMap(&predecessors[0], indexMap);
        DistanceMap distanceMap(&distances[0], indexMap);

        boost::dijkstra_shortest_paths(m_ugraph, s_vertex,
boost::weight_map(boost::get(&EdgeProperties::m_weight1,
m_ugraph)).predecessor_map(predecessorMap).distance_map(distanceMap));

        vertex_distance_filter filter(distances, 400.0f);
        typedef boost::filtered_graph<unGraph, vertex_distance_filter>
FilteredGraphType;
        FilteredGraphType filteredGraph(m_ugraph, filter);

// Work on the filtered graph. Subgraph maybe???
            std::vector< double >
v_centrality_vec(boost::num_vertices(filteredGraph), 0.0);

// different weight from above. here m_weight2
            boost::brandes_betweenness_centrality(filteredGraph ,
boost::centrality_map(boost::make_iterator_property_map(v_centrality_vec.begin(),boost::get(boost::vertex_index,
filteredGraph),double())).vertex_index_map(get(boost::vertex_index,
m_ugraph)).weight_map(boost::get(&EdgeProperties::m_weight2, m_ugraph)) );

// here we start having problems... comments above
            boost::graph_traits<unGraph>::vertex_iterator
vertex_iterator_begin, vertex_iterator_end;
            for ( boost::tie(vertex_iterator_begin, vertex_iterator_end) =
                  vertices(filteredGraph); vertex_iterator_begin !=
                  vertex_iterator_end; ++vertex_iterator_begin)
            {
            // this is the original unfiltered graph!!!!
                m_ugraph[*vertex_iterator_begin].m_bc =
v_centrality_vec[*vertex_iterator_begin];
            }



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net