From eeb75f11d70d1f106c6af4592003db7866241301 Mon Sep 17 00:00:00 2001 From: bangerth Date: Fri, 25 Sep 2009 12:56:47 +0000 Subject: [PATCH] Fix a problem where we refused to number graphs that have disconnected components. git-svn-id: https://svn.dealii.org/trunk@19546 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/doc/news/changes.h | 9 + deal.II/lac/include/lac/sparsity_tools.h | 22 +- deal.II/lac/source/sparsity_tools.cc | 209 ++- tests/bits/gerold_2/cmp/generic | 1515 +++++++++++++++++++++- tests/lac/sparsity_tools_01.cc | 59 + tests/lac/sparsity_tools_01/cmp/generic | 5 + 6 files changed, 1748 insertions(+), 71 deletions(-) create mode 100644 tests/lac/sparsity_tools_01.cc create mode 100644 tests/lac/sparsity_tools_01/cmp/generic diff --git a/deal.II/doc/news/changes.h b/deal.II/doc/news/changes.h index 80021ecc9b..d2e07c4bea 100644 --- a/deal.II/doc/news/changes.h +++ b/deal.II/doc/news/changes.h @@ -341,6 +341,15 @@ inconvenience this causes.
    +
  1. +

    + Fixed: SparsityTools::reorder_Cuthill_McKee would produce an error if the + input graph had disconnected components. This is now fixed. +

    +
    + (WB 2009/09/25) +
  2. +
  3. Fixed: When using the TrilinosWrappers::MPI::Vector::reinit() function with a parallel diff --git a/deal.II/lac/include/lac/sparsity_tools.h b/deal.II/lac/include/lac/sparsity_tools.h index 84fcf6b009..70f0a7ea46 100644 --- a/deal.II/lac/include/lac/sparsity_tools.h +++ b/deal.II/lac/include/lac/sparsity_tools.h @@ -2,7 +2,7 @@ // $Id$ // Version: $Name$ // -// Copyright (C) 2008 by the deal.II authors +// Copyright (C) 2008, 2009 by the deal.II authors // // This file is subject to QPL and may not be distributed // without copyright and license information. Please refer @@ -166,12 +166,30 @@ namespace SparsityTools * equal coordination numbers. The * renumbering algorithms will therefore * not give optimal results. + * + * If the graph has two or more + * unconnected components and if no + * starting indices are given, the + * algorithm will number each + * component + * consecutively. However, this + * requires the determination of a + * starting index for each + * component; as a consequence, the + * algorithm will produce an + * exception if starting indices + * are given, taking the latter as + * an indication that the caller of + * the function would like to + * override the part of the + * algorithm that chooses starting + * indices. */ void reorder_Cuthill_McKee (const SparsityPattern &sparsity, std::vector &new_indices, const std::vector &starting_indices = std::vector()); - + /** * Exception */ diff --git a/deal.II/lac/source/sparsity_tools.cc b/deal.II/lac/source/sparsity_tools.cc index 2dab62ddf0..c65686a150 100644 --- a/deal.II/lac/source/sparsity_tools.cc +++ b/deal.II/lac/source/sparsity_tools.cc @@ -42,7 +42,7 @@ // But that appears to not be happening, and so we have to do the // following hack where we just forward declare everything ourselves :-( -extern "C" +extern "C" { // the following is from Metis-4.0/Lib/struct.h: typedef int idxtype; @@ -54,7 +54,7 @@ extern "C" void METIS_PartGraphRecursive(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, - int *, int *, int *, int *, idxtype *); + int *, int *, int *, int *, idxtype *); } #endif @@ -63,7 +63,7 @@ DEAL_II_NAMESPACE_OPEN namespace SparsityTools { - + void partition (const SparsityPattern &sparsity_pattern, const unsigned int n_partitions, std::vector &partition_indices) @@ -129,7 +129,7 @@ namespace SparsityTools NULL, NULL, &wgtflag, &numflag, &nparts, &options[0], &dummy, &int_partition_indices[0]); - + // Otherwise use kway else METIS_PartGraphKway(&n, &int_rowstart[0], &int_colnums[0], @@ -146,6 +146,83 @@ namespace SparsityTools } + namespace internal + { + /** + * Given a connectivity graph and + * a list of indices (where + * invalid_unsigned_int indicates + * that a node has not been + * numbered yet), pick a valid + * starting index among the + * as-yet unnumbered one. + */ + unsigned int + find_unnumbered_starting_index (const SparsityPattern &sparsity, + const std::vector &new_indices) + { + { + unsigned int starting_point = numbers::invalid_unsigned_int; + unsigned int min_coordination = sparsity.n_rows(); + for (unsigned int row=0; row=sparsity.n_rows())) last_round_dofs[i] = numbers::invalid_unsigned_int; - + std::remove_if (last_round_dofs.begin(), last_round_dofs.end(), std::bind2nd(std::equal_to(), numbers::invalid_unsigned_int)); - + // now if no valid points remain: // find dof with lowest coordination // number if (last_round_dofs.size() == 0) - { - unsigned int starting_point = numbers::invalid_unsigned_int; - unsigned int min_coordination = sparsity.n_rows(); - for (unsigned int row=0; row 0, + ExcMessage ("The input graph appears to have more than one " + "component, but as stated in the documentation " + "we only want to reorder such graphs if no " + "starting indices are given. The function was " + "called with starting indices, however.")) + + next_round_dofs + .push_back (internal::find_unnumbered_starting_index (sparsity, + new_indices)); + } + // store for each coordination // number the dofs with these // coordination number std::multimap dofs_by_coordination; - + // find coordination number for // each of these dofs for (std::vector::iterator s=next_round_dofs.begin(); - s!=next_round_dofs.end(); ++s) + s!=next_round_dofs.end(); ++s) { unsigned int coordination = 0; for (unsigned int j=sparsity.get_rowstart_indices()[*s]; @@ -301,12 +380,12 @@ namespace SparsityTools const std::pair new_entry (coordination, *s); dofs_by_coordination.insert (new_entry); } - + // assign new DoF numbers to // the elements of the present // front: std::multimap::iterator i; - for (i = dofs_by_coordination.begin(); i!=dofs_by_coordination.end(); ++i) + for (i = dofs_by_coordination.begin(); i!=dofs_by_coordination.end(); ++i) new_indices[i->second] = next_free_number++; // after that: copy this round's @@ -335,9 +414,7 @@ namespace SparsityTools new_indices.end()) && (next_free_number == sparsity.n_rows()), - ExcMessage("Some rows have not been renumbered. Maybe " - "the connectivity graph has two or more disconnected " - "subgraphs?")); + ExcInternalError()); } } diff --git a/tests/bits/gerold_2/cmp/generic b/tests/bits/gerold_2/cmp/generic index 8274245d55..8468a64a91 100644 --- a/tests/bits/gerold_2/cmp/generic +++ b/tests/bits/gerold_2/cmp/generic @@ -1,4 +1,1513 @@ -DEAL::Solving problem in 3 space dimensions. -DEAL::read ucd data file -DEAL::ucd data file readin exe +DEAL::0 +DEAL::1 +DEAL::4 +DEAL::10 +DEAL::20 +DEAL::35 +DEAL::2 +DEAL::7 +DEAL::13 +DEAL::23 +DEAL::38 +DEAL::56 +DEAL::5 +DEAL::14 +DEAL::24 +DEAL::39 +DEAL::61 +DEAL::82 +DEAL::11 +DEAL::25 +DEAL::40 +DEAL::62 +DEAL::87 +DEAL::112 +DEAL::21 +DEAL::41 +DEAL::63 +DEAL::88 +DEAL::117 +DEAL::145 +DEAL::37 +DEAL::64 +DEAL::89 +DEAL::118 +DEAL::150 +DEAL::181 +DEAL::57 +DEAL::90 +DEAL::119 +DEAL::151 +DEAL::184 +DEAL::217 +DEAL::83 +DEAL::120 +DEAL::152 +DEAL::185 +DEAL::220 +DEAL::252 +DEAL::113 +DEAL::153 +DEAL::186 +DEAL::221 +DEAL::257 +DEAL::287 +DEAL::146 +DEAL::187 +DEAL::222 +DEAL::258 +DEAL::292 +DEAL::320 +DEAL::182 +DEAL::223 +DEAL::259 +DEAL::293 +DEAL::325 +DEAL::350 +DEAL::216 +DEAL::253 +DEAL::288 +DEAL::321 +DEAL::351 +DEAL::376 +DEAL::3 +DEAL::8 +DEAL::15 +DEAL::26 +DEAL::42 +DEAL::58 +DEAL::9 +DEAL::19 +DEAL::32 +DEAL::50 +DEAL::72 +DEAL::91 +DEAL::16 +DEAL::33 +DEAL::51 +DEAL::73 +DEAL::99 +DEAL::121 +DEAL::27 +DEAL::52 +DEAL::74 +DEAL::100 +DEAL::130 +DEAL::154 +DEAL::43 +DEAL::75 +DEAL::101 +DEAL::131 +DEAL::164 +DEAL::188 +DEAL::65 +DEAL::102 +DEAL::132 +DEAL::165 +DEAL::200 +DEAL::224 +DEAL::92 +DEAL::133 +DEAL::166 +DEAL::201 +DEAL::236 +DEAL::260 +DEAL::122 +DEAL::167 +DEAL::202 +DEAL::237 +DEAL::271 +DEAL::294 +DEAL::155 +DEAL::203 +DEAL::238 +DEAL::272 +DEAL::305 +DEAL::326 +DEAL::189 +DEAL::239 +DEAL::273 +DEAL::306 +DEAL::337 +DEAL::355 +DEAL::225 +DEAL::274 +DEAL::307 +DEAL::338 +DEAL::366 +DEAL::379 +DEAL::254 +DEAL::295 +DEAL::327 +DEAL::356 +DEAL::380 +DEAL::397 +DEAL::6 +DEAL::17 +DEAL::28 +DEAL::44 +DEAL::66 +DEAL::84 +DEAL::18 +DEAL::34 +DEAL::53 +DEAL::76 +DEAL::103 +DEAL::123 +DEAL::29 +DEAL::54 +DEAL::77 +DEAL::104 +DEAL::134 +DEAL::156 +DEAL::45 +DEAL::78 +DEAL::105 +DEAL::135 +DEAL::168 +DEAL::190 +DEAL::67 +DEAL::106 +DEAL::136 +DEAL::169 +DEAL::204 +DEAL::226 +DEAL::93 +DEAL::137 +DEAL::170 +DEAL::205 +DEAL::240 +DEAL::261 +DEAL::124 +DEAL::171 +DEAL::206 +DEAL::241 +DEAL::275 +DEAL::296 +DEAL::157 +DEAL::207 +DEAL::242 +DEAL::276 +DEAL::308 +DEAL::328 +DEAL::191 +DEAL::243 +DEAL::277 +DEAL::309 +DEAL::339 +DEAL::357 +DEAL::227 +DEAL::278 +DEAL::310 +DEAL::340 +DEAL::367 +DEAL::381 +DEAL::262 +DEAL::311 +DEAL::341 +DEAL::368 +DEAL::391 +DEAL::400 +DEAL::289 +DEAL::329 +DEAL::358 +DEAL::382 +DEAL::401 +DEAL::412 +DEAL::12 +DEAL::30 +DEAL::46 +DEAL::68 +DEAL::94 +DEAL::114 +DEAL::31 +DEAL::55 +DEAL::79 +DEAL::107 +DEAL::138 +DEAL::158 +DEAL::47 +DEAL::80 +DEAL::108 +DEAL::139 +DEAL::172 +DEAL::192 +DEAL::69 +DEAL::109 +DEAL::140 +DEAL::173 +DEAL::208 +DEAL::228 +DEAL::95 +DEAL::141 +DEAL::174 +DEAL::209 +DEAL::244 +DEAL::263 +DEAL::125 +DEAL::175 +DEAL::210 +DEAL::245 +DEAL::279 +DEAL::297 +DEAL::159 +DEAL::211 +DEAL::246 +DEAL::280 +DEAL::312 +DEAL::330 +DEAL::193 +DEAL::247 +DEAL::281 +DEAL::313 +DEAL::342 +DEAL::359 +DEAL::229 +DEAL::282 +DEAL::314 +DEAL::343 +DEAL::369 +DEAL::383 +DEAL::264 +DEAL::315 +DEAL::344 +DEAL::370 +DEAL::392 +DEAL::402 +DEAL::298 +DEAL::345 +DEAL::371 +DEAL::393 +DEAL::409 +DEAL::415 +DEAL::322 +DEAL::360 +DEAL::384 +DEAL::403 +DEAL::416 +DEAL::422 +DEAL::22 +DEAL::48 +DEAL::70 +DEAL::96 +DEAL::126 +DEAL::147 +DEAL::49 +DEAL::81 +DEAL::110 +DEAL::142 +DEAL::176 +DEAL::194 +DEAL::71 +DEAL::111 +DEAL::143 +DEAL::177 +DEAL::212 +DEAL::230 +DEAL::97 +DEAL::144 +DEAL::178 +DEAL::213 +DEAL::248 +DEAL::265 +DEAL::127 +DEAL::179 +DEAL::214 +DEAL::249 +DEAL::283 +DEAL::299 +DEAL::160 +DEAL::215 +DEAL::250 +DEAL::284 +DEAL::316 +DEAL::331 +DEAL::195 +DEAL::251 +DEAL::285 +DEAL::317 +DEAL::346 +DEAL::361 +DEAL::231 +DEAL::286 +DEAL::318 +DEAL::347 +DEAL::372 +DEAL::385 +DEAL::266 +DEAL::319 +DEAL::348 +DEAL::373 +DEAL::394 +DEAL::404 +DEAL::300 +DEAL::349 +DEAL::374 +DEAL::395 +DEAL::410 +DEAL::417 +DEAL::332 +DEAL::375 +DEAL::396 +DEAL::411 +DEAL::421 +DEAL::425 +DEAL::352 +DEAL::386 +DEAL::405 +DEAL::418 +DEAL::426 +DEAL::428 +DEAL::36 +DEAL::59 +DEAL::85 +DEAL::115 +DEAL::148 +DEAL::180 +DEAL::60 +DEAL::98 +DEAL::128 +DEAL::161 +DEAL::196 +DEAL::218 +DEAL::86 +DEAL::129 +DEAL::162 +DEAL::197 +DEAL::232 +DEAL::255 +DEAL::116 +DEAL::163 +DEAL::198 +DEAL::233 +DEAL::267 +DEAL::290 +DEAL::149 +DEAL::199 +DEAL::234 +DEAL::268 +DEAL::301 +DEAL::323 +DEAL::183 +DEAL::235 +DEAL::269 +DEAL::302 +DEAL::333 +DEAL::353 +DEAL::219 +DEAL::270 +DEAL::303 +DEAL::334 +DEAL::362 +DEAL::378 +DEAL::256 +DEAL::304 +DEAL::335 +DEAL::363 +DEAL::387 +DEAL::398 +DEAL::291 +DEAL::336 +DEAL::364 +DEAL::388 +DEAL::406 +DEAL::413 +DEAL::324 +DEAL::365 +DEAL::389 +DEAL::407 +DEAL::419 +DEAL::423 +DEAL::354 +DEAL::390 +DEAL::408 +DEAL::420 +DEAL::427 +DEAL::429 +DEAL::377 +DEAL::399 +DEAL::414 +DEAL::424 +DEAL::430 +DEAL::431 +DEAL::432 +DEAL::433 +DEAL::436 +DEAL::442 +DEAL::452 +DEAL::467 +DEAL::434 +DEAL::439 +DEAL::445 +DEAL::455 +DEAL::470 +DEAL::488 +DEAL::437 +DEAL::446 +DEAL::456 +DEAL::471 +DEAL::493 +DEAL::514 +DEAL::443 +DEAL::457 +DEAL::472 +DEAL::494 +DEAL::519 +DEAL::544 +DEAL::453 +DEAL::473 +DEAL::495 +DEAL::520 +DEAL::549 +DEAL::577 +DEAL::469 +DEAL::496 +DEAL::521 +DEAL::550 +DEAL::582 +DEAL::613 +DEAL::489 +DEAL::522 +DEAL::551 +DEAL::583 +DEAL::616 +DEAL::649 +DEAL::515 +DEAL::552 +DEAL::584 +DEAL::617 +DEAL::652 +DEAL::684 +DEAL::545 +DEAL::585 +DEAL::618 +DEAL::653 +DEAL::689 +DEAL::719 +DEAL::578 +DEAL::619 +DEAL::654 +DEAL::690 +DEAL::724 +DEAL::752 +DEAL::614 +DEAL::655 +DEAL::691 +DEAL::725 +DEAL::757 +DEAL::782 +DEAL::648 +DEAL::685 +DEAL::720 +DEAL::753 +DEAL::783 +DEAL::808 +DEAL::435 +DEAL::440 +DEAL::447 +DEAL::458 +DEAL::474 +DEAL::490 +DEAL::441 +DEAL::451 +DEAL::464 +DEAL::482 +DEAL::504 +DEAL::523 +DEAL::448 +DEAL::465 +DEAL::483 +DEAL::505 +DEAL::531 +DEAL::553 +DEAL::459 +DEAL::484 +DEAL::506 +DEAL::532 +DEAL::562 +DEAL::586 +DEAL::475 +DEAL::507 +DEAL::533 +DEAL::563 +DEAL::596 +DEAL::620 +DEAL::497 +DEAL::534 +DEAL::564 +DEAL::597 +DEAL::632 +DEAL::656 +DEAL::524 +DEAL::565 +DEAL::598 +DEAL::633 +DEAL::668 +DEAL::692 +DEAL::554 +DEAL::599 +DEAL::634 +DEAL::669 +DEAL::703 +DEAL::726 +DEAL::587 +DEAL::635 +DEAL::670 +DEAL::704 +DEAL::737 +DEAL::758 +DEAL::621 +DEAL::671 +DEAL::705 +DEAL::738 +DEAL::769 +DEAL::787 +DEAL::657 +DEAL::706 +DEAL::739 +DEAL::770 +DEAL::798 +DEAL::811 +DEAL::686 +DEAL::727 +DEAL::759 +DEAL::788 +DEAL::812 +DEAL::829 +DEAL::438 +DEAL::449 +DEAL::460 +DEAL::476 +DEAL::498 +DEAL::516 +DEAL::450 +DEAL::466 +DEAL::485 +DEAL::508 +DEAL::535 +DEAL::555 +DEAL::461 +DEAL::486 +DEAL::509 +DEAL::536 +DEAL::566 +DEAL::588 +DEAL::477 +DEAL::510 +DEAL::537 +DEAL::567 +DEAL::600 +DEAL::622 +DEAL::499 +DEAL::538 +DEAL::568 +DEAL::601 +DEAL::636 +DEAL::658 +DEAL::525 +DEAL::569 +DEAL::602 +DEAL::637 +DEAL::672 +DEAL::693 +DEAL::556 +DEAL::603 +DEAL::638 +DEAL::673 +DEAL::707 +DEAL::728 +DEAL::589 +DEAL::639 +DEAL::674 +DEAL::708 +DEAL::740 +DEAL::760 +DEAL::623 +DEAL::675 +DEAL::709 +DEAL::741 +DEAL::771 +DEAL::789 +DEAL::659 +DEAL::710 +DEAL::742 +DEAL::772 +DEAL::799 +DEAL::813 +DEAL::694 +DEAL::743 +DEAL::773 +DEAL::800 +DEAL::823 +DEAL::832 +DEAL::721 +DEAL::761 +DEAL::790 +DEAL::814 +DEAL::833 +DEAL::844 +DEAL::444 +DEAL::462 +DEAL::478 +DEAL::500 +DEAL::526 +DEAL::546 +DEAL::463 +DEAL::487 +DEAL::511 +DEAL::539 +DEAL::570 +DEAL::590 +DEAL::479 +DEAL::512 +DEAL::540 +DEAL::571 +DEAL::604 +DEAL::624 +DEAL::501 +DEAL::541 +DEAL::572 +DEAL::605 +DEAL::640 +DEAL::660 +DEAL::527 +DEAL::573 +DEAL::606 +DEAL::641 +DEAL::676 +DEAL::695 +DEAL::557 +DEAL::607 +DEAL::642 +DEAL::677 +DEAL::711 +DEAL::729 +DEAL::591 +DEAL::643 +DEAL::678 +DEAL::712 +DEAL::744 +DEAL::762 +DEAL::625 +DEAL::679 +DEAL::713 +DEAL::745 +DEAL::774 +DEAL::791 +DEAL::661 +DEAL::714 +DEAL::746 +DEAL::775 +DEAL::801 +DEAL::815 +DEAL::696 +DEAL::747 +DEAL::776 +DEAL::802 +DEAL::824 +DEAL::834 +DEAL::730 +DEAL::777 +DEAL::803 +DEAL::825 +DEAL::841 +DEAL::847 +DEAL::754 +DEAL::792 +DEAL::816 +DEAL::835 +DEAL::848 +DEAL::854 +DEAL::454 +DEAL::480 +DEAL::502 +DEAL::528 +DEAL::558 +DEAL::579 +DEAL::481 +DEAL::513 +DEAL::542 +DEAL::574 +DEAL::608 +DEAL::626 +DEAL::503 +DEAL::543 +DEAL::575 +DEAL::609 +DEAL::644 +DEAL::662 +DEAL::529 +DEAL::576 +DEAL::610 +DEAL::645 +DEAL::680 +DEAL::697 +DEAL::559 +DEAL::611 +DEAL::646 +DEAL::681 +DEAL::715 +DEAL::731 +DEAL::592 +DEAL::647 +DEAL::682 +DEAL::716 +DEAL::748 +DEAL::763 +DEAL::627 +DEAL::683 +DEAL::717 +DEAL::749 +DEAL::778 +DEAL::793 +DEAL::663 +DEAL::718 +DEAL::750 +DEAL::779 +DEAL::804 +DEAL::817 +DEAL::698 +DEAL::751 +DEAL::780 +DEAL::805 +DEAL::826 +DEAL::836 +DEAL::732 +DEAL::781 +DEAL::806 +DEAL::827 +DEAL::842 +DEAL::849 +DEAL::764 +DEAL::807 +DEAL::828 +DEAL::843 +DEAL::853 +DEAL::857 +DEAL::784 +DEAL::818 +DEAL::837 +DEAL::850 +DEAL::858 +DEAL::860 +DEAL::468 +DEAL::491 +DEAL::517 +DEAL::547 +DEAL::580 +DEAL::612 +DEAL::492 +DEAL::530 +DEAL::560 +DEAL::593 +DEAL::628 +DEAL::650 +DEAL::518 +DEAL::561 +DEAL::594 +DEAL::629 +DEAL::664 +DEAL::687 +DEAL::548 +DEAL::595 +DEAL::630 +DEAL::665 +DEAL::699 +DEAL::722 +DEAL::581 +DEAL::631 +DEAL::666 +DEAL::700 +DEAL::733 +DEAL::755 +DEAL::615 +DEAL::667 +DEAL::701 +DEAL::734 +DEAL::765 +DEAL::785 +DEAL::651 +DEAL::702 +DEAL::735 +DEAL::766 +DEAL::794 +DEAL::810 +DEAL::688 +DEAL::736 +DEAL::767 +DEAL::795 +DEAL::819 +DEAL::830 +DEAL::723 +DEAL::768 +DEAL::796 +DEAL::820 +DEAL::838 +DEAL::845 +DEAL::756 +DEAL::797 +DEAL::821 +DEAL::839 +DEAL::851 +DEAL::855 +DEAL::786 +DEAL::822 +DEAL::840 +DEAL::852 +DEAL::859 +DEAL::861 +DEAL::809 +DEAL::831 +DEAL::846 +DEAL::856 +DEAL::862 +DEAL::863 +DEAL::864 +DEAL::865 +DEAL::868 +DEAL::874 +DEAL::884 +DEAL::899 +DEAL::866 +DEAL::871 +DEAL::877 +DEAL::887 +DEAL::902 +DEAL::920 +DEAL::869 +DEAL::878 +DEAL::888 +DEAL::903 +DEAL::926 +DEAL::945 +DEAL::875 +DEAL::889 +DEAL::904 +DEAL::927 +DEAL::951 +DEAL::972 +DEAL::885 +DEAL::905 +DEAL::928 +DEAL::952 +DEAL::978 +DEAL::999 +DEAL::900 +DEAL::921 +DEAL::946 +DEAL::973 +DEAL::1000 +DEAL::1024 +DEAL::867 +DEAL::872 +DEAL::879 +DEAL::890 +DEAL::906 +DEAL::922 +DEAL::873 +DEAL::883 +DEAL::896 +DEAL::914 +DEAL::935 +DEAL::953 +DEAL::880 +DEAL::897 +DEAL::915 +DEAL::936 +DEAL::960 +DEAL::979 +DEAL::891 +DEAL::916 +DEAL::937 +DEAL::961 +DEAL::987 +DEAL::1005 +DEAL::907 +DEAL::938 +DEAL::962 +DEAL::988 +DEAL::1014 +DEAL::1027 +DEAL::923 +DEAL::954 +DEAL::980 +DEAL::1006 +DEAL::1028 +DEAL::1045 +DEAL::870 +DEAL::881 +DEAL::892 +DEAL::908 +DEAL::929 +DEAL::947 +DEAL::882 +DEAL::898 +DEAL::917 +DEAL::939 +DEAL::963 +DEAL::981 +DEAL::893 +DEAL::918 +DEAL::940 +DEAL::964 +DEAL::989 +DEAL::1007 +DEAL::909 +DEAL::941 +DEAL::965 +DEAL::990 +DEAL::1015 +DEAL::1029 +DEAL::930 +DEAL::966 +DEAL::991 +DEAL::1016 +DEAL::1039 +DEAL::1048 +DEAL::948 +DEAL::982 +DEAL::1008 +DEAL::1030 +DEAL::1049 +DEAL::1060 +DEAL::876 +DEAL::894 +DEAL::910 +DEAL::931 +DEAL::955 +DEAL::974 +DEAL::895 +DEAL::919 +DEAL::942 +DEAL::967 +DEAL::992 +DEAL::1009 +DEAL::911 +DEAL::943 +DEAL::968 +DEAL::993 +DEAL::1017 +DEAL::1031 +DEAL::932 +DEAL::969 +DEAL::994 +DEAL::1018 +DEAL::1040 +DEAL::1050 +DEAL::956 +DEAL::995 +DEAL::1019 +DEAL::1041 +DEAL::1057 +DEAL::1063 +DEAL::975 +DEAL::1010 +DEAL::1032 +DEAL::1051 +DEAL::1064 +DEAL::1070 +DEAL::886 +DEAL::912 +DEAL::933 +DEAL::957 +DEAL::983 +DEAL::1001 +DEAL::913 +DEAL::944 +DEAL::970 +DEAL::996 +DEAL::1020 +DEAL::1033 +DEAL::934 +DEAL::971 +DEAL::997 +DEAL::1021 +DEAL::1042 +DEAL::1052 +DEAL::958 +DEAL::998 +DEAL::1022 +DEAL::1043 +DEAL::1058 +DEAL::1065 +DEAL::984 +DEAL::1023 +DEAL::1044 +DEAL::1059 +DEAL::1069 +DEAL::1073 +DEAL::1002 +DEAL::1034 +DEAL::1053 +DEAL::1066 +DEAL::1074 +DEAL::1076 +DEAL::901 +DEAL::924 +DEAL::949 +DEAL::976 +DEAL::1003 +DEAL::1025 +DEAL::925 +DEAL::959 +DEAL::985 +DEAL::1011 +DEAL::1035 +DEAL::1046 +DEAL::950 +DEAL::986 +DEAL::1012 +DEAL::1036 +DEAL::1054 +DEAL::1061 +DEAL::977 +DEAL::1013 +DEAL::1037 +DEAL::1055 +DEAL::1067 +DEAL::1071 +DEAL::1004 +DEAL::1038 +DEAL::1056 +DEAL::1068 +DEAL::1075 +DEAL::1077 +DEAL::1026 +DEAL::1047 +DEAL::1062 +DEAL::1072 +DEAL::1078 +DEAL::1079 +DEAL::1080 +DEAL::1081 +DEAL::1084 +DEAL::1090 +DEAL::1100 +DEAL::1115 +DEAL::1082 +DEAL::1087 +DEAL::1093 +DEAL::1103 +DEAL::1118 +DEAL::1136 +DEAL::1085 +DEAL::1094 +DEAL::1104 +DEAL::1119 +DEAL::1141 +DEAL::1162 +DEAL::1091 +DEAL::1105 +DEAL::1120 +DEAL::1142 +DEAL::1167 +DEAL::1192 +DEAL::1101 +DEAL::1121 +DEAL::1143 +DEAL::1168 +DEAL::1197 +DEAL::1225 +DEAL::1116 +DEAL::1137 +DEAL::1163 +DEAL::1193 +DEAL::1226 +DEAL::1260 +DEAL::1083 +DEAL::1088 +DEAL::1095 +DEAL::1106 +DEAL::1122 +DEAL::1138 +DEAL::1089 +DEAL::1099 +DEAL::1112 +DEAL::1130 +DEAL::1152 +DEAL::1169 +DEAL::1096 +DEAL::1113 +DEAL::1131 +DEAL::1153 +DEAL::1179 +DEAL::1198 +DEAL::1107 +DEAL::1132 +DEAL::1154 +DEAL::1180 +DEAL::1210 +DEAL::1230 +DEAL::1123 +DEAL::1155 +DEAL::1181 +DEAL::1211 +DEAL::1244 +DEAL::1264 +DEAL::1139 +DEAL::1170 +DEAL::1199 +DEAL::1231 +DEAL::1265 +DEAL::1297 +DEAL::1086 +DEAL::1097 +DEAL::1108 +DEAL::1124 +DEAL::1144 +DEAL::1164 +DEAL::1098 +DEAL::1114 +DEAL::1133 +DEAL::1156 +DEAL::1182 +DEAL::1200 +DEAL::1109 +DEAL::1134 +DEAL::1157 +DEAL::1183 +DEAL::1212 +DEAL::1232 +DEAL::1125 +DEAL::1158 +DEAL::1184 +DEAL::1213 +DEAL::1245 +DEAL::1266 +DEAL::1145 +DEAL::1185 +DEAL::1214 +DEAL::1246 +DEAL::1280 +DEAL::1300 +DEAL::1165 +DEAL::1201 +DEAL::1233 +DEAL::1267 +DEAL::1301 +DEAL::1332 +DEAL::1092 +DEAL::1110 +DEAL::1126 +DEAL::1146 +DEAL::1171 +DEAL::1194 +DEAL::1111 +DEAL::1135 +DEAL::1159 +DEAL::1186 +DEAL::1215 +DEAL::1234 +DEAL::1127 +DEAL::1160 +DEAL::1187 +DEAL::1216 +DEAL::1247 +DEAL::1268 +DEAL::1147 +DEAL::1188 +DEAL::1217 +DEAL::1248 +DEAL::1281 +DEAL::1302 +DEAL::1172 +DEAL::1218 +DEAL::1249 +DEAL::1282 +DEAL::1316 +DEAL::1337 +DEAL::1195 +DEAL::1235 +DEAL::1269 +DEAL::1303 +DEAL::1338 +DEAL::1367 +DEAL::1102 +DEAL::1128 +DEAL::1148 +DEAL::1173 +DEAL::1202 +DEAL::1227 +DEAL::1129 +DEAL::1161 +DEAL::1189 +DEAL::1219 +DEAL::1250 +DEAL::1270 +DEAL::1149 +DEAL::1190 +DEAL::1220 +DEAL::1251 +DEAL::1283 +DEAL::1304 +DEAL::1174 +DEAL::1221 +DEAL::1252 +DEAL::1284 +DEAL::1317 +DEAL::1339 +DEAL::1203 +DEAL::1253 +DEAL::1285 +DEAL::1318 +DEAL::1351 +DEAL::1372 +DEAL::1228 +DEAL::1271 +DEAL::1305 +DEAL::1340 +DEAL::1373 +DEAL::1400 +DEAL::1117 +DEAL::1150 +DEAL::1175 +DEAL::1204 +DEAL::1236 +DEAL::1261 +DEAL::1151 +DEAL::1191 +DEAL::1222 +DEAL::1254 +DEAL::1286 +DEAL::1306 +DEAL::1176 +DEAL::1223 +DEAL::1255 +DEAL::1287 +DEAL::1319 +DEAL::1341 +DEAL::1205 +DEAL::1256 +DEAL::1288 +DEAL::1320 +DEAL::1352 +DEAL::1374 +DEAL::1237 +DEAL::1289 +DEAL::1321 +DEAL::1353 +DEAL::1385 +DEAL::1405 +DEAL::1262 +DEAL::1307 +DEAL::1342 +DEAL::1375 +DEAL::1406 +DEAL::1430 +DEAL::1140 +DEAL::1177 +DEAL::1206 +DEAL::1238 +DEAL::1272 +DEAL::1298 +DEAL::1178 +DEAL::1224 +DEAL::1257 +DEAL::1290 +DEAL::1322 +DEAL::1343 +DEAL::1207 +DEAL::1258 +DEAL::1291 +DEAL::1323 +DEAL::1354 +DEAL::1376 +DEAL::1239 +DEAL::1292 +DEAL::1324 +DEAL::1355 +DEAL::1386 +DEAL::1407 +DEAL::1273 +DEAL::1325 +DEAL::1356 +DEAL::1387 +DEAL::1417 +DEAL::1435 +DEAL::1299 +DEAL::1344 +DEAL::1377 +DEAL::1408 +DEAL::1436 +DEAL::1458 +DEAL::1166 +DEAL::1208 +DEAL::1240 +DEAL::1274 +DEAL::1308 +DEAL::1333 +DEAL::1209 +DEAL::1259 +DEAL::1293 +DEAL::1326 +DEAL::1357 +DEAL::1378 +DEAL::1241 +DEAL::1294 +DEAL::1327 +DEAL::1358 +DEAL::1388 +DEAL::1409 +DEAL::1275 +DEAL::1328 +DEAL::1359 +DEAL::1389 +DEAL::1418 +DEAL::1437 +DEAL::1309 +DEAL::1360 +DEAL::1390 +DEAL::1419 +DEAL::1446 +DEAL::1459 +DEAL::1334 +DEAL::1379 +DEAL::1410 +DEAL::1438 +DEAL::1460 +DEAL::1477 +DEAL::1196 +DEAL::1242 +DEAL::1276 +DEAL::1310 +DEAL::1345 +DEAL::1368 +DEAL::1243 +DEAL::1295 +DEAL::1329 +DEAL::1361 +DEAL::1391 +DEAL::1411 +DEAL::1277 +DEAL::1330 +DEAL::1362 +DEAL::1392 +DEAL::1420 +DEAL::1439 +DEAL::1311 +DEAL::1363 +DEAL::1393 +DEAL::1421 +DEAL::1447 +DEAL::1461 +DEAL::1346 +DEAL::1394 +DEAL::1422 +DEAL::1448 +DEAL::1471 +DEAL::1480 +DEAL::1369 +DEAL::1412 +DEAL::1440 +DEAL::1462 +DEAL::1481 +DEAL::1492 +DEAL::1229 +DEAL::1278 +DEAL::1312 +DEAL::1347 +DEAL::1380 +DEAL::1401 +DEAL::1279 +DEAL::1331 +DEAL::1364 +DEAL::1395 +DEAL::1423 +DEAL::1441 +DEAL::1313 +DEAL::1365 +DEAL::1396 +DEAL::1424 +DEAL::1449 +DEAL::1463 +DEAL::1348 +DEAL::1397 +DEAL::1425 +DEAL::1450 +DEAL::1472 +DEAL::1482 +DEAL::1381 +DEAL::1426 +DEAL::1451 +DEAL::1473 +DEAL::1489 +DEAL::1495 +DEAL::1402 +DEAL::1442 +DEAL::1464 +DEAL::1483 +DEAL::1496 +DEAL::1502 +DEAL::1263 +DEAL::1314 +DEAL::1349 +DEAL::1382 +DEAL::1413 +DEAL::1431 +DEAL::1315 +DEAL::1366 +DEAL::1398 +DEAL::1427 +DEAL::1452 +DEAL::1465 +DEAL::1350 +DEAL::1399 +DEAL::1428 +DEAL::1453 +DEAL::1474 +DEAL::1484 +DEAL::1383 +DEAL::1429 +DEAL::1454 +DEAL::1475 +DEAL::1490 +DEAL::1497 +DEAL::1414 +DEAL::1455 +DEAL::1476 +DEAL::1491 +DEAL::1501 +DEAL::1505 +DEAL::1432 +DEAL::1466 +DEAL::1485 +DEAL::1498 +DEAL::1506 +DEAL::1508 +DEAL::1296 +DEAL::1335 +DEAL::1370 +DEAL::1403 +DEAL::1433 +DEAL::1456 +DEAL::1336 +DEAL::1384 +DEAL::1415 +DEAL::1443 +DEAL::1467 +DEAL::1478 +DEAL::1371 +DEAL::1416 +DEAL::1444 +DEAL::1468 +DEAL::1486 +DEAL::1493 +DEAL::1404 +DEAL::1445 +DEAL::1469 +DEAL::1487 +DEAL::1499 +DEAL::1503 +DEAL::1434 +DEAL::1470 +DEAL::1488 +DEAL::1500 +DEAL::1507 +DEAL::1509 +DEAL::1457 +DEAL::1479 +DEAL::1494 +DEAL::1504 +DEAL::1510 +DEAL::1511 diff --git a/tests/lac/sparsity_tools_01.cc b/tests/lac/sparsity_tools_01.cc new file mode 100644 index 0000000000..7ef8cdcf37 --- /dev/null +++ b/tests/lac/sparsity_tools_01.cc @@ -0,0 +1,59 @@ +//---------------------------- sparsity_tools_01.cc --------------------------- +// $Id$ +// Version: $Name$ +// +// Copyright (C) 2008, 2009 by the deal.II authors +// +// This file is subject to QPL and may not be distributed +// without copyright and license information. Please refer +// to the file deal.II/doc/license.html for the text and +// further information on this license. +// +//---------------------------- sparsity_tools_01.cc --------------------------- + + +// apply SparsityTools::reorder_Cuthill_McKee to a graph that consists +// of two or more non-connected parts. the reordering algorithm used +// to trip over that + +#include "../tests.h" +#include +#include + +#include +#include + +int main () +{ + std::ofstream logfile("sparsity_tools_01/output"); + logfile.setf(std::ios::fixed); + deallog << std::setprecision(3); + deallog.attach(logfile); + deallog.depth_console(0); + deallog.threshold_double(1.e-10); + + SparsityPattern sp (4,4,4); + for (unsigned int i=0; i<4; ++i) + sp.add (i,i); + + // create a graph with components + // 0,2 and 1,3 that are + // disconnected + sp.add (0,2); + sp.add (2,0); + + sp.add (1,3); + sp.add (3,1); + + sp.compress (); + + // now find permutation + std::vector permutation(4); + SparsityTools::reorder_Cuthill_McKee (sp, permutation); + + for (unsigned int i=0; i