graph.hh 10.2 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
24
25
26
27
28
29
30

#ifndef GRAPH_HH
#define GRAPH_HH

#include <tr1/unordered_map>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/vector_property_map.hpp>
#include <boost/dynamic_property_map.hpp>
#include <boost/variant.hpp>
#include <boost/python/object.hpp>
#include "histogram.hh"
#include "config.h"
31
#include "graph_properties.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
32
33
34

namespace graph_tool
{
35
36
using namespace std;
using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
37
38

// GraphInterface
39
40
41
// 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
42
43
44
45

class GraphInterface
{
public:
46
    GraphInterface();
Tiago Peixoto's avatar
Tiago Peixoto committed
47
48
49
50
    ~GraphInterface();

    enum degree_t
    {
51
52
53
54
        IN_DEGREE,
        OUT_DEGREE,
        TOTAL_DEGREE,
        SCALAR
Tiago Peixoto's avatar
Tiago Peixoto committed
55
56
57
    };

    // histogram types
58
59
60
61
62
63
    typedef tr1::unordered_map<double,double> hist_t;
    typedef tr1::unordered_map<pair<double,double>,double,
                                    hash<pair<double,double> > > hist2d_t;
    typedef tr1::unordered_map<tuple<double,double,double>,double,
                               hash<tuple<double,double,double> > > hist3d_t;
    typedef tr1::unordered_map<double,pair<double,double> > avg_corr_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
64

65
    typedef variant<degree_t,string> deg_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
66
67

    //graph generation
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
    typedef function<double (size_t j, size_t k)> pjk_t;
    typedef function<pair<size_t,size_t> (double r1, double r2)> inv_ceil_t;
    typedef function<double (size_t jl, size_t kl, size_t j, size_t k)> corr_t;
    typedef function<pair<size_t,size_t>(double r1, 
                                         double r2, 
                                         size_t j, 
                                         size_t k)> inv_corr_t;
    void GenerateCorrelatedConfigurationalModel(size_t N, pjk_t p, pjk_t ceil,
                                                inv_ceil_t inv_ceil,
                                                double ceil_pjk_bound, 
                                                corr_t corr, corr_t ceil_corr,
                                                inv_corr_t inv_ceil_corr, 
                                                double ceil_corr_bound,
                                                bool undirected_corr, 
                                                size_t seed, bool verbose);
Tiago Peixoto's avatar
Tiago Peixoto committed
83
84
85
86

    // basic stats
    size_t GetNumberOfVertices() const;
    size_t GetNumberOfEdges() const;
87
    hist_t GetVertexHistogram(deg_t degree) const;
88
    hist_t GetEdgeHistogram(string property) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
89
90

    //correlations
91
    hist2d_t   GetCombinedVertexHistogram(deg_t degree1, deg_t degree2) const;
92
93
94
95
96
97
98
99
100
    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;
101
102

    // mixing
103
104
    pair<double,double> GetAssortativityCoefficient(deg_t deg) const;
    pair<double,double> GetScalarAssortativityCoefficient(deg_t deg) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
105
106

    //clustering
107
108
109
110
    void SetLocalClusteringToProperty(string property);
    pair<double,double> GetGlobalClustering();
    void SetExtendedClusteringToProperty(string property_prefix,
                                         size_t max_depth);
Tiago Peixoto's avatar
Tiago Peixoto committed
111
112

    // other
113
114
115
116
117
    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;
118
    double GetReciprocity() const;
119
120
121
122
123
    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);
124

Tiago Peixoto's avatar
Tiago Peixoto committed
125
126
127
    // community structure
    enum comm_corr_t
    {
128
129
130
        ERDOS_REYNI,
        UNCORRELATED,
        CORRELATED
Tiago Peixoto's avatar
Tiago Peixoto committed
131
132
    };

133
134
135
136
137
138
139
    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);
    void   GetCommunityNetwork(string property, string size_property,
                               string out_file, string format) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
140

Tiago Peixoto's avatar
Tiago Peixoto committed
141
142
143
144
145
146
147
    // filtering
    void SetDirected(bool directed) {_directed = directed;}
    bool GetDirected() const {return _directed;}

    void SetReversed(bool reversed) {_reversed = reversed;}
    bool GetReversed() const {return _reversed;}

148
149
150
    void SetVertexFilterProperty(string property);
    void SetVertexFilterRange(pair<double,double> allowed_range,
                              pair<bool,bool> include, bool invert);
Tiago Peixoto's avatar
Tiago Peixoto committed
151
152
    bool IsVertexFilterActive() const;

153
154
155
    void SetEdgeFilterProperty(string property);
    void SetEdgeFilterRange(pair<double,double> allowed_range,
                            pair<bool,bool> include, bool invert);
Tiago Peixoto's avatar
Tiago Peixoto committed
156
157
158
    bool IsEdgeFilterActive() const;

    // modification
