graph_distance.cc 5.61 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

#include <algorithm>
#include <tr1/unordered_set>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/lambda/bind.hpp>
24
#include <iostream>
25
26
27
28
29
30
31
32
33
34
35
36
37

#include "graph.hh"
#include "histogram.hh"
#include "graph_filtering.hh"
#include "graph_selectors.hh"
#include "graph_properties.hh"

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

//==============================================================================
38
39
// GetDistanceHistogram()
// retrieves the vertex-vertex distance histogram
40
41
42
//==============================================================================
struct no_weightS {};

43
struct get_distance_histogram
44
45
{

46
47
    template <class Graph, class IndexMap, class WeightMap, class Hist>
    void operator()(const Graph &g, IndexMap index_map, WeightMap weights, Hist& hist) const
48
49
50
51
    {        
        // select get_vertex_dists based on the existence of weights
        typedef typename mpl::if_<is_same<WeightMap, no_weightS>,
                                       get_dists_bfs,
52
53
                                  get_dists_djk>::type get_vertex_dists_t;

54
        get_vertex_dists_t get_vertex_dists;
55
56
57
58
        int i, N = num_vertices(g);

        #pragma omp parallel for default(shared) private(i) 
        for (i = 0; i < N; ++i)
59
        {
60
61
62
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
63
64
65
            typedef tr1::unordered_map<typename graph_traits<Graph>::vertex_descriptor,double,DescriptorHash<IndexMap> > dmap_t;
            dmap_t dmap(0, DescriptorHash<IndexMap>(index_map));
            InitializedPropertyMap<dmap_t> dist_map(dmap, numeric_limits<double>::max());
66

67
68
69
70
71
72
73
74
            dist_map[v] = 0.0;
            get_vertex_dists(g, v, index_map, dist_map, weights);

            typename graph_traits<Graph>::vertex_iterator v2, v_end;
            for (tie(v2, v_end) = vertices(g); v2 != v_end; ++v2)
                if (*v2 != v && dist_map[*v2] != numeric_limits<double>::max())
                    #pragma omp atomic
                    hist[dist_map[*v2]]++;            
75
        }        
76
77
78
    }

    // weighted version. Use dijkstra_shortest_paths()
79
    struct get_dists_djk
80
    {
81
82
83
84
85
        template <class Graph, class Vertex, class IndexMap, class DistanceMap, class WeightMap>
        void operator()(const Graph& g, Vertex s, IndexMap index_map, DistanceMap dist_map, WeightMap weights) const
        {
            dijkstra_shortest_paths(g, s, vertex_index_map(index_map).weight_map(weights).distance_map(dist_map));  
        }
86
87
88
    };

    // unweighted version. Use BFS.
89
    struct get_dists_bfs
90
    {
91
92
93
94
95
96
        template <class Graph, class Vertex, class IndexMap, class DistanceMap>
        void operator()(const Graph& g, Vertex s, IndexMap index_map, DistanceMap dist_map, no_weightS) const
        {
            typedef tr1::unordered_map<typename graph_traits<Graph>::vertex_descriptor,default_color_type,DescriptorHash<IndexMap> > cmap_t;
            cmap_t cmap(0, DescriptorHash<IndexMap>(index_map));
            InitializedPropertyMap<cmap_t> color_map(cmap, color_traits<default_color_type>::white());
97
                        
98
99
            breadth_first_visit(g, s, visitor(make_bfs_visitor(record_distances(dist_map, on_tree_edge()))).color_map(color_map)); 
        }
100
101
102
103
104
    };

    
};

105
GraphInterface::hist_t GraphInterface::GetDistanceHistogram(string weight) const
106
{
107
    hist_t hist;
108
109
110

    if (weight == "")
    {
111
        check_filter(*this, bind<void>(get_distance_histogram(), _1, _vertex_index, no_weightS(), var(hist)),
112
                     reverse_check(), directed_check()); 
113
114
115
    }
    else
    {
116
117
118
119
120
        try 
        {
            dynamic_property_map& weight_prop = find_property_map(_properties, weight, typeid(graph_traits<multigraph_t>::edge_descriptor));
            try 
            {
121
122
123
124
                vector_property_map<double, edge_index_map_t> weight_map;
                weight_map = get_static_property_map<vector_property_map<double, edge_index_map_t> >(weight_prop);
                check_filter(*this, bind<void>(get_distance_histogram(), _1, _vertex_index, weight_map, var(hist)),
                             reverse_check(), directed_check()); 
125
126
127
            }
            catch (bad_cast)
            {
128
129
130
                DynamicPropertyMapWrap<double, graph_traits<multigraph_t>::edge_descriptor> weight_map(weight_prop);
                check_filter(*this, bind<void>(get_distance_histogram(), _1, _vertex_index, weight_map, var(hist)),
                             reverse_check(), directed_check()); 
131
132
133
134
135
136
            }
        }
        catch (property_not_found& e)
        {
            throw GraphException("error getting scalar property: " + string(e.what()));
        }
137
    }
138
    return hist;
139
}