| 208 | }; |
| 209 | |
| 210 | void SimplicialNodeReduction::apply() { |
| 211 | bucket_sorter degree_queue(graph_before, degree_limit); |
| 212 | |
| 213 | graph_after.start_construction(graph_before.number_of_nodes(), graph_before.number_of_edges()); |
| 214 | |
| 215 | // mapping from nodes of graph_before to nodes of graph_after |
| 216 | std::vector<NodeID> reverse_mapping(graph_before.number_of_nodes(), 0); |
| 217 | std::vector<bool> remove(graph_before.number_of_nodes(), false); |
| 218 | std::vector<short> test_labels(graph_before.number_of_nodes(), 0); |
| 219 | while (degree_queue.size() > 0) { |
| 220 | auto current_degree = degree_queue.minValue(); |
| 221 | NodeID node_to_test = degree_queue.deleteMin(); |
| 222 | if (current_degree <= 1 || clique_test(graph_before, node_to_test, current_degree, test_labels, remove)) { |
| 223 | remove[node_to_test] = true; |
| 224 | label_first.push_back(node_to_test); |
| 225 | |
| 226 | // Update the degree of all neighbors of the eliminated nodes. |
| 227 | // The eliminated nodes are all only a member of one clique, |
| 228 | // so the neighbors of node_to_test are all we need to update. |
| 229 | forall_out_edges(graph_before, edge, node_to_test) { |
| 230 | auto target = graph_before.getEdgeTarget(edge); |
| 231 | if (degree_queue.contains(target)) { |
| 232 | degree_queue.decreaseKey(target, 1); |
| 233 | } |
| 234 | } endfor |
| 235 | } |
| 236 | } |
| 237 | |
| 238 | forall_nodes(graph_before, node) { |
| 239 | if (!remove[node]) { |
| 240 | auto new_node_id = graph_after.new_node(); |
| 241 | graph_after.setNodeWeight(new_node_id, graph_before.getNodeWeight(node)); |
| 242 | graph_after.set_contraction_offset(new_node_id, graph_before.get_contraction_offset(node)); |
| 243 | mapping.push_back(node); |
| 244 | reverse_mapping[node] = new_node_id; |
| 245 | } |
| 246 | } endfor |
| 247 | |
| 248 | // Copy edges |
| 249 | for (NodeID new_node_id = 0; new_node_id < graph_before.number_of_nodes() - label_first.size(); ++new_node_id) { |
| 250 | forall_out_edges(graph_before, edge, mapping[new_node_id]) { |
| 251 | auto target = graph_before.getEdgeTarget(edge); |
| 252 | if (!remove[target]) { |
| 253 | auto new_edge_id = graph_after.new_edge(new_node_id, reverse_mapping[target]); |
| 254 | graph_after.setEdgeWeight(new_edge_id, graph_before.getEdgeWeight(edge)); |
| 255 | } |
| 256 | } endfor |
| 257 | } |
| 258 | |
| 259 | graph_after.finish_construction(); |
| 260 | } |
| 261 | |
| 262 | void SimplicialNodeReduction::map(std::vector<NodeID> &reduced_label, std::vector<NodeID> &new_label) const { |
| 263 | new_label.resize(graph_before.number_of_nodes()); |
no test coverage detected