graph_filtering.cc 11 KB
Newer Older
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>
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 <boost/python/type_id.hpp>
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
// Whenever no implementation is called, the following exception is thrown
35
graph_tool::ActionNotFound::ActionNotFound(const boost::any& graph_view,
36
                                           const type_info& action,
37
38
39
40
41
                                           const vector<const type_info*>& args)
    : GraphException(""), _graph_view(graph_view),
      _action(action), _args(args) {}

const char * graph_tool::ActionNotFound::what () const throw ()
42
43
44
45
46
47
48
49
50
{
    using python::detail::gcc_demangle;

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

51
    error += "Graph view: " + string(gcc_demangle(_graph_view.type().name()))
52
        + "\n\n";
53

54
    error += "Action: " + string(gcc_demangle(_action.name())) + "\n\n";
55
    for (size_t i = 0; i < _args.size(); ++i)
56
57
    {
        error += "Arg " + lexical_cast<string>(i+1) + ": " +
58
            string(gcc_demangle(_args[i]->name())) + "\n\n";
59
    }
60
    return error.c_str();
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
// this function retrieves a graph view stored in graph_views, or stores one if
// non-existent
template <class Graph>
typename remove_const<Graph>::type&
retrieve_graph(vector<boost::any>& graph_views, Graph& init)
{
    typedef typename remove_const<Graph>::type g_t;
    size_t index = mpl::find<all_graph_views,g_t>::type::pos::value;
    if (index >= graph_views.size())
        graph_views.resize(index+1);
    boost::any gview = graph_views[index];
    shared_ptr<g_t>* gptr = any_cast<shared_ptr<g_t> >(&gview);
    if (gptr == 0)
    {
        shared_ptr<g_t> new_g(new g_t(init));
        gptr = &new_g;
        gview = new_g;
        graph_views[index] = gview;
    }
    return **gptr;
}


// this will check whether a graph is reversed and return the proper view
// encapsulated
template <class Graph>
boost::any check_reverse(const Graph &g, bool reverse,
                         vector<boost::any>& graph_views)
{
    if (reverse)
    {
        typedef typename mpl::if_<is_const<Graph>,
                                  const reverse_graph
                                      <typename remove_const<Graph>::type>,
                                  reverse_graph<Graph> >::type
            reverse_graph_t;

        reverse_graph_t rg(g);
        return &retrieve_graph(graph_views, rg);
    }

    return boost::any(&const_cast<Graph&>(g));
};

// 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,
                          vector<boost::any>& graph_views)
{
    if (directed)
    {
        return check_reverse(g, reverse, graph_views);
    }

    typedef UndirectedAdaptor<Graph> ug_t;
    ug_t ug(g);
    return &retrieve_graph(graph_views, ug);
};

// this will check whether a graph is filtered and return the proper view
// encapsulated
template <class Graph, class EdgeFilter, class VertexFilter>
boost::any
127
check_filtered(const Graph &g, const EdgeFilter& edge_filter,
128
               const bool& e_invert, bool e_active, size_t max_eindex,
129
               const VertexFilter& vertex_filter, const bool& v_invert,
130
131
132
133
134
135
136
137
138
               bool v_active, vector<boost::any>& graph_views, bool reverse,
               bool directed)
{
#ifndef NO_GRAPH_FILTERING
    MaskFilter<EdgeFilter> e_filter(edge_filter, e_invert);
    MaskFilter<VertexFilter> v_filter(vertex_filter, v_invert);

    if (e_active)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
139
140
        if (max_eindex > 0)
            edge_filter.reserve(max_eindex+1);
141
142
        if (v_active)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
143
144
            if (num_vertices(g) > 0)
                vertex_filter.reserve(num_vertices(g));
145
146
147
148
149
            typedef filtered_graph<Graph, MaskFilter<EdgeFilter>,
                                   MaskFilter<VertexFilter> > fg_t;
            fg_t init(g, e_filter, v_filter);
            fg_t& fg = retrieve_graph(graph_views, init);
            fg.m_edge_pred = e_filter;
150
            fg.m_vertex_pred = v_filter;
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
            return check_directed(fg, reverse, directed, graph_views);
        }
        else
        {
            typedef filtered_graph<Graph, MaskFilter<EdgeFilter>,
                                   keep_all> fg_t;
            fg_t init(g, e_filter, keep_all());
            fg_t& fg = retrieve_graph(graph_views, init);
            fg.m_edge_pred = e_filter;
            return check_directed(fg, reverse, directed, graph_views);
        }
    }
    else
    {
        if (v_active)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
167
168
            if (num_vertices(g) > 0)
                vertex_filter.reserve(num_vertices(g));
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
            typedef filtered_graph<Graph, keep_all,
                                   MaskFilter<VertexFilter> > fg_t;
            fg_t init(g, keep_all(), v_filter);
            fg_t& fg = retrieve_graph(graph_views, init);
            fg.m_vertex_pred = v_filter;
            return check_directed(fg, reverse, directed, graph_views);
        }
        else
        {
            return check_directed(g, reverse, directed, graph_views);
        }
    }
#else
    return check_directed(g, reverse, directed, graph_views);
#endif
}

// gets the correct graph view at run time
boost::any GraphInterface::GetGraphView() const
{
    // TODO: implement memoization

191
    boost::any graph =
Tiago Peixoto's avatar
Tiago Peixoto committed
192
193
194
195
196
197
        check_filtered(_state->_mg, _edge_filter_map, _edge_filter_invert,
                       _edge_filter_active, _state->_max_edge_index,
                       _vertex_filter_map, _vertex_filter_invert,
                       _vertex_filter_active,
                       const_cast<vector<boost::any>&>(_graph_views), _reversed,
                       _directed);
198
199
200
    return graph;
}

