graph_filtering.cc 8.56 KB
Newer Older
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>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//
// 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"
19
#include <cxxabi.h>
20
21
22
23
24

using namespace graph_tool;
using namespace graph_tool::detail;
using namespace boost;

25
26
27
28
29
30
31
32
33
bool graph_tool::graph_filtering_enabled()
{
#ifndef NO_GRAPH_FILTERING
    return true;
#else
    return false;
#endif
}

34
35
36
37
38
39
40
41
42
string name_demangle(string name)
{
    int status = 0;
    char *realname = abi::__cxa_demangle(name.c_str(), 0, 0, &status);
    string ret(realname);
    free(realname);
    return ret;
}

43
// Whenever no implementation is called, the following exception is thrown
44
graph_tool::ActionNotFound::ActionNotFound(const type_info& action,
45
                                           const vector<const type_info*>& args)
46
    : GraphException(""), _action(action), _args(args)
47
48
49
{
    using python::detail::gcc_demangle;

50
    _error =
51
        "No static implementation was found for the desired routine. "
52
53
        "This is a graph_tool bug. :-( Please submit a bug report at "
        PACKAGE_BUGREPORT ". What follows is debug information.\n\n";
54

55
    _error += "Action: " + name_demangle(_action.name()) + "\n\n";
56
    for (size_t i = 0; i < _args.size(); ++i)
57
    {
58
        _error += "Arg " + lexical_cast<string>(i+1) + ": " +
59
            name_demangle(_args[i]->name()) + "\n\n";
60
61
62
    }
}

63
64
65
// this will check whether a graph is reversed and return the proper view
// encapsulated
template <class Graph>
66
boost::any check_reverse(const Graph& g, bool reverse, GraphInterface& gi)
67
68
69
{
    if (reverse)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
70
71
72
        typedef typename boost::mpl::if_<std::is_const<Graph>,
                                         const reverse_graph<typename std::remove_const<Graph>::type>,
                                         reverse_graph<Graph> >::type
73
74
75
            reverse_graph_t;

        reverse_graph_t rg(g);
76
        return std::ref(*retrieve_graph_view(gi, rg).get());
77
78
    }

79
    return boost::any(std::ref(const_cast<Graph&>(g)));
80
81
82
83
84
85
};

// this will check whether a graph is directed and return the proper view
// encapsulated
template <class Graph>
boost::any check_directed(const Graph &g, bool reverse, bool directed,
86
                          GraphInterface& gi)
87
88
89
{
    if (directed)
    {
90
        return check_reverse(g, reverse, gi);
91
92
93
94
    }

    typedef UndirectedAdaptor<Graph> ug_t;
    ug_t ug(g);
95
    return std::ref(*retrieve_graph_view(gi, ug).get());
96
97
98
99
100
101
};

// this will check whether a graph is filtered and return the proper view
// encapsulated
template <class Graph, class EdgeFilter, class VertexFilter>
boost::any
102
check_filtered(const Graph &g, const EdgeFilter& edge_filter,
103
               const bool& e_invert, bool e_active, size_t max_eindex,
104
               const VertexFilter& vertex_filter, const bool& v_invert,
105
               bool v_active, GraphInterface& gi, bool reverse, bool directed)
106
107
{
#ifndef NO_GRAPH_FILTERING
108
109
110
111
    MaskFilter<EdgeFilter> e_filter(const_cast<EdgeFilter&>(edge_filter),
                                    e_invert);
    MaskFilter<VertexFilter> v_filter(const_cast<VertexFilter&>(vertex_filter),
                                      v_invert);
112
113
114

    if (e_active)
    {
115
116
117
        if (!v_active)
            throw GraphException("Edge filter is active but vertex filter is not. This is a bug.");

Tiago Peixoto's avatar
Tiago Peixoto committed
118
        if (max_eindex > 0)
119
            edge_filter.reserve(max_eindex);
120
121
122
123
124
        if (num_vertices(g) > 0)
            vertex_filter.reserve(num_vertices(g));
        typedef filtered_graph<Graph, MaskFilter<EdgeFilter>,
                               MaskFilter<VertexFilter> > fg_t;
        fg_t init(g, e_filter, v_filter);
125
        fg_t& fg = *retrieve_graph_view(gi, init).get();
126
127
        fg.m_edge_pred = e_filter;
        fg.m_vertex_pred = v_filter;
128
        return check_directed(fg, reverse, directed, gi);
129
130
131
132
    }
    else
    {
        if (v_active)
133
134
            throw GraphException("Vertex filter is active but edge filter is not. This is a bug.");

135
        return check_directed(g, reverse, directed, gi);
136
137
    }
#else
138
    return check_directed(g, reverse, directed, gi);
139
140
141
142
#endif
}

