graph.hh 10.7 KB
Newer Older
1

Tiago Peixoto's avatar
Tiago Peixoto committed
2
3
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
4
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
5
6
7
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
8
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
9
10
11
12
13
14
15
16
// 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
17
// along with this program. If not, see <http://www.gnu.org/licenses/>.
Tiago Peixoto's avatar
Tiago Peixoto committed
18
19
20
21
22
23

#ifndef GRAPH_HH
#define GRAPH_HH

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
24
25
26

#include <boost/graph/filtered_graph.hpp>

Tiago Peixoto's avatar
Tiago Peixoto committed
27
28
29
30
#include <boost/vector_property_map.hpp>
#include <boost/dynamic_property_map.hpp>
#include <boost/variant.hpp>
#include <boost/python/object.hpp>
31
#include <boost/python/dict.hpp>
32
#include <boost/lambda/lambda.hpp>
33
#include <boost/lambda/bind.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
34
35
#include "histogram.hh"
#include "config.h"
36
#include "graph_properties.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
37
38
39

namespace graph_tool
{
40
41
using namespace std;
using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
42
43

// GraphInterface
44
45
46
// this class is the main interface to the internally kept graph. This is how
// the external world will manipulate the graph. All the algorithms should be
// registered here. This class will be exported to python in graph_bind.hh
Tiago Peixoto's avatar
Tiago Peixoto committed
47

48
49
50
51
52
53
54
55
56
namespace detail
{
// Generic graph_action functor. See graph_filtering.hh for details.
template <class Action, class GraphViews,
          class TR1=boost::mpl::vector<>, class TR2=boost::mpl::vector<>,
          class TR3=boost::mpl::vector<>, class TR4=boost::mpl::vector<> >
struct graph_action;
}

57
58
59
// default visibility is necessary for related typeinfo objects to work across
// DSO boundaries
#pragma GCC visibility push(default)
Tiago Peixoto's avatar
Tiago Peixoto committed
60
61
62
class GraphInterface
{
public:
63
    GraphInterface();
Tiago Peixoto's avatar
Tiago Peixoto committed
64
65
    ~GraphInterface();

66
    // this enum specifies all the different types of degree
Tiago Peixoto's avatar
Tiago Peixoto committed
67
68
    enum degree_t
    {
69
70
        IN_DEGREE,
        OUT_DEGREE,
71
        TOTAL_DEGREE, // in + out
Tiago Peixoto's avatar
Tiago Peixoto committed
72
73
    };

74
75
    typedef variant<degree_t,string> deg_t; // useful when function also expects
                                            // a scalar vertex property
Tiago Peixoto's avatar
Tiago Peixoto committed
76

77
78
79
    //
    // Basic manipulation
    //
Tiago Peixoto's avatar
Tiago Peixoto committed
80
81
82

    size_t GetNumberOfVertices() const;
    size_t GetNumberOfEdges() const;
83
84
85
86
87
88
    void SetDirected(bool directed) {_directed = directed;}
    bool GetDirected() const {return _directed;}
    void SetReversed(bool reversed) {_reversed = reversed;}
    bool GetReversed() const {return _reversed;}

    // graph filtering
89
    void SetVertexFilterProperty(string property, bool invert);
90
    bool IsVertexFilterActive() const;
91
    void SetEdgeFilterProperty(string property, bool invert);
92
93
94
95
96
97
98
99
100
    bool IsEdgeFilterActive() const;


    // graph modification
    void RemoveVertexProperty(string property);
    void RemoveEdgeProperty(string property);
    void RemoveGraphProperty(string property);
    void InsertEdgeIndexProperty(string property);
    void InsertVertexIndexProperty(string property);
101
102
103
    void AddVertexProperty(string property, string type);
    void AddEdgeProperty(string property, string type);
    void AddGraphProperty(string property, string type);
104
105
106
    void ReIndexEdges();
    void PurgeVertices(); // removes filtered vertices
    void PurgeEdges();    // removes filtered edges
107
    void Clear();
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
    void RandomRewire(std::string strat, bool self_loops, bool parallel_edges,
                      size_t seed);

    // i/o
    void WriteToFile(string s);
    void WriteToFile(string s, string format);
    void ReadFromFile(string s);
    void ReadFromFile(string s, string format);

    //
    // Algorithms
    // Below are all the algorithms that operate somehow on the graph
    //

