graph_dijkstra.cc 9.75 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1 2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2015 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
//
// 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_filtering.hh"
#include "graph_python_interface.hh"

#include <boost/python.hpp>
#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
23
#include <boost/coroutine/all.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
24 25 26 27 28 29 30 31 32 33 34 35 36

#include "graph.hh"
#include "graph_selectors.hh"
#include "graph_util.hh"

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


class DJKVisitorWrapper
{
public:
37
    DJKVisitorWrapper(GraphInterface& gi, python::object vis)
Tiago Peixoto's avatar
Tiago Peixoto committed
38 39 40
        : _gi(gi), _vis(vis) {}

    template <class Vertex, class Graph>
41
    void initialize_vertex(Vertex u, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
42
    {
43 44
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _vis.attr("initialize_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
45 46 47
    }

    template <class Vertex, class Graph>
48
    void discover_vertex(Vertex u, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
49
    {
50 51
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _vis.attr("discover_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
52 53 54
    }

    template <class Vertex, class Graph>
55
    void examine_vertex(Vertex u, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
56
    {
57 58
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _vis.attr("examine_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
59 60 61
    }

    template <class Edge, class Graph>
62
    void examine_edge(Edge e, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
63
    {
64 65
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _vis.attr("examine_edge")(PythonEdge<Graph>(gp, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
66 67 68
    }

    template <class Edge, class Graph>
69
    void edge_relaxed(Edge e, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
70
    {
71 72
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _vis.attr("edge_relaxed")(PythonEdge<Graph>(gp, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
73 74 75
    }

    template <class Edge, class Graph>
76
    void edge_not_relaxed(Edge e, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
77
    {
78 79
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _vis.attr("edge_not_relaxed")(PythonEdge<Graph>(gp, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
80 81 82
    }

    template <class Vertex, class Graph>
83
    void finish_vertex(Vertex u, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
84
    {
85 86
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _vis.attr("finish_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
87 88 89
    }

private:
90 91
    GraphInterface& _gi;
    boost::python::object _vis;
Tiago Peixoto's avatar
Tiago Peixoto committed
92 93 94 95 96 97
};


class DJKCmp
{
public:
98
    DJKCmp() {}
Tiago Peixoto's avatar
Tiago Peixoto committed
99 100 101 102 103
    DJKCmp(python::object cmp): _cmp(cmp) {}

    template <class Value1, class Value2>
    bool operator()(const Value1& v1, const Value2& v2) const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
104
        return python::extract<bool>(_cmp(v1, v2));
Tiago Peixoto's avatar
Tiago Peixoto committed
105 106 107 108 109 110 111 112 113
    }

private:
    python::object _cmp;
};

class DJKCmb
{
public:
114
    DJKCmb() {}
Tiago Peixoto's avatar
Tiago Peixoto committed
115 116 117 118 119 120 121 122 123 124 125 126 127 128
    DJKCmb(python::object cmb): _cmb(cmb) {}

    template <class Value1, class Value2 >
    Value1 operator()(const Value1& v1, const Value2& v2) const
    {
        return python::extract<Value1>(_cmb(v1, v2));
    }

private:
    python::object _cmb;
};

struct do_djk_search
{
129
    template <class Graph, class DistanceMap, class PredMap, class Visitor>
Tiago Peixoto's avatar
Tiago Peixoto committed
130
    void operator()(const Graph& g, size_t s, DistanceMap dist,
131 132
                    PredMap pred_map, boost::any aweight,
                    Visitor vis, const DJKCmp& cmp, const DJKCmb& cmb,
Tiago Peixoto's avatar
Tiago Peixoto committed
133 134 135 136 137
                    pair<python::object, python::object> range) const
    {
        typedef typename property_traits<DistanceMap>::value_type dtype_t;
        dtype_t z = python::extract<dtype_t>(range.first);
        dtype_t i = python::extract<dtype_t>(range.second);
138 139 140
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
        DynamicPropertyMapWrap<dtype_t, edge_t> weight(aweight,
                                                       edge_properties());
Tiago Peixoto's avatar
Tiago Peixoto committed
141 142
        dijkstra_shortest_paths_no_color_map
            (g, vertex(s, g), visitor(vis).weight_map(weight).
143
             predecessor_map(pred_map).
Tiago Peixoto's avatar
Tiago Peixoto committed
144 145 146 147 148
             distance_map(dist).distance_compare(cmp).
             distance_combine(cmb).distance_inf(i).distance_zero(z));
    }
};

149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
struct do_djk_search_fast
{
    template <class Graph, class DistanceMap, class WeightMap, class Visitor>
    void operator()(const Graph& g, size_t s, DistanceMap dist,
                    WeightMap weight, Visitor vis,
                    pair<python::object, python::object> range) const
    {
        typedef typename property_traits<DistanceMap>::value_type dtype_t;
        dtype_t z = python::extract<dtype_t>(range.first);
        dtype_t i = python::extract<dtype_t>(range.second);
        dijkstra_shortest_paths_no_color_map
            (g, vertex(s, g), visitor(vis).weight_map(weight).
             distance_map(dist).distance_inf(i).distance_zero(z));
    }
};

Tiago Peixoto's avatar
Tiago Peixoto committed
165

166 167 168 169
void dijkstra_search(GraphInterface& g, size_t source, boost::any dist_map,
                     boost::any pred_map, boost::any weight, python::object vis,
                     python::object cmp, python::object cmb,
                     python::object zero, python::object inf)
Tiago Peixoto's avatar
Tiago Peixoto committed
170
{
171 172 173 174
    typedef typename property_map_type::
        apply<int64_t, GraphInterface::vertex_index_map_t>::type pred_t;
    pred_t pred = any_cast<pred_t>(pred_map);
    run_action<graph_tool::detail::all_graph_views, mpl::true_>()
175
        (g, std::bind(do_djk_search(), placeholders::_1, source,
176
                      placeholders::_2, pred, weight,
177
                      DJKVisitorWrapper(g, vis), DJKCmp(cmp), DJKCmb(cmb),
Tiago Peixoto's avatar
Tiago Peixoto committed
178
                      make_pair(zero, inf)),
179
         writable_vertex_properties())(dist_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
180 181
}

182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233

typedef boost::coroutines::asymmetric_coroutine<boost::python::object> coro_t;

class DJKGeneratorVisitor : public dijkstra_visitor<>
{
public:
    DJKGeneratorVisitor(GraphInterface& gi,
                        coro_t::push_type& yield)
        : _gi(gi), _yield(yield) {}

    template <class Edge, class Graph>
    void edge_relaxed(const Edge& e, Graph& g)
    {
        std::shared_ptr<Graph> gp = retrieve_graph_view<Graph>(_gi, g);
        _yield(boost::python::object(PythonEdge<Graph>(gp, e)));
    }

private:
    GraphInterface& _gi;
    coro_t::push_type& _yield;
};

class DJKGenerator
{
public:
    template <class Dispatch>
    DJKGenerator(Dispatch& dispatch)
        : _coro(std::make_shared<coro_t::pull_type>(dispatch)),
          _iter(begin(*_coro)), _end(end(*_coro)) {}
    boost::python::object next()
    {
        if (_iter == _end)
            boost::python::objects::stop_iteration_error();
        boost::python::object oe = *_iter;
        ++_iter;
        return oe;
    }
private:
    std::shared_ptr<coro_t::pull_type> _coro;
    coro_t::pull_type::iterator _iter;
    coro_t::pull_type::iterator _end;
};

boost::python::object dijkstra_search_generator(GraphInterface& g,
                                                size_t source,
                                                boost::any dist_map,
                                                boost::any weight,
                                                python::object cmp,
                                                python::object cmb,
                                                python::object zero,
                                                python::object inf)
{
Tiago Peixoto's avatar
Tiago Peixoto committed
234
#ifdef HAVE_BOOST_COROUTINE
235 236 237 238 239 240 241 242 243 244 245
    auto dispatch = [&](auto& yield)
        {
            DJKGeneratorVisitor vis(g, yield);
            run_action<graph_tool::detail::all_graph_views, mpl::true_>()
            (g, std::bind(do_djk_search(), placeholders::_1, source,
                          placeholders::_2, dummy_property_map(), weight,
                          vis, DJKCmp(cmp), DJKCmb(cmb),
                          make_pair(zero, inf)),
             writable_vertex_properties())(dist_map);
        };
    return boost::python::object(DJKGenerator(dispatch));
Tiago Peixoto's avatar
Tiago Peixoto committed
246 247 248
#else
    throw GraphException("This functionality is not available because boost::coroutine was not found at compile-time")
#endif
249 250 251 252 253 254 255 256
}

boost::python::object dijkstra_search_generator_fast(GraphInterface& g,
                                                     size_t source,
                                                     boost::any dist_map,
                                                     boost::any weight,
                                                     python::object zero, python::object inf)
{
Tiago Peixoto's avatar
Tiago Peixoto committed
257
#ifdef HAVE_BOOST_COROUTINE
258 259 260 261 262 263 264 265 266 267 268
    auto dispatch = [&](auto& yield)
        {
            DJKGeneratorVisitor vis(g, yield);
            run_action<graph_tool::detail::all_graph_views, mpl::true_>()
            (g, std::bind(do_djk_search_fast(), placeholders::_1, source,
                          placeholders::_2, placeholders::_3,
                          vis, make_pair(zero, inf)),
             writable_vertex_scalar_properties(),
             edge_scalar_properties())(dist_map, weight);
        };
    return boost::python::object(DJKGenerator(dispatch));
Tiago Peixoto's avatar
Tiago Peixoto committed
269 270 271
#else
    throw GraphException("This functionality is not available because boost::coroutine was not found at compile-time")
#endif
272 273
}

Tiago Peixoto's avatar
Tiago Peixoto committed
274 275 276 277
void export_dijkstra()
{
    using namespace boost::python;
    def("dijkstra_search", &dijkstra_search);
278 279 280 281 282 283
    def("dijkstra_generator", &dijkstra_search_generator);
    def("dijkstra_generator_fast", &dijkstra_search_generator_fast);
    class_<DJKGenerator>("DJKGenerator", no_init)
        .def("__iter__", objects::identity_function())
        .def("next", &DJKGenerator::next)
        .def("__next__", &DJKGenerator::next);
Tiago Peixoto's avatar
Tiago Peixoto committed
284
}