Faking Net Graphs

Explanation

If you have a SnarlDistanceIndex or another SnarlDecomposition implementation, it will present you with a "net graph". For each snarl, the snarl's net graph is the graph that connects the child chains of the snarl and the insides of the snarl's bounding nodes.

If you don't actually have a SnarlDecomposition (for example, if you are trying to build one), you might need to fake the net graph yourself. You can do this as long as you know:

• The bounding node IDs and orientations for the snarl
• The start end end node IDs and orientations along each chain in the snarl
• The backing HandleGraph that the snarl is in.

If you also have child nodes in your snarl directly, which aren't wrapped in 0-snarl, single node chains like the SnarlDecomposition presents, then you need to know about them too.

Example: Building a Distance Index

When building up a TemporaryDistanceIndex& temp_index, you will need to construct a TemporarySnarlRecord. You will have access to the partly-filled-in TemporarySnarlRecord& temp_snarl_record, the collection of children vector<pair<SnarlDistanceIndex::temp_record_t, size_t>> all_children, and the backing HandleGraph* graph.

So first, we can make a list of where to find the things we need:

• For the snarl itself, the bounding oriented nodes are:
  • temp_snarl_record.start_node_id, temp_snarl_record.start_node_rev (should be pointing into the snarl)
  • temp_snarl_record.end_node_id, temp_snarl_record.end_node_rev (should be pointing out of the snarl)
• For child i, if it is a chain, the TemporaryChainRecord& rec is temp_index.temp_chain_records[all_children[i].second], and the bounding oriented nodes are:
  • rec.start_node_id, rec.start_node_rev (should be pointing into the chain)
  • rec.end_node_id, rec.end_node_rev (should be pointing out of the chain)
• For child i, if it is a node, the TemporaryNodeRecord& rec is temp_index.temp_node_records[all_children[i].second - temp_index.min_node_id], and the node in its local forward orientation is just:
  • rec.node_id

Now, we want to build a primitive that allows us to navigate the net graph of the snarl. A HandleGraph has follow_edges(), which takes a handle (which refers to a node ID and an orientation), and a flag for looking off the left or right side of it, and produces the handles that would be reached along edges in the graph, in the orientation you would reach them in. We want a similar primitive for the net graph, in terms of child number among all_children. (We'll assume that the last 2 entries are TEMP_NODEs for the snarl's own bounding nodes.)

First, we define a helper function to get us the appropriate backing graph handle for any orientation of any child, depending on the direction (relative to that orientation of the child) we want to go. That would be something like this code (which was helpfully provided by Anthropic's Claude code generator after about an hour and a half of cajoling, and might even be correct):

// Helper to get a handle for a child at a given end
auto child_handle = [&](const pair<size_t, bool>& child_and_orientation, bool go_left) -> handle_t {
    size_t i = child_and_orientation.first;
    bool is_reverse = child_and_orientation.second;
    const pair<SnarlDistanceIndex::temp_record_t, size_t>& child_ref = all_children[i];

    if (child_ref.first == TEMP_CHAIN) {
        const TemporaryDistanceIndex::TemporaryChainRecord& chain =
            temp_index.temp_chain_records[child_ref.second];

        // Pick between start and end: if reversed, left/right are swapped
        bool pick_start = go_left != is_reverse;
        handlegraph::nid_t node_id = pick_start ? chain.start_node_id : chain.end_node_id;
        bool node_rev = pick_start ? chain.start_node_rev : chain.end_node_rev;

        // Get the handle and conditionally flip if reversed
        handle_t h = graph->get_handle(node_id, node_rev);
        return is_reverse ? graph->flip(h) : h;

    } else if (child_ref.first == TEMP_NODE) {
        // TODO: Can we just use child_ref.second as node_id directly?
        const TemporaryDistanceIndex::TemporaryNodeRecord& node =
            temp_index.temp_node_records[child_ref.second - temp_index.min_node_id];
        return graph->get_handle(node.node_id, is_reverse);
    }
};

That seems like a lot, but it's mostly axe-sharpening.

Then, we need to invert that function and index the children by handle, so we can look up a handle we arrive at in the backing graph, and get the child number and orientation we arrive at in the net graph. We can build the necessary data structure with something like this code (again wrested from the steely fingers of Anthropic's Claude):

// Build index from handle to child number and is_reverse flag in all_children
unordered_map<handle_t, pair<size_t, bool>> handle_to_child;

for (size_t i = 0; i < all_children.size(); i++) {
    for (bool is_reverse : {false, true}) {
        for (bool go_left : {false, true}) {
            handle_to_child[child_handle({i, is_reverse}, go_left)] = {i, is_reverse};
        }
    }
}

Finally, we (actually, a very harried Anthropic Claude again) can construct the equivalent of follow_edges on this implicit net graph.

// Lambda that takes a (child index, is_reverse) pair, and calls callback
// with each connected child index-and-orientation.
auto follow_net_edges = [&](const pair<size_t, bool>& child_and_orientation,
                            bool go_left,
                            const function<void(const pair<size_t, bool>&)>& callback) {

    // Get the handle at the appropriate end of this child
    handle_t h = child_handle(child_and_orientation, go_left);

    // Follow edges in the specified direction
    graph->follow_edges(h, go_left, [&](const handle_t& next_handle) {
        // Look up which child this handle enters (must be in map since we can't escape the snarl)
        callback(handle_to_child.at(next_handle));
        return true;
    });
};