graph_dfs.cc 2.89 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
19
20
21
22
23
24
25
26
27
28
29
30
31
// 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"

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


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


    template <class Vertex, class Graph>
32
    void initialize_vertex(Vertex u, const Graph&)
Tiago Peixoto's avatar
Tiago Peixoto committed
33
34
35
36
    {
        _vis.attr("initialize_vertex")(PythonVertex(_gi, u));
    }
    template <class Vertex, class Graph>
37
    void start_vertex(Vertex u, const Graph&)
Tiago Peixoto's avatar
Tiago Peixoto committed
38
39
40
41
    {
        _vis.attr("start_vertex")(PythonVertex(_gi, u));
    }
    template <class Vertex, class Graph>
42
    void discover_vertex(Vertex u, const Graph&)
Tiago Peixoto's avatar
Tiago Peixoto committed
43
44
45
46
47
    {
        _vis.attr("discover_vertex")(PythonVertex(_gi, u));
    }

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

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

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

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

    template <class Vertex, class Graph>
76
    void finish_vertex(Vertex u, const Graph&)
Tiago Peixoto's avatar
Tiago Peixoto committed
77
78
79
80
81
82
83
84
85
86
    {
        _vis.attr("finish_vertex")(PythonVertex(_gi, u));
    }

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

struct do_dfs
{
87
88
    template <class Graph, class VertexIndexMap>
    void operator()(Graph& g, VertexIndexMap vertex_index, size_t s,
Tiago Peixoto's avatar
Tiago Peixoto committed
89
90
91
                    DFSVisitorWrapper vis) const
    {
        typename property_map_type::apply<default_color_type,
92
93
94
                                          VertexIndexMap>::type
            color(vertex_index);
        depth_first_visit(g, vertex(s, g), vis, color);
Tiago Peixoto's avatar
Tiago Peixoto committed
95
96
97
98
99
100
101
102
    }
};


void dfs_search(GraphInterface& g, python::object gi, size_t s,
                python::object vis)
{
    run_action<graph_tool::detail::all_graph_views,mpl::true_>()
103
104
        (g, bind<void>(do_dfs(), _1, g.GetVertexIndex(),
                       s, DFSVisitorWrapper(gi, vis)))();
Tiago Peixoto's avatar
Tiago Peixoto committed
105
106
107
108
109
110
111
}

void export_dfs()
{
    using namespace boost::python;
    def("dfs_search", &dfs_search);
}