graph_bellman_ford.cc 4.72 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-2013 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//
// 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/bellman_ford_shortest_paths.hpp>

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

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


class BFVisitorWrapper
{
public:
    BFVisitorWrapper(python::object gi, python::object vis)
        : _gi(gi), _vis(vis) {}

    template <class Edge, class Graph>
40
    void examine_edge(Edge e, const Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
41
42
    {
        _vis.attr("examine_edge")
43
            (PythonEdge<Graph>(_gi, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
44
45
46
    }

    template <class Edge, class Graph>
47
    void edge_relaxed(Edge e, const Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
48
49
    {
        _vis.attr("edge_relaxed")
50
            (PythonEdge<Graph>(_gi, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
51
52
53
    }

    template <class Edge, class Graph>
54
    void edge_not_relaxed(Edge e, const Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
55
56
    {
        _vis.attr("edge_not_relaxed")
57
            (PythonEdge<Graph>(_gi, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
58
59
60
    }

    template <class Edge, class Graph>
61
    void edge_minimized(Edge e, const Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
62
63
    {
        _vis.attr("edge_minimized")
64
            (PythonEdge<Graph>(_gi, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
65
66
67
    }

    template <class Edge, class Graph>
68
    void edge_not_minimized(Edge e, const Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
69
70
    {
        _vis.attr("edge_not_minimized")
71
            (PythonEdge<Graph>(_gi, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
72
73
74
75
76
77
78
79
80
81
82
83
84
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
    }

private:
    python::object _gi, _vis;
};


class BFCmp
{
public:
    BFCmp(python::object cmp): _cmp(cmp) {}

    template <class Value1, class Value2>
    bool operator()(const Value1& v1, const Value2& v2) const
    {
        return extract<bool>(_cmp(v1, v2));
    }

private:
    python::object _cmp;
};

class BFCmb
{
public:
    BFCmb(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_bf_search
{
111
    template <class Graph, class DistanceMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
112
    void operator()(const Graph& g, size_t s, DistanceMap dist,
113
114
                    boost::any pred_map, boost::any aweight,
                    BFVisitorWrapper vis, pair<BFCmp, BFCmb> cm,
Tiago Peixoto's avatar
Tiago Peixoto committed
115
116
117
118
119
120
121
122
123
                    pair<python::object, python::object> range, bool& ret) 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);

        typedef typename property_map_type::
            apply<int32_t, typeof(get(vertex_index, g))>::type pred_t;
        pred_t pred = any_cast<pred_t>(pred_map);
124
125
126
        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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
        ret = bellman_ford_shortest_paths
            (g, HardNumVertices()(g),
             root_vertex(vertex(s, g)).visitor(vis).weight_map(weight).
             distance_map(dist).
             predecessor_map(pred).
             distance_compare(cm.first).
             distance_combine(cm.second).distance_inf(i).
             distance_zero(z));
    }
};


bool bellman_ford_search(GraphInterface& g, python::object gi, 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)
{
    bool ret = false;
    run_action<graph_tool::detail::all_graph_views,mpl::true_>()
147
148
149
150
151
152
        (g, bind<void>(do_bf_search(), _1, source, _2, pred_map, weight,
                       BFVisitorWrapper(gi, vis),
                       make_pair(BFCmp(cmp), BFCmb(cmb)), make_pair(zero, inf),
                       ref(ret)),
         writable_vertex_properties())
        (dist_map);
Tiago Peixoto's avatar
Tiago Peixoto committed
153
154
155
156
157
158
159
160
    return ret;
}

void export_bellman_ford()
{
    using namespace boost::python;
    def("bellman_ford_search", &bellman_ford_search);
}