| 26 | |
| 27 | |
| 28 | void nested_dissection::perform_nested_dissection(PartitionConfig &config) { |
| 29 | if (original_graph->number_of_nodes() == 0) { |
| 30 | return; |
| 31 | } |
| 32 | |
| 33 | // 'reduced_graph' is a copy of 'original_graph', with reductions applied. |
| 34 | // If no reductions were applied, 'reduced_graph' is empty, and we use 'original_graph' instead. |
| 35 | graph_access reduced_graph; |
| 36 | graph_access *active_graph; |
| 37 | bool used_reductions = apply_reductions(config, *original_graph, m_reduction_stack, m_recursion_level); |
| 38 | if (used_reductions) { |
| 39 | active_graph = &m_reduction_stack.back()->get_reduced_graph(); |
| 40 | } else { |
| 41 | active_graph = original_graph; |
| 42 | } |
| 43 | |
| 44 | m_reduced_label.resize(active_graph->number_of_nodes()); |
| 45 | |
| 46 | if (active_graph->number_of_nodes() > 0) { |
| 47 | if (active_graph->number_of_nodes() < config.dissection_rec_limit) { |
| 48 | // Stop nested dissection and use the min degree algorithm instead |
| 49 | MinDegree(active_graph).perform_ordering(m_reduced_label); |
| 50 | } else { |
| 51 | NodeID order_begin = 0; |
| 52 | // continue nested dissection |
| 53 | compute_separator(config, *active_graph); |
| 54 | |
| 55 | // perform nested dissection on subgraphs |
| 56 | forall_blocks((*active_graph), p) { |
| 57 | if (p != active_graph->getSeparatorBlock()) { |
| 58 | recurse_dissection(config, (*active_graph), p, order_begin); |
| 59 | } |
| 60 | } endfor |
| 61 | // Perform nested dissection on separator block |
| 62 | recurse_dissection(config, (*active_graph), active_graph->getSeparatorBlock(), order_begin); |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | if (used_reductions) { |
| 67 | // Map the ordering from the reduced graph to the original graph |
| 68 | map_ordering(m_reduction_stack, m_reduced_label, m_label); |
| 69 | } else { |
| 70 | m_label = m_reduced_label; |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | void nested_dissection::compute_separator(PartitionConfig &config, graph_access &G) { |
| 75 | // set up the graph and config for computing a node separator |
no test coverage detected