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-2012 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
    }
}