graph.hh 10.1 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
5
6
//
// 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
7
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 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, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

#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
35
36
37
38
39
40
41
42
43
44
45
46
47
48

namespace graph_tool
{

//==============================================================================
// GraphInterface
// this structure is an interface to the internally kept graph
//==============================================================================

class GraphInterface
{
public:
    GraphInterface(); 
    ~GraphInterface();

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

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

    typedef boost::variant<degree_t,std::string> deg_t;

    //graph generation
    typedef boost::function<double (size_t j, size_t k)> pjk_t;
    typedef boost::function<std::pair<size_t,size_t> (double r1, double r2)> inv_ceil_t;
    typedef boost::function<double (size_t jl, size_t kl, size_t j, size_t k)> corr_t;
    typedef boost::function<std::pair<size_t,size_t>  (double r1, double r2, size_t j, size_t k)> inv_corr_t;
68
    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
69
70
71
72

    // basic stats
    size_t GetNumberOfVertices() const;
    size_t GetNumberOfEdges() const;
73
74
    hist_t GetVertexHistogram(deg_t degree) const;
    hist_t GetEdgeHistogram(std::string property) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
75
76

    //correlations
77
    hist2d_t   GetCombinedVertexHistogram(deg_t degree1, deg_t degree2) const;    
78
    avg_corr_t GetAverageCombinedVertexCorrelation(deg_t degree1, deg_t degree2) const;
79
    hist2d_t   GetVertexCorrelationHistogram(deg_t degree1, deg_t degree2, std::string weight) const;
80
    hist3d_t   GetEdgeVertexCorrelationHistogram(deg_t deg1, std::string scalar, deg_t deg2) const;
81
    avg_corr_t GetAverageNearestNeighboursCorrelation(deg_t origin_degree, deg_t neighbour_degree, std::string weight) const;
82
83
84
85

    // mixing
    std::pair<double,double> GetAssortativityCoefficient(deg_t deg) const;
    std::pair<double,double> GetScalarAssortativityCoefficient(deg_t deg) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
86
87

    //clustering
88
    void SetLocalClusteringToProperty(std::string property);
89
    std::pair<double,double> GetGlobalClustering();
90
    void SetExtendedClusteringToProperty(std::string property_prefix, size_t max_depth);
Tiago Peixoto's avatar
Tiago Peixoto committed
91
92

