graph_distance.cc 6.13 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
// Copyright (C) 2006-2013 Tiago de Paula Peixoto <tiago@skewed.de>
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//
// 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 3
// 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, see <http://www.gnu.org/licenses/>.

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

#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

#include <boost/python.hpp>

using namespace std;
using namespace boost;
using namespace graph_tool;

struct stop_search {};

template <class DistMap, class PredMap>
class bfs_max_visitor:
    public boost::bfs_visitor<null_visitor>
{
public:
    bfs_max_visitor(DistMap dist_map, PredMap pred, size_t max_dist)
        : _dist_map(dist_map), _pred(pred), _max_dist(max_dist), _dist(0) {}

    template <class Graph>
41
42
    void tree_edge(typename graph_traits<Graph>::edge_descriptor e,
                   Graph& g)
43
44
45
46
47
48
    {
        _pred[target(e,g)] = source(e,g);
    }

    template <class Graph>
    void discover_vertex(typename graph_traits<Graph>::vertex_descriptor v,
49
                         Graph&)
50
    {
51
        if (size_t(_pred[v]) == v)
52
53
54
55
56
57
58
59
60
61
62
63
64
65
            return;
        size_t dist = _dist_map[_pred[v]] + 1;
        if (dist > _max_dist)
            throw stop_search();
        _dist_map[v] = dist;
    }

private:
    DistMap _dist_map;
    PredMap _pred;
    size_t _max_dist;
    size_t _dist;
};

66
template <class DistMap>
67
68
69
70
class djk_max_visitor:
    public boost::dijkstra_visitor<null_visitor>
{
public:
71
    djk_max_visitor(DistMap dist_map,
72
73
74
75
76
                    typename property_traits<DistMap>::value_type max_dist)
        : _dist_map(dist_map), _max_dist(max_dist) {}

    template <class Graph>
    void examine_vertex(typename graph_traits<Graph>::vertex_descriptor u,
77
                        Graph&)
78
    {
79
80
81
82
        if (_dist_map[u] > _max_dist)
        {
            typedef typename property_traits<DistMap>::value_type d_type;
            _dist_map[u] = numeric_limits<d_type>::max();
83
            throw stop_search();
84
        }
85
86
87
88
89
90
91
92
93
94
    }

private:
    DistMap _dist_map;
    typename property_traits<DistMap>::value_type _max_dist;
};


struct do_bfs_search
{
95
    template <class Graph, class VertexIndexMap, class DistMap, class PredMap>
96
    void operator()(const Graph& g, size_t source, VertexIndexMap vertex_index,
97
98
                    DistMap dist_map, PredMap pred_map, long double max_dist)
        const
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
    {
        typedef typename property_traits<DistMap>::value_type dist_t;
        dist_t max_d = (max_dist > 0) ?
            max_dist : numeric_limits<dist_t>::max();

        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
            dist_map[v] = numeric_limits<dist_t>::max();
        }
        dist_map[vertex(source,g)] = 0;

        pred_map[vertex(source, g)] = vertex(source, g);
        unchecked_vector_property_map<boost::default_color_type, VertexIndexMap>
            color_map(vertex_index, num_vertices(g));
        try
        {
            breadth_first_search(g, vertex(source, g),
121
                                 visitor(bfs_max_visitor<DistMap, PredMap>
122
123
124
125
126
127
128
129
130
131
                                         (dist_map, pred_map, max_d)).
                                 vertex_index_map(vertex_index).
                                 color_map(color_map));
        }
        catch (stop_search&) {}
    }
};

struct do_djk_search
{
132
133
    template <class Graph, class VertexIndexMap, class DistMap, class PredMap,
              class WeightMap>
134
    void operator()(const Graph& g, size_t source, VertexIndexMap vertex_index,
135
136
                    DistMap dist_map, PredMap pred_map, WeightMap weight,
                    long double max_dist) const
137
138
139
140
141
142
143
144
145
146
147
    {
        typedef typename property_traits<DistMap>::value_type dist_t;
        dist_t max_d = (max_dist > 0) ?
            max_dist : numeric_limits<dist_t>::max();

        try
        {
            dijkstra_shortest_paths(g, vertex(source, g),
                                    weight_map(weight).
                                    distance_map(dist_map).
                                    vertex_index_map(vertex_index).
148
                                    predecessor_map(pred_map).
149
150
                                    visitor(djk_max_visitor<DistMap>
                                            (dist_map, max_d)));
151
152
153
154
155
156
        }
        catch (stop_search&) {}
    }
};

void get_dists(GraphInterface& gi, size_t source, boost::any dist_map,
157
               boost::any weight, boost::any pred_map, long double max_dist)
158
{
159
160
161
162
163
    typedef property_map_type
        ::apply<int64_t, GraphInterface::vertex_index_map_t>::type pred_map_t;

    pred_map_t pmap = any_cast<pred_map_t>(pred_map);

164
165
166
167
    if (weight.empty())
    {
        run_action<>()
            (gi, bind<void>(do_bfs_search(), _1, source, gi.GetVertexIndex(),
168
169
170
171
                            _2, pmap.get_unchecked(num_vertices(gi.GetGraph())),
                            max_dist),
             writable_vertex_scalar_properties(),
             mpl::vector<pred_map_t>())
172
173
174
175
176
177
            (dist_map);
    }
    else
    {
        run_action<>()
            (gi, bind<void>(do_djk_search(), _1, source, gi.GetVertexIndex(),
178
179
                            _2, pmap.get_unchecked(num_vertices(gi.GetGraph())),
                            _3, max_dist),
180
181
182
183
184
185
186
187
188
189
190
             writable_vertex_scalar_properties(),
             edge_scalar_properties())
            (dist_map, weight);

    }
}

void export_dists()
{
    python::def("get_dists", &get_dists);
};