有向循环图中基于节点与边属性的路径过滤及存储方案问询

核心设计思路 #

针对查询类型固定（<5种）、需复用过滤逻辑的需求，采用规则抽象+预计算匹配状态+带状态遍历的方案：

1. 将过滤逻辑抽象为可复用的规则对象，统一管理节点/边的匹配条件；
2. 在Node和Link类中扩展存储结构，预计算并缓存每个规则下的匹配状态，避免每次查询重复解析属性；
3. 遍历过程中携带路径状态（已满足的条件、已访问节点），处理环和多父节点场景，确保不同路径的过滤进度独立。

1. 可复用过滤规则抽象 #

定义FilterRule结构体，封装所有过滤条件，每个规则对应一类查询需求：

#include <functional>
#include <vector>
#include <string>

struct FilterRule {
    // 起始节点匹配条件（可选，查询时也可直接指定起始节点）
    std::function<bool(const Node&)> startNodeMatch;
    // 目标节点必须满足的条件
    std::function<bool(const Node&)> targetNodeMatch;
    // 路径必须至少经过一次的节点条件集合
    std::vector<std::function<bool(const Node&)>> requiredNodeChecks;
    // 路径必须至少经过一次的边条件集合
    std::vector<std::function<bool(const Link&)>> requiredLinkChecks;
    // 路径中禁止出现的节点条件（可选）
    std::function<bool(const Node&)> forbiddenNodeMatch;
    // 路径中禁止出现的边条件（可选）
    std::function<bool(const Link&)> forbiddenLinkMatch;
};

2. Node与Link类扩展 #

修改原有类，添加规则匹配状态的存储，预计算后可直接复用：

修改后的Node类 #

#include <unordered_map>
#include <optional>

class Node
{
   std::string nodeName;
   std::map<std::string, Link*> forwardLinkMap;
   std::map<std::string, std::string> nodeProperties;
   // 存储每个规则ID对应的节点匹配状态（如是否符合目标条件）
   std::unordered_map<std::string, bool> ruleNodeMatches;
   // 缓存该节点是否能到达符合目标条件的节点（避免重复遍历）
   std::unordered_map<std::string, std::optional<bool>> ruleReachableTarget;
};

修改后的Link类 #

class Link
{
  std::string linkName;
  Node* parentNode;
  Node* childNode;
  std::map<std::string, std::string> linkProperties;
  // 存储每个规则ID对应的边匹配状态（如是否符合必经边条件）
  std::unordered_map<std::string, bool> ruleLinkMatches;
};

3. 预计算规则匹配状态 #

在规则创建完成后，遍历整个图一次，计算所有节点和边在该规则下的匹配状态，后续查询直接读取缓存：

#include <queue>
#include <unordered_set>

// 预计算指定规则下所有节点和边的匹配状态
void precomputeRuleMatches(Node* startNode, const FilterRule& rule, const std::string& ruleId) {
    std::unordered_set<Node*> visited;
    std::queue<Node*> traverseQueue;
    traverseQueue.push(startNode);
    visited.insert(startNode);

    while (!traverseQueue.empty()) {
        Node* currentNode = traverseQueue.front();
        traverseQueue.pop();

        // 计算节点是否符合目标条件并缓存
        currentNode->ruleNodeMatches[ruleId] = rule.targetNodeMatch(*currentNode);

        // 处理所有出边
        for (const auto& [linkName, link] : currentNode->forwardLinkMap) {
            // 计算边是否符合任意必经边条件并缓存
            link->ruleLinkMatches[ruleId] = std::any_of(
                rule.requiredLinkChecks.begin(), 
                rule.requiredLinkChecks.end(),
                [&](const auto& check) { return check(*link); }
            );

            if (!visited.count(link->childNode)) {
                visited.insert(link->childNode);
                traverseQueue.push(link->childNode);
            }
        }
    }
}

4. 带状态的路径遍历实现 #

采用DFS+回溯的方式，携带路径状态（已访问节点、已满足的必经条件），处理环和多父节点：

路径状态结构体 #

#include <vector>
#include <unordered_set>

struct PathState {
    Node* currentNode;
    std::unordered_set<Node*> visitedNodes; // 记录当前路径节点，防止环
    std::vector<std::size_t> satisfiedNodeChecks; // 已满足的必经节点条件索引
    std::vector<std::size_t> satisfiedLinkChecks; // 已满足的必经边条件索引
    std::vector<Node*> pathNodes; // 当前路径的节点序列
    std::vector<Link*> pathLinks; // 当前路径的边序列
};

遍历与过滤函数 #

#include <algorithm>
#include <vector>

// 查找符合规则的所有路径
std::vector<std::pair<std::vector<Node*>, std::vector<Link*>>> findValidPaths(
    Node* startNode, 
    const FilterRule& rule, 
    const std::string& ruleId
) {
    std::vector<std::pair<std::vector<Node*>, std::vector<Link*>>> validPaths;

    // 检查起始节点是否符合规则要求
    if (!rule.startNodeMatch || rule.startNodeMatch(*startNode)) {
        PathState initialState;
        initialState.currentNode = startNode;
        initialState.visitedNodes.insert(startNode);
        initialState.pathNodes.push_back(startNode);
        dfsTraverse(initialState, rule, validPaths);
    }

    return validPaths;
}

