有向图：寻找没有后边的特殊路径
Directed Graph: Find special path without backedge
我需要在有向图中找到一条路径（要求见下文），其节点可以分类为层。这些层对于图的结构很重要（图的属性见下文）
这种分层有向图的例子
需要查找的路径要求：
- 路径必须从第一层开始到最后一层结束。
- 路径中必须没有节点u,v，由backedgee=连接(u,v),
（即不能有圆，其节点都是路径的一部分）。
允许的路径示例
允许的路径：p=(1,2,5,6,8,9)，因为这些节点之间没有后边，即没有圆在图中，它只包含来自 p.
的节点
不允许的路径示例
不允许的路径：p=(1,2,4,6,8,9)，因为有一个 backedge e=(4,1 )，即有一个圆c=(1,2,4,1)，其中所有节点都是p[=76的一部分=].
限制有向图的属性：
- 每一层至少包含一个节点。
- 一条有向边e=(u,v)只能存在，如果 layer(v) = layer(u) + 1（即到下一层）
- 后边 e=(u,v) 只能存在，如果 layer(u) >= layer(v) + 2（即至少向后两层）
- 从第一个节点到最后一个节点总是至少有一条“正常”路径。
- 尽管可能不存在特殊路径（如上所述）。
我想到了类似 DFS 的方法，或拓扑排序（首先忽略后边）。但是我找不到具有可行运行时间的算法。图可能会变得很大（例如，每层超过 100 个节点，层数超过 10 层）。任何ideas/hints，如果存在合理复杂度的算法？
上下文：这个图论问题是我试图解决的另一个更复杂问题的抽象（希望有用）。
编辑 1:
下面是使用 python+networkx 所建议的实现。请注意，该图的构建方式是，如果存在后备边 e=(u,v)，则始终应用 u>v。用户数据文件太大 post（>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)
- 识别所有潜在的后边（ e=(u,v) if layer(u) >= layer(v) + 2 ]
- 对于每个潜在的后备边，将节点 u、v 添加到“禁止对”列表中
- 从图中删除潜在的后边
- 按长度递增的顺序确定从源到目的地的最短路径 (https://www.geeksforgeeks.org/find-paths-given-source-destination)
- 检查禁止对的路径。如果路径包含 none，则 DONE
- 确定下一条最短路径（循环回到第 4 步）
将示例图指定为 space 分隔文本文件
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
将此读入探路者 (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
我需要在有向图中找到一条路径（要求见下文），其节点可以分类为层。这些层对于图的结构很重要（图的属性见下文）
这种分层有向图的例子
需要查找的路径要求：
- 路径必须从第一层开始到最后一层结束。
- 路径中必须没有节点u,v，由backedgee=连接(u,v), （即不能有圆，其节点都是路径的一部分）。
允许的路径示例
允许的路径：p=(1,2,5,6,8,9)，因为这些节点之间没有后边，即没有圆在图中，它只包含来自 p.
的节点不允许的路径示例
不允许的路径：p=(1,2,4,6,8,9)，因为有一个 backedge e=(4,1 )，即有一个圆c=(1,2,4,1)，其中所有节点都是p[=76的一部分=].
限制有向图的属性：
- 每一层至少包含一个节点。
- 一条有向边e=(u,v)只能存在，如果 layer(v) = layer(u) + 1（即到下一层）
- 后边 e=(u,v) 只能存在，如果 layer(u) >= layer(v) + 2（即至少向后两层）
- 从第一个节点到最后一个节点总是至少有一条“正常”路径。
- 尽管可能不存在特殊路径（如上所述）。
我想到了类似 DFS 的方法，或拓扑排序（首先忽略后边）。但是我找不到具有可行运行时间的算法。图可能会变得很大（例如，每层超过 100 个节点，层数超过 10 层）。任何ideas/hints，如果存在合理复杂度的算法？
上下文：这个图论问题是我试图解决的另一个更复杂问题的抽象（希望有用）。
编辑 1:
下面是使用 python+networkx 所建议的实现。请注意，该图的构建方式是，如果存在后备边 e=(u,v)，则始终应用 u>v。用户数据文件太大 post（>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)
- 识别所有潜在的后边（ e=(u,v) if layer(u) >= layer(v) + 2 ]
- 对于每个潜在的后备边，将节点 u、v 添加到“禁止对”列表中
- 从图中删除潜在的后边
- 按长度递增的顺序确定从源到目的地的最短路径 (https://www.geeksforgeeks.org/find-paths-given-source-destination)
- 检查禁止对的路径。如果路径包含 none，则 DONE
- 确定下一条最短路径（循环回到第 4 步）
将示例图指定为 space 分隔文本文件
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
将此读入探路者 (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