graph_motifs.cc 4.99 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-2014 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.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
19
#include "graph_filtering.hh"
20
#include "graph_properties.hh"
21
#include "graph_util.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
22
#include "graph_selectors.hh"
23

24
25
#include "graph_motifs.hh"

Tiago Peixoto's avatar
Tiago Peixoto committed
26
#include "graph_python_interface.hh"
27
28
29
30
31
32
33
34
35
36
#include <boost/python.hpp>

using namespace std;
using namespace graph_tool;


struct append_to_list
{

    template <class Graph>
37
    void operator()(Graph& g, boost::any& list) const
38
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
39
40
41
        typedef typename boost::mpl::if_<typename is_directed::apply<Graph>::type,
                                         d_graph_t,
                                         u_graph_t>::type graph_t;
42
43
        vector<graph_t>& glist = any_cast<vector<graph_t>&>(list);
        glist.push_back(graph_t());
44
        graph_copy(g, glist.back());
45
46
47
48
49
50
    }
};

struct retrieve_from_list
{
    template <class Graph>
51
    void operator()(Graph& g, boost::any& list, bool& done) const
52
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
53
54
55
        typedef typename boost::mpl::if_<typename is_directed::apply<Graph>::type,
                                         d_graph_t,
                                         u_graph_t>::type graph_t;
56
57
58
59
60
61
        vector<graph_t>& glist = any_cast<vector<graph_t>&>(list);
        if (glist.empty())
        {
            done = true;
            return;
        }
62
        graph_copy(glist.back(), g);
Tiago Peixoto's avatar
Tiago Peixoto committed
63
        glist.pop_back();
64
65
66
    }
};

Tiago Peixoto's avatar
Tiago Peixoto committed
67
68
69
70
void get_motifs(GraphInterface& g, size_t k, boost::python::list subgraph_list,
                boost::python::list hist, boost::python::list pvmaps,
                bool collect_vmaps, boost::python::list p, bool comp_iso,
                bool fill_list, rng_t& rng)
71
72
73
74
75
76
77
78
{
    boost::any list;
    if (g.GetDirected())
        list = vector<d_graph_t>();
    else
        list = vector<u_graph_t>();
    try
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
79
        for (int i = 0; i <  boost::python::len(subgraph_list); ++i)
80
81
        {
            GraphInterface& sub =
Tiago Peixoto's avatar
Tiago Peixoto committed
82
83
84
85
                 boost::python::extract<GraphInterface&>(subgraph_list[i]);
            run_action<>()(sub, std::bind(append_to_list(),
                                          placeholders::_1,
                                          std::ref(list)))();
86
87
88
89
        }
    }
    catch (bad_any_cast&)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
90
        throw ValueException("All motif graphs must be either directed or "
91
92
93
94
95
96
                             "undirected!");
    }

    vector<size_t> phist;
    vector<double> plist;
    double total = 1;
Tiago Peixoto's avatar
Tiago Peixoto committed
97
    for (int i = 0; i < boost::python::len(p); ++i)
98
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
99
        plist.push_back(boost::python::extract<double>(p[i]));
100
101
102
103
104
105
106
107
108
        total *= plist[i];
    }

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

109
110
111
112
113
    typedef property_map_type
            ::apply<int32_t, GraphInterface::vertex_index_map_t>::type
            vmap_t;
    vector<vector<vmap_t> > vmaps;

114
    run_action<>()
Tiago Peixoto's avatar
Tiago Peixoto committed
115
116
117
118
119
        (g, std::bind(get_all_motifs(collect_vmaps, plist[0], comp_iso,
                                     fill_list, rng),
                      placeholders::_1, k, std::ref(list), std::ref(phist),
                      std::ref(vmaps), placeholders::_2),
         boost::mpl::vector<sample_all,sample_some>())(sampler);
120
121
122
123

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

124
125
    for (size_t i = 0; i < vmaps.size(); ++i)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
126
         boost::python::list vlist;
127
128
129
130
131
        for (size_t j = 0; j < vmaps[i].size(); ++j)
            vlist.append(PythonPropertyMap<vmap_t>(vmaps[i][j]));
        pvmaps.append(vlist);
    }

132
133
    if (fill_list)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
134
        for (int i = 0; i < boost::python::len(subgraph_list); ++i)
135
136
137
138
139
140
141
142
143
            subgraph_list.pop();

        bool done = false;
        while (!done)
        {

            GraphInterface sub;
            sub.SetDirected(g.GetDirected());
            typedef graph_tool::detail::get_all_graph_views::apply
144
                <graph_tool::detail::filt_scalar_type,
Tiago Peixoto's avatar
Tiago Peixoto committed
145
146
147
                 boost::mpl::bool_<false>, boost::mpl::bool_<false>,
                 boost::mpl::bool_<false>, boost::mpl::bool_<true>,
                 boost::mpl::bool_<true> >::type gviews;
148
            run_action<gviews>()
Tiago Peixoto's avatar
Tiago Peixoto committed
149
150
                (sub, std::bind(retrieve_from_list(), placeholders::_1,
                                std::ref(list), std::ref(done)))();
151
152
153
154
155
156
            if (!done)
                subgraph_list.append(sub);
        }
        subgraph_list.reverse();
    }
}