Zoltan2
Loading...
Searching...
No Matches
Zoltan2_componentMetrics.hpp
Go to the documentation of this file.
1// @HEADER
2//
3// ***********************************************************************
4//
5// Zoltan2: A package of combinatorial algorithms for scientific computing
6// Copyright 2012 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Karen Devine (kddevin@sandia.gov)
39// Erik Boman (egboman@sandia.gov)
40// Siva Rajamanickam (srajama@sandia.gov)
41//
42// ***********************************************************************
43//
44// @HEADER
45
53#ifndef _ZOLTAN2_COMPONENTMETRICS_HPP_
54#define _ZOLTAN2_COMPONENTMETRICS_HPP_
55
56#include <Zoltan2_Standards.hpp>
58#include <Teuchos_Comm.hpp>
59#include <queue>
60
61namespace Zoltan2
62{
63
64template <typename Adapter>
66
67public:
68 typedef typename Adapter::lno_t lno_t;
69 typedef typename Adapter::gno_t gno_t;
70 typedef typename Adapter::offset_t offset_t;
71 typedef typename Adapter::scalar_t scalar_t;
72
73 perProcessorComponentMetrics(const Adapter &ia,
74 const Teuchos::Comm<int> &comm);
75
76#ifdef HAVE_ZOLTAN2_MPI
77 // Wrap MPI_Comm as a Teuchos::Comm, then call Teuchos::Comm constructor
78 // Uses delegating constructor feature of C++11.
79 perProcessorComponentMetrics(const Adapter &ia, const MPI_Comm mpicomm) :
81 Teuchos::MpiComm<int>(Teuchos::opaqueWrapper(mpicomm)))
82 {}
83#endif
84
86
87 inline size_t getNumComponents() {return nComponent;}
88 inline size_t getMaxComponentSize() {return maxComponentSize;}
89 inline size_t getMinComponentSize() {return minComponentSize;}
90 inline double getAvgComponentSize() {return avgComponentSize;}
91
92private:
93 size_t nComponent; // number of components
94 size_t maxComponentSize; // size of largest component
95 size_t minComponentSize; // size of smalled component
96 double avgComponentSize; // average component size
97
98 inline void markAndEnqueue(std::queue<gno_t> &q, bool *mark,
99 size_t &nUnmarkedVtx, size_t &cSize, gno_t vtx) {
100 // insert vtx into the queue
101 q.push(vtx);
102
103 // mark vtx
104 nUnmarkedVtx--;
105 mark[vtx] = true;
106
107 // increment component size
108 cSize++;
109 }
110};
111
113template <typename Adapter>
115 const Adapter &ia, const Teuchos::Comm<int> &comm) :
116 nComponent(0), maxComponentSize(0), minComponentSize(0),
117 avgComponentSize(0.)
118{
119 // build local graph model from input adapter
120 std::bitset<NUM_MODEL_FLAGS> graphFlags;
121 graphFlags.set(REMOVE_SELF_EDGES);
122 graphFlags.set(BUILD_LOCAL_GRAPH); // Local graph;
123 // all vertex numbering is 0 to nVtx-1
124
125 Teuchos::RCP<const Teuchos::Comm<int> > tcomm = rcp(&comm, false);
126 Teuchos::RCP<const Zoltan2::Environment> env =
127 rcp(new Zoltan2::Environment(tcomm));
128
129 typedef typename Adapter::base_adapter_t base_adapter_t;
130 Teuchos::RCP<const base_adapter_t> ria = rcp(&ia, false);
131 Zoltan2::GraphModel<base_adapter_t> graph(ria, env, tcomm, graphFlags);
132
133 // get graph from model
134 const size_t nVtx = graph.getLocalNumVertices();
135 ArrayView<const gno_t> adj;
136 ArrayView<const offset_t> offset;
137 ArrayView<StridedData<lno_t, scalar_t> > wgts; // unused
138 graph.getEdgeList(adj, offset, wgts);
139
140 // do a simple BFS on the graph;
141 // can replace later with KokkosKernels or other TPL
142 size_t nUnmarkedVtx = nVtx;
143 bool *mark = new bool[nUnmarkedVtx];
144 for (size_t i = 0; i < nUnmarkedVtx; i++) mark[i] = false;
145 size_t startVtx = 0;
146
147 std::queue<gno_t> q;
148
149 // until all vertices are marked...
150 while (nUnmarkedVtx > 0) {
151
152 // Find the next component
153 size_t cSize = 0;
154 nComponent++;
155
156 // Find an unmarked vertex; put it in the queue
157 while (mark[startVtx]) startVtx++;
158 markAndEnqueue(q, mark, nUnmarkedVtx, cSize, startVtx);
159
160 while (!q.empty()) {
161 gno_t vtx = q.front();
162 q.pop();
163
164 // Add neighbors of vtx to queue.
165 for (offset_t j = offset[vtx]; j < offset[vtx+1]; j++) {
166 if (!mark[adj[j]]) {
167 markAndEnqueue(q, mark, nUnmarkedVtx, cSize, adj[j]);
168 }
169 }
170 }
171
172 // update stats
173 if (nComponent == 1) {
174 maxComponentSize = cSize;
175 minComponentSize = cSize;
176 }
177 else {
178 if (cSize > maxComponentSize) maxComponentSize = cSize;
179 if (cSize < minComponentSize) minComponentSize = cSize;
180 }
181 }
182
183 // update stats
184 if (nComponent) avgComponentSize = double(nVtx) / double(nComponent);
185
186 delete [] mark;
187}
188
189
190} // namespace Zoltan2
191#endif
Defines the GraphModel interface.
Gathering definitions used in software development.
The user parameters, debug, timing and memory profiling output objects, and error checking methods.
GraphModel defines the interface required for graph models.
size_t getEdgeList(ArrayView< const gno_t > &edgeIds, ArrayView< const offset_t > &offsets, ArrayView< input_t > &wgts) const
Sets pointers to this process' edge (neighbor) global Ids, including off-process edges.
size_t getLocalNumVertices() const
Returns the number vertices on this process.
perProcessorComponentMetrics(const Adapter &ia, const Teuchos::Comm< int > &comm)
map_t::global_ordinal_type gno_t
Created by mbenlioglu on Aug 31, 2020.
@ REMOVE_SELF_EDGES
algorithm requires no self edges
@ BUILD_LOCAL_GRAPH
model represents graph within only one rank