graph.hh 10 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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 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"
32
#include "graph_properties.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
33
34
35
36
37
38
39
40
41
42
43
44

namespace graph_tool
{

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

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

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

    // histogram types
    typedef std::tr1::unordered_map<double,size_t> hist_t;
58
59
    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
60
61
62
63
64
65
66
67
68
    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;
69
    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
70
71
72
73

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

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

    // 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
87
88

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

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

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
116
117
118
119
120
121
122
123
    // 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);
Tiago Peixoto's avatar
   
Tiago Peixoto committed
124
    void SetVertexFilterRange(std::pair<double,double> allowed_range, std::pair<bool,bool> include, bool invert);
Tiago Peixoto's avatar
Tiago Peixoto committed
125
126
127
    bool IsVertexFilterActive() const;

    void SetEdgeFilterProperty(std::string property);
Tiago Peixoto's avatar
   
Tiago Peixoto committed
128
    void SetEdgeFilterRange(std::pair<double,double> allowed_range, std::pair<bool,bool> include, bool invert);
Tiago Peixoto's avatar
Tiago Peixoto committed
129
130
131
132
    bool IsEdgeFilterActive() const;

    // modification
    void RemoveVertexProperty(std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
133
134
    void RemoveEdgeProperty(std::string property);
    void RemoveGraphProperty(std::string property);
Tiago Peixoto's avatar
Tiago Peixoto committed
135
136
    void InsertEdgeIndexProperty(std::string property);
    void InsertVertexIndexProperty(std::string property);
137
138
    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
139
    void EditGraphProperty(std::string property, std::string type, boost::python::object op);
140
    void ListProperties() const;
141
142
    void PurgeVertices();
    void PurgeEdges();
Tiago Peixoto's avatar
Tiago Peixoto committed
143
144

    // layout
145
146
    void ComputeGraphLayoutGursoy(std::string prop, std::string weight, std::string topology, size_t iter = 0, size_t seed = 4357);
    void ComputeGraphLayoutSpringBlock(std::string prop, std::string weight, std::string type, size_t iter = 0, size_t seed = 4357);
Tiago Peixoto's avatar
Tiago Peixoto committed
147
148

    // i/o
Tiago Peixoto's avatar
Tiago Peixoto committed
149
150
151
152
    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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

    // 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:
168
    template <class Action, class ReverseCheck, class DirectedCheck>
Tiago Peixoto's avatar
Tiago Peixoto committed
169
    friend void check_filter(const GraphInterface &g, Action a, ReverseCheck, DirectedCheck);
170
    template <class Graph, class Action, class ReverseCheck, class DirectedCheck>
Tiago Peixoto's avatar
Tiago Peixoto committed
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
    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;
193
    typedef boost::variant<boost::vector_property_map<double, vertex_index_map_t>,
194
195
196
197
198
                           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
199
200
    vertex_filter_map_t _vertex_filter_map;
    std::pair<double,double> _vertex_range;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
201
202
    std::pair<bool,bool> _vertex_range_include;
    bool _vertex_range_invert;
Tiago Peixoto's avatar
Tiago Peixoto committed
203
204
205

    // edge filter
    std::string _edge_filter_property;
206
    typedef boost::variant<boost::vector_property_map<double, edge_index_map_t>,
207
                           HashedDescriptorMap<edge_index_map_t, double>,
208
209
210
211
                           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
212
213
    edge_filter_map_t _edge_filter_map;
    std::pair<double,double> _edge_range;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
214
215
    std::pair<bool,bool> _edge_range_include;
    bool _edge_range_invert;
216

Tiago Peixoto's avatar
Tiago Peixoto committed
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
};

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