graph.hh 7.68 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
// 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
16
// along with this program. If not, see <http://www.gnu.org/licenses/>.
Tiago Peixoto's avatar
Tiago Peixoto committed
17
18
19
20
21
22

#ifndef GRAPH_HH
#define GRAPH_HH

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
23

Tiago Peixoto's avatar
Tiago Peixoto committed
24
25
#include <boost/vector_property_map.hpp>
#include <boost/dynamic_property_map.hpp>
26
27
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
28
29
#include <boost/variant.hpp>
#include <boost/python/object.hpp>
30
#include <boost/python/dict.hpp>
31
#include <boost/mpl/vector.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
32
33
34
35
#include "config.h"

namespace graph_tool
{
36
37
using namespace std;
using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
38
39

// GraphInterface
40
41
42
// this class is the main interface to the internally kept graph. This is how
// the external world will manipulate the graph. All the algorithms should be
// registered here. This class will be exported to python in graph_bind.hh
Tiago Peixoto's avatar
Tiago Peixoto committed
43

44
45
46
47
48
49
50
51
52
namespace detail
{
// Generic graph_action functor. See graph_filtering.hh for details.
template <class Action, class GraphViews,
          class TR1=boost::mpl::vector<>, class TR2=boost::mpl::vector<>,
          class TR3=boost::mpl::vector<>, class TR4=boost::mpl::vector<> >
struct graph_action;
}

53
54
55
// default visibility is necessary for related typeinfo objects to work across
// DSO boundaries
#pragma GCC visibility push(default)
Tiago Peixoto's avatar
Tiago Peixoto committed
56
57
58
class GraphInterface
{
public:
59
    GraphInterface();
60
    GraphInterface(const GraphInterface& gi);
Tiago Peixoto's avatar
Tiago Peixoto committed
61
62
    ~GraphInterface();

63
64
65
    // useful enums

    typedef enum
Tiago Peixoto's avatar
Tiago Peixoto committed
66
    {
67
68
        IN_DEGREE,
        OUT_DEGREE,
69
70
        TOTAL_DEGREE
    } degree_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
71

72
73
74
75
76
    typedef boost::variant<degree_t, string> deg_t; // general "degree" type,
                                                    // i.e., either a degree_t
                                                    // above or a string
                                                    // representing a scalar
                                                    // vertex property
Tiago Peixoto's avatar
Tiago Peixoto committed
77

78
79
80
    //
    // Basic manipulation
    //
Tiago Peixoto's avatar
Tiago Peixoto committed
81
82
83

    size_t GetNumberOfVertices() const;
    size_t GetNumberOfEdges() const;
84
85
86
87
88
89
    void SetDirected(bool directed) {_directed = directed;}
    bool GetDirected() const {return _directed;}
    void SetReversed(bool reversed) {_reversed = reversed;}
    bool GetReversed() const {return _reversed;}

    // graph filtering
90
    void SetVertexFilterProperty(string property, bool invert);
91
    pair<string, bool> GetVertexFilterProperty() const;
92
    bool IsVertexFilterActive() const;
93
    void SetEdgeFilterProperty(string property, bool invert);
94
    pair<string, bool> GetEdgeFilterProperty() const;
95
96
97
98
99
100
101
102
    bool IsEdgeFilterActive() const;

    // graph modification
    void RemoveVertexProperty(string property);
    void RemoveEdgeProperty(string property);
    void RemoveGraphProperty(string property);
    void InsertEdgeIndexProperty(string property);
    void InsertVertexIndexProperty(string property);
103
104
105
    void AddVertexProperty(string property, string type);
    void AddEdgeProperty(string property, string type);
    void AddGraphProperty(string property, string type);
106
107
108
    void ReIndexEdges();
    void PurgeVertices(); // removes filtered vertices
    void PurgeEdges();    // removes filtered edges
109
    void Clear();
110
111

    // i/o
112
113
    void WriteToFile(string s, python::object pf, string format);
    void ReadFromFile(string s, python::object pf, string format);
114
115

    //
116
    // python interface
117
    //
118
    python::object Vertices() const;
119
    python::object Vertex(size_t i) const;
120
121
    python::object Edges() const;

122
    python::object AddVertex();
123
124
125
    void           RemoveVertex(const python::object& v);
    python::object AddEdge(const python::object& s, const python::object& t);
    void           RemoveEdge(const python::object& e);
126
127
128
129
130
131
132

    python::dict GetVertexProperties() const;
    python::dict GetEdgeProperties() const;
    python::dict GetGraphProperties() const;

