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<Teuchos::Comm<int> > comm;
73 typedef typename Adapter::lno_t
lno_t;
74 typedef typename Adapter::gno_t
gno_t;
79 const RCP<Teuchos::ParameterList> &pl__,
80 const RCP<Teuchos::Comm<int> > &comm__
81 ) : model(model__), pl(pl__), comm(comm__)
92 ArrayView<const gno_t> edgeIds;
93 ArrayView<const lno_t> offsets;
94 ArrayView<StridedData<lno_t, scalar_t> > wgts;
96 const size_t nVtx = model->getLocalNumVertices();
97 model->getEdgeList(edgeIds, offsets, wgts);
98 const int numWeightsPerEdge = model->getNumWeightsPerEdge();
99 if (numWeightsPerEdge > 1){
100 throw std::runtime_error(
"Multiple weights not supported.");
105 cout <<
"Debug: Local graph from getLocalEdgeList" << endl;
106 cout <<
"rank " << comm->getRank() <<
": nVtx= " << nVtx << endl;
107 cout <<
"rank " << comm->getRank() <<
": edgeIds: " << edgeIds << endl;
108 cout <<
"rank " << comm->getRank() <<
": offsets: " << offsets << endl;
112 ArrayRCP<lno_t> invPerm = solution->getPermutationRCP(
true);
116 if (offsets[nVtx] == 0) {
117 for (
size_t i = 0; i < nVtx; ++i) {
120 solution->setHaveInverse(
true);
126 for (
size_t i = 0; i < nVtx; ++i) {
136 Teuchos::Array<std::pair<gno_t, size_t> > children;
138 while (count < nVtx) {
142 while ((next < nVtx) && (static_cast<Tpetra::global_size_t>(invPerm[next]) != INVALID)) next++;
146 std::string root_method = pl->get(
"root_method",
"pseudoperipheral");
147 if (root_method == std::string(
"first"))
149 else if (root_method == std::string(
"smallest_degree"))
150 root = findSmallestDegree(next, nVtx, edgeIds, offsets);
151 else if (root_method == std::string(
"pseudoperipheral"))
152 root = findPseudoPeripheral(next, nVtx, edgeIds, offsets);
155 throw std::runtime_error(
"invalid root_method");
161 invPerm[
root] = count++;
171 for (lno_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
172 gno_t child = edgeIds[ptr];
173 if (static_cast<Tpetra::global_size_t>(invPerm[child]) == INVALID){
175 std::pair<gno_t,size_t> newchild;
176 newchild.first = child;
177 newchild.second = offsets[child+1] - offsets[child];
178 children.push_back(newchild);
186 typename Teuchos::Array<std::pair<gno_t,size_t> >::iterator it = children.begin ();
187 for ( ; it != children.end(); ++it){
189 gno_t child = it->first;
190 invPerm[child] = count++;
201 for (
size_t i=0; i < nVtx/2; ++i) {
204 invPerm[i] = invPerm[nVtx-1-i];
205 invPerm[nVtx-1-i] = temp;
209 solution->setHaveInverse(
true);
215 gno_t findSmallestDegree(
218 ArrayView<const gno_t> edgeIds,
219 ArrayView<const lno_t> offsets)
222 Teuchos::Array<bool> mark(nVtx);
225 lno_t smallestDegree = nVtx;
226 gno_t smallestVertex = 0;
229 for (
int i=0; i<nVtx; i++)
239 lno_t deg = offsets[v+1] - offsets[v];
240 if (deg < smallestDegree){
241 smallestDegree = deg;
245 for (lno_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
246 gno_t child = edgeIds[ptr];
253 return smallestVertex;
257 gno_t findPseudoPeripheral(
260 ArrayView<const gno_t> edgeIds,
261 ArrayView<const lno_t> offsets)
264 Teuchos::Array<bool> mark(nVtx);
267 const int numBFS = 2;
268 for (
int bfs=0; bfs<numBFS; bfs++){
270 for (
int i=0; i<nVtx; i++)
279 for (lno_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
280 gno_t child = edgeIds[ptr];
AlgRCM(const RCP< GraphModel< Adapter > > &model__, const RCP< Teuchos::ParameterList > &pl__, const RCP< Teuchos::Comm< int > > &comm__)
Defines the OrderingSolution class.
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
Algorithm defines the base class for all algorithms.
Sort vector of pairs (key, value) by value.
Adapter::scalar_t scalar_t
GraphModel defines the interface required for graph models.
Defines the GraphModel interface.
The class containing ordering solutions.
void sort(Teuchos::Array< std::pair< key_t, value_t > > &listofPairs, bool inc=true)