graph_distance.cc 6.68 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
// Copyright (C) 2006-2014 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
//
// 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:
37
38
39
    bfs_max_visitor(DistMap dist_map, PredMap pred, size_t max_dist, size_t target)
        : _dist_map(dist_map), _pred(pred), _max_dist(max_dist), _target(target),
          _dist(0) {}
40
41

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

48
49
50
51
    template <class Graph>
    void examine_vertex(typename graph_traits<Graph>::vertex_descriptor v,
                        Graph&)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
52
53
        typedef typename property_traits<DistMap>::value_type val_t;
        if ( _dist_map[v] > val_t(_max_dist))
54
55
56
            throw stop_search();
    }

57
58
    template <class Graph>
    void discover_vertex(typename graph_traits<Graph>::vertex_descriptor v,
59
                         Graph&)
60
    {
61
        if (size_t(_pred[v]) == v)
62
            return;
63
        _dist_map[v] = _dist_map[_pred[v]] + 1;
64
65
        if (v == _target)
            throw stop_search();
66
67
68
69
70
71
    }

private:
    DistMap _dist_map;
    PredMap _pred;
    size_t _max_dist;
72
    size_t _target;
73
74
75
    size_t _dist;
};

76
template <class DistMap>
77
78
79
80
class djk_max_visitor:
    public boost::dijkstra_visitor<null_visitor>
{
public:
81
    djk_max_visitor(DistMap dist_map,
82
83
                    typename property_traits<DistMap>::value_type max_dist, size_t target)
        : _dist_map(dist_map), _max_dist(max_dist), _target(target) {}
84

85

86
    template <class Graph>
87
88
    void examine_vertex(typename graph_traits<Graph>::vertex_descriptor u,
                        Graph&)
89
    {
90
        if (_dist_map[u] > _max_dist)
91
            throw stop_search();
92

93
94
        if (u == _target)
            throw stop_search();
95
96
    }

97

98
99
100
private:
    DistMap _dist_map;
    typename property_traits<DistMap>::value_type _max_dist;
101
    size_t _target;
102
103
104
105
106
};


struct do_bfs_search
{
107
    template <class Graph, class VertexIndexMap, class DistMap, class PredMap>
108
109
110
    void operator()(const Graph& g, size_t source, size_t target,
                    VertexIndexMap vertex_index, DistMap dist_map,
                    PredMap pred_map, long double max_dist) const
111
112
113
114
115
    {
        typedef typename property_traits<DistMap>::value_type dist_t;
        dist_t max_d = (max_dist > 0) ?
            max_dist : numeric_limits<dist_t>::max();

116
        int i, N = num_vertices(g);
117
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
118
119
120
121
        for (i = 0; i < N; ++i)
            dist_map[i] = numeric_limits<dist_t>::max();
        dist_map[source] = 0;

122
123
124
125
126
127
        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),
128
                                 visitor(bfs_max_visitor<DistMap, PredMap>
129
                                         (dist_map, pred_map, max_d, target)).
130
131
132
133
134
135
136
137
138
                                 vertex_index_map(vertex_index).
                                 color_map(color_map));
        }
        catch (stop_search&) {}
    }
};

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

149
        int i, N = num_vertices(g);
150
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
151
152
153
154
        for (i = 0; i < N; ++i)
            dist_map[i] = numeric_limits<dist_t>::max();
        dist_map[source] = 0;

155
156
157
158
159
160
        try
        {
            dijkstra_shortest_paths(g, vertex(source, g),
                                    weight_map(weight).
                                    distance_map(dist_map).
                                    vertex_index_map(vertex_index).
161
                                    predecessor_map(pred_map).
162
                                    visitor(djk_max_visitor<DistMap>
163
                                            (dist_map, max_d, target)));
164
165
166
167
168
        }
        catch (stop_search&) {}
    }
};

169
void get_dists(GraphInterface& gi, size_t source, int tgt, boost::any dist_map,
170
               boost::any weight, boost::any pred_map, long double max_dist)
171
{
172
173
174
175
176
    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);

177
178
    size_t target = tgt < 0 ? graph_traits<GraphInterface::multigraph_t>::null_vertex() : tgt;

179
180
181
    if (weight.empty())
    {
        run_action<>()
Tiago Peixoto's avatar
Tiago Peixoto committed
182
183
184
            (gi, std::bind(do_bfs_search(), placeholders::_1, source, target, gi.GetVertexIndex(),
                           placeholders::_2, pmap.get_unchecked(num_vertices(gi.GetGraph())),
                           max_dist),
185
             writable_vertex_scalar_properties())
186
187
188
189
190
            (dist_map);
    }
    else
    {
        run_action<>()
Tiago Peixoto's avatar
Tiago Peixoto committed
191
192
193
            (gi, std::bind(do_djk_search(), placeholders::_1, source, target, gi.GetVertexIndex(),
                           placeholders::_2, pmap.get_unchecked(num_vertices(gi.GetGraph())),
                           placeholders::_3, max_dist),
194
195
196
197
198
199
200
201
202
203
204
             writable_vertex_scalar_properties(),
             edge_scalar_properties())
            (dist_map, weight);

    }
}

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