graph_filtering.cc 8.83 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 boost::any& graph_view,
45
                                           const type_info& action,
46
47
48
49
50
                                           const vector<const type_info*>& args)
    : GraphException(""), _graph_view(graph_view),
      _action(action), _args(args) {}

const char * graph_tool::ActionNotFound::what () const throw ()
51
52
53
54
55
{
    using python::detail::gcc_demangle;

    string error =
        "No static implementation was found for the desired routine. "
56
        "This is a graph_tool bug. :-( Please follow bug report "
57
58
59
        "instructions at " PACKAGE_BUGREPORT ". What follows is debug "
        "information.\n\n";

60
61
    error += "Graph view: " + name_demangle(_graph_view.type().name()) + "\n\n";
    error += "Action: " + name_demangle(_action.name()) + "\n\n";
62
    for (size_t i = 0; i < _args.size(); ++i)
63
64
    {
        error += "Arg " + lexical_cast<string>(i+1) + ": " +
65
            name_demangle(_args[i]->name()) + "\n\n";
66
    }
67
    return error.c_str();
68
69
}

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

        reverse_graph_t rg(g);
83
        return retrieve_graph_view(gi, rg).get();
84
85
    }

86
    return boost::any(const_cast<Graph*>(&g));
87
88
89
90
91
92
};

// 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,
93
                          GraphInterface& gi)
94
95
96
{
    if (directed)
    {
97
        return check_reverse(g, reverse, gi);
98
99
100
101
    }

    typedef UndirectedAdaptor<Graph> ug_t;
    ug_t ug(g);
102
    return retrieve_graph_view(gi, ug).get();
103
104
105
106
107
108
};

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

    if (e_active)
    {
122
123
124
        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
125
        if (max_eindex > 0)
126
            edge_filter.reserve(max_eindex);
127
128
129
130
131
        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);
132
        fg_t& fg = *retrieve_graph_view(gi, init).get();
133
134
        fg.m_edge_pred = e_filter;
        fg.m_vertex_pred = v_filter;
135
        return check_directed(fg, reverse, directed, gi);
136
137
138
139
    }
    else
    {
        if (v_active)
140
141
            throw GraphException("Vertex filter is active but edge filter is not. This is a bug.");

142
        return check_directed(g, reverse, directed, gi);
143
144
    }
#else
145
    return check_directed(g, reverse, directed, gi);
146
147
148
149
#endif
}

// gets the correct graph view at run time
150
boost::any GraphInterface::get_graph_view() const
151
{
152
    boost::any graph =
153
        check_filtered(*_mg, _edge_filter_map, _edge_filter_invert,
154
                       _edge_filter_active, _mg->get_edge_index_range(),
Tiago Peixoto's avatar
Tiago Peixoto committed
155
156
                       _vertex_filter_map, _vertex_filter_invert,
                       _vertex_filter_active,
157
                       const_cast<GraphInterface&>(*this), _reversed,
Tiago Peixoto's avatar
Tiago Peixoto committed
158
                       _directed);
159
160
161
    return graph;
}

162
// these test whether or not the vertex and edge filters are active
163
bool GraphInterface::is_vertex_filter_active() const
164
165
{ return _vertex_filter_active; }

166
bool GraphInterface::is_edge_filter_active() const
167
168
{ return _edge_filter_active; }

169

170
// this function will reindex all the edges, in the order in which they are
171
// found
172
void GraphInterface::re_index_edges()
173
{
174
    _mg->reindex_edges();
175
176
177
178
}

// this will definitively remove all the edges from the graph, which are being
// currently filtered out. This will also disable the edge filter
179
void GraphInterface::purge_edges()
180
{
181
    if (!is_edge_filter_active())
182
183
184
185
        return;

    MaskFilter<edge_filter_t> filter(_edge_filter_map, _edge_filter_invert);
    vector<graph_traits<multigraph_t>::edge_descriptor> deleted_edges;
186
    for (auto v : vertices_range(*_mg))
187
    {
188
189
190
191
192
        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);
193
194
195
196
197
        deleted_edges.clear();
    }
}


198
// this will definitively remove all the vertices from the graph, which are
199
// being currently filtered out. This will also disable the vertex filter
200
void GraphInterface::purge_vertices(boost::any aold_index)
201
{
202
    if (!is_vertex_filter_active())
203
204
        return;

205
206
207
208
209
    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);

210
211
    MaskFilter<vertex_filter_t> filter(_vertex_filter_map,
                                       _vertex_filter_invert);
212
    size_t N = num_vertices(*_mg);
213
214
    vector<bool> deleted(N, false);
    for (size_t i = 0; i < N; ++i)
215
        deleted[i] = !filter(vertex(i, *_mg));
216
    vector<int> old_indexes;
217

218
219
    vector<graph_traits<multigraph_t>::edge_descriptor> edges;

220
    //remove vertices
221
    for (int i = N-1; i >= 0; --i)
222
223
224
    {
        if (deleted[i])
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
225
            graph_traits<multigraph_t>::vertex_descriptor v =
226
227
                vertex(i, *_mg);
            remove_vertex(v, *_mg);
228
        }
229
230
231
232
233
234
235
236
237
        else
        {
            old_indexes.push_back(i);
        }
    }

    N = old_indexes.size();
    for (int i = N-1; i >= 0; --i)
    {
238
        old_index[vertex((N - 1) - i, *_mg)] = old_indexes[i];
239
240
241
    }
}

242
void GraphInterface::set_vertex_filter_property(boost::any property, bool invert)
243
244
245
246
247
248
249
{
#ifdef NO_GRAPH_FILTERING
    throw GraphException("graph filtering was not enabled at compile time");
#endif

    try
    {
250
        _vertex_filter_map =
251
            any_cast<vertex_filter_t::checked_t>(property).get_unchecked();
252
253
254
        _vertex_filter_invert = invert;
        _vertex_filter_active = true;
    }
255
    catch(bad_any_cast&)
256
    {
257
258
        if (!property.empty())
            throw GraphException("Invalid vertex filter property!");
259
        _vertex_filter_active = false;
260
261
262
    }
}

263
void GraphInterface::set_edge_filter_property(boost::any property, bool invert)
264
265
266
267
268
269
270
{
#ifdef NO_GRAPH_FILTERING
    throw GraphException("graph filtering was not enabled at compile time");
#endif

    try
    {
271
        _edge_filter_map =
272
            any_cast<edge_filter_t::checked_t>(property).get_unchecked();
273
274
275
        _edge_filter_invert = invert;
        _edge_filter_active = true;
    }
276
    catch(bad_any_cast&)
277
    {
278
279
        if (!property.empty())
            throw GraphException("Invalid edge filter property!");
280
        _edge_filter_active = false;
281
282
    }
}