← Back to branch summary

~dgleich/matlab-bgl/master

« back to all changes in this revision

Viewing changes to libmbgl/yasmic/matrix_row_col_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/matrix_row_col_graph.hpp
 
1
#ifndef YASMIC_MATRIX_ROW_COL_GRAPH
 
2
#define YASMIC_MATRIX_ROW_COL_GRAPH
 
3
 
 
4
/**
 
5
 * @file matrix_row_col_graph.hpp
 
6
 * @author David Gleich
 
7
 * 
 
8
 * A row and column graph filter for a matrix. 
 
9
 *
 
10
 * Regardless of the input, the output is just a nonzero-matrix.
 
11
 *
 
12
 * The row and column graph of a matrix has a vertex for each row and column 
 
13
 * and an edge where A(i,j) != 0.  The weight on the edge is A(i,j).
 
14
 *
 
15
 * The first m vertices correspond to the row vertices, the next
 
16
 * n vertices correspond to the columns.
 
17
 *
 
18
 * We just wrap the original dataset and forward calls.  
 
19
 * (This does not make a copy of the original matrix!)
 
20
 */
 
21
 
 
22
namespace yasmic
 
23
{
 
24
 
 
25
namespace impl
 
26
{
 
27
    template <class Matrix>
 
28
        struct matrix_row_col_graph_nz_iter_help
 
29
        {
 
30
 
 
31
                typedef typename smatrix_traits<Matrix>::index_type index_type;
 
32
                typedef typename smatrix_traits<Matrix>::value_type value_type;
 
33
 
 
34
                typedef boost::tuple<index_type, index_type, value_type> nz_type;
 
35
        };
 
36
 
 
37
    // implement the "repeating" iterator
 
38
        template <class Matrix>
 
39
        class matrix_row_col_graph_nz_iterator
 
40
        : public boost::iterator_facade<
 
41
        matrix_row_col_graph_nz_iterator<Matrix>,
 
42
                typename matrix_row_col_graph_nz_iter_help<Matrix>::nz_type const,
 
43
        boost::forward_traversal_tag, 
 
44
        typename matrix_row_col_graph_nz_iter_help<Matrix>::nz_type const >
 
45
    {
 
46
 
 
47
    public:
 
48
        matrix_row_col_graph_nz_iterator() 
 
49
                        : _m(NULL), _repeat(true), _nr(0)
 
50
                {}
 
51
        
 
52
        matrix_row_col_graph_nz_iterator(Matrix& m)
 
53
                        : _m(&m), _repeat(true), _nr(nrows(m))
 
54
        { 
 
55
                        i = nonzeros(m).first;
 
56
                }
 
57
 
 
58
        matrix_row_col_graph_nz_iterator(Matrix& m,bool)
 
59
                        : _m(&m), _repeat(true), _nr(nrows(m))
 
60
        { 
 
61
                        i = nonzeros(m).second;
 
62
                }
 
63
        
 
64
        
 
65
    private:
 
66
        friend class boost::iterator_core_access;
 
67
 
 
68
        void increment() 
 
69
        {  
 
70
            if (_repeat)
 
71
            {
 
72
                _repeat = false;
 
73
            }
 
74
            else
 
75
            {
 
76
                _repeat = true;
 
77
                ++i;
 
78
            }
 
79
        }
 
80
        
 
81
        bool equal(matrix_row_col_graph_nz_iterator const& other) const
 
82
        {
 
83
                        return (i == other.i && _repeat == other._repeat);
 
84
        }
 
85
        
 
86
        typename matrix_row_col_graph_nz_iter_help<Matrix>::nz_type
 
87
        dereference() const 
 
88
        { 
 
89
            if (_repeat)
 
90
            {
 
91
                return boost::make_tuple(
 
92
                    row(*i, *_m),column(*i, *_m)+_nr,value(*i,*_m));
 
93
            }
 
94
            else
 
95
            {
 
96
                return boost::make_tuple(
 
97
                   column(*i, *_m)+_nr,row(*i, *_m),value(*i,*_m));
 
98
            }
 
99
        }
 
100
 
 
101
        bool _repeat;
 
102
 
 
103
                Matrix *_m;
 
104
                
 
105
                typename smatrix_traits<Matrix>::nonzero_iterator i;
 
106
        typename smatrix_traits<Matrix>::index_type _nr;
 
107
    };
 
108
 
 
109
 
 
110
}  /* end namespace yasmic::impl */
 
111
 
 
112
 
 
113
template <class Matrix>
 
114
class matrix_row_col_graph
 
115
{
 
116
public:
 
117
        Matrix& _m;
 
118
 
 
119
        matrix_row_col_graph(Matrix& m)
 
120
                : _m(m)
 
121
        {}
 
122
 
 
123
        typedef typename smatrix_traits<Matrix>::index_type index_type;
 
124
        typedef typename smatrix_traits<Matrix>::value_type value_type;
 
125
 
 
126
    typedef typename boost::tuple<index_type, index_type, value_type> nonzero_descriptor;
 
127
    typedef impl::matrix_row_col_graph_nz_iterator<Matrix> nonzero_iterator;
 
128
 
 
129
        typedef void row_iterator;
 
130
        typedef void row_nonzero_descriptor;
 
131
        typedef void row_nonzero_iterator;
 
132
 
 
133
        typedef void column_iterator;
 
134
 
 
135
        typedef typename smatrix_traits<Matrix>::size_type size_type;
 
136
        typedef typename smatrix_traits<Matrix>::nz_index_type nz_index_type;
 
137
        typedef typename smatrix_traits<Matrix>::properties properties;
 
138
};
 
139
 
 
140
namespace impl 
 
141
{
 
142
        template <class Matrix>
 
143
        struct matrix_row_col_graph_help
 
144
        {
 
145
                typedef smatrix_traits<matrix_row_col_graph<Matrix> > traits;
 
146
 
 
147
                typedef std::pair<typename traits::size_type, typename traits::size_type> dims_ret_type;
 
148
                typedef std::pair<typename traits::nonzero_iterator, typename traits::nonzero_iterator> nzs_ret_type;
 
149
                typedef typename traits::size_type nnz_ret_type;
 
150
        };
 
151
}
 
152
 
 
153
 
 
154
template <class Matrix>
 
155
inline typename impl::matrix_row_col_graph_help<Matrix>::nnz_ret_type 
 
156
nnz(matrix_row_col_graph<Matrix>& tm)
 
157
{
 
158
        return 2*nnz(tm._m);
 
159
}
 
160
 
 
161
template <class Matrix>
 
162
inline typename impl::matrix_row_col_graph_help<Matrix>::dims_ret_type 
 
163
dimensions(matrix_row_col_graph<Matrix>& tm)
 
164
{
 
165
        typename impl::transpose_matrix_help<Matrix>::dims_ret_type d = dimensions(tm._m);
 
166
        return (std::make_pair(d.second + d.first, d.second + d.first));
 
167
}
 
168
 
 
169
template <class Matrix>
 
170
inline typename impl::matrix_row_col_graph_help<Matrix>::nzs_ret_type 
 
171
nonzeros(matrix_row_col_graph<Matrix>& tm)
 
172
{
 
173
 
 
174
    return std::make_pair( impl::matrix_row_col_graph_nz_iterator<Matrix>(tm._m),
 
175
        impl::matrix_row_col_graph_nz_iterator<Matrix>(tm._m,true));
 
176
}
 
177
 
 
178
} // namespace yasmic
 
179
 
 
180
#endif // YASMIC_MATRIX_ROW_COL_GRAPH
 
181
 
 
182