    // other
93
    void   LabelComponents(std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
94
    void   LabelParallelEdges(std::string property);
95
96
    hist_t GetDistanceHistogram(std::string weight) const;
    hist_t GetSampledDistanceHistogram(std::string weight, size_t samples, size_t seed) const;
97
    double GetReciprocity() const;
98
    void   GetMinimumSpanningTree(std::string weight, std::string property);
99
    void   GetLineGraph(std::string out_file, std::string format);
100
    void   GetBetweenness(std::string weight, std::string edge_betweenness, std::string vertex_betweenness);
Tiago Peixoto's avatar
Tiago Peixoto committed
101

Tiago Peixoto's avatar
Tiago Peixoto committed
102
103
104
    // community structure
    enum comm_corr_t
    {
105
106
107
        ERDOS_REYNI,
        UNCORRELATED,
        CORRELATED
Tiago Peixoto's avatar
Tiago Peixoto committed
108
109
    };

Tiago Peixoto's avatar
Tiago Peixoto committed
110
    void   GetCommunityStructure(double gamma, comm_corr_t corr, size_t n_iter, double Tmin, double Tmax, size_t Nseeds, size_t seed, bool verbose, std::string history_file, std::string weight, std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
111
    double GetModularity(std::string weight, std::string property);
112
    void   GetCommunityNetwork(std::string property, std::string out_file, std::string format) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
113

Tiago Peixoto's avatar
Tiago Peixoto committed
114
115
116
117
118
119
120
121
122
    // filtering
    void SetDirected(bool directed) {_directed = directed;}
    bool GetDirected() const {return _directed;}

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

    void SetVertexFilterProperty(std::string property);
    std::string GetVertexFilterProperty() const {return _vertex_filter_property;}
123
    void SetVertexFilterRange(std::pair<double,double> allowed_range);
Tiago Peixoto's avatar
Tiago Peixoto committed
124
125
126
127
128
    std::pair<double, double> GetVertexFilterRange() const {return _vertex_range;}
    bool IsVertexFilterActive() const;

    void SetEdgeFilterProperty(std::string property);
    std::string GetEdgeFilterProperty() const {return _edge_filter_property;}
Tiago Peixoto's avatar
Tiago Peixoto committed
129
130
    void SetEdgeFilterRange(std::pair<double,double> allowed_range) {_edge_range = allowed_range;}
    std::pair<double,double> GetEdgeFilterRange() const {return _edge_range;}
Tiago Peixoto's avatar
Tiago Peixoto committed
131
132
    bool IsEdgeFilterActive() const;

133
134
    void SetGenericVertexFilter(boost::python::object filter);
    void SetGenericEdgeFilter(boost::python::object filter);
Tiago Peixoto's avatar
Tiago Peixoto committed
135
136
137

    // modification
    void RemoveVertexProperty(std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
138
139
    void RemoveEdgeProperty(std::string property);
    void RemoveGraphProperty(std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
140
141
    void InsertEdgeIndexProperty(std::string property);
    void InsertVertexIndexProperty(std::string property);
142
143
    void EditVertexProperty(std::string property, std::string type, boost::python::object op);
    void EditEdgeProperty(std::string property, std::string type, boost::python::object op);
Tiago Peixoto's avatar
Tiago Peixoto committed
144
    void EditGraphProperty(std::string property, std::string type, boost::python::object op);
145
    void ListProperties() const;
Tiago Peixoto's avatar
Tiago Peixoto committed
146
147
148
149
150
151

    // layout
    void ComputeGraphLayoutGursoy(size_t iter = 0, size_t seed = 4357);
    void ComputeGraphLayoutSpringBlock(size_t iter = 0, size_t seed = 4357);

    // i/o
Tiago Peixoto's avatar
Tiago Peixoto committed
152
153
154
155
    void WriteToFile(std::string s);
    void WriteToFile(std::string s, std::string format);
    void ReadFromFile(std::string s);
    void ReadFromFile(std::string s, std::string format);
Tiago Peixoto's avatar
Tiago Peixoto committed
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

    // signal handling
    void InitSignalHandling();

    // the following defines the edges' internal properties
    typedef boost::property<boost::edge_index_t, size_t> EdgeProperty;

    // this is the main graph type
    typedef boost::adjacency_list <boost::vecS, // edges
                                   boost::vecS, // vertices
                                   boost::bidirectionalS,
                                   boost::no_property,
                                   EdgeProperty >  multigraph_t;

private:
    template <class Action, class ReverseCheck, class DirectedCheck> 
    friend void check_filter(const GraphInterface &g, Action a, ReverseCheck, DirectedCheck);
    template <class Graph, class Action, class ReverseCheck, class DirectedCheck> 
    friend void check_python_filter(const Graph& g, const GraphInterface &gi, Action a, bool& found, ReverseCheck, DirectedCheck);

    friend class scalarS;

    multigraph_t _mg;

    bool _reversed;
    bool _directed;

    // vertex index map
    typedef boost::property_map<multigraph_t, boost::vertex_index_t>::type vertex_index_map_t;
    vertex_index_map_t _vertex_index;

    // edge index map
    typedef boost::property_map<multigraph_t, boost::edge_index_t>::type edge_index_map_t;
    edge_index_map_t _edge_index;

    // graph properties
    boost::dynamic_properties _properties;

    // vertex filter
    std::string _vertex_filter_property;
196
    typedef boost::variant<boost::vector_property_map<double, vertex_index_map_t>,
197
198
199
200
201
                           HashedDescriptorMap<vertex_index_map_t,double>,
                           boost::vector_property_map<size_t, vertex_index_map_t>,
                           HashedDescriptorMap<vertex_index_map_t, size_t>,
                           vertex_index_map_t,
                           DynamicPropertyMapWrap<double, boost::graph_traits<multigraph_t>::vertex_descriptor> > vertex_filter_map_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
202
203
204
205
206
207
    vertex_filter_map_t _vertex_filter_map;
    std::pair<double,double> _vertex_range;
    boost::python::object _vertex_python_filter;

    // edge filter
    std::string _edge_filter_property;
208
    typedef boost::variant<boost::vector_property_map<double, edge_index_map_t>,
209
210
211
212
213
                           HashedDescriptorMap<edge_index_map_t, double>,                            
                           boost::vector_property_map<size_t, edge_index_map_t>,
                           HashedDescriptorMap<edge_index_map_t, size_t>,
                           edge_index_map_t,
                           DynamicPropertyMapWrap<double, boost::graph_traits<multigraph_t>::edge_descriptor> > edge_filter_map_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
    edge_filter_map_t _edge_filter_map;
    std::pair<double,double> _edge_range;
    boost::python::object _edge_python_filter;
    
};

std::pair<GraphInterface::degree_t,std::string> get_degree_type(GraphInterface::deg_t degree);

//==============================================================================
// GraphException
//==============================================================================

class GraphException : public std::exception
{
    std::string _error;
public:
    GraphException(std::string error) {_error = error;}
    virtual ~GraphException() throw () {}
    virtual const char * what () const throw () {return _error.c_str();}
};

} //namespace graph_tool

//#include "node_graph_io.hh"

#endif