graph_bellman_ford.cc 4.67 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) 2007-2011 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
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
67
68
69
70
71
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
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
151
152
153
154
155
156
157
158
//
// 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>
    void examine_edge(Edge e, Graph& g)
    {
        _vis.attr("examine_edge")
            (PythonEdge<typename Graph::orig_graph_t>(_gi, e));
    }

    template <class Edge, class Graph>
    void edge_relaxed(Edge e, Graph& g)
    {
        _vis.attr("edge_relaxed")
            (PythonEdge<typename Graph::orig_graph_t>(_gi, e));
    }

    template <class Edge, class Graph>
    void edge_not_relaxed(Edge e, Graph& g)
    {
        _vis.attr("edge_not_relaxed")
            (PythonEdge<typename Graph::orig_graph_t>(_gi, e));
    }

    template <class Edge, class Graph>
    void edge_minimized(Edge e, Graph& g)
    {
        _vis.attr("edge_minimized")
            (PythonEdge<typename Graph::orig_graph_t>(_gi, e));
    }

    template <class Edge, class Graph>
    void edge_not_minimized(Edge e, Graph& g)
    {
        _vis.attr("edge_not_minimized")
            (PythonEdge<typename Graph::orig_graph_t>(_gi, e));
    }

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
{
    template <class Graph, class DistanceMap, class WeightMap>
    void operator()(const Graph& g, size_t s, DistanceMap dist,
                    boost::any pred_map, WeightMap weight, BFVisitorWrapper vis,
                    pair<BFCmp, BFCmb> cm,
                    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);
        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_>()
        (g, bind<void>(do_bf_search(), _1, source, _2, pred_map, _3,
                        BFVisitorWrapper(gi, vis),
                        make_pair(BFCmp(cmp), BFCmb(cmb)), make_pair(zero, inf),
                        ref(ret)),
         writable_vertex_scalar_properties(),
         edge_scalar_properties())
        (dist_map, weight);
    return ret;
}

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