00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef __deal2__compressed_simple_sparsity_pattern_h
00013 #define __deal2__compressed_simple_sparsity_pattern_h
00014
00015
00016 #include <deal.II/base/config.h>
00017 #include <deal.II/base/subscriptor.h>
00018 #include <deal.II/base/utilities.h>
00019 #include <deal.II/lac/exceptions.h>
00020 #include <deal.II/base/index_set.h>
00021
00022 #include <vector>
00023 #include <algorithm>
00024 #include <iostream>
00025
00026 DEAL_II_NAMESPACE_OPEN
00027
00028 template <typename number> class SparseMatrix;
00029
00030
00087 class CompressedSimpleSparsityPattern : public Subscriptor
00088 {
00089 public:
00096 typedef std::vector<unsigned int>::const_iterator row_iterator;
00097
00108 CompressedSimpleSparsityPattern ();
00109
00126 CompressedSimpleSparsityPattern (const CompressedSimpleSparsityPattern &);
00127
00139 CompressedSimpleSparsityPattern (const unsigned int m,
00140 const unsigned int n,
00141 const IndexSet & rowset = IndexSet());
00142
00147 CompressedSimpleSparsityPattern (const unsigned int n);
00148
00157 CompressedSimpleSparsityPattern & operator = (const CompressedSimpleSparsityPattern &);
00158
00173 void reinit (const unsigned int m,
00174 const unsigned int n,
00175 const IndexSet & rowset = IndexSet());
00176
00186 void compress ();
00187
00195 bool empty () const;
00196
00203 unsigned int max_entries_per_row () const;
00204
00210 void add (const unsigned int i,
00211 const unsigned int j);
00212
00219 template <typename ForwardIterator>
00220 void add_entries (const unsigned int row,
00221 ForwardIterator begin,
00222 ForwardIterator end,
00223 const bool indices_are_unique_and_sorted = false);
00224
00229 bool exists (const unsigned int i,
00230 const unsigned int j) const;
00231
00243 void symmetrize ();
00244
00254 void print (std::ostream &out) const;
00255
00279 void print_gnuplot (std::ostream &out) const;
00280
00286 unsigned int n_rows () const;
00287
00293 unsigned int n_cols () const;
00294
00303 unsigned int row_length (const unsigned int row) const;
00304
00310 unsigned int column_number (const unsigned int row,
00311 const unsigned int index) const;
00312
00319 row_iterator row_begin (const unsigned int row) const;
00320
00324 row_iterator row_end (const unsigned int row) const;
00333 unsigned int bandwidth () const;
00334
00339 unsigned int n_nonzero_elements () const;
00340
00348 const IndexSet & row_index_set () const;
00349
00365 static
00366 bool stores_only_added_elements ();
00367
00373 std::size_t memory_consumption () const;
00374
00375 private:
00380 unsigned int rows;
00381
00386 unsigned int cols;
00387
00392 IndexSet rowset;
00393
00394
00404 struct Line
00405 {
00406 public:
00412 std::vector<unsigned int> entries;
00413
00417 Line ();
00418
00423 void add (const unsigned int col_num);
00424
00429 template <typename ForwardIterator>
00430 void add_entries (ForwardIterator begin,
00431 ForwardIterator end,
00432 const bool indices_are_sorted);
00433
00437 std::size_t memory_consumption () const;
00438 };
00439
00440
00446 std::vector<Line> lines;
00447 };
00448
00450
00451
00452
00453 inline
00454 void
00455 CompressedSimpleSparsityPattern::Line::add (const unsigned int j)
00456 {
00457
00458
00459 if ( (entries.size()==0) || ( entries.back() < j) )
00460 {
00461 entries.push_back(j);
00462 return;
00463 }
00464
00465
00466
00467 std::vector<unsigned int>::iterator
00468 it = Utilities::lower_bound(entries.begin(),
00469 entries.end(),
00470 j);
00471
00472
00473
00474 if (*it == j)
00475 return;
00476
00477
00478
00479
00480 entries.insert(it, j);
00481 }
00482
00483
00484
00485 inline
00486 unsigned int
00487 CompressedSimpleSparsityPattern::n_rows () const
00488 {
00489 return rows;
00490 }
00491
00492
00493
00494 inline
00495 unsigned int
00496 CompressedSimpleSparsityPattern::n_cols () const
00497 {
00498 return cols;
00499 }
00500
00501
00502
00503 inline
00504 void
00505 CompressedSimpleSparsityPattern::add (const unsigned int i,
00506 const unsigned int j)
00507 {
00508 Assert (i<rows, ExcIndexRange(i, 0, rows));
00509 Assert (j<cols, ExcIndexRange(j, 0, cols));
00510
00511 if (rowset.size() > 0 && !rowset.is_element(i))
00512 return;
00513
00514 const unsigned int rowindex =
00515 rowset.size()==0 ? i : rowset.index_within_set(i);
00516 lines[rowindex].add (j);
00517 }
00518
00519
00520
00521 template <typename ForwardIterator>
00522 inline
00523 void
00524 CompressedSimpleSparsityPattern::add_entries (const unsigned int row,
00525 ForwardIterator begin,
00526 ForwardIterator end,
00527 const bool indices_are_sorted)
00528 {
00529 Assert (row < rows, ExcIndexRange (row, 0, rows));
00530
00531 if (rowset.size() > 0 && !rowset.is_element(row))
00532 return;
00533
00534 const unsigned int rowindex =
00535 rowset.size()==0 ? row : rowset.index_within_set(row);
00536 lines[rowindex].add_entries (begin, end, indices_are_sorted);
00537 }
00538
00539
00540
00541 inline
00542 CompressedSimpleSparsityPattern::Line::Line ()
00543 {}
00544
00545
00546
00547 inline
00548 unsigned int
00549 CompressedSimpleSparsityPattern::row_length (const unsigned int row) const
00550 {
00551 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00552 if (rowset.size() > 0 && !rowset.is_element(row))
00553 return 0;
00554
00555 const unsigned int rowindex =
00556 rowset.size()==0 ? row : rowset.index_within_set(row);
00557 return lines[rowindex].entries.size();
00558 }
00559
00560
00561
00562 inline
00563 unsigned int
00564 CompressedSimpleSparsityPattern::column_number (const unsigned int row,
00565 const unsigned int index) const
00566 {
00567 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00568 Assert( rowset.size() == 0 || rowset.is_element(row), ExcInternalError());
00569
00570 const unsigned int local_row = rowset.size() ? rowset.index_within_set(row) : row;
00571 Assert (index < lines[local_row].entries.size(),
00572 ExcIndexRange (index, 0, lines[local_row].entries.size()));
00573 return lines[local_row].entries[index];
00574 }
00575
00576
00577
00578 inline
00579 CompressedSimpleSparsityPattern::row_iterator
00580 CompressedSimpleSparsityPattern::row_begin (const unsigned int row) const
00581 {
00582 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00583 const unsigned int local_row = rowset.size() ? rowset.index_within_set(row) : row;
00584 return lines[local_row].entries.begin();
00585 }
00586
00587
00588
00589 inline
00590 CompressedSimpleSparsityPattern::row_iterator
00591 CompressedSimpleSparsityPattern::row_end (const unsigned int row) const
00592 {
00593 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00594 const unsigned int local_row = rowset.size() ? rowset.index_within_set(row) : row;
00595 return lines[local_row].entries.end();
00596 }
00597
00598
00599
00600 inline
00601 const IndexSet &
00602 CompressedSimpleSparsityPattern::row_index_set () const
00603 {
00604 return rowset;
00605 }
00606
00607
00608
00609 inline
00610 bool
00611 CompressedSimpleSparsityPattern::stores_only_added_elements ()
00612 {
00613 return true;
00614 }
00615
00616
00617 DEAL_II_NAMESPACE_CLOSE
00618
00619 #endif
00620