graph.hh 10 KB
Newer Older
Tiago de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
3
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.de>
Tiago de Paula Peixoto's avatar
Tiago de Paula 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
7
// as published by the Free Software Foundation; either version 3
Tiago de Paula Peixoto's avatar
Tiago de Paula 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 de Paula Peixoto's avatar
Tiago de Paula 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 de Paula Peixoto's avatar
Tiago de Paula 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 de Paula Peixoto's avatar
Tiago de Paula 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 de Paula Peixoto's avatar
Tiago de Paula 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 de Paula Peixoto's avatar
Tiago de Paula 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 de Paula Peixoto's avatar
Tiago de Paula 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 de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
91
92

    // other
93
    void   LabelComponents(std::string property);
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);
101
102
    double GetCentralPointDominance(std::string vertex_betweenness);
    
103
104
105
    // community structure
    enum comm_corr_t
    {
106
107
108
        ERDOS_REYNI,
        UNCORRELATED,
        CORRELATED
109
110
    };

111
    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);
112
    double GetModularity(std::string weight, std::string property);
113
    void   GetCommunityNetwork(std::string property, std::string size_property, std::string out_file, std::string format) const;
114

Tiago de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
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);
Tiago de Paula Peixoto's avatar
   
Tiago de Paula Peixoto committed
123
    void SetVertexFilterRange(std::pair<double,double> allowed_range, std::pair<bool,bool> include, bool invert);
Tiago de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
124
125
126
    bool IsVertexFilterActive() const;

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

    // modification
    void RemoveVertexProperty(std::string property);
132
133
    void RemoveEdgeProperty(std::string property);
    void RemoveGraphProperty(std::string property);
Tiago de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
134
135
    void InsertEdgeIndexProperty(std::string property);
    void InsertVertexIndexProperty(std::string property);
136
137
    void EditVertexProperty(std::string property, std::string type, boost::python::object op);
    void EditEdgeProperty(std::string property, std::string type, boost::python::object op);
138
    void EditGraphProperty(std::string property, std::string type, boost::python::object op);
139
    void ListProperties() const;
Tiago de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
140
141

    // layout
142
143
    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 de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
144
145

    // i/o
146
147
148
149
    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 de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
150
151
152
153
154
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

    // 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;
190
    typedef boost::variant<boost::vector_property_map<double, vertex_index_map_t>,
191
192
193
194
195
                           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 de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
196
197
    vertex_filter_map_t _vertex_filter_map;
    std::pair<double,double> _vertex_range;
Tiago de Paula Peixoto's avatar
   
Tiago de Paula Peixoto committed
198
199
    std::pair<bool,bool> _vertex_range_include;
    bool _vertex_range_invert;
Tiago de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
200
201
202

    // edge filter
    std::string _edge_filter_property;
203
    typedef boost::variant<boost::vector_property_map<double, edge_index_map_t>,
204
205
206
207
208
                           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 de Paula Peixoto's avatar
Tiago de Paula Peixoto committed
209
210
    edge_filter_map_t _edge_filter_map;
    std::pair<double,double> _edge_range;
Tiago de Paula Peixoto's avatar
   
Tiago de Paula Peixoto committed
211
212
    std::pair<bool,bool> _edge_range_include;
    bool _edge_range_invert;
Tiago de Paula Peixoto's avatar
Tiago de Paula 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
    
};

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