]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/example/minimum_degree_ordering.cpp
2 //=======================================================================
3 // Copyright 1997-2001 University of Notre Dame.
4 // Authors: Lie-Quan Lee
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
12 This file is to demo how to use minimum_degree_ordering algorithm.
14 Important Note: This implementation requires the BGL graph to be
15 directed. Therefore, nonzero entry (i, j) in a symmetrical matrix
16 A coresponds to two directed edges (i->j and j->i).
18 The bcsstk01.rsa is an example graph in Harwell-Boeing format,
19 and bcsstk01 is the ordering produced by Liu's MMD implementation.
20 Link this file with iohb.c to get the harwell-boeing I/O functions.
21 To run this example, type:
23 ./minimum_degree_ordering bcsstk01.rsa bcsstk01
27 #include <boost/config.hpp>
30 #include "boost/graph/adjacency_list.hpp"
31 #include "boost/graph/graph_utility.hpp"
32 #include "boost/graph/minimum_degree_ordering.hpp"
34 void terminate(const char* msg
)
36 std::cerr
<< msg
<< std::endl
;
40 //copy and modify from mtl harwell boeing stream
43 harwell_boeing(char* filename
) {
49 //readHB_info(filename, &M, &N, &nonzeros, &Type, &Nrhs);
50 colptr
= (int *)malloc((N
+1)*sizeof(int));
51 if ( colptr
== NULL
) terminate("Insufficient memory for colptr.\n");
52 rowind
= (int *)malloc(nonzeros
*sizeof(int));
53 if ( rowind
== NULL
) terminate("Insufficient memory for rowind.\n");
55 if ( Type
[0] == 'C' ) {
57 val
= (double *)malloc(nonzeros
*sizeof(double)*2);
58 if ( val
== NULL
) terminate("Insufficient memory for val.\n");
61 if ( Type
[0] != 'P' ) {
62 val
= (double *)malloc(nonzeros
*sizeof(double));
63 if ( val
== NULL
) terminate("Insufficient memory for val.\n");
67 //readHB_mat_double(filename, colptr, rowind, val);
80 inline int nrows() const { return M
; }
93 int main(int argc
, char* argv
[])
96 using namespace boost
;
99 cout
<< argv
[0] << " HB file" << endl
;
106 delta
= atoi(argv
[3]);
108 harwell_boeing
hbs(argv
[1]);
110 //must be BGL directed graph now
111 typedef adjacency_list
<vecS
, vecS
, directedS
> Graph
;
115 cout
<< "n is " << n
<< endl
;
121 for (int i
= 0; i
< n
; ++i
)
122 for (int j
= hbs
.colptr
[i
]; j
< hbs
.colptr
[i
+1]; ++j
)
123 if ( (hbs
.rowind
[j
- 1] - 1 ) > i
) {
124 add_edge(hbs
.rowind
[j
- 1] - 1, i
, G
);
125 add_edge(i
, hbs
.rowind
[j
- 1] - 1, G
);
129 cout
<< "number of off-diagnal elements: " << num_edge
<< endl
;
131 typedef std::vector
<int> Vector
;
133 Vector
inverse_perm(n
, 0);
136 Vector
supernode_sizes(n
, 1); // init has to be 1
138 boost::property_map
<Graph
, vertex_index_t
>::type
139 id
= get(vertex_index
, G
);
143 minimum_degree_ordering
145 make_iterator_property_map(°ree
[0], id
, degree
[0]),
148 make_iterator_property_map(&supernode_sizes
[0], id
, supernode_sizes
[0]),
152 ifstream
input(argv
[2]);
153 if ( input
.fail() ) {
154 cout
<< argv
[3] << " is failed to open!. " << endl
;
158 bool is_correct
= true;
160 for ( i
=0; i
<n
; i
++ ) {
162 if ( comp
!= inverse_perm
[i
]+1 ) {
163 cout
<< "at i= " << i
<< ": " << comp
164 << " ***is NOT EQUAL to*** " << inverse_perm
[i
]+1 << endl
;
168 for ( i
=0; i
<n
; i
++ ) {
170 if ( comp
!= perm
[i
]+1 ) {
171 cout
<< "at i= " << i
<< ": " << comp
172 << " ***is NOT EQUAL to*** " << perm
[i
]+1 << endl
;
177 cout
<< "Permutation and inverse permutation are correct. "<< endl
;
179 cout
<< "WARNING -- Permutation or inverse permutation is not the "
180 << "same ones generated by Liu's " << endl
;