45 #ifndef _ZOLTAN2_ALGRCM_HPP_
46 #define _ZOLTAN2_ALGRCM_HPP_
62 template <
typename Adapter>
67 const RCP<GraphModel<Adapter> > model;
68 const RCP<Teuchos::ParameterList> pl;
69 const RCP<const Teuchos::Comm<int> > comm;
73 typedef typename Adapter::lno_t
lno_t;
74 typedef typename Adapter::gno_t
gno_t;
80 const RCP<Teuchos::ParameterList> &pl__,
81 const RCP<
const Teuchos::Comm<int> > &comm__
82 ) : model(model__), pl(pl__), comm(comm__)
88 throw std::logic_error(
"AlgRCM does not yet support global ordering.");
98 ArrayView<const gno_t> edgeIds;
99 ArrayView<const offset_t> offsets;
100 ArrayView<StridedData<lno_t, scalar_t> > wgts;
102 const size_t nVtx = model->getLocalNumVertices();
103 model->getEdgeList(edgeIds, offsets, wgts);
104 const int numWeightsPerEdge = model->getNumWeightsPerEdge();
105 if (numWeightsPerEdge > 1){
106 throw std::runtime_error(
"Multiple weights not supported.");
111 cout <<
"Debug: Local graph from getLocalEdgeList" << endl;
112 cout <<
"rank " << comm->getRank() <<
": nVtx= " << nVtx << endl;
113 cout <<
"rank " << comm->getRank() <<
": edgeIds: " << edgeIds << endl;
114 cout <<
"rank " << comm->getRank() <<
": offsets: " << offsets << endl;
118 const ArrayRCP<lno_t> invPerm = solution->getPermutationRCP(
true);
122 if (offsets[nVtx] == 0) {
123 for (
size_t i = 0; i < nVtx; ++i) {
126 solution->setHaveInverse(
true);
132 for (
size_t i = 0; i < nVtx; ++i) {
142 Teuchos::Array<std::pair<gno_t, offset_t> > children;
144 while (count < nVtx) {
148 while ((next < nVtx) && (static_cast<Tpetra::global_size_t>(invPerm[next]) != INVALID)) next++;
152 std::string root_method = pl->get(
"root_method",
"pseudoperipheral");
153 if (root_method == std::string(
"first"))
155 else if (root_method == std::string(
"smallest_degree"))
156 root = findSmallestDegree(next, nVtx, edgeIds, offsets);
157 else if (root_method == std::string(
"pseudoperipheral"))
158 root = findPseudoPeripheral(next, nVtx, edgeIds, offsets);
161 throw std::runtime_error(
"invalid root_method");
167 invPerm[
root] = count++;
177 for (
offset_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
178 gno_t child = edgeIds[ptr];
179 if (static_cast<Tpetra::global_size_t>(invPerm[child]) == INVALID){
181 std::pair<gno_t,offset_t> newchild;
182 newchild.first = child;
183 newchild.second = offsets[child+1] - offsets[child];
184 children.push_back(newchild);
192 typename Teuchos::Array<std::pair<gno_t,offset_t> >::iterator it = children.begin ();
193 for ( ; it != children.end(); ++it){
195 gno_t child = it->first;
196 invPerm[child] = count++;
207 for (
size_t i=0; i < nVtx/2; ++i) {
210 invPerm[i] = invPerm[nVtx-1-i];
211 invPerm[nVtx-1-i] = temp;
215 solution->setHaveInverse(
true);
221 gno_t findSmallestDegree(
224 ArrayView<const gno_t> edgeIds,
225 ArrayView<const offset_t> offsets)
228 Teuchos::Array<bool> mark(nVtx);
232 gno_t smallestVertex = 0;
235 for (
int i=0; i<nVtx; i++)
245 offset_t deg = offsets[v+1] - offsets[v];
246 if (deg < smallestDegree){
247 smallestDegree = deg;
251 for (
offset_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
252 gno_t child = edgeIds[ptr];
259 return smallestVertex;
263 gno_t findPseudoPeripheral(
266 ArrayView<const gno_t> edgeIds,
267 ArrayView<const offset_t> offsets)
270 Teuchos::Array<bool> mark(nVtx);
273 const int numBFS = 2;
274 for (
int bfs=0; bfs<numBFS; bfs++){
276 for (
int i=0; i<nVtx; i++)
285 for (
offset_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
286 gno_t child = edgeIds[ptr];
int localOrder(const RCP< LocalOrderingSolution< lno_t > > &solution)
Ordering method.
Defines the OrderingSolution class.
AlgRCM(const RCP< GraphModel< Adapter > > &model__, const RCP< Teuchos::ParameterList > &pl__, const RCP< const Teuchos::Comm< int > > &comm__)
Adapter::offset_t offset_t
Algorithm defines the base class for all algorithms.
int globalOrder(const RCP< GlobalOrderingSolution< gno_t > > &)
Ordering method.
Sort vector of pairs (key, value) by value.
Adapter::scalar_t scalar_t
GraphModel defines the interface required for graph models.
Tpetra::global_size_t global_size_t
Defines the GraphModel interface.
void sort(Teuchos::Array< std::pair< key_t, value_t > > &listofPairs, bool inc=true)