// gets the correct graph view at run time
143
boost::any GraphInterface::get_graph_view() const
144
{
145
    boost::any graph =
146
        check_filtered(*_mg, _edge_filter_map, _edge_filter_invert,
147
                       _edge_filter_active, _mg->get_edge_index_range(),
Tiago Peixoto's avatar
Tiago Peixoto committed
148
149
                       _vertex_filter_map, _vertex_filter_invert,
                       _vertex_filter_active,
150
                       const_cast<GraphInterface&>(*this), _reversed,
Tiago Peixoto's avatar
Tiago Peixoto committed
151
                       _directed);
152
153
154
    return graph;
}

155
// these test whether or not the vertex and edge filters are active
156
bool GraphInterface::is_vertex_filter_active() const
157
158
{ return _vertex_filter_active; }

159
bool GraphInterface::is_edge_filter_active() const
160
161
{ return _edge_filter_active; }

162

163
// this function will reindex all the edges, in the order in which they are
164
// found
165
void GraphInterface::re_index_edges()
166
{
167
    _mg->reindex_edges();
168
169
170
171
}

// this will definitively remove all the edges from the graph, which are being
// currently filtered out. This will also disable the edge filter
172
void GraphInterface::purge_edges()
173
{
174
    if (!is_edge_filter_active())
175
176
177
178
        return;

    MaskFilter<edge_filter_t> filter(_edge_filter_map, _edge_filter_invert);
    vector<graph_traits<multigraph_t>::edge_descriptor> deleted_edges;
179
    for (auto v : vertices_range(*_mg))
180
    {
181
182
183
184
185
        for (auto e : out_edges_range(v, *_mg))
            if (!filter(e))
                deleted_edges.push_back(e);
        for (auto& e  : deleted_edges)
            remove_edge(e, *_mg);
186
187
188
189
190
        deleted_edges.clear();
    }
}


191
// this will definitively remove all the vertices from the graph, which are
192
// being currently filtered out. This will also disable the vertex filter
193
void GraphInterface::purge_vertices(boost::any aold_index)
194
{
195
    if (!is_vertex_filter_active())
196
197
        return;

198
199
200
201
202
    typedef property_map_type::apply<int32_t,
                                     GraphInterface::vertex_index_map_t>::type
        index_prop_t;
    index_prop_t old_index = any_cast<index_prop_t>(aold_index);

203
204
    MaskFilter<vertex_filter_t> filter(_vertex_filter_map,
                                       _vertex_filter_invert);
205
    size_t N = num_vertices(*_mg);
206
207
    vector<bool> deleted(N, false);
    for (size_t i = 0; i < N; ++i)
208
        deleted[i] = !filter(vertex(i, *_mg));
209
    vector<int> old_indexes;
210

211
212
    vector<graph_traits<multigraph_t>::edge_descriptor> edges;

213
    //remove vertices
214
    for (int i = N-1; i >= 0; --i)
215
216
217
    {
        if (deleted[i])
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
218
            graph_traits<multigraph_t>::vertex_descriptor v =
219
220
                vertex(i, *_mg);
            remove_vertex(v, *_mg);
221
        }
222
223
224
225
226
227
228
229
230
        else
        {
            old_indexes.push_back(i);
        }
    }

    N = old_indexes.size();
    for (int i = N-1; i >= 0; --i)
    {
231
        old_index[vertex((N - 1) - i, *_mg)] = old_indexes[i];
232
233
234
    }
}

235
void GraphInterface::set_vertex_filter_property(boost::any property, bool invert)
236
237
238
239
240
241
242
{
#ifdef NO_GRAPH_FILTERING
    throw GraphException("graph filtering was not enabled at compile time");
#endif

    try
    {
243
        _vertex_filter_map =
244
            any_cast<vertex_filter_t::checked_t>(property).get_unchecked();
245
246
247
        _vertex_filter_invert = invert;
        _vertex_filter_active = true;
    }
248
    catch(bad_any_cast&)
249
    {
250
251
        if (!property.empty())
            throw GraphException("Invalid vertex filter property!");
252
        _vertex_filter_active = false;
253
254
255
    }
}

256
void GraphInterface::set_edge_filter_property(boost::any property, bool invert)
257
258
259
260
261
262
263
{
#ifdef NO_GRAPH_FILTERING
    throw GraphException("graph filtering was not enabled at compile time");
#endif

    try
    {
264
        _edge_filter_map =
265
            any_cast<edge_filter_t::checked_t>(property).get_unchecked();
266
267
268
        _edge_filter_invert = invert;
        _edge_filter_active = true;
    }
269
    catch(bad_any_cast&)
270
    {
271
272
        if (!property.empty())
            throw GraphException("Invalid edge filter property!");
273
        _edge_filter_active = false;
274
275
    }
}