如何在C++的LEMON库中基于ListDigraph指定节点创建子图？

直接手动实现子图构建与映射同步即可，以下是具体步骤和代码示例：

1. 前置准备

   • 将指定节点列表存入std::set或ListDigraph::NodeMap<bool>，用于快速判断节点是否需要保留在子图中
   • 创建新的子图对象、原节点到子图节点的关联映射，以及子图对应的节点/弧映射

2. 代码实现

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

using namespace lemon;

int main() {
    // 假设原图及映射已完成初始化
    ListDigraph originalGraph;
    ListDigraph::NodeMap<int> originalLabel(originalGraph);
    ListDigraph::ArcMap<int> originalLength(originalGraph);
    std::vector<ListDigraph::Node> selectedNodes; // 你的指定节点列表

    // 1. 构建节点存在性集合，提升查询效率
    std::set<ListDigraph::Node> nodeSet(selectedNodes.begin(), selectedNodes.end());

    // 2. 初始化子图及对应映射
    ListDigraph subGraph;
    ListDigraph::NodeMap<ListDigraph::Node> origToSub(originalGraph); // 原节点到子图节点的关联
    ListDigraph::NodeMap<int> subLabel(subGraph);
    ListDigraph::ArcMap<int> subLength(subGraph);

    // 3. 复制指定节点到子图，同步label映射
    for (auto node : selectedNodes) {
        ListDigraph::Node subNode = subGraph.addNode();
        origToSub[node] = subNode;
        subLabel[subNode] = originalLabel[node];
    }

    // 4. 复制符合条件的弧到子图，同步length映射
    for (ListDigraph::ArcIt arc(originalGraph); arc != INVALID; ++arc) {
        ListDigraph::Node u = originalGraph.source(arc);
        ListDigraph::Node v = originalGraph.target(arc);
        // 仅保留两端都在选中节点集合内的弧
        if (nodeSet.count(u) && nodeSet.count(v)) {
            ListDigraph::Arc subArc = subGraph.addArc(origToSub[u], origToSub[v]);
            subLength[subArc] = originalLength[arc];
        }
    }

    // 后续可直接使用subGraph、subLabel、subLength
    return 0;
}

3. 关键说明
   • 使用std::set存储选中节点，可实现O(logN)时间复杂度的存在性检查，节点数量较小时也可改用线性遍历，但集合方案效率更高
   • origToSub映射是核心，它关联了原图节点与子图中对应的节点，确保弧的端点能正确对应到子图节点
   • 遍历原图强所有弧，仅保留两端都属于选中节点的弧，完全匹配需求

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