graph.hh 10 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
3
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
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
//
// 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 2
// 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);
Tiago Peixoto's avatar
Tiago Peixoto committed
100

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

Tiago Peixoto's avatar
Tiago Peixoto committed
109
    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
110
    double GetModularity(std::string weight, std::string property);
111
    void   GetCommunityNetwork(std::string property, std::string out_file, std::string format) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
112

Tiago Peixoto's avatar
Tiago Peixoto committed
113
114
115
116
117
118
119
120
121
    // 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;}
122
    void SetVertexFilterRange(std::pair<double,double> allowed_range);
Tiago Peixoto's avatar
Tiago Peixoto committed
123
124
125
126
127
    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
128
129
    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
130
131
    bool IsEdgeFilterActive() const;

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

    // modification
    void RemoveVertexProperty(std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
137
138
    void RemoveEdgeProperty(std::string property);
    void RemoveGraphProperty(std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
139
140
    void InsertEdgeIndexProperty(std::string property);
    void InsertVertexIndexProperty(std::string property);
141
142
    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
143
    void EditGraphProperty(std::string property, std::string type, boost::python::object op);
144
    void ListProperties() const;
Tiago Peixoto's avatar
Tiago Peixoto committed
145
146
147
148
149
150

    // 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
151
152
153
154
    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
155
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

    // 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;
195
    typedef boost::variant<boost::vector_property_map<double, vertex_index_map_t>,
196
197
198
199
200
                           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
201
202
203
204
205
206
    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;
207
    typedef boost::variant<boost::vector_property_map<double, edge_index_map_t>,
208
209
210
211
212
                           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
213
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
    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