graph.hh 8.18 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 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"

namespace graph_tool
{

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

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

    enum degree_t
    {
	IN_DEGREE,
	OUT_DEGREE,
	TOTAL_DEGREE,
	SCALAR
    };

    // histogram types
    typedef std::tr1::unordered_map<double,size_t> hist_t;
    typedef std::tr1::unordered_map<std::pair<double,double>,size_t, boost::hash<std::pair<double,double> > > hist2d_t;
    typedef std::tr1::unordered_map<boost::tuple<double,double,double>,size_t, boost::hash<boost::tuple<double,double,double> > > hist3d_t;
    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;
67
    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
68
69
70
71

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

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

    // 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
85
86

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

    // other
    hist_t GetComponentSizeHistogram() const;
93
94
    hist_t GetDistanceHistogram(std::string weight) const;
    hist_t GetSampledDistanceHistogram(std::string weight, size_t samples, size_t seed) const;
Tiago Peixoto's avatar
Tiago Peixoto committed
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
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;}
    void SetVertexFilterRange(std::pair<double, double> allowed_range) {_vertex_range = allowed_range;}
    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;}
    void SetEdgeFilterRange(std::pair<double, double> allowed_range) {_edge_range = allowed_range;}
    std::pair<double, double> GetEdgeFilterRange() const {return _edge_range;}
    bool IsEdgeFilterActive() const;

    void SetGenericVertexFilter(boost::python::object filter) {_vertex_python_filter = filter;}
    void SetGenericEdgeFilter(boost::python::object filter) {_edge_python_filter = filter;}

    // modification
    void RemoveEdgeProperty(std::string property);
    void RemoveVertexProperty(std::string property);
    void InsertEdgeIndexProperty(std::string property);
    void InsertVertexIndexProperty(std::string property);
123
124
    void EditVertexProperty(std::string property, boost::python::object op);
    void EditEdgeProperty(std::string property, boost::python::object op);
Tiago Peixoto's avatar
Tiago Peixoto committed
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
    void RemoveParallelEdges();

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

    // i/o
    void WriteToFile(std::string s); 
    void ReadFromFile(std::string s); 

    // 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;
    typedef boost::vector_property_map<double, vertex_index_map_t> vertex_filter_map_t;
    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;
    typedef boost::vector_property_map<double, edge_index_map_t> edge_filter_map_t;
    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