graph_motifs.cc 4.58 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 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
//
// 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"

#include "graph.hh"
#include "graph_selectors.hh"
#include "graph_properties.hh"

#include "graph_motifs.hh"

#include <boost/python.hpp>

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

struct null_copy
{
    template <class T1, class T2>
        void operator()(const T1& t1, const T2& t2) const {}
};

struct append_to_list
{

    template <class Graph>
42
    void operator()(Graph& g, boost::any& list) const
43 44 45 46 47 48
    {
        typedef typename mpl::if_<typename is_directed::apply<Graph>::type,
                                  d_graph_t,
                                  u_graph_t>::type graph_t;
        vector<graph_t>& glist = any_cast<vector<graph_t>&>(list);
        glist.push_back(graph_t());
49
        copy_graph(g, glist.back(), vertex_copy(null_copy()).
50 51 52 53 54 55 56
                   edge_copy(null_copy()));
    }
};

struct retrieve_from_list
{
    template <class Graph>
57
    void operator()(Graph& g, boost::any& list, bool& done) const
58 59 60 61 62 63 64 65 66 67
    {
        typedef typename mpl::if_<typename is_directed::apply<Graph>::type,
                                  d_graph_t,
                                  u_graph_t>::type graph_t;
        vector<graph_t>& glist = any_cast<vector<graph_t>&>(list);
        if (glist.empty())
        {
            done = true;
            return;
        }
68
        copy_graph(glist.back(), g, edge_copy(null_copy()));
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
        glist.pop_back();
    }
};

void get_motifs(GraphInterface& g, size_t k, python::list subgraph_list,
                python::list hist, python::list p, bool comp_iso,
                bool fill_list, size_t seed)
{
    rng_t rng(static_cast<rng_t::result_type>(seed));

    boost::any list;
    if (g.GetDirected())
        list = vector<d_graph_t>();
    else
        list = vector<u_graph_t>();
    try
    {
86
        for (int i = 0; i < python::len(subgraph_list); ++i)
87 88 89
        {
            GraphInterface& sub =
                python::extract<GraphInterface&>(subgraph_list[i]);
90
            run_action<>()(sub, bind<void>(append_to_list(), _1,
91
                                           boost::ref(list)))();
92 93 94 95
        }
    }
    catch (bad_any_cast&)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
96
        throw ValueException("All motif graphs must be either directed or "
97 98 99 100 101 102
                             "undirected!");
    }

    vector<size_t> phist;
    vector<double> plist;
    double total = 1;
103
    for (int i = 0; i < python::len(p); ++i)
104 105 106 107 108 109 110 111 112 113 114 115
    {
        plist.push_back(python::extract<double>(p[i]));
        total *= plist[i];
    }

    boost::any sampler;
    if (total == 1.0)
        sampler = sample_all();
    else
        sampler = sample_some(plist, rng);

    run_action<>()
116 117 118
        (g, boost::bind<void>(get_all_motifs(), _1, k, boost::ref(list),
                              boost::ref(phist), _2,
                              plist[0], comp_iso, fill_list, boost::ref(rng)),
119 120 121 122 123 124 125
         mpl::vector<sample_all,sample_some>())(sampler);

    for (size_t i = 0; i < phist.size(); ++i)
        hist.append(phist[i]);

    if (fill_list)
    {
126
        for (int i = 0; i < python::len(subgraph_list); ++i)
127 128 129 130 131 132 133 134 135 136 137 138 139 140
            subgraph_list.pop();

        bool done = false;
        while (!done)
        {

            GraphInterface sub;
            sub.SetDirected(g.GetDirected());
            typedef graph_tool::detail::get_all_graph_views::apply
                <graph_tool::detail::scalar_pairs,
                mpl::bool_<false>,mpl::bool_<false>,
                mpl::bool_<false>,mpl::bool_<true>,
                mpl::bool_<true> >::type gviews;
            run_action<gviews>()
141 142
                (sub, boost::bind<void>(retrieve_from_list(), _1,
                                        boost::ref(list), boost::ref(done)))();
143 144 145 146 147 148 149 150 151 152
            if (!done)
            {
                sub.ReIndexEdges();
                subgraph_list.append(sub);
            }
        }
        subgraph_list.reverse();
    }
}