← Back to branch summary

~dgleich/matlab-bgl/master

« back to all changes in this revision

Viewing changes to libmbgl/yasmic/undir_simple_csr_matrix_as_graph.hpp

  • Committer: David Gleich
  • Date: 2008-09-29 22:06:39 UTC
  • mfrom: (1.1.19 work)
  • Revision ID: dgleich@stanford.edu-20080929220639-4ic8mxd20lu81dla
Incorporated misc. fixes and graph layout algorithms.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libmbgl/yasmic/undir_simple_csr_matrix_as_graph.hpp
 
1
#ifndef YASMIC_UNDIR_SIMPLE_CSR_MATRIX_AS_GRAPH_HPP
 
2
#define YASMIC_UNDIR_SIMPLE_CSR_MATRIX_AS_GRAPH_HPP
 
3
 
 
4
/** @file undir_simple_csr_matrix.hpp
 
5
 * @author David F. Gleich
 
6
 * @copyright Stanford University, 2008
 
7
 * An almost exact copy of simple_csr_matrix_as_graph.hpp but with
 
8
 */
 
9
 
 
10
/** History
 
11
 *  2008-09-26: Initial coding
 
12
 */
 
13
 
 
14
#include <yasmic/simple_csr_matrix_as_graph.hpp>
 
15
#include <yasmic/undir_simple_csr_matrix.hpp>
 
16
#include <boost/graph/graph_traits.hpp>
 
17
#include <boost/graph/properties.hpp>
 
18
#include <boost/integer.hpp>
 
19
#include <boost/iterator/iterator_facade.hpp>
 
20
#include <boost/mpl/if.hpp>
 
21
#include <boost/type_traits/is_unsigned.hpp>
 
22
#include <boost/integer.hpp>
 
23
#include <yasmic/boost_mod/integer_extra.hpp>
 
24
#include <boost/iterator/counting_iterator.hpp>
 
25
 
 
26
#define YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS \
 
27
    typename Index,typename Value,typename EdgeIndex
 
28
#define YASMIC_SIMPLE_CSR_GRAPH_TYPE \
 
29
    typename yasmic::undir_simple_csr_matrix<Index,Value,EdgeIndex>
 
30
 
 
31
namespace yasmic {
 
32
    namespace impl {
 
33
        template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
34
        class undir_simple_csr_edge_iterator;
 
35
        template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
36
        class undir_simple_csr_out_edge_iterator;
 
37
    } // end namspase yasmic::impl
 
38
} // end namespace yasmic
 
39
 
 
40
template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
41
class yasmic::impl::undir_simple_csr_edge_iterator
 
42
{
 
43
public:
 
44
    typedef std::forward_iterator_tag iterator_category;
 
45
    typedef yasmic::impl::simple_csr_edge<Index,EdgeIndex> value_type;
 
46
 
 
47
    typedef const value_type* pointer;
 
48
 
 
49
    typedef value_type reference;
 
50
    // required due to "bug" in InputIterator concept, it is unused
 
51
    typedef typename boost::int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
 
52
 
 
53
    undir_simple_csr_edge_iterator() : ai(NULL), current_edge(), end_of_this_vertex(0) {}
 
54
 
 
55
    undir_simple_csr_edge_iterator(
 
56
                const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g,
 
57
                value_type current_edge,
 
58
                EdgeIndex end_of_this_vertex)
 
59
    : ai(g.ai), current_edge(current_edge),
 
60
      end_of_this_vertex(end_of_this_vertex) {}
 
61
 
 
62
    // From InputIterator
 
63
    reference operator*() const { return current_edge; }
 
64
    pointer operator->() const { return &current_edge; }
 
65
 
 
66
    bool operator==(const undir_simple_csr_edge_iterator<Index,Value,EdgeIndex>& o) const {
 
67
        return current_edge == o.current_edge;
 
68
    }
 
69
    bool operator!=(const undir_simple_csr_edge_iterator<Index,Value,EdgeIndex>& o) const {
 
70
        return current_edge != o.current_edge;
 
71
    }
 
72
 
 
73
    undir_simple_csr_edge_iterator& operator++() {
 
74
        ++current_edge.i;
 
75
        while (current_edge.i == end_of_this_vertex) {
 
76
            ++current_edge.r;
 
77
            end_of_this_vertex = ai[current_edge.r + 1];
 
78
        }
 
79
        return *this;
 
80
    }
 
81
 
 
82
    undir_simple_csr_edge_iterator operator++(int) {
 
83
        undir_simple_csr_edge_iterator temp = *this;
 
84
        ++*this;
 
85
        return temp;
 
86
    }
 
87
private:
 
88
    const EdgeIndex* ai;
 
89
    value_type current_edge;
 
90
    EdgeIndex end_of_this_vertex;
 
91
};
 
