有向图：查找特殊路径且不包含反向边。

Question

我需要在一个有向图中找到一条路径（具体要求见下文），图中的节点可以分层分类。这些层对于图的结构非常重要（详见图的属性）。

这是一个分层有向图的示例

需要找到的路径要求：

• 路径必须从第一层开始，结束于最后一层。
• 路径上不能有任何节点u、v，它们之间存在反向边e=(u,v)， 即路径上不能存在任何形成环的节点。

允许路径的示例

允许路径：p=(1,2,5,6,8,9)，因为这些节点之间没有反向边，即图中不存在仅由p中节点组成的环。

禁止路径的示例

禁止路径: p=(1,2,4,6,8,9)，因为存在反向边e=(4,1)，即存在一个环 c=(1,2,4,1)，其中所有节点都是p的一部分。

限制有向图的属性:

• 每个层至少包含一个节点。
• 只有当layer(v) = layer(u) + 1（即到下一层）时，才可以存在有向边e=(u,v)
• 只有当layer(u) >= layer(v) + 2（即至少两个层之前）时，才可以存在反向边e=(u,v)
• 始终至少存在一条“正常”路径从第一个节点到最后一个节点。
• 虽然可能不存在特殊路径（如上所述）。

我考虑了类似DFS的方法，或者拓扑排序（先忽略反向边）。但我找不到一个运行时间可行的算法。图可能会变得非常大（例如每层超过100个节点，有十多层）。如果存在复杂度合理的算法，有什么想法/提示吗？

上下文：这个图论问题是我正在尝试解决的另一个更复杂问题的（希望有用的）抽象。

编辑1：

以下是使用python+networkx建议的实现。请注意，图是以这样的方式构建的，即如果存在反向边e=(u,v)，则始终适用于u>v。用户数据文件太大无法发布（>17000行）。

def is_result(path, forbidden_pairs):
    for (u,v) in forbidden_pairs:
        if u in path and v in path:
            return False;
    return True;

def find_path(G, s, e):
    forbidden_pairs = set()
    for (u,v) in G.edges:
        if (u > v):
            forbidden_pairs.add((u,v))
    
    for (u,v) in forbidden_pairs:
        G.remove_edge(u,v)
    
    for path in nx.all_shortest_paths(G, s, e):
        if is_result(path, forbidden_pairs):
            return(path)

- srcnuzn

---

我非常确定从最大独立集到这个问题存在P时间约化，这将使得这个问题成为NP难问题。但这可能不适用于“更复杂”的问题，所以也许这并不是你要寻找的抽象化。 - Matt Timmermans

这不是一个答案，但在图论术语中，您要寻找的是有向图中的诱导路径。子图是通过选择一些节点和选择中节点之间的所有边（或弧）从图中诱导出来的。您想要找出是否存在两个特定节点之间的诱导路径。这可能有助于搜索答案。 - Dave

Answer 1

1. 识别所有潜在的反向边（如果 layer(u) >= layer(v) + 2，则 e=(u,v)）
2. 对于每个潜在的反向边，将节点 u、v 添加到“禁止配对列表”中
3. 从图中删除潜在的反向边
4. 按递增长度顺序确定源到目标的最短路径（参见 https://www.geeksforgeeks.org/find-paths-given-source-destination ）
5. 检查路径是否包含禁止配对。如果路径不包含任何禁止配对，则 DONE
6. 确定下一个最短路径（返回步骤 4）

示例图的规范化文本文件格式为带空格的文本文件。

n 1 1
n 2 2
n 3 2
n 4 3
n 5 3
n 6 4
n 7 5
n 8 5
n 9 6
l 1 2
l 1 3
l 2 4
l 2 5
l 3 5
l 3 4
l 4 1
l 4 6
l 5 6
l 6 7
l 7 9
l 8 9
s 1
e 9

将此输入Pathfinder (https://github.com/JamesBremner/PathFinder)，得到的结果是：

这是实现代码。

void cPathFinder::srcnuzn()
{
    // backup the full graph
    auto backup = myG;

    // identify and remove potential back edges
        std::vector<std::pair<int, int>> vforbidden;
        for (auto &l : links())
        {
            if (node(source(l)).myCost - node(target(l)).myCost >= 2)
            {

                // path must not contain this pair of nodes
                vforbidden.push_back(std::make_pair(source(l), target(l)));

                // remove the edge
                removeLink(source(l), target(l));
            }
        }

    try
    {
        // recursively visit all possible paths
        visitAllPaths(
            myStart, myEnd,
            [this, &vforbidden](int pathlength)
            {
                // this "visitor" is called whenever a possible path is found
                int prev = -1;
                bool fOK = true;
                for (int i = 0; i < pathlength; i++)
                {
                    int n = myPath[i];
                    if (prev < 0)
                    {
                        prev = n;
                        continue;
                    }

                    // check of path contains any node pairs forbidden by backedges
                    for (auto &f : vforbidden)
                    {
                        if (f.first == n && f.second == prev)
                        {
                            fOK = false;
                            break;
                        }
                    }
                    if( !fOK )
                        break;
                }
                if (fOK)
                {
                    // feasible path found, mark and throw wxception to escape from recursion
                    myPath.resize(pathlength);
                    throw std::domain_error("srcnuzn_ok");
                }

                // path is not feasible, return to continue recusion to next path
                return;
            });

        // all possible paths visited witn no feasible found
        std::cout << "no feasible path\n";
        myPath.clear();
    }

    catch (std::domain_error &e)
    {
        // esception thrown, indicating a feasible path found
        std::cout << "srcnuzn_ok ";
        for (auto n : myPath)
            std::cout << userName(n) << " ";
        std::cout << "\n";
    }

    // restore full graph
    myG = backup;
}

这里有一个图表，有8层，每层有3个节点和2条随机反向边。

在具有这些参数的不同随机图上运行算法4次，平均需要2.3毫秒才能完成。

8 layers, 3 nodes per layer, 2 back edges per layer = 2ms
10 layers, 10 nodes per layer, 4 back edges per layer = 16ms

- ravenspoint

---

让我更正之前的说法：“我的”伪代码实现没有“及时”终止，所以我不得不取消执行。对于造成的混淆，我很抱歉！目前，由于假期/度假，我的编程时间非常有限。当我再次更加可用时，我将发布一个干净的实现+用户数据集，以便我们可以重现这种行为并重新评估算法。 - srcnuzn

我fork了你的存储库并调整了我的用户数据（https://github.com/srcnuzn/PathFinder/）。使用这些数据和我对你的伪代码的实现（见上文），算法无法按时终止。我真的认为，这种对我的问题的抽象是不可行的，因为它会导致巨大的图形。 - srcnuzn

我已经运行了你的422节点数据集。它运行时间长的原因不是算法，而是graphviz需要很长时间才能完成生成可视化视图。对于大型数据集，我将禁用graphviz。 - ravenspoint

当禁用graphviz时，您的数据集在不到一秒的运行时间内完成。以下是结果：srcnuzn_ok 1 2 31 58 87 114 143 170 199 226 255 282 311 338 367 394 422 - ravenspoint

让我们在聊天中继续这个讨论。 - srcnuzn