graph_distance.cc 6.12 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
//
// 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
48
49
    {
        _pred[target(e,g)] = source(e,g);
    }

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

        if (v == _target)
            throw stop_search();
61
62
63
64
65
66
    }

private:
    DistMap _dist_map;
    PredMap _pred;
    size_t _max_dist;
67
    size_t _target;
68
69
70
    size_t _dist;
};

71
template <class DistMap>
72
73
74
75
class djk_max_visitor:
    public boost::dijkstra_visitor<null_visitor>
{
public:
76
    djk_max_visitor(DistMap dist_map,
77
78
                    typename property_traits<DistMap>::value_type max_dist, size_t target)
        : _dist_map(dist_map), _max_dist(max_dist), _target(target) {}
79
80

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

private:
    DistMap _dist_map;
    typename property_traits<DistMap>::value_type _max_dist;
97
    size_t _target;
98
99
100
101
102
};


struct do_bfs_search
{
103
    template <class Graph, class VertexIndexMap, class DistMap, class PredMap>
104
105
106
    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
107
108
109
110
111
112
113
114
115
116
117
    {
        typedef typename property_traits<DistMap>::value_type dist_t;
        dist_t max_d = (max_dist > 0) ?
            max_dist : numeric_limits<dist_t>::max();

        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),
118
                                 visitor(bfs_max_visitor<DistMap, PredMap>
119
                                         (dist_map, pred_map, max_d, target)).
120
121
122
123
124
125
126
127
128
                                 vertex_index_map(vertex_index).
                                 color_map(color_map));
        }
        catch (stop_search&) {}
    }
};

struct do_djk_search
{
129
130
    template <class Graph, class VertexIndexMap, class DistMap, class PredMap,
              class WeightMap>
131
132
133
    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
134
135
136
137
138
139
140
141
142
143
144
    {
        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).
145
                                    predecessor_map(pred_map).
146
                                    visitor(djk_max_visitor<DistMap>
147
                                            (dist_map, max_d, target)));
148
149
150
151
152
        }
        catch (stop_search&) {}
    }
};

153
void get_dists(GraphInterface& gi, size_t source, int tgt, boost::any dist_map,
154
               boost::any weight, boost::any pred_map, long double max_dist)
155
{
156
157
158
159
160
    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);

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

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

    }
}

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