graph.hh 6.92 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) 2006-2015 Tiago de Paula Peixoto <tiago@skewed.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

#ifndef GRAPH_HH
#define GRAPH_HH
20
#include "config.h"
Tiago Peixoto's avatar
Tiago Peixoto committed
21

22
23
24
25
#include <Python.h>
#include <boost/python/object.hpp>
#include <boost/python/dict.hpp>

Tiago Peixoto's avatar
Tiago Peixoto committed
26
27
#include <deque>

28
29
#include "graph_adjacency.hh"

Tiago Peixoto's avatar
Tiago Peixoto committed
30
#include <boost/graph/graph_traits.hpp>
31

32
#include "fast_vector_property_map.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
33
#include <boost/variant.hpp>
34
#include <boost/mpl/vector.hpp>
35
#include "graph_properties.hh"
36
#include "graph_exceptions.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
37
38
39

namespace graph_tool
{
40
using namespace std;
Tiago Peixoto's avatar
Tiago Peixoto committed
41
42

// GraphInterface
43
44
45
// 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
46

47
48
49
namespace detail
{
// Generic graph_action functor. See graph_filtering.hh for details.
Tiago Peixoto's avatar
Tiago Peixoto committed
50
template <class Action, class GraphViews, class Wrap = boost::mpl::false_,
51
          class... TRS>
52
53
54
struct graph_action;
}

Tiago Peixoto's avatar
Tiago Peixoto committed
55
56
57
class GraphInterface
{
public:
58
    GraphInterface();
59
    GraphInterface(const GraphInterface& g, bool keep_ref,
Tiago Peixoto's avatar
Tiago Peixoto committed
60
61
                   boost::python::object ovprops, boost::python::object oeprops,
                   boost::python::object vorder);
Tiago Peixoto's avatar
Tiago Peixoto committed
62
63
    ~GraphInterface();

64
65
66
    // useful enums

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

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

77
78
79
    //
    // Basic manipulation
    //
Tiago Peixoto's avatar
Tiago Peixoto committed
80

81
82
    size_t GetNumberOfVertices(bool filtered = true);
    size_t GetNumberOfEdges(bool filtered = true);
83
    void SetDirected(bool directed) {_directed = directed;}
84
    bool GetDirected() {return _directed;}
85
    void SetReversed(bool reversed) {_reversed = reversed;}
86
    bool GetReversed() {return _reversed;}
87
88
89
    void SetKeepEpos(bool keep) {_mg->set_keep_epos(keep);}
    bool GetKeepEpos() {return _mg->get_keep_epos();}

90
91

    // graph filtering
92
    void SetVertexFilterProperty(boost::any prop, bool invert);
93
    bool IsVertexFilterActive() const;
94
    void SetEdgeFilterProperty(boost::any prop, bool invert);
95
96
97
    bool IsEdgeFilterActive() const;

    // graph modification
98
    void InsertPropertyMap(string name, boost::any map);
99
    void ReIndexEdges();
100
    void PurgeVertices(boost::any old_index); // removes filtered vertices
101
    void PurgeEdges();    // removes filtered edges
102
    void Clear();
103
    void ClearEdges();
104
105
    void ShiftVertexProperty(boost::any map, boost::python::object oindex) const;
    void MoveVertexProperty(boost::any map, boost::python::object oindex) const;
106
    void ReIndexVertexProperty(boost::any map, boost::any old_index) const;
107
108
109
110
    void CopyVertexProperty(const GraphInterface& src, boost::any prop_src,
                            boost::any prop_tgt);
    void CopyEdgeProperty(const GraphInterface& src, boost::any prop_src,
                          boost::any prop_tgt);
111
112