    // basic statistics
123
    hist_t GetVertexHistogram(deg_t degree) const;
124
    hist_t GetEdgeHistogram(string property) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
125

126
    // correlations
127
    hist2d_t   GetCombinedVertexHistogram(deg_t degree1, deg_t degree2) const;
128
129
130
131
132
133
134
135
136
    avg_corr_t GetAverageCombinedVertexCorrelation(deg_t degree1,
                                                   deg_t degree2)const;
    hist2d_t   GetVertexCorrelationHistogram(deg_t degree1, deg_t degree2,
                                             string weight) const;
    hist3d_t   GetEdgeVertexCorrelationHistogram(deg_t deg1, string scalar,
                                                 deg_t deg2) const;
    avg_corr_t GetAverageNearestNeighboursCorrelation(deg_t origin_degree,
                                                      deg_t neighbour_degree,
                                                      string weight) const;
137

138
    // vertex mixing
139
140
    pair<double,double> GetAssortativityCoefficient(deg_t deg) const;
    pair<double,double> GetScalarAssortativityCoefficient(deg_t deg) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
141

142
    // clustering
143
144
145
146
    void SetLocalClusteringToProperty(string property);
    pair<double,double> GetGlobalClustering();
    void SetExtendedClusteringToProperty(string property_prefix,
                                         size_t max_depth);
Tiago Peixoto's avatar
Tiago Peixoto committed
147
148

    // other
149
150
151
152
153
    void   LabelComponents(string property);
    void   LabelParallelEdges(string property);
    hist_t GetDistanceHistogram(string weight) const;
    hist_t GetSampledDistanceHistogram(string weight, size_t samples,
                                       size_t seed) const;
154
    double GetReciprocity() const;
155
156
157
158
159
    void   GetMinimumSpanningTree(string weight, string property);
    void   GetLineGraph(string out_file, string format);
    void   GetBetweenness(string weight, string edge_betweenness,
                          string vertex_betweenness);
    double GetCentralPointDominance(string vertex_betweenness);
160

Tiago Peixoto's avatar
Tiago Peixoto committed
161
    // community structure
162
    enum comm_corr_t // null model correlation type
Tiago Peixoto's avatar
Tiago Peixoto committed
163
    {
164
165
166
        ERDOS_REYNI,
        UNCORRELATED,
        CORRELATED
Tiago Peixoto's avatar
Tiago Peixoto committed
167
168
    };

169
170
171
172
173
    void   GetCommunityStructure(double gamma, comm_corr_t corr, size_t n_iter,
                                 double Tmin, double Tmax, size_t Nseeds,
                                 size_t seed, bool verbose, string history_file,
                                 string weight, string property);
    double GetModularity(string weight, string property);
174
    // TODO: this should return a GraphInterface type
175
176
    void   GetCommunityNetwork(string property, string size_property,
                               string out_file, string format) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
177

178
179
180
181
182
183
184
    // Graph generation
    void GenerateCorrelatedConfigurationalModel
        (size_t N, python::object ppjk, python::object pceil_pjk,
         python::object pinv_ceil_pjk, double ceil_pjk_bound,
         python::object pcorr, python::object pceil_corr,
         python::object pinv_ceil_corr, double ceil_corr_bound,
         bool undirected_corr, size_t seed, bool verbose);
Tiago Peixoto's avatar
Tiago Peixoto committed
185

186
    // graph layout
187
188
189
    void ComputeGraphLayoutGursoy(string prop, string weight, string topology,
                                  size_t iter = 0, size_t seed = 4357);
    void ComputeGraphLayoutSpringBlock(string prop, string weight, string type,
190
191
192
                                       size_t iter = 0, 
                                       bool progressive = false,
                                       size_t seed = 4357);
Tiago Peixoto's avatar
Tiago Peixoto committed
193

194
195
    // python interface
    python::object Vertices() const;
196
    python::object Vertex(size_t i) const;
197
198
    python::object Edges() const;

199
200
201
202
203
204
205
206
207
208
209
210
    python::object AddVertex();
    void RemoveVertex(python::object v);
    python::object AddEdge(python::object s, python::object t);
    void RemoveEdge(python::object e);

    python::dict GetVertexProperties() const;
    python::dict GetEdgeProperties() const;
    python::dict GetGraphProperties() const;

