libMesh::SparsityPattern Namespace Reference

Classes
class	Graph
class	NonlocalGraph
class	Build
Typedefs
typedef std::vector < dof_id_type, Threads::scalable_allocator < dof_id_type > >	Row
Functions
template<typename BidirectionalIterator >
static void	sort_row (const BidirectionalIterator begin, BidirectionalIterator middle, const BidirectionalIterator end)
void	_dummy_function (void)

---

Detailed Description

This defines the sparsity pattern, or graph, of a sparse matrix. The format is quite simple -- the global indices of the nonzero entries in each row are packed into a vector. The global indices (i,j) of the nth nonzero entry of row i are given by j = sparsity_pattern[i][n];

---

Typedef Documentation

typedef std::vector<dof_id_type, Threads::scalable_allocator<dof_id_type> > libMesh::SparsityPattern::Row

Definition at line 48 of file sparsity_pattern.h.

---

Function Documentation

void libMesh::SparsityPattern::_dummy_function

(

void

)

Dummy function that does nothing but can be used to prohibit compiler optimization in some situations where some compilers have optimization bugs.

Definition at line 2146 of file dof_map.C.

Referenced by sort_row().

{
}

template<typename BidirectionalIterator >

void libMesh::SparsityPattern::sort_row	(	const BidirectionalIterator	begin,
		BidirectionalIterator	middle,
		const BidirectionalIterator	end
	)			[inline, static]

Splices the two sorted ranges [begin,middle) and [middle,end) into one sorted range [begin,end). This method is much like std::inplace_merge except it assumes the intersection of the two sorted ranges is empty and that any element in each range occurs only once in that range. Additionally, this sort occurs in-place, while std::inplace_merge may use a temporary buffer.

Definition at line 147 of file sparsity_pattern.h.

References _dummy_function(), and swap().

Referenced by libMesh::SparsityPattern::Build::operator()().

{
  if ((begin == middle) || (middle == end)) return;

  libmesh_assert_greater (std::distance (begin,  middle), 0);
  libmesh_assert_greater (std::distance (middle, end), 0);
  libmesh_assert (std::unique (begin,  middle) == middle);
  libmesh_assert (std::unique (middle, end) == end);

  while (middle != end)
    {
      BidirectionalIterator
        b = middle,
        a = b-1;

      // Bubble-sort the middle value downward
      while (!(*a < *b)) // *a & *b are less-than comparable, so use <
        {
          std::swap (*a, *b);

#if defined(__GNUC__) && (__GNUC__ < 4) && !defined(__INTEL_COMPILER)
          /* Prohibit optimization at this point since gcc 3.3.5 seems
             to have a bug.  */
          SparsityPattern::_dummy_function();
#endif

          if (a == begin) break;

          b=a;
          --a;
        }

      ++middle;
    }

  // Assure the algorithm worked if we are in DEBUG mode
#ifdef DEBUG
  {
    // SGI STL extension!
    // libmesh_assert (std::is_sorted(begin,end));

    BidirectionalIterator
      prev  = begin,
      first = begin;

    for (++first; first != end; prev=first, ++first)
      if (*first < *prev)
        libmesh_assert(false);
  }
#endif

  // Make sure the two ranges did not contain any common elements
  libmesh_assert (std::unique (begin, end) == end);
}