How to retrieve the size of the largest cluster formed by the decoder?

[RefaatIsmail]

Hi, this is more of question rather than an issue, I am posting it here so other users can potentially benefit as well.

I know setting cluster_node_limit to 50 for example forces decoder to use UnionFind when the biggest cluster reaches 50 (please correct me if I am wrong).

Is there an existing method or field on the solver (or within the decoder API) that lets me extract the size of the largest cluster of nodes after decoding?

[RefaatIsmail]

Basically I am trying to keep track of whether UF kicked in for a given syndrome, or the decoder finished running before it hit the cluster_node_limit

[yuewuo]

Excellent question! I currently have only a few functions that allow the user to probe into the internal variables, and they're not complete of course. It'll be great if you find some functionalities that are desired, either let me know or you could possibly submit a PR that implements it. For now, you can achieve the goal of getting the number of nodes of each cluster using the following functions:

You can use solver.get_node(node_index) function to get a Node object, something like below.

def print_dual_variables():
    node_index = 0
    node = solver.get_node(node_index)
    non_zero_nodes = []
    while node is not None:
        if node.dual_variable != 0:
            # only non-zero dual variables matter
            non_zero_nodes.append(
                (node.dual_variable.numer, node.dual_variable.denom, node.vertices, node.edges)
            )
        # increment
        node_index += 1
        node = solver.get_node(node_index)
    print(repr(non_zero_nodes))
print_dual_variables()

To get the cluster from a node, you can either manually cluster the nodes (basically if two nodes share any vertices or edges, they below to the same cluster), or you can use the solver.get_cluster(vertex_index) function and pass in any vertex index $v \in V_S$ of the node $S = (V_S, E_S)$. The returned Cluster object will then allow you to iterate over its internal nodes:

cluster = solver.get_cluster(vertex_index)
for node in cluster.nodes:
    if node.dual_variable > 0:
        print(repr(node))

[RefaatIsmail]

Thanks Yue for detailed information! I would like to contribute, unfortunately, I am not very well-versed in Rust tho. I will try to see how I can help when I get the chance to take a closer look at the source files.

I think this feature "knowing whether the decoder hit the maximum node limit or not" would be helpful to know whether the solution is "certified" or not.

[yuewuo]

Thanks. Also, to know whether the solution is "certified", just call subgraph, range = solver.subgraph_range(), it will then print out the range. It is certified to be optimal when range.upper == range.lower. You'll see that even UF decoder, sometimes, are able to certify the optimality of certain syndrome (although this was not how UF decoder was originally explained).

[RefaatIsmail]

This is very helpful—thank you! I assume there's not a similarly straightforward way (other than the previous mentioned machinery) to find out if UF was used in a given run (ie if a cluster node limit was reached).

I am trying to figure out how many of "wrong predictions" were caused by hitting this limit, to see if increasing limit would benefit my error rate enough to justify the extra computational cost.

I am thinking I could do this by basically seeing if the percentage of wrong predictions in samples that used UF is significantly higher than those that did not. And want to see if a decent chunk of the total samples actually hit the limit—enough to meaningfully impact the overall error rate.