    //
113
    // python interface
114
    //
Tiago Peixoto's avatar
Tiago Peixoto committed
115
    boost::python::object DegreeMap(string deg, boost::any weight) const;
116

117
    // used for graph properties
Tiago Peixoto's avatar
Tiago Peixoto committed
118
    boost::graph_property_tag GetDescriptor() const { return boost::graph_property_tag(); }
119
    bool CheckValid() const {return true;}
120

121
    // I/O
Tiago Peixoto's avatar
Tiago Peixoto committed
122
123
124
125
126
127
128
    void WriteToFile(string s, boost::python::object pf, string format,
                     boost::python::list properties);
    boost::python::tuple ReadFromFile(string s, boost::python::object pf,
                                      string format,
                                      boost::python::list ignore_vp,
                                      boost::python::list ignore_ep,
                                      boost::python::list ignore_gp);
Tiago Peixoto's avatar
Tiago Peixoto committed
129

130
131
132
133
    //
    // Internal types
    //

134
135
136
137
138
139
140
141
142
143
    // // the following defines the edges' internal properties
    // typedef property<edge_index_t, size_t> EdgeProperty;

    // // this is the main graph type
    // typedef adjacency_list <vecS, // edges
    //                         vecS, // vertices
    //                         bidirectionalS,
    //                         no_property,
    //                         EdgeProperty,
    //                         vecS>  multigraph_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
144
145
146
    typedef boost::adj_list<size_t> multigraph_t;
    typedef boost::graph_traits<multigraph_t>::vertex_descriptor vertex_t;
    typedef boost::graph_traits<multigraph_t>::edge_descriptor edge_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
147

Tiago Peixoto's avatar
Tiago Peixoto committed
148
149
150
    typedef boost::property_map<multigraph_t, boost::vertex_index_t>::type vertex_index_map_t;
    typedef boost::property_map<multigraph_t, boost::edge_index_t>::type edge_index_map_t;
    typedef ConstantPropertyMap<size_t, boost::graph_property_tag> graph_index_map_t;
151

152
153
    // internal access

154
    multigraph_t& GetGraph() {return *_mg;}
155
156
    vertex_index_map_t GetVertexIndex() {return _vertex_index;}
    edge_index_map_t   GetEdgeIndex()   {return _edge_index;}
157
    size_t             GetMaxEdgeIndex(){return _mg->get_last_index();}
158

159
    graph_index_map_t  GetGraphIndex()  {return graph_index_map_t(0);}
Tiago Peixoto's avatar
Tiago Peixoto committed
160

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

Tiago Peixoto's avatar
Tiago Peixoto committed
164
165
private:

166
    // Generic graph_action functor. See graph_filtering.hh for details.
167
    template <class Action, class GraphViews, class Wrap, class... TRS>
168
    friend struct detail::graph_action;
Tiago Peixoto's avatar
Tiago Peixoto committed
169

170
171
172
173
174
    // python interface
    friend class PythonVertex;
    template <class Graph>
    friend class PythonEdge;

175
176
    // this is the main graph
    shared_ptr<multigraph_t> _mg;
Tiago Peixoto's avatar
Tiago Peixoto committed
177
178
179
180
181
182

    // vertex index map
    vertex_index_map_t _vertex_index;

    // edge index map
    edge_index_map_t _edge_index;
Tiago Peixoto's avatar
Tiago Peixoto committed
183
184
185
186
187
188
189

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

    // reverse and directed states
    bool _reversed;
    bool _directed;
Tiago Peixoto's avatar
Tiago Peixoto committed
190

191
192
    // graph index map
    graph_index_map_t _graph_index;
Tiago Peixoto's avatar
Tiago Peixoto committed
193
194

    // vertex filter
Tiago Peixoto's avatar
Tiago Peixoto committed
195
    typedef boost::unchecked_vector_property_map<uint8_t,vertex_index_map_t>
196
        vertex_filter_t;
197
198
199
    vertex_filter_t _vertex_filter_map;
    bool _vertex_filter_invert;
    bool _vertex_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
200
201

    // edge filter
Tiago Peixoto's avatar
Tiago Peixoto committed
202
    typedef boost::unchecked_vector_property_map<uint8_t,edge_index_map_t>
Tiago Peixoto's avatar
Tiago Peixoto committed
203
        edge_filter_t;
204
205
206
    edge_filter_t _edge_filter_map;
    bool _edge_filter_invert;
    bool _edge_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
207
208
209
210
211
};

} //namespace graph_tool

#endif