// 递归DFS遍历
void dfsTraverse(
    PathState currentState, 
    const FilterRule& rule, 
    std::vector<std::pair<std::vector<Node*>, std::vector<Link*>>>& validPaths
) {
    Node* currentNode = currentState.currentNode;

    // 检查当前节点是否是目标节点，且所有必经条件已满足
    if (rule.targetNodeMatch(*currentNode)) {
        bool allNodeChecksMet = currentState.satisfiedNodeChecks.size() == rule.requiredNodeChecks.size();
        bool allLinkChecksMet = currentState.satisfiedLinkChecks.size() == rule.requiredLinkChecks.size();
        if (allNodeChecksMet && allLinkChecksMet) {
            validPaths.emplace_back(currentState.pathNodes, currentState.pathLinks);
        }
    }

    // 遍历所有出边
    for (const auto& [linkName, link] : currentNode->forwardLinkMap) {
        Node* nextNode = link->childNode;

        // 跳过禁止的边或节点，以及当前路径已访问的节点（防环）
        if ((rule.forbiddenLinkMatch && rule.forbiddenLinkMatch(*link)) ||
            (rule.forbiddenNodeMatch && rule.forbiddenNodeMatch(*nextNode)) ||
            currentState.visitedNodes.count(nextNode)) {
            continue;
        }

        // 复制当前状态，更新路径信息
        PathState newState = currentState;
        newState.currentNode = nextNode;
        newState.visitedNodes.insert(nextNode);
        newState.pathNodes.push_back(nextNode);
        newState.pathLinks.push_back(link);

        // 更新已满足的必经边条件
        for (std::size_t i = 0; i < rule.requiredLinkChecks.size(); ++i) {
            if (std::find(newState.satisfiedLinkChecks.begin(), newState.satisfiedLinkChecks.end(), i) == newState.satisfiedLinkChecks.end()) {
                if (rule.requiredLinkChecks[i](*link)) {
                    newState.satisfiedLinkChecks.push_back(i);
                }
            }
        }

        // 更新已满足的必经节点条件
        for (std::size_t i = 0; i < rule.requiredNodeChecks.size(); ++i) {
            if (std::find(newState.satisfiedNodeChecks.begin(), newState.satisfiedNodeChecks.end(), i) == newState.satisfiedNodeChecks.end()) {
                if (rule.requiredNodeChecks[i](*nextNode)) {
                    newState.satisfiedNodeChecks.push_back(i);
                }
            }
        }

        // 递归遍历下一个节点
        dfsTraverse(newState, rule, validPaths);
    }
}

5. 示例用法 #

示例1：从指定节点到含海滩属性的节点，且途经中餐节点 #

// 创建规则
FilterRule beachWithChineseRule;
beachWithChineseRule.startNodeMatch = [](const Node& node) {
    return node.nodeName == "Beijing";
};
beachWithChineseRule.targetNodeMatch = [](const Node& node) {
    auto it = node.nodeProperties.find("hasBeach");
    return it != node.nodeProperties.end() && it->second == "Yes";
};
beachWithChineseRule.requiredNodeChecks.emplace_back([](const Node& node) {
    auto it = node.nodeProperties.find("canGetChineseFood");
    return it != node.nodeProperties.end() && it->second == "Yes";
});

// 预计算匹配状态
precomputeRuleMatches(startNode, beachWithChineseRule, "rule_beach_chinese");

// 查询路径
auto validPaths1 = findValidPaths(startNode, beachWithChineseRule, "rule_beach_chinese");

示例2：到人口<1000的城市，途经限速≥50的边 #

FilterRule smallCityWithSpeedRule;
smallCityWithSpeedRule.targetNodeMatch = [](const Node& node) {
    auto it = node.nodeProperties.find("population");
    if (it == node.nodeProperties.end()) return false;
    int population = std::stoi(it->second);
    return population < 1000;
};
smallCityWithSpeedRule.requiredLinkChecks.emplace_back([](const Link& link) {
    auto it = link.linkProperties.find("maxSpeed");
    if (it == link.linkProperties.end()) return false;
    int speed = std::stoi(it->second);
    return speed >= 50;
});

// 预计算匹配状态
precomputeRuleMatches(startNode, smallCityWithSpeedRule, "rule_small_city_speed");

// 查询路径
auto validPaths2 = findValidPaths(startNode, smallCityWithSpeedRule, "rule_small_city_speed");

多父节点场景处理说明 #

每个路径状态在递归时采用值传递复制，不同父节点到达同一子节点时，会携带各自独立的条件满足进度（如是否已途经中餐节点），因此不会出现状态混淆的问题。例如节点X可从节点A和节点B到达：A过来的路径已满足必经条件，B过来的路径未满足，遍历会分别处理这两种情况，确保所有符合条件的路径都能被找到。

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