----------------------------------------------------------------------------- Compute the sets of connected components of the input "graph" which contain the nodes in "indices".
| 22 | // Compute the sets of connected components of the input "graph" which |
| 23 | // contain the nodes in "indices". |
| 24 | std::vector<std::vector<int>> |
| 25 | residual_graph_components(const graph::AdjacencyList<int>& graph, |
| 26 | std::span<const int> indices) |
| 27 | { |
| 28 | if (indices.empty()) |
| 29 | return std::vector<std::vector<int>>(); |
| 30 | |
| 31 | const int n = graph.num_nodes(); |
| 32 | |
| 33 | // Mark all nodes as labelled, except those in the residual graph |
| 34 | std::vector<std::int_fast8_t> labelled(n, true); |
| 35 | for (int w : indices) |
| 36 | labelled[w] = false; |
| 37 | |
| 38 | // Find first unlabelled entry |
| 39 | auto it = std::find(labelled.begin(), labelled.end(), false); |
| 40 | |
| 41 | std::vector<std::vector<int>> rgc; |
| 42 | std::vector<int> r; |
| 43 | r.reserve(n); |
| 44 | while (it != labelled.end()) |
| 45 | { |
| 46 | r.clear(); |
| 47 | r.push_back(std::distance(labelled.begin(), it)); |
| 48 | labelled[r.front()] = true; |
| 49 | |
| 50 | // Get connected component of graph starting from r[0] |
| 51 | std::size_t c = 0; |
| 52 | while (c < r.size()) |
| 53 | { |
| 54 | for (int w : graph.links(r[c])) |
| 55 | { |
| 56 | if (!labelled[w]) |
| 57 | { |
| 58 | r.push_back(w); |
| 59 | labelled[w] = true; |
| 60 | } |
| 61 | } |
| 62 | ++c; |
| 63 | } |
| 64 | rgc.push_back(r); |
| 65 | |
| 66 | // Find next unlabelled entry |
| 67 | it = std::find(it, labelled.end(), false); |
| 68 | } |
| 69 | |
| 70 | std::ranges::sort(rgc, |
| 71 | [](const std::vector<int>& a, const std::vector<int>& b) |
| 72 | { return (a.size() > b.size()); }); |
| 73 | |
| 74 | return rgc; |
| 75 | } |
| 76 | //----------------------------------------------------------------------------- |
| 77 | // Get the (maximum) width of a level structure |
| 78 | std::size_t max_level_width(const graph::AdjacencyList<int>& levels) |
no test coverage detected