201
// these test whether or not the vertex and edge filters are active
202
203
204
205
206
207
bool GraphInterface::IsVertexFilterActive() const
{ return _vertex_filter_active; }

bool GraphInterface::IsEdgeFilterActive() const
{ return _edge_filter_active; }

208

209
// this function will reindex all the edges, in the order in which they are
210
// found
211
void GraphInterface::ReIndexEdges()
212
{
213
    size_t index = 0;
214
    graph_traits<multigraph_t>::edge_iterator e, e_end;
Tiago Peixoto's avatar
Tiago Peixoto committed
215
    for (tie(e, e_end) = edges(_state->_mg); e != e_end; ++e)
216
        _edge_index[*e] = index++;
Tiago Peixoto's avatar
Tiago Peixoto committed
217
218
219
    _state->_max_edge_index = (index > 0) ? index - 1 : 0;
    _state->_nedges = index;
    _state->_free_indexes.clear();
220
221
222
223
224
225
226
227
228
229
230
231
232
}

// this will definitively remove all the edges from the graph, which are being
// currently filtered out. This will also disable the edge filter
void GraphInterface::PurgeEdges()
{
    if (!IsEdgeFilterActive())
        return;

    MaskFilter<edge_filter_t> filter(_edge_filter_map, _edge_filter_invert);
    graph_traits<multigraph_t>::vertex_iterator v, v_end;
    graph_traits<multigraph_t>::out_edge_iterator e, e_end;
    vector<graph_traits<multigraph_t>::edge_descriptor> deleted_edges;
Tiago Peixoto's avatar
Tiago Peixoto committed
233
    for (tie(v, v_end) = vertices(_state->_mg); v != v_end; ++v)
234
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
235
        for (tie(e, e_end) = out_edges(*v, _state->_mg); e != e_end; ++e)
236
237
238
239
            if (!filter(*e))
                deleted_edges.push_back(*e);
        for (typeof(deleted_edges.begin()) iter = deleted_edges.begin();
             iter != deleted_edges.end(); ++iter)
Tiago Peixoto's avatar
Tiago Peixoto committed
240
            RemoveEdgeIndex(*iter);
241
242
243
244
245
        deleted_edges.clear();
    }
}


246
// this will definitively remove all the vertices from the graph, which are
247
// being currently filtered out. This will also disable the vertex filter
248
void GraphInterface::PurgeVertices(boost::any aold_index)
249
250
251
252
{
    if (!IsVertexFilterActive())
        return;

253
254
255
256
257
    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);

258
259
    MaskFilter<vertex_filter_t> filter(_vertex_filter_map,
                                       _vertex_filter_invert);
Tiago Peixoto's avatar
Tiago Peixoto committed
260
    size_t N = num_vertices(_state->_mg);
261
262
    vector<bool> deleted(N, false);
    for (size_t i = 0; i < N; ++i)
Tiago Peixoto's avatar
Tiago Peixoto committed
263
        deleted[i] = !filter(vertex(i, _state->_mg));
264
    vector<int> old_indexes;
265

266
267
    vector<graph_traits<multigraph_t>::edge_descriptor> edges;

268
    //remove vertices
269
    for (int i = N-1; i >= 0; --i)
270
271
272
    {
        if (deleted[i])
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
273
274
            graph_traits<multigraph_t>::vertex_descriptor v =
                vertex(i, _state->_mg);
275
            graph_traits<multigraph_t>::out_edge_iterator e, e_end;
Tiago Peixoto's avatar
Tiago Peixoto committed
276
            for(tie(e, e_end) = out_edges(v, _state->_mg); e != e_end; ++e)
277
                edges.push_back(*e);
278
            graph_traits<multigraph_t>::in_edge_iterator ei, ei_end;
Tiago Peixoto's avatar
Tiago Peixoto committed
279
            for(tie(ei, ei_end) = in_edges(v, _state->_mg); ei != ei_end; ++ei)
280
281
282
                edges.push_back(*ei);
            for(size_t j = 0; j < edges.size(); ++j)
                RemoveEdgeIndex(edges[j]);
Tiago Peixoto's avatar
Tiago Peixoto committed
283
284
            clear_vertex(v, _state->_mg);
            remove_vertex(v, _state->_mg);
285
            edges.clear();
286
        }
287
288
289
290
291
292
293
294
295
296
        else
        {
            old_indexes.push_back(i);
        }
    }

    N = old_indexes.size();
    for (int i = N-1; i >= 0; --i)
    {
        old_index[vertex((N - 1) - i, _state->_mg)] = old_indexes[i];
297
298
299
    }
}

300
void GraphInterface::SetVertexFilterProperty(boost::any property, bool invert)
301
302
303
304
305
306
307
{
#ifdef NO_GRAPH_FILTERING
    throw GraphException("graph filtering was not enabled at compile time");
#endif

    try
    {
308
        _vertex_filter_map =
309
            any_cast<vertex_filter_t::checked_t>(property).get_unchecked();
310
311
312
        _vertex_filter_invert = invert;
        _vertex_filter_active = true;
    }
313
    catch(bad_any_cast&)
314
    {
315
        _vertex_filter_active = false;
316
317
318
    }
}

319
void GraphInterface::SetEdgeFilterProperty(boost::any property, bool invert)
320
321
322
323
324
325
326
{
#ifdef NO_GRAPH_FILTERING
    throw GraphException("graph filtering was not enabled at compile time");
#endif

    try
    {
327
        _edge_filter_map =
328
            any_cast<edge_filter_t::checked_t>(property).get_unchecked();
329
330
331
        _edge_filter_invert = invert;
        _edge_filter_active = true;
    }
332
    catch(bad_any_cast&)
333
    {
334
        _edge_filter_active = false;
335
336
337
    }
}