graph_distance.cc 5.81 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Copyright (C) 2008  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 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>
    void examine_edge(typename graph_traits<Graph>::edge_descriptor e,
                      Graph& g)
    {
        _pred[target(e,g)] = source(e,g);
    }

    template <class Graph>
    void discover_vertex(typename graph_traits<Graph>::vertex_descriptor v,
                         Graph& g)
    {
        if (_pred[v] == v)
            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;
};

67
template <class DistMap>
68
69
70
71
class djk_max_visitor:
    public boost::dijkstra_visitor<null_visitor>
{
public:
72
    djk_max_visitor(DistMap dist_map,
73
74
75
76
77
78
79
                    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,
                        Graph& g)
    {
80
81
82
83
        if (_dist_map[u] > _max_dist)
        {
            typedef typename property_traits<DistMap>::value_type d_type;
            _dist_map[u] = numeric_limits<d_type>::max();
84
            throw stop_search();
85
        }
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
    }

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


struct do_bfs_search
{
    template <class Graph, class VertexIndexMap, class DistMap>
    void operator()(const Graph& g, size_t source, VertexIndexMap vertex_index,
                    DistMap dist_map, long double max_dist) const
    {
        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;

        typedef unchecked_vector_property_map
            <typename graph_traits<Graph>::vertex_descriptor, VertexIndexMap>
            pred_map_t;
        pred_map_t pred_map(vertex_index, num_vertices(g));
        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),
                                 visitor(bfs_max_visitor<DistMap, pred_map_t>
                                         (dist_map, pred_map, max_d)).
                                 vertex_index_map(vertex_index).
                                 color_map(color_map));
        }
        catch (stop_search&) {}
    }
};

struct do_djk_search
{
    template <class Graph, class VertexIndexMap, class DistMap, class WeightMap>
    void operator()(const Graph& g, size_t source, VertexIndexMap vertex_index,
                    DistMap dist_map, WeightMap weight, long double max_dist)
        const
    {
        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).
151
152
                                    visitor(djk_max_visitor<DistMap>
                                            (dist_map, max_d)));
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
        }
        catch (stop_search&) {}
    }
};

void get_dists(GraphInterface& gi, size_t source, boost::any dist_map,
               boost::any weight, long double max_dist)
{
    if (weight.empty())
    {
        run_action<>()
            (gi, bind<void>(do_bfs_search(), _1, source, gi.GetVertexIndex(),
                            _2, max_dist),
             writable_vertex_scalar_properties())
            (dist_map);
    }
    else
    {
        run_action<>()
            (gi, bind<void>(do_djk_search(), _1, source, gi.GetVertexIndex(),
                            _2, _3, max_dist),
             writable_vertex_scalar_properties(),
             edge_scalar_properties())
            (dist_map, weight);

    }
}

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