    // used for graph properties
    graph_property_tag GetDescriptor() const { return graph_property_tag(); }
133
    bool CheckValid() const {return true;}
134

135
136
    void ExportPythonInterface() const;

Tiago Peixoto's avatar
Tiago Peixoto committed
137
138
139
    // signal handling
    void InitSignalHandling();

140
141
142
143
    //
    // Internal types
    //

Tiago Peixoto's avatar
Tiago Peixoto committed
144
    // the following defines the edges' internal properties
145
    typedef property<edge_index_t, size_t> EdgeProperty;
Tiago Peixoto's avatar
Tiago Peixoto committed
146
147

    // this is the main graph type
148
149
150
151
152
153
154
    typedef adjacency_list <vecS, // edges
                            vecS, // vertices
                            bidirectionalS,
                            no_property,
                            EdgeProperty>  multigraph_t;
    typedef graph_traits<multigraph_t>::vertex_descriptor vertex_t;
    typedef graph_traits<multigraph_t>::edge_descriptor edge_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
155

156
157
    typedef property_map<multigraph_t,vertex_index_t>::type vertex_index_map_t;
    typedef property_map<multigraph_t,edge_index_t>::type edge_index_map_t;
158

159
160
161
private:
    // Gets the encapsulated graph view. See graph_filtering.cc for details
    boost::any GetGraphView() const;
162

163
164
165
166
167
    // Generic graph_action functor. See graph_filtering.hh for details.
    template <class Action,
              class TR1=boost::mpl::vector<>, class TR2=boost::mpl::vector<>,
              class TR3=boost::mpl::vector<>, class TR4=boost::mpl::vector<> >
    friend struct detail::graph_action;
Tiago Peixoto's avatar
Tiago Peixoto committed
168

169
170
171
172
173
174
175
176
177
178
    // Arbitrary code execution
    template <class Action>
    friend void RunAction(GraphInterface &g, const Action& a);

    friend boost::any degree_selector(deg_t deg, const GraphInterface&gi);

    friend boost::any vertex_prop(const string& name, const GraphInterface& gi);
    friend boost::any edge_prop(const string& name, const GraphInterface& gi);
    friend boost::any graph_prop(const string& name, const GraphInterface& gi);

179
180
181
182
183
    // python interface
    friend class PythonVertex;
    template <class Graph>
    friend class PythonEdge;

184
    // this is the main graph
Tiago Peixoto's avatar
Tiago Peixoto committed
185
186
    multigraph_t _mg;

187
188
189
    // this will hold an instance of the graph views at run time
    vector<boost::any> _graph_views;

190
    // reverse and directed states
Tiago Peixoto's avatar
Tiago Peixoto committed
191
192
193
194
195
196
197
198
199
200
    bool _reversed;
    bool _directed;

    // vertex index map
    vertex_index_map_t _vertex_index;

    // edge index map
    edge_index_map_t _edge_index;

    // graph properties
201
    dynamic_properties _properties;
Tiago Peixoto's avatar
Tiago Peixoto committed
202
203

    // vertex filter
204
    typedef vector_property_map<uint8_t,vertex_index_map_t> vertex_filter_t;
205
    vertex_filter_t _vertex_filter_map;
206
    string _vertex_filter_property;
207
208
    bool _vertex_filter_invert;
    bool _vertex_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
209
210

    // edge filter
211
    typedef vector_property_map<uint8_t,edge_index_map_t> edge_filter_t;
212
    edge_filter_t _edge_filter_map;
213
    string _edge_filter_property;
214
215
    bool _edge_filter_invert;
    bool _edge_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
216
};
217
#pragma GCC visibility pop
Tiago Peixoto's avatar
Tiago Peixoto committed
218

219
220
// This is the main exception which will be thrown the outside world, when
// things go wrong
Tiago Peixoto's avatar
Tiago Peixoto committed
221

222
#pragma GCC visibility push(default)
223
class GraphException : public exception
Tiago Peixoto's avatar
Tiago Peixoto committed
224
{
225
    string _error;
Tiago Peixoto's avatar
Tiago Peixoto committed
226
public:
227
    GraphException(const string& error) {_error = error;}
Tiago Peixoto's avatar
Tiago Peixoto committed
228
229
    virtual ~GraphException() throw () {}
    virtual const char * what () const throw () {return _error.c_str();}
230
231
protected:
    virtual void SetError(const string& error) {_error = error;}
Tiago Peixoto's avatar
Tiago Peixoto committed
232
};
233
#pragma GCC visibility pop
Tiago Peixoto's avatar
Tiago Peixoto committed
234
235
236
237
238
239
240

} //namespace graph_tool

#endif