graph_dfs.cc 4.52 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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/depth_first_search.hpp>
#include <boost/graph/undirected_dfs.hpp>

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

19
20
21
22
#ifdef HAVE_BOOST_COROUTINE
#include <boost/coroutine/all.hpp>
#endif // HAVE_BOOST_COROUTINE

Tiago Peixoto's avatar
Tiago Peixoto committed
23
24
25
26
27
28
29
30
using namespace std;
using namespace boost;
using namespace graph_tool;


class DFSVisitorWrapper
{
public:
31
    DFSVisitorWrapper(GraphInterface& gi, python::object vis)
Tiago Peixoto's avatar
Tiago Peixoto committed
32
33
34
35
        : _gi(gi), _vis(vis) {}


    template <class Vertex, class Graph>
36
    void initialize_vertex(Vertex u, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
37
    {
38
        auto gp = retrieve_graph_view<Graph>(_gi, g);
39
        _vis.attr("initialize_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
40
41
    }
    template <class Vertex, class Graph>
42
    void start_vertex(Vertex u, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
43
    {
44
        auto gp = retrieve_graph_view<Graph>(_gi, g);
45
        _vis.attr("start_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
46
47
    }
    template <class Vertex, class Graph>
48
    void discover_vertex(Vertex u, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
49
    {
50
        auto gp = retrieve_graph_view<Graph>(_gi, g);
51
        _vis.attr("discover_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
52
53
54
    }

    template <class Edge, class Graph>
55
    void examine_edge(Edge e, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
56
    {
57
        auto gp = retrieve_graph_view<Graph>(_gi, g);
58
        _vis.attr("examine_edge")(PythonEdge<Graph>(gp, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
59
60
61
    }

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

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

    template <class Edge, class Graph>
76
    void forward_or_cross_edge(Edge e, Graph& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
77
    {
78
        auto gp = retrieve_graph_view<Graph>(_gi, g);
79
        _vis.attr("forward_or_cross_edge")(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
        auto gp = retrieve_graph_view<Graph>(_gi, g);
86
        _vis.attr("finish_vertex")(PythonVertex<Graph>(gp, u));
Tiago Peixoto's avatar
Tiago Peixoto committed
87
88
89
    }

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

struct do_dfs
{
96
    template <class Graph, class VertexIndexMap, class Visitor>
97
    void operator()(Graph& g, VertexIndexMap vertex_index, size_t s,
98
                    Visitor vis) const
Tiago Peixoto's avatar
Tiago Peixoto committed
99
100
    {
        typename property_map_type::apply<default_color_type,
101
102
103
                                          VertexIndexMap>::type
            color(vertex_index);
        depth_first_visit(g, vertex(s, g), vis, color);
Tiago Peixoto's avatar
Tiago Peixoto committed
104
105
106
107
    }
};


108
void dfs_search(GraphInterface& g, size_t s, python::object vis)
Tiago Peixoto's avatar
Tiago Peixoto committed
109
110
{
    run_action<graph_tool::detail::all_graph_views,mpl::true_>()
111
        (g, std::bind(do_dfs(), std::placeholders::_1, g.get_vertex_index(),
112
                      s, DFSVisitorWrapper(g, vis)))();
Tiago Peixoto's avatar
Tiago Peixoto committed
113
114
}

115
#ifdef HAVE_BOOST_COROUTINE
116
117
118
119
120
121
122
123
124
125
126

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

    template <class Edge, class Graph>
    void tree_edge(const Edge& e, Graph& g)
    {
127
        auto gp = retrieve_graph_view<Graph>(_gi, g);
128
129
130
131
132
133
134
135
        _yield(boost::python::object(PythonEdge<Graph>(gp, e)));
    }

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

136
137
138
#endif // HAVE_BOOST_COROUTINE


139
140
boost::python::object dfs_search_generator(GraphInterface& g, size_t s)
{
Tiago Peixoto's avatar
Tiago Peixoto committed
141
#ifdef HAVE_BOOST_COROUTINE
142
143
144
145
    auto dispatch = [&](auto& yield)
        {
            DFSGeneratorVisitor vis(g, yield);
            run_action<graph_tool::detail::all_graph_views,mpl::true_>()
146
                (g, std::bind(do_dfs(), std::placeholders::_1,
147
148
                              g.get_vertex_index(), s, vis))();
        };
149
    return boost::python::object(CoroGenerator(dispatch));
Tiago Peixoto's avatar
Tiago Peixoto committed
150
#else
151
    throw GraphException("This functionality is not available because boost::coroutine was not found at compile-time");
Tiago Peixoto's avatar
Tiago Peixoto committed
152
#endif
153
154
}

Tiago Peixoto's avatar
Tiago Peixoto committed
155
156
157
158
void export_dfs()
{
    using namespace boost::python;
    def("dfs_search", &dfs_search);
159
    def("dfs_search_generator", &dfs_search_generator);
Tiago Peixoto's avatar
Tiago Peixoto committed
160
}