Helper function to test if a node and its neighborhood form a clique G: input graph node: node to be tested actual_degree: degree of 'node', ignoring removed nodes labels: vector to count neighbors removed: mark simplicial nodes as removed
| 90 | // labels: vector to count neighbors |
| 91 | // removed: mark simplicial nodes as removed |
| 92 | bool clique_test(graph_access &G, NodeID node, Gain actual_degree, std::vector<short> &labels, const std::vector<bool> &removed) { |
| 93 | // To test if 'node' is simplicial, we iterate through its neighbors. |
| 94 | // In each iteration, we |
| 95 | // - mark the currently visited node |
| 96 | // - count the neighbors with a mark |
| 97 | // - if the count equals the number of already visited neighbors, |
| 98 | // then the node could be simplicial |
| 99 | // - otherwise, there is a pair of neighbors that's not connected by an edge |
| 100 | |
| 101 | // Update labels |
| 102 | bool simplicial = true; |
| 103 | Count count; |
| 104 | // Neighbors visited so far |
| 105 | Count max_count = 0; |
| 106 | forall_out_edges(G, edge, node) { |
| 107 | auto neighbor = G.getEdgeTarget(edge); |
| 108 | if (!removed[neighbor]) { |
| 109 | labels[neighbor] = 1; |
| 110 | if (G.getNodeDegree(neighbor) < actual_degree || |
| 111 | G.get_contraction_offset(neighbor) != 0) { |
| 112 | simplicial = false; |
| 113 | break; |
| 114 | } |
| 115 | count = 0; |
| 116 | forall_out_edges(G, edge2, neighbor) { |
| 117 | count += labels[G.getEdgeTarget(edge2)]; |
| 118 | if (count == max_count) { |
| 119 | max_count++; |
| 120 | // 'node' might still be simplicial, |
| 121 | // so continue the outer loop |
| 122 | goto still_simplicial; |
| 123 | } |
| 124 | } endfor |
| 125 | // 'neighbor' is not adjacent to 'max_count' previously visited |
| 126 | // neighbors of 'node', and thus, 'node' is not simplicial. |
| 127 | simplicial = false; |
| 128 | break; |
| 129 | } |
| 130 | still_simplicial:; |
| 131 | } endfor |
| 132 | |
| 133 | // Reset labels |
| 134 | forall_out_edges(G, edge, node) { |
| 135 | labels[G.getEdgeTarget(edge)] = 0; |
| 136 | } endfor |
| 137 | |
| 138 | return simplicial; |
| 139 | } |
| 140 | |
| 141 | class bucket_sorter { |
| 142 | public: |