92
 
 
93
template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
94
class yasmic::impl::undir_simple_csr_out_edge_iterator
 
95
    : public boost::iterator_facade<
 
96
            typename yasmic::impl::undir_simple_csr_out_edge_iterator<Index,Value,EdgeIndex>,
 
97
            yasmic::impl::simple_csr_edge<Index,EdgeIndex>,
 
98
            std::random_access_iterator_tag,
 
99
            const typename yasmic::impl::simple_csr_edge<Index,EdgeIndex>&,
 
100
            typename boost::int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast>
 
101
{
 
102
private:
 
103
    typedef yasmic::impl::simple_csr_edge<Index,EdgeIndex> edge_descriptor;
 
104
 
 
105
public:
 
106
    typedef typename boost::int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast
 
107
        difference_type;
 
108
 
 
109
    undir_simple_csr_out_edge_iterator() {}
 
110
 
 
111
    // Implicit copy constructor OK
 
112
    explicit undir_simple_csr_out_edge_iterator(edge_descriptor e) : _e(e) { }
 
113
 
 
114
private:
 
115
    // iterator_facade requirements
 
116
    const edge_descriptor& dereference() const { return _e; }
 
117
 
 
118
    bool equal(const simple_csr_out_edge_iterator<Index,Value,EdgeIndex>& other) const
 
119
    { return _e == other._e; }
 
120
 
 
121
    void increment() { ++_e.i; }
 
122
    void decrement() { ++_e.i; }
 
123
    void advance(difference_type n) { _e.i += n; }
 
124
 
 
125
    difference_type distance_to(const yasmic::impl::undir_simple_csr_out_edge_iterator<Index,Value,EdgeIndex>& other) const
 
126
    { return other._e.i - _e.idx; }
 
127
 
 
128
    edge_descriptor _e;
 
129
 
 
130
    friend class boost::iterator_core_access;
 
131
};
 