    // used for graph properties
    graph_property_tag GetDescriptor() const { return graph_property_tag(); }

211
212
    void ExportPythonInterface() const;

Tiago Peixoto's avatar
Tiago Peixoto committed
213
214
215
    // signal handling
    void InitSignalHandling();

216
217
218
219
220
221
222
223
224
    // arbitrary code execution, for run-time code integration
    template <class Action, class Args>
    void RunAction(const Action &a, const Args& args)
    {
        using namespace boost::lambda;
        run_action(*this, bind<void>(a, boost::lambda::_1, _vertex_index,
                                     _edge_index, var(_properties), var(args)));
    }

225
226
227
228
    //
    // Internal types
    //

Tiago Peixoto's avatar
Tiago Peixoto committed
229
    // the following defines the edges' internal properties
230
    typedef property<edge_index_t, size_t> EdgeProperty;
Tiago Peixoto's avatar
Tiago Peixoto committed
231
232

    // this is the main graph type
233
234
235
236
237
238
239
    typedef adjacency_list <vecS, // edges
                            vecS, // vertices
                            bidirectionalS,
                            no_property,
                            EdgeProperty>  multigraph_t;
    typedef graph_traits<multigraph_t>::vertex_descriptor vertex_t;
    typedef graph_traits<multigraph_t>::edge_descriptor edge_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
240

241
242
    typedef property_map<multigraph_t,vertex_index_t>::type vertex_index_map_t;
    typedef property_map<multigraph_t,edge_index_t>::type edge_index_map_t;
243

244
    size_t GetEdgeHash(const edge_t& e) const;
245

246
247
248
private:
    // Gets the encapsulated graph view. See graph_filtering.cc for details
    boost::any GetGraphView() const;
249

250
251
252
253
254
    // Generic graph_action functor. See graph_filtering.hh for details.
    template <class Action,
              class TR1=boost::mpl::vector<>, class TR2=boost::mpl::vector<>,
              class TR3=boost::mpl::vector<>, class TR4=boost::mpl::vector<> >
    friend struct detail::graph_action;
Tiago Peixoto's avatar
Tiago Peixoto committed
255

256
    // this is the main graph
Tiago Peixoto's avatar
Tiago Peixoto committed
257
258
    multigraph_t _mg;

259
260
261
    // this will hold an instance of the graph views at run time
    vector<boost::any> _graph_views;

262
    // reverse and directed states
Tiago Peixoto's avatar
Tiago Peixoto committed
263
264
265
266
267
268
269
270
271
272
    bool _reversed;
    bool _directed;

    // vertex index map
    vertex_index_map_t _vertex_index;

    // edge index map
    edge_index_map_t _edge_index;

    // graph properties
273
    dynamic_properties _properties;
Tiago Peixoto's avatar
Tiago Peixoto committed
274
275

    // vertex filter
276
277
278
279
    typedef vector_property_map<bool,vertex_index_map_t> vertex_filter_t;
    vertex_filter_t _vertex_filter_map;
    bool _vertex_filter_invert;
    bool _vertex_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
280
281

    // edge filter
282
283
284
285
    typedef vector_property_map<bool,edge_index_map_t> edge_filter_t;
    edge_filter_t _edge_filter_map;
    bool _edge_filter_invert;
    bool _edge_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
286
};
287
#pragma GCC visibility pop
Tiago Peixoto's avatar
Tiago Peixoto committed
288

289
290
pair<GraphInterface::degree_t,string>
get_degree_type(GraphInterface::deg_t degree);
Tiago Peixoto's avatar
Tiago Peixoto committed
291

292
293
// This is the main exception which will be thrown the outside world, when
// things go wrong
Tiago Peixoto's avatar
Tiago Peixoto committed
294

295
#pragma GCC visibility push(default)
296
class GraphException : public exception
Tiago Peixoto's avatar
Tiago Peixoto committed
297
{
298
    string _error;
Tiago Peixoto's avatar
Tiago Peixoto committed
299
public:
300
    GraphException(string error) {_error = error;}
Tiago Peixoto's avatar
Tiago Peixoto committed
301
302
303
    virtual ~GraphException() throw () {}
    virtual const char * what () const throw () {return _error.c_str();}
};
304
#pragma GCC visibility pop
Tiago Peixoto's avatar
Tiago Peixoto committed
305
306
307
308
309
310
311

} //namespace graph_tool

#endif