From e2e587bb0d43e20f77b4520bb285b9f30c4cbcef Mon Sep 17 00:00:00 2001 From: bangerth Date: Thu, 7 Nov 2013 01:36:38 +0000 Subject: [PATCH] Move around a couple of things. Reindent the whole file. git-svn-id: https://svn.dealii.org/trunk@31571 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/include/deal.II/base/graph_coloring.h | 697 +++++++++--------- 1 file changed, 351 insertions(+), 346 deletions(-) diff --git a/deal.II/include/deal.II/base/graph_coloring.h b/deal.II/include/deal.II/base/graph_coloring.h index b38d1a5717..d7b62733b7 100644 --- a/deal.II/include/deal.II/base/graph_coloring.h +++ b/deal.II/include/deal.II/base/graph_coloring.h @@ -31,374 +31,376 @@ DEAL_II_NAMESPACE_OPEN -/// This namespace contains the functions necessary to color a graph. +/// This namespace contains the functions necessary to color graphs. namespace graph_coloring { - /** - * Create a partitioning of the given range of iterators using a simplified - * version of the Cuthill-McKee algorithm (Breadth First Search algorithm). - * Any pair of two iterators that point to conflicting objects will be placed - * into different partitions, where the question whether two objects conflict - * is determined by a user-provided function. - * - * This function can also be considered as a graph coloring: each object - * pointed to by an iterator is considered to be a node and there is an - * edge between each two nodes that conflict. The graph coloring algorithm - * then assigns a color to each node in such a way that two nodes connected - * by an edge do not have the same color. - * - * A typical use case for this function is in assembling a matrix in parallel. - * There, one would like to assemble local contributions on different cells - * at the same time (an operation that is purely local and so requires - * no synchronization) but then we need to add these local contributions - * to the global matrix. In general, the contributions from different cells - * may be to the same matrix entries if the cells share degrees of freedom - * and, consequently, can not happen at the same time unless we want to - * risk a race condition (see http://en.wikipedia.org/wiki/Race_condition ). - * Thus, we call these two cells in conflict, and we can only allow operations - * in parallel from cells that do not conflict. In other words, two cells - * are in conflict if the set of matrix entries (for example characterized - * by the rows) have a nonempty intersection. - * - * In this generality, computing the graph of conflicts would require calling - * a function that determines whether two iterators (or the two objects they - * represent) conflict, and calling it for every pair of iterators, i.e., - * $\frac 12 N (N-1)$ times. This is too expensive in general. A better - * approach is to require a user-defined function that returns for every - * iterator it is called for a set of indicators of some kind that characterize - * a conflict; two iterators are in conflict if their conflict indicator sets - * have a nonempty intersection. In the example of assembling a matrix, - * the conflict indicator set would contain the indices of all degrees of - * freedom on the cell pointed to (in the case of continuous Galerkin methods) - * or the union of indices of degree of freedom on the current cell and all - * cells adjacent to the faces of the current cell (in the case of - * discontinuous Galerkin methods, because there one computes face integrals - * coupling the degrees of freedom connected by a common face -- see step-12). - * However, in other situations, these conflict indicator sets may represent - * something different altogether -- it is up to the caller of this function - * to describe what it means for two iterators to conflict. Given this, - * computing conflict graph edges can be done significantly more cheaply - * than with ${\cal O}(N^2)$ operations. - * - * In any case, the result of the function will be so that iterators whose - * conflict indicator sets have overlap will not be assigned to the same - * partition (i.e., they will have a different color). - * - * @param[in] begin The first element of a range of iterators for which a - * partitioning is sought. - * @param[in] end The element past the end of the range of iterators. - * @param[in] get_conflict_indices A user defined function object returning - * a set of indicators that are descriptive of what represents a - * conflict. See above for a more thorough discussion. - * @return A set of sets of iterators (where sets are represented by - * std::vector for efficiency). Each element of the outermost set - * corresponds to the iterators pointing to objects that are in the - * same partition (have the same color) and consequently do not - * conflict. The elements of different sets may conflict. - * - * @author Martin Kronbichler, Bruno Turcksin - */ - template - std::vector > - create_partitioning(const Iterator &begin, - const typename identity::type &end, - const std_cxx1x::function (Iterator const &)> &get_conflict_indices) + namespace internal { - std::vector > partitioning(1,std::vector (1,begin)); + /** + * Create a partitioning of the given range of iterators using a simplified + * version of the Cuthill-McKee algorithm (Breadth First Search algorithm). + * Any pair of two iterators that point to conflicting objects will be placed + * into different partitions, where the question whether two objects conflict + * is determined by a user-provided function. + * + * This function can also be considered as a graph coloring: each object + * pointed to by an iterator is considered to be a node and there is an + * edge between each two nodes that conflict. The graph coloring algorithm + * then assigns a color to each node in such a way that two nodes connected + * by an edge do not have the same color. + * + * A typical use case for this function is in assembling a matrix in parallel. + * There, one would like to assemble local contributions on different cells + * at the same time (an operation that is purely local and so requires + * no synchronization) but then we need to add these local contributions + * to the global matrix. In general, the contributions from different cells + * may be to the same matrix entries if the cells share degrees of freedom + * and, consequently, can not happen at the same time unless we want to + * risk a race condition (see http://en.wikipedia.org/wiki/Race_condition ). + * Thus, we call these two cells in conflict, and we can only allow operations + * in parallel from cells that do not conflict. In other words, two cells + * are in conflict if the set of matrix entries (for example characterized + * by the rows) have a nonempty intersection. + * + * In this generality, computing the graph of conflicts would require calling + * a function that determines whether two iterators (or the two objects they + * represent) conflict, and calling it for every pair of iterators, i.e., + * $\frac 12 N (N-1)$ times. This is too expensive in general. A better + * approach is to require a user-defined function that returns for every + * iterator it is called for a set of indicators of some kind that characterize + * a conflict; two iterators are in conflict if their conflict indicator sets + * have a nonempty intersection. In the example of assembling a matrix, + * the conflict indicator set would contain the indices of all degrees of + * freedom on the cell pointed to (in the case of continuous Galerkin methods) + * or the union of indices of degree of freedom on the current cell and all + * cells adjacent to the faces of the current cell (in the case of + * discontinuous Galerkin methods, because there one computes face integrals + * coupling the degrees of freedom connected by a common face -- see step-12). + * However, in other situations, these conflict indicator sets may represent + * something different altogether -- it is up to the caller of this function + * to describe what it means for two iterators to conflict. Given this, + * computing conflict graph edges can be done significantly more cheaply + * than with ${\cal O}(N^2)$ operations. + * + * In any case, the result of the function will be so that iterators whose + * conflict indicator sets have overlap will not be assigned to the same + * partition (i.e., they will have a different color). + * + * @param[in] begin The first element of a range of iterators for which a + * partitioning is sought. + * @param[in] end The element past the end of the range of iterators. + * @param[in] get_conflict_indices A user defined function object returning + * a set of indicators that are descriptive of what represents a + * conflict. See above for a more thorough discussion. + * @return A set of sets of iterators (where sets are represented by + * std::vector for efficiency). Each element of the outermost set + * corresponds to the iterators pointing to objects that are in the + * same partition (have the same color) and consequently do not + * conflict. The elements of different sets may conflict. + * + * @author Martin Kronbichler, Bruno Turcksin + */ + template + std::vector > + create_partitioning(const Iterator &begin, + const typename identity::type &end, + const std_cxx1x::function (const Iterator &)> &get_conflict_indices) + { + std::vector > partitioning(1,std::vector (1,begin)); - // Number of iterators. - unsigned int n_iterators = 0; + // Number of iterators. + unsigned int n_iterators = 0; - // Create a map from conflict indices to iterators - boost::unordered_map > indices_to_iterators; - for (Iterator it=begin; it!=end; ++it) - { - std::vector conflict_indices = get_conflict_indices(it); - const unsigned int n_conflict_indices = conflict_indices.size(); - for (unsigned int i=0; i > indices_to_iterators; + for (Iterator it=begin; it!=end; ++it) + { + std::vector conflict_indices = get_conflict_indices(it); + const unsigned int n_conflict_indices = conflict_indices.size(); + for (unsigned int i=0; i used_it; - used_it.insert(begin); - while (used_it.size()!=n_iterators) - { - typename std::vector::iterator vector_it(partitioning.back().begin()); - typename std::vector::iterator vector_end(partitioning.back().end()); - std::vector new_zone; - for (; vector_it!=vector_end; ++vector_it) - { - std::vector conflict_indices = get_conflict_indices(*vector_it); - const unsigned int n_conflict_indices(conflict_indices.size()); - for (unsigned int i=0; i used_it; + used_it.insert(begin); + while (used_it.size()!=n_iterators) { - std::vector iterator_vector(indices_to_iterators[conflict_indices[i]]); - for (unsigned int j=0; j::iterator vector_it(partitioning.back().begin()); + typename std::vector::iterator vector_end(partitioning.back().end()); + std::vector new_zone; + for (; vector_it!=vector_end; ++vector_it) { - new_zone.push_back(iterator_vector[j]); - used_it.insert(iterator_vector[j]); + std::vector conflict_indices = get_conflict_indices(*vector_it); + const unsigned int n_conflict_indices(conflict_indices.size()); + for (unsigned int i=0; i iterator_vector(indices_to_iterators[conflict_indices[i]]); + for (unsigned int j=0; j (1,it)); + break; + } } - } - // If there are iterators in the new zone, then the zone is added to the - // partition. Otherwise, the graph is disconnected and we need to find - // an iterator on the other part of the graph. - if (new_zone.size()!=0) - partitioning.push_back(new_zone); - else - for (Iterator it=begin; it!=end; ++it) - if (used_it.count(it)==0) - { - partitioning.push_back(std::vector (1,it)); - break; - } - } - return partitioning; - } + return partitioning; + } - /** - * This function uses DSATUR (Degree SATURation) to color one zone of the - * partition. DSATUR works as follows: - * -# Arrange the vertices by decreasing order of degrees. - * -# Color a vertex of maximal degree with color 1. - * -# Choose a vertex with a maximal saturation degree. If there is equality, - * choose any vertex of maximal degree in the uncolored subgraph. - * -# Color the chosen vertex with the least possible (lowest numbered) color. - * -# If all the vertices are colored, stop. Otherwise, return to 3. - */ - template - std::vector > make_dsatur_coloring(std::vector &partition, - std_cxx1x::function (Iterator const &)> - const &get_conflict_indices) - { - std::vector > partition_coloring; - // Number of zones composing the partitioning. - const unsigned int partition_size(partition.size()); - std::vector sorted_vertices(partition_size); - std::vector degrees(partition_size); - std::vector > conflict_indices(partition_size); - std::vector > graph(partition_size); - - // Get the conflict indices associated to each iterator. The conflict_indices have to be sorted so - // set_intersection can be used later. - for (unsigned int i=0; i + std::vector > + make_dsatur_coloring(std::vector &partition, + const std_cxx1x::function (const Iterator &)> &get_conflict_indices) { - conflict_indices[i] = get_conflict_indices(partition[i]); - std::sort(conflict_indices[i].begin(),conflict_indices[i].end()); - } - - // Compute the degree of each vertex of the graph using the - // intersection of the conflict indices. - std::vector conflict_indices_intersection; - std::vector::iterator intersection_it; - for (unsigned int i=0; i > partition_coloring; + // Number of zones composing the partitioning. + const unsigned int partition_size(partition.size()); + std::vector sorted_vertices(partition_size); + std::vector degrees(partition_size); + std::vector > conflict_indices(partition_size); + std::vector > graph(partition_size); + + // Get the conflict indices associated to each iterator. The conflict_indices have to be sorted so + // set_intersection can be used later. + for (unsigned int i=0; i::iterator degrees_it; - for (unsigned int i=0; i > colors_used; - for (unsigned int i=0; i conflict_indices_intersection; + std::vector::iterator intersection_it; + for (unsigned int i=0; i::iterator degrees_it; + for (unsigned int i=0; i (1, - partition[current_vertex])); - boost::unordered_set tmp; - tmp.insert(current_vertex); - colors_used.push_back(tmp); - } - } - return partition_coloring; - } + // Color the graph. + std::vector > colors_used; + for (unsigned int i=0; i (1, + partition[current_vertex])); + boost::unordered_set tmp; + tmp.insert(current_vertex); + colors_used.push_back(tmp); + } + } + return partition_coloring; + } - /** - * Given a partition-coloring graph, gather the colors together. All the - * colors on even (resp. odd) partition can be executed simultaneously. This - * function tries to create colors of similar number of elements. - */ - template - std::vector > - gather_colors(std::vector > > const &partition_coloring) - { - std::vector > coloring; - // Count the number of iterators in each color. - const unsigned int partition_size(partition_coloring.size()); - std::vector > colors_counter(partition_size); - for (unsigned int i=0; i + std::vector > + gather_colors(std::vector > > const &partition_coloring) { - const unsigned int n_colors(partition_coloring[i].size()); - colors_counter[i].resize(n_colors); - for (unsigned int j=0; j > coloring; - // Find the partition with the largest number of colors for the even partition. - unsigned int i_color(0); - unsigned int max_even_n_colors(0); - const unsigned int colors_size(colors_counter.size()); - for (unsigned int i=0; i > colors_counter(partition_size); + for (unsigned int i=0; i used_k; - for (unsigned int j=0; j::iterator it; - it = std::max_element(colors_counter[i].begin(),colors_counter[i].end()); - unsigned int min_iterators(-1); - unsigned int pos(0); - // Find the color of coloring with the least number of colors among - // the colors that have not been used yet. - for (unsigned int k=0; k used_k; + for (unsigned int j=0; j::iterator it; + it = std::max_element(colors_counter[i].begin(),colors_counter[i].end()); + unsigned int min_iterators(-1); + unsigned int pos(0); + // Find the color of coloring with the least number of colors among + // the colors that have not been used yet. + for (unsigned int k=0; k used_k; - for (unsigned int j=0; j::iterator it; - it = std::max_element(colors_counter[i].begin(),colors_counter[i].end()); - unsigned int min_iterators(-1); - unsigned int pos(0); - // Find the color of coloring with the least number of colors among - // the colors that have not been used yet. - for (unsigned int k=0; k used_k; + for (unsigned int j=0; j::iterator it; + it = std::max_element(colors_counter[i].begin(),colors_counter[i].end()); + unsigned int min_iterators(-1); + unsigned int pos(0); + // Find the color of coloring with the least number of colors among + // the colors that have not been used yet. + for (unsigned int k=0; k - std::vector > - make_graph_coloring(Iterator const &begin,typename identity::type const &end, - std_cxx1x::function (Iterator const &)> - const &get_conflict_indices) + std::vector > + make_graph_coloring(const Iterator &begin, + const typename identity::type &end, + const std_cxx1x::function (const Iterator &)> &get_conflict_indices) { // Create the partitioning. - std::vector > partitioning = create_partitioning(begin,end, - get_conflict_indices); + std::vector > + partitioning = internal::create_partitioning (begin, + end, + get_conflict_indices); // Color the iterators within each partition. const unsigned int partitioning_size(partitioning.size()); - std::vector > > partition_coloring( - partitioning_size); - for (unsigned int i=0; i > > + partition_coloring(partitioning_size); - // Gather the colors together. - std::vector > coloring = gather_colors(partition_coloring); + // TODO: run these in parallel + for (unsigned int i=0; i