45 #ifndef _ZOLTAN2_ALGRCM_HPP_
46 #define _ZOLTAN2_ALGRCM_HPP_
62 template <
typename Adapter>
67 const RCP<const typename Adapter::base_adapter_t> adapter;
68 const RCP<Teuchos::ParameterList> pl;
69 const RCP<const Teuchos::Comm<int> > comm;
70 RCP<const Environment> env;
81 const RCP<const typename Adapter::base_adapter_t> &adapter__,
82 const RCP<Teuchos::ParameterList> &pl__,
83 const RCP<
const Teuchos::Comm<int> > &comm__,
84 RCP<const Environment> &env__,
86 ) : adapter(adapter__), pl(pl__), comm(comm__), env(env__), graphFlags(graphFlags__)
92 throw std::logic_error(
"AlgRCM does not yet support global ordering.");
102 ArrayView<const gno_t> edgeIds;
103 ArrayView<const offset_t> offsets;
104 ArrayView<StridedData<lno_t, scalar_t> > wgts;
107 const size_t nVtx = model->getLocalNumVertices();
108 model->getEdgeList(edgeIds, offsets, wgts);
109 const int numWeightsPerEdge = model->getNumWeightsPerEdge();
110 if (numWeightsPerEdge > 1){
111 throw std::runtime_error(
"Multiple weights not supported.");
116 cout <<
"Debug: Local graph from getLocalEdgeList" << endl;
117 cout <<
"rank " << comm->getRank() <<
": nVtx= " << nVtx << endl;
118 cout <<
"rank " << comm->getRank() <<
": edgeIds: " << edgeIds << endl;
119 cout <<
"rank " << comm->getRank() <<
": offsets: " << offsets << endl;
123 const ArrayRCP<lno_t> invPerm = solution->getPermutationRCP(
true);
124 const ArrayRCP<lno_t> tmpPerm(invPerm.size());
128 if (offsets[nVtx] == 0) {
129 for (
size_t i = 0; i < nVtx; ++i) {
132 solution->setHaveInverse(
true);
138 for (
size_t i = 0; i < nVtx; ++i) {
148 Teuchos::Array<std::pair<gno_t, offset_t> > children;
150 while (count < nVtx) {
154 while ((next < nVtx) && (static_cast<Tpetra::global_size_t>(invPerm[next]) != INVALID)) next++;
158 std::string root_method = pl->get(
"root_method",
"pseudoperipheral");
159 if (root_method == std::string(
"first"))
161 else if (root_method == std::string(
"smallest_degree"))
162 root = findSmallestDegree(next, nVtx, edgeIds, offsets);
163 else if (root_method == std::string(
"pseudoperipheral"))
164 root = findPseudoPeripheral(next, nVtx, edgeIds, offsets);
167 throw std::runtime_error(
"invalid root_method");
173 invPerm[
root] = count++;
184 for (
offset_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
185 gno_t child = edgeIds[ptr];
186 if (static_cast<Tpetra::global_size_t>(invPerm[child]) == INVALID){
188 std::pair<gno_t,offset_t> newchild;
189 newchild.first = child;
190 newchild.second = offsets[child+1] - offsets[child];
191 children.push_back(newchild);
199 typename Teuchos::Array<std::pair<gno_t,offset_t> >::iterator it = children.begin ();
200 for ( ; it != children.end(); ++it){
202 gno_t child = it->first;
203 invPerm[child] = count++;
204 tmpPerm[invPerm[child]] = child;
217 for (
size_t i=0; i < nVtx/2; ++i) {
224 invPerm[tmpPerm[nVtx-1-i]] = i;
225 invPerm[temp] = nVtx-1-i;
230 solution->setHaveInverse(
true);
236 gno_t findSmallestDegree(
239 ArrayView<const gno_t> edgeIds,
240 ArrayView<const offset_t> offsets)
243 Teuchos::Array<bool> mark(nVtx);
247 gno_t smallestVertex = 0;
250 for (
int i=0; i<nVtx; i++)
260 offset_t deg = offsets[v+1] - offsets[v];
261 if (deg < smallestDegree){
262 smallestDegree = deg;
266 for (
offset_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
267 gno_t child = edgeIds[ptr];
274 return smallestVertex;
278 gno_t findPseudoPeripheral(
281 ArrayView<const gno_t> edgeIds,
282 ArrayView<const offset_t> offsets)
285 Teuchos::Array<bool> mark(nVtx);
288 const int numBFS = 2;
289 for (
int bfs=0; bfs<numBFS; bfs++){
291 for (
int i=0; i<nVtx; i++)
300 for (
offset_t ptr = offsets[v]; ptr < offsets[v+1]; ++ptr){
301 gno_t child = edgeIds[ptr];
int localOrder(const RCP< LocalOrderingSolution< lno_t > > &solution)
Ordering method.
AlgRCM(const RCP< const typename Adapter::base_adapter_t > &adapter__, const RCP< Teuchos::ParameterList > &pl__, const RCP< const Teuchos::Comm< int > > &comm__, RCP< const Environment > &env__, const modelFlag_t &graphFlags__)
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
map_t::global_ordinal_type gno_t
Defines the OrderingSolution class.
Adapter::offset_t offset_t
Algorithm defines the base class for all algorithms.
map_t::local_ordinal_type lno_t
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)