159
160
161
162
163
164
165
166
    void RemoveVertexProperty(string property);
    void RemoveEdgeProperty(string property);
    void RemoveGraphProperty(string property);
    void InsertEdgeIndexProperty(string property);
    void InsertVertexIndexProperty(string property);
    void EditVertexProperty(string property, string type, python::object op);
    void EditEdgeProperty(string property, string type, python::object op);
    void EditGraphProperty(string property, string type, python::object op);
167
    void ListProperties() const;
168
169
    void PurgeVertices();
    void PurgeEdges();
Tiago Peixoto's avatar
Tiago Peixoto committed
170
171

    // layout
172
173
174
175
    void ComputeGraphLayoutGursoy(string prop, string weight, string topology,
                                  size_t iter = 0, size_t seed = 4357);
    void ComputeGraphLayoutSpringBlock(string prop, string weight, string type,
                                       size_t iter = 0, size_t seed = 4357);
Tiago Peixoto's avatar
Tiago Peixoto committed
176
177

    // i/o
178
179
180
181
    void WriteToFile(string s);
    void WriteToFile(string s, string format);
    void ReadFromFile(string s);
    void ReadFromFile(string s, string format);
Tiago Peixoto's avatar
Tiago Peixoto committed
182
183
184
185
186

    // signal handling
    void InitSignalHandling();

    // the following defines the edges' internal properties
187
    typedef property<edge_index_t, size_t> EdgeProperty;
Tiago Peixoto's avatar
Tiago Peixoto committed
188
189

    // this is the main graph type
190
191
192
193
194
195
196
    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
197
198

private:
199
    template <class Action, class ReverseCheck, class DirectedCheck>
200
201
        friend void check_filter(const GraphInterface &g, Action a,
                                 ReverseCheck, DirectedCheck);
Tiago Peixoto's avatar
Tiago Peixoto committed
202
203
    friend class scalarS;

204
    // this is the main graph
Tiago Peixoto's avatar
Tiago Peixoto committed
205
206
207
208
209
210
    multigraph_t _mg;

    bool _reversed;
    bool _directed;

    // vertex index map
211
    typedef property_map<multigraph_t,vertex_index_t>::type vertex_index_map_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
212
213
214
    vertex_index_map_t _vertex_index;

    // edge index map
215
    typedef property_map<multigraph_t,edge_index_t>::type edge_index_map_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
216
217
218
    edge_index_map_t _edge_index;

    // graph properties
219
    dynamic_properties _properties;
Tiago Peixoto's avatar
Tiago Peixoto committed
220
221

    // vertex filter
222
223
224
225
226
227
228
229
    string _vertex_filter_property;
    typedef variant<vector_property_map<double,vertex_index_map_t>,
                    HashedDescriptorMap<vertex_index_map_t,double>,
                    vector_property_map<size_t,vertex_index_map_t>,
                    HashedDescriptorMap<vertex_index_map_t,size_t>,
                    vertex_index_map_t,
                    DynamicPropertyMapWrap<double,vertex_t> >
        vertex_filter_map_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
230
    vertex_filter_map_t _vertex_filter_map;
231
232
    pair<double,double> _vertex_range;
    pair<bool,bool> _vertex_range_include;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
233
    bool _vertex_range_invert;
Tiago Peixoto's avatar
Tiago Peixoto committed
234
235

    // edge filter
236
237
238
239
240
241
242
243
    string _edge_filter_property;
    typedef variant<vector_property_map<double, edge_index_map_t>,
                    HashedDescriptorMap<edge_index_map_t, double>,
                    vector_property_map<size_t, edge_index_map_t>,
                    HashedDescriptorMap<edge_index_map_t, size_t>,
                    edge_index_map_t,
                    DynamicPropertyMapWrap<double,edge_t> >
        edge_filter_map_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
244
    edge_filter_map_t _edge_filter_map;
245
246
    pair<double,double> _edge_range;
    pair<bool,bool> _edge_range_include;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
247
    bool _edge_range_invert;
248

Tiago Peixoto's avatar
Tiago Peixoto committed
249
250
};

251
252
pair<GraphInterface::degree_t,string>
get_degree_type(GraphInterface::deg_t degree);
Tiago Peixoto's avatar
Tiago Peixoto committed
253

254
255
256
// GraphException 
// This is the main exception which will be thrown the outside world, when
// things go wrong
Tiago Peixoto's avatar
Tiago Peixoto committed
257

258
class GraphException : public exception
Tiago Peixoto's avatar
Tiago Peixoto committed
259
{
260
    string _error;
Tiago Peixoto's avatar
Tiago Peixoto committed
261
public:
262
    GraphException(string error) {_error = error;}
Tiago Peixoto's avatar
Tiago Peixoto committed
263
264
265
266
267
268
269
270
271
272
    virtual ~GraphException() throw () {}
    virtual const char * what () const throw () {return _error.c_str();}
};

} //namespace graph_tool

#endif