132
 
 
133
namespace boost {
 
134
    //
 
135
    // implement the graph traits
 
136
    //
 
137
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
138
    struct graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE> {
 
139
        // requirements for Graph
 
140
        typedef Index vertex_descriptor;
 
141
        typedef yasmic::impl::simple_csr_edge<Index,EdgeIndex> edge_descriptor;
 
142
        typedef undirected_tag directed_category;
 
143
        typedef allow_parallel_edge_tag edge_parallel_category;
 
144
        typedef yasmic::impl::simple_csr_graph_traversal traversal_category;
 
145
        static vertex_descriptor null_vertex()
 
146
        {
 
147
            return std::numeric_limits<vertex_descriptor>::max BOOST_PREVENT_MACRO_SUBSTITUTION ();
 
148
        }
 
149
        // requirements for VertexListGraph
 
150
        typedef typename yasmic::impl::remove_signedness<Index>::type vertices_size_type;
 
151
        typedef counting_iterator<Index> vertex_iterator;
 
152
        // requirements for EdgeListGraph
 
153
        typedef typename yasmic::impl::remove_signedness<EdgeIndex>::type edges_size_type;
 
154
        typedef yasmic::impl::undir_simple_csr_edge_iterator<Index,Value,EdgeIndex>
 
155
            edge_iterator;
 
156
        // requirements for IncidenceGraph
 
157
        typedef edges_size_type degree_size_type;
 
158
        typedef yasmic::impl::undir_simple_csr_out_edge_iterator<Index,Value,EdgeIndex>
 
159
            out_edge_iterator;
 
160
        // requirements for AdjacencyGraph
 
161
        typedef Index* adjacency_iterator;
 
162
        // requirements for various bugs
 
163
        typedef void in_edge_iterator;
 
164
    };
 
165
 
 
166
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
167
    struct graph_traits<const YASMIC_SIMPLE_CSR_GRAPH_TYPE>
 
168
    : graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE> {};
 
169
 
 
170
    //
 
171
    // implement the requirements for VertexListGraph
 
172
    //
 
173
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
174
    inline typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::vertices_size_type
 
175
        num_vertices(const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g) {
 
176
            return g.nrows;
 
177
    }
 
178
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
179
    inline std::pair<counting_iterator<Index>,counting_iterator<Index> >
 
180
        vertices(const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g) {
 
181
            return std::make_pair(counting_iterator<Index>(0),
 
182
                                  counting_iterator<Index>(num_vertices(g)));
 
183
    }
 
184
    //
 
185
    // implement the requirements for EdgeListGraph
 
186
    //
 
187
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
188
    inline Index source(
 
189
        typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_descriptor e,
 
190
        const YASMIC_SIMPLE_CSR_GRAPH_TYPE&)
 
191
    {
 
192
        return e.r;
 
193
    }
 
194
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
195
    inline Index target(
 
196
        typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_descriptor e,
 
197
        const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g)
 
198
    {
 
199
        return g.aj[e.i];
 
200
    }
 
201
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
202
    inline typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edges_size_type
 
203
        num_edges(const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g) {
 
204
            return g.nnz;
 
205
    }
 
206
 
 
207
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
208
    inline std::pair< typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_iterator,
 
209
                      typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_iterator >
 
210
        edges(const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g) {
 
211
            typedef typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_iterator ei;
 
212
            typedef typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_descriptor e;
 
213
            if (g.nnz == 0) {
 
214
                return std::make_pair(ei(),ei());
 
215
            }
 
216
            else {
 
217
                Index r=0;
 
218
                while (g.ai[r] == g.ai[r+1]) { ++r; }
 
219
                return std::make_pair(ei(g,e(r,0),g.ai[r+1]),
 
220
                                       ei(g,e(g.nrows,g.nnz),0));
 
221
            }
 
222
    }
 
223
    //
 
224
    // implement the requirements for IncidenceGraph
 
225
    //
 
226
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
227
    inline typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::degree_size_type
 
228
        out_degree(Index u, const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g) {
 
229
            return g.ai[u+1] - g.ai[u];
 
230
    }
 
231
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
232
    inline std::pair< typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::out_edge_iterator,
 
233
                      typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::out_edge_iterator >
 
234
        out_edges(Index v, const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g) {
 
235
            typedef typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::out_edge_iterator ei;
 
236
            typedef typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_descriptor e;
 
237
 
 
238
            return std::make_pair(ei(e(v,g.ai[v])),ei(e(v+1,g.ai[v+1])));
 
239
    }
 
240
    //
 
241
    // implement the requirements for adjacency_iterator
 
242
    //
 
243
    template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
244
    inline std::pair< typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::adjacency_iterator,
 
245
                      typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::adjacency_iterator >
 
246
        adjacent_vertices(Index v, const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g) {
 
247
            return std::make_pair(&g.aj[v],&g.aj[v+1]);
 
248
    }
 
249
 
 
250
        template <YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS, typename Tag>
 
251
    struct property_map<YASMIC_SIMPLE_CSR_GRAPH_TYPE, Tag> {
 
252
    private:
 
253
        typedef identity_property_map vertex_index_type;
 
254
        typedef typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_descriptor
 
255
            edge_descriptor;
 
256
        typedef detail::simple_csr_edge_index_map<EdgeIndex,edge_descriptor> edge_index_type;
 
257
        typedef iterator_property_map<Value*,edge_index_type> edge_weight_type;
 
258
 
 
259
        typedef typename mpl::if_<is_same<Tag, edge_weight_t>,
 
260
                            edge_weight_type,
 
261
                            detail::error_property_not_found>::type
 
262
            edge_weight_or_none;
 
263
 
 
264
        typedef typename mpl::if_<is_same<Tag, edge_index_t>,
 
265
                            edge_index_type,
 
266
                            edge_weight_or_none>::type
 
267
            edge_prop_or_none;
 
268
    public:
 
269
            typedef typename mpl::if_<is_same<Tag, vertex_index_t>,
 
270
                                vertex_index_type,
 
271
                                edge_prop_or_none>::type type;
 
272
        typedef type const_type;
 
273
        }; // end property_map
 
274
 
 
275
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
276
    inline identity_property_map
 
277
    get(vertex_index_t, const YASMIC_SIMPLE_CSR_GRAPH_TYPE&)
 
278
    {
 
279
        return identity_property_map();
 
280
    }
 
281
 
 
282
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
283
    inline Index
 
284
    get(vertex_index_t,
 
285
        const YASMIC_SIMPLE_CSR_GRAPH_TYPE&, Index v)
 
286
    {
 
287
        return v;
 
288
    }
 
289
 
 
290
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
291
    inline typename property_map<YASMIC_SIMPLE_CSR_GRAPH_TYPE, edge_index_t>::const_type
 
292
    get(edge_index_t, const YASMIC_SIMPLE_CSR_GRAPH_TYPE&)
 
293
    {
 
294
        typedef typename property_map<YASMIC_SIMPLE_CSR_GRAPH_TYPE, edge_index_t>::const_type
 
295
            result_type;
 
296
        return result_type();
 
297
    }
 
298
 
 
299
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
300
    inline EdgeIndex
 
301
    get(edge_index_t, const YASMIC_SIMPLE_CSR_GRAPH_TYPE&,
 
302
        typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_descriptor e)
 
303
    {
 
304
        return e.i;
 
305
    }
 
306
 
 
307
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
308
    inline typename property_map<YASMIC_SIMPLE_CSR_GRAPH_TYPE, edge_weight_t>::const_type
 
309
    get(edge_weight_t, const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g)
 
310
    {
 
311
        return make_iterator_property_map(g.a,get(edge_index,g));
 
312
    }
 
313
 
 
314
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
315
    inline Value
 
316
    get(edge_weight_t, const YASMIC_SIMPLE_CSR_GRAPH_TYPE& g,
 
317
        typename graph_traits<YASMIC_SIMPLE_CSR_GRAPH_TYPE>::edge_descriptor e)
 
318
    {
 
319
        return g.a[e.i];
 
320
    }
 
321
 
 
322
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
323
    struct edge_property_type< YASMIC_SIMPLE_CSR_GRAPH_TYPE >  {
 
324
        typedef void type;
 
325
    };
 
326
 
 
327
    template<YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS>
 
328
    struct vertex_property_type< YASMIC_SIMPLE_CSR_GRAPH_TYPE >  {
 
329
        typedef void type;
 
330
    };
 
331
 
 
332
} // end namespace boost
 
333
 
 
334
#undef YASMIC_SIMPLE_CSR_GRAPH_TYPE
 
335
#undef YASMIC_SIMPLE_CSR_TEMPLATE_PARAMS
 
336
 
 
337
#endif /* YASMIC_UNDIR_SIMPLE_CSR_MATRIX_AS_GRAPH_HPP */
 
338