Reference documentation for deal.II version 8.1.0
compressed_simple_sparsity_pattern.h
1 // ---------------------------------------------------------------------
2 // @f$Id: compressed_simple_sparsity_pattern.h 30036 2013-07-18 16:55:32Z maier @f$
3 //
4 // Copyright (C) 2001 - 2013 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // The deal.II library is free software; you can use it, redistribute
9 // it, and/or modify it under the terms of the GNU Lesser General
10 // Public License as published by the Free Software Foundation; either
11 // version 2.1 of the License, or (at your option) any later version.
12 // The full text of the license can be found in the file LICENSE at
13 // the top level of the deal.II distribution.
14 //
15 // ---------------------------------------------------------------------
16 
17 #ifndef __deal2__compressed_simple_sparsity_pattern_h
18 #define __deal2__compressed_simple_sparsity_pattern_h
19 
20 
21 #include <deal.II/base/config.h>
22 #include <deal.II/base/subscriptor.h>
23 #include <deal.II/base/utilities.h>
24 #include <deal.II/lac/exceptions.h>
25 #include <deal.II/base/index_set.h>
26 
27 #include <vector>
28 #include <algorithm>
29 #include <iostream>
30 
32 
33 template <typename number> class SparseMatrix;
34 
35 
93 {
94 public:
99 
106  typedef std::vector<size_type>::const_iterator row_iterator;
107 
119 
137 
149  CompressedSimpleSparsityPattern (const size_type m,
150  const size_type n,
151  const IndexSet &rowset = IndexSet());
152 
157  CompressedSimpleSparsityPattern (const IndexSet &indexset);
158 
163  CompressedSimpleSparsityPattern (const size_type n);
164 
174 
189  void reinit (const size_type m,
190  const size_type n,
191  const IndexSet &rowset = IndexSet());
192 
202  void compress ();
203 
211  bool empty () const;
212 
219  size_type max_entries_per_row () const;
220 
226  void add (const size_type i,
227  const size_type j);
228 
235  template <typename ForwardIterator>
236  void add_entries (const size_type row,
237  ForwardIterator begin,
238  ForwardIterator end,
239  const bool indices_are_unique_and_sorted = false);
240 
245  bool exists (const size_type i,
246  const size_type j) const;
247 
259  void symmetrize ();
260 
270  void print (std::ostream &out) const;
271 
295  void print_gnuplot (std::ostream &out) const;
296 
302  size_type n_rows () const;
303 
309  size_type n_cols () const;
310 
319  size_type row_length (const size_type row) const;
320 
326  size_type column_number (const size_type row,
327  const size_type index) const;
328 
335  row_iterator row_begin (const size_type row) const;
336 
340  row_iterator row_end (const size_type row) const;
349  size_type bandwidth () const;
350 
355  size_type n_nonzero_elements () const;
356 
364  const IndexSet &row_index_set () const;
365 
381  static
383 
389  size_type memory_consumption () const;
390 
391 private:
396  size_type rows;
397 
402  size_type cols;
403 
409 
410 
420  struct Line
421  {
422  public:
428  std::vector<size_type> entries;
429 
433  Line ();
434 
439  void add (const size_type col_num);
440 
445  template <typename ForwardIterator>
446  void add_entries (ForwardIterator begin,
447  ForwardIterator end,
448  const bool indices_are_sorted);
449 
453  size_type memory_consumption () const;
454  };
455 
456 
462  std::vector<Line> lines;
463 };
464 
466 /*---------------------- Inline functions -----------------------------------*/
467 
468 
469 inline
470 void
472 {
473  // first check the last element (or if line
474  // is still empty)
475  if ( (entries.size()==0) || ( entries.back() < j) )
476  {
477  entries.push_back(j);
478  return;
479  }
480 
481  // do a binary search to find the place
482  // where to insert:
483  std::vector<size_type>::iterator
484  it = Utilities::lower_bound(entries.begin(),
485  entries.end(),
486  j);
487 
488  // If this entry is a duplicate, exit
489  // immediately
490  if (*it == j)
491  return;
492 
493  // Insert at the right place in the
494  // vector. Vector grows automatically to
495  // fit elements. Always doubles its size.
496  entries.insert(it, j);
497 }
498 
499 
500 
501 inline
504 {
505  return rows;
506 }
507 
508 
509 
510 inline
513 {
514  return cols;
515 }
516 
517 
518 
519 inline
520 void
522  const size_type j)
523 {
524  Assert (i<rows, ExcIndexRangeType<size_type>(i, 0, rows));
525  Assert (j<cols, ExcIndexRangeType<size_type>(j, 0, cols));
526 
527  if (rowset.size() > 0 && !rowset.is_element(i))
528  return;
529 
530  const size_type rowindex =
531  rowset.size()==0 ? i : rowset.index_within_set(i);
532  lines[rowindex].add (j);
533 }
534 
535 
536 
537 template <typename ForwardIterator>
538 inline
539 void
541  ForwardIterator begin,
542  ForwardIterator end,
543  const bool indices_are_sorted)
544 {
545  Assert (row < rows, ExcIndexRangeType<size_type> (row, 0, rows));
546 
547  if (rowset.size() > 0 && !rowset.is_element(row))
548  return;
549 
550  const size_type rowindex =
551  rowset.size()==0 ? row : rowset.index_within_set(row);
552  lines[rowindex].add_entries (begin, end, indices_are_sorted);
553 }
554 
555 
556 
557 inline
559 {}
560 
561 
562 
563 inline
566 {
567  Assert (row < n_rows(), ExcIndexRangeType<size_type> (row, 0, n_rows()));
568  if (rowset.size() > 0 && !rowset.is_element(row))
569  return 0;
570 
571  const size_type rowindex =
572  rowset.size()==0 ? row : rowset.index_within_set(row);
573  return lines[rowindex].entries.size();
574 }
575 
576 
577 
578 inline
581  const size_type index) const
582 {
583  Assert (row < n_rows(), ExcIndexRangeType<size_type> (row, 0, n_rows()));
584  Assert( rowset.size() == 0 || rowset.is_element(row), ExcInternalError());
585 
586  const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row;
587  Assert (index < lines[local_row].entries.size(),
588  ExcIndexRangeType<size_type> (index, 0, lines[local_row].entries.size()));
589  return lines[local_row].entries[index];
590 }
591 
592 
593 
594 inline
597 {
598  Assert (row < n_rows(), ExcIndexRangeType<size_type> (row, 0, n_rows()));
599  const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row;
600  return lines[local_row].entries.begin();
601 }
602 
603 
604 
605 inline
607 CompressedSimpleSparsityPattern::row_end (const size_type row) const
608 {
609  Assert (row < n_rows(), ExcIndexRangeType<size_type> (row, 0, n_rows()));
610  const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row;
611  return lines[local_row].entries.end();
612 }
613 
614 
615 
616 inline
617 const IndexSet &
619 {
620  return rowset;
621 }
622 
623 
624 
625 inline
626 bool
628 {
629  return true;
630 }
631 
632 
633 DEAL_II_NAMESPACE_CLOSE
634 
635 #endif
size_type memory_consumption() const
Iterator lower_bound(Iterator first, Iterator last, const T &val)
Definition: utilities.h:731
CompressedSimpleSparsityPattern & operator=(const CompressedSimpleSparsityPattern &)
types::global_dof_index index_within_set(const types::global_dof_index global_index) const
Definition: index_set.h:970
void add_entries(ForwardIterator begin, ForwardIterator end, const bool indices_are_sorted)
types::global_dof_index size() const
Definition: index_set.h:685
size_type max_entries_per_row() const
void print(std::ostream &out) const
void print_gnuplot(std::ostream &out) const
size_type n_nonzero_elements() const
unsigned int global_dof_index
Definition: types.h:100
#define Assert(cond, exc)
Definition: exceptions.h:299
void add(const size_type i, const size_type j)
row_iterator row_begin(const size_type row) const
void add_entries(const size_type row, ForwardIterator begin, ForwardIterator end, const bool indices_are_unique_and_sorted=false)
bool exists(const size_type i, const size_type j) const
size_type row_length(const size_type row) const
row_iterator row_end(const size_type row) const
size_type column_number(const size_type row, const size_type index) const
void reinit(const size_type m, const size_type n, const IndexSet &rowset=IndexSet())
size_type bandwidth() const
::ExceptionBase & ExcInternalError()
bool is_element(const types::global_dof_index index) const
Definition: index_set.h:811
std::vector< size_type >::const_iterator row_iterator