graph.hh 7.39 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>
32
#include "graph_properties.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
33 34 35 36
#include "config.h"

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

// GraphInterface
41 42 43
// 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
44

45 46 47 48 49 50 51 52 53
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;
}

54 55 56
// 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
57 58 59
class GraphInterface
{
public:
60
    GraphInterface();
61
    GraphInterface(const GraphInterface& gi);
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() const;
    size_t GetNumberOfEdges() const;
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

    // graph filtering
89
    void SetVertexFilterProperty(boost::any prop, bool invert);
90
    bool IsVertexFilterActive() const;
91
    void SetEdgeFilterProperty(boost::any prop, bool invert);
92 93 94
    bool IsEdgeFilterActive() const;

    // graph modification
95
    void InsertPropertyMap(string name, boost::any map);
96 97 98
    void ReIndexEdges();
    void PurgeVertices(); // removes filtered vertices
    void PurgeEdges();    // removes filtered edges
99
    void Clear();
100 101 102 103 104 105
    void ClearEdges();
    void ShiftVertexProperty(boost::any map, size_t index) const;
    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);
106 107

    //
108
    // python interface
109
    //
110
    python::object Vertices() const;
111
    python::object Vertex(size_t i) const;
112 113
    python::object Edges() const;

114
    python::object AddVertex();
115 116 117
    void           RemoveVertex(const python::object& v);
    python::object AddEdge(const python::object& s, const python::object& t);
    void           RemoveEdge(const python::object& e);
118 119 120

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

123 124
    void ExportPythonInterface() const;

125 126 127 128
    // I/O
    void WriteToFile(string s, python::object pf, string format,
                     python::list properties);
    python::tuple ReadFromFile(string s, python::object pf, string format);
Tiago Peixoto's avatar
Tiago Peixoto committed
129

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

Tiago Peixoto's avatar
Tiago Peixoto committed
134
    // the following defines the edges' internal properties
135
    typedef property<edge_index_t, size_t> EdgeProperty;
Tiago Peixoto's avatar
Tiago Peixoto committed
136 137

    // this is the main graph type
138 139 140 141 142 143 144
    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
145

146 147
    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;
148
    typedef ConstantPropertyMap<size_t,graph_property_tag> graph_index_map_t;
149

150 151 152 153 154 155
    // internal access

    multigraph_t& GetGraph() {return _mg;}
    vertex_index_map_t GetVertexIndex() {return _vertex_index;}
    edge_index_map_t   GetEdgeIndex()   {return _edge_index;}
    graph_index_map_t  GetGraphIndex()  {return graph_index_map_t(0);}
Tiago Peixoto's avatar
Tiago Peixoto committed
156

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

161 162 163 164 165
    // 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
166

167 168
    // Arbitrary code execution
    template <class Action>
169
    friend void RunAction(GraphInterface& g, const Action& a);
170

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

176
    // this is the main graph
Tiago Peixoto's avatar
Tiago Peixoto committed
177 178
    multigraph_t _mg;

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

182
    // reverse and directed states
Tiago Peixoto's avatar
Tiago Peixoto committed
183 184 185 186 187 188 189 190
    bool _reversed;
    bool _directed;

    // vertex index map
    vertex_index_map_t _vertex_index;

    // edge index map
    edge_index_map_t _edge_index;
191 192
    vector<size_t> _free_indexes; // indexes of deleted edges to be used up for
                                  // new edges to avoid needless fragmentation
Tiago Peixoto's avatar
Tiago Peixoto committed
193

194 195
    // graph index map
    graph_index_map_t _graph_index;
Tiago Peixoto's avatar
Tiago Peixoto committed
196 197

    // vertex filter
198
    typedef vector_property_map<uint8_t,vertex_index_map_t> vertex_filter_t;
199 200 201
    vertex_filter_t _vertex_filter_map;
    bool _vertex_filter_invert;
    bool _vertex_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
202 203

    // edge filter
204
    typedef vector_property_map<uint8_t,edge_index_map_t> edge_filter_t;
205 206 207
    edge_filter_t _edge_filter_map;
    bool _edge_filter_invert;
    bool _edge_filter_active;
Tiago Peixoto's avatar
Tiago Peixoto committed
208
};
209
#pragma GCC visibility pop
Tiago Peixoto's avatar
Tiago Peixoto committed
210

211 212 213
// Exceptions
// ==========
//
214 215
// This is the main exception which will be thrown the outside world, when
// things go wrong
Tiago Peixoto's avatar
Tiago Peixoto committed
216

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

} //namespace graph_tool

#endif