LEMON图库中如何通过NodeMap值获取ListDigraph::Node节点？

Great question—reverse lookups (from NodeMap values back to ListDigraph::Node instances) aren’t a built-in feature in LEMON, but they’re totally doable with standard C++ containers, and I’ll walk you through how to implement this efficiently.

Does LEMON have a built-in reverse mapping? #

Short answer: No. The ListDigraph::NodeMap is designed as a one-way mapping (from nodes to values) out of the box. LEMON doesn’t provide a ready-made structure for the reverse direction, so you’ll need to build your own.

Implementing an Efficient Reverse Mapping #

To map values back to nodes, you can use standard C++ associative containers. The choice depends on whether your NodeMap values are unique or can repeat:

1. For Unique Values (Fastest Lookup) #

Use std::unordered_map<ValueType, ListDigraph::Node>—this gives average O(1) lookup time. Here’s a quick example:

#include <lemon/list_graph.h>
#include <unordered_map>

using namespace lemon;

int main() {
    ListDigraph g;
    ListDigraph::NodeMap<std::string> node_names(g); // Example value type: string

    // Add nodes and assign values
    auto node_a = g.addNode();
    node_names[node_a] = "Alice";
    auto node_b = g.addNode();
    node_names[node_b] = "Bob";

    // Build reverse map
    std::unordered_map<std::string, ListDigraph::Node> name_to_node;
    for (ListDigraph::NodeIt node(g); node != INVALID; ++node) {
        name_to_node[node_names[node]] = node;
    }

    // Look up node by value
    if (auto it = name_to_node.find("Alice"); it != name_to_node.end()) {
        ListDigraph::Node found_node = it->second;
        // Use the node as needed
    }

    return 0;
}

2. For Non-Unique Values #

If multiple nodes can have the same value, use std::unordered_multimap<ValueType, ListDigraph::Node> (or std::multimap if you need ordered keys). This lets you retrieve all nodes associated with a given value:

// Build reverse map for non-unique values
std::unordered_multimap<int, ListDigraph::Node> value_to_nodes;
for (ListDigraph::NodeIt node(g); node != INVALID; ++node) {
    value_to_nodes.emplace(node_value[node], node);
}

// Get all nodes with value 10
auto [start, end] = value_to_nodes.equal_range(10);
for (auto it = start; it != end; ++it) {
    ListDigraph::Node node = it->second;
    // Process each node
}

Key Notes for Maintenance #

• Sync with NodeMap changes: If you update a node’s value in the original NodeMap, remember to update the reverse map too—remove the old value-entry pair and add the new one to avoid stale data.
• Handle node deletion: When you remove a node from the graph, erase its entry from both the NodeMap and the reverse map to prevent dangling references.

Can You Iterate Over the Reverse Map's Underlying Values? #

Absolutely! All C++ associative containers support iteration. You can loop through the reverse map to access every (value, node) pair:

// Iterate over all entries in the reverse map
for (const auto& entry : value_to_nodes) {
    int value = entry.first;
    ListDigraph::Node node = entry.second;
    // Perform operations here
}

You can also use iterators directly if you need more control over the traversal.

内容的提问来源于stack exchange，提问作者TKr