在有向图中查找从根到所有顶点的给定长度的所有路径

Question

首先，如果我有任何英文错误，请提前道歉。

我有下图

而且我需要找到仅从 "4K 2048 raw" 开始的 n 长度的所有路径（例如 4 个顶点）。我使用 C++，但无法更改语言。我使用 Boost Graph 库并试图理解他们的 DFS 访问者概念但没有成功。

我什至接受像 "4k 2048 raw" -> "4k 2048 raw" -> "4k 2048 raw" -> "4k 2048 raw" 这样的路径。

我像生成器一样使用图表。如果有人有解决方案，有或没有 BGL，谢谢。

Answer 1

使用深度优先搜索 (DFS) 的算法

   SELECT N as ROOT
   DFS from N until a leaf node is reached
   SAVE path from ROOT to leaf
   SELECT M as second last node in just saved path
   LOOP
       IF M = ROOT
          BREAK
       DFS from M until a leaf node is reached
       SET P to path from ROOT to M to leaf
       IF Leaf != ROOT AND ( P length is required OR greater )
          SAVE P
       SET M = second last node in P


   // this gives all the paths from ROOT to leaf nodes
   // now find paths to non leaf nodes

   LOOP P over saved paths
       LOOP V over nodes in P, except last
           SET P to path from ROOT to V
           IF P length is required
               SAVE P
   REMOVE saved paths longer than required
   SORT saved paths by their last node
   REMOVE duplicates
   OUTPUT saved paths

Answer 2

为什么不 post 图表，并为您的回答者节省 10 分钟的生命：

digraph {
    a [label="4k 2048 raw" ];
    b [label="4k 128 denoising" ];
    c [label="4k 32 denoising" ];
    d [label="4k 512 raw" ];
    e [label="2k 2048 raw" ];
    f [label="4k 128 raw" ];
    g [label="4k 32 raw" ];
    h [label="1k 2048 raw" ];

    a -> { h; g; f; c; b; e; d; };
    b -> { h; c; f; e; d; g; }
    c -> { h; g; f; e; d; }
    d -> { e; f; g; h; }
    e -> { f; h; g; }
    f -> { h; g; }
    g -> { h; }

    // self edges
    a -> a; b -> b; c -> c; d -> d;
    e -> e; f -> f; g -> g; h -> h;
}

比较结果online。

有 BGL

可以，但我怀疑它是否真的有用，因为您描述的算法并不容易存在，或者在 BFS/DFS 访问者上实施它会效率低下。这是创建匹配 adjacency_list:

的样子

Live On Wandbox

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                std::string>;
using V = G::vertex_descriptor;

int main() {
    G graph;

    auto a = add_vertex("4k 2048 raw", graph);
    auto b = add_vertex("4k 128 denoising", graph);
    auto c = add_vertex("4k 32 denoising", graph);
    auto d = add_vertex("4k 512 raw", graph);
    auto e = add_vertex("2k 2048 raw", graph);
    auto f = add_vertex("4k 128 raw", graph);
    auto g = add_vertex("4k 32 raw", graph);
    auto h = add_vertex("1k 2048 raw", graph);

    for (auto n : {h, g, f, c, b, e, d}) add_edge(a,n,graph);
    for (auto n : {h, c, f, e, d, g})    add_edge(b,n,graph);
    for (auto n : {h, g, f, e, d})       add_edge(c,n,graph);
    for (auto n : {e, f, g, h})          add_edge(d,n,graph);
    for (auto n : {f, h, g})             add_edge(e,n,graph);
    for (auto n : {h, g})                add_edge(f,n,graph);
    for (auto n : {h})                   add_edge(g,n,graph);
    // self edges
    for(auto n: boost::make_iterator_range(vertices(graph)))
        add_edge(n, n, graph);

    write_graphviz(std::cout, graph,
                make_label_writer(get(boost::vertex_bundle, graph)));
}

版画

digraph G {
0[label="4k 2048 raw"];
1[label="4k 128 denoising"];
2[label="4k 32 denoising"];
3[label="4k 512 raw"];
4[label="2k 2048 raw"];
5[label="4k 128 raw"];
6[label="4k 32 raw"];
7[label="1k 2048 raw"];
0->7 ;
0->6 ;
0->5 ;
0->2 ;
0->1 ;
0->4 ;
0->3 ;
0->0 ;
1->7 ;
1->2 ;
1->5 ;
1->4 ;
1->3 ;
1->6 ;
1->1 ;
2->7 ;
2->6 ;
2->5 ;
2->4 ;
2->3 ;
2->2 ;
3->4 ;
3->5 ;
3->6 ;
3->7 ;
3->3 ;
4->5 ;
4->7 ;
4->6 ;
4->4 ;
5->7 ;
5->6 ;
5->5 ;
6->7 ;
6->6 ;
7->7 ;
}

呈现给 the same

~~请注意，我现在甚至没有尝试实施路径搜索~~。

应用 depth_first_visit 并没有真正帮助我们，因为它不会两次访问任何顶点，所以您只能得到您所追求的路径的最小子集：

Live On Compiler Explorer

auto pretty =
    std::ranges::views::transform([&graph](V n) { return graph[n]; });

PathRecord vis([=](Path const& p) {
    if (p.size() == 4)
        fmt::print("{}\n", p | pretty);
});

std::vector<boost::default_color_type> colors(num_vertices(graph));
depth_first_visit(graph, A, vis, colors.data());

版画

["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "4k 128 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "1k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "4k 32 raw"]
["4k 2048 raw", "4k 32 denoising", "2k 2048 raw", "2k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "2k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 128 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 32 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "1k 2048 raw"]
["4k 2048 raw", "4k 32 denoising", "4k 512 raw", "4k 512 raw"]

使用标准库定制

仅使用标准库（和 libfmt，因为 range-formatting 尚未在标准中）：

Live On Compiler Explorer

#include <array>
#include <cassert>
#include <vector>

enum { a, b, c, d, e, f, g, h, NUM };
using Graph = std::array<std::array<bool, NUM>, NUM>; // adjacency matrix
using Path = std::vector<int>;

Graph make_sample() {
    Graph r;
    for (int t : {h, g, f, c, b, e, d}) r[a][t] = true;
    for (int t : {h, c, f, e, d, g})    r[b][t] = true;
    for (int t : {h, g, f, e, d})       r[c][t] = true;
    for (int t : {e, f, g, h})          r[d][t] = true;
    for (int t : {f, h, g})             r[e][t] = true;
    for (int t : {h, g})                r[f][t] = true;
    for (int t : {h})                   r[g][t] = true;
    // self edges
    for (int n = a; n < NUM; ++n)
        r[n][n] = true;
    return r;
}

template <typename Out>
Out explore(Graph const& g, Path current, unsigned length, Out out) {
    if (length) {
        for (int n = a; n < NUM; ++n) {
            if (g[current.back()][n]) {
                current.push_back(n);
                explore(g, current, length - 1, out);
                current.pop_back();
            }
        }
    } else {
        *out++ = current;
    }
    return out;
}

template <typename Out>
Out paths(Graph const& g, int start, unsigned length, Out out) {
    assert(length >= 1);
    return explore(g, {start}, length -1, out);
}

#include <fmt/ranges.h>
#include <ranges>
#include <set>

auto pretty(auto const& paths) {
    using std::ranges::views::transform;
    std::array static constexpr names{
        "4k 2048 raw", "4k 128 denoising", "4k 32 denoising", "4k 512 raw",
        "2k 2048 raw", "4k 128 raw",       "4k 32 raw",       "1k 2048 raw",
    };

    return fmt::join( //
        paths | transform([](Path const& p) {
            auto name_of = [](int n) { return names.at(n); };
            return p | transform(name_of);
        }),
        "\n - ");
}

int main() {
    std::vector<Path> vec;
    std::set<Path>    set;

    Graph g = make_sample();
    paths(g, 0, 4, back_inserter(vec));
    paths(g, 0, 4, inserter(set, set.end()));

    fmt::print("Set: {}\n - {}\n", set.size(), pretty(set));
    fmt::print("Vec: {}\n - {}\n", vec.size(), pretty(vec));
}

length == 3

的输出

Set: 51
 - ["4k 2048 raw", "4k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 512 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 512 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "1k 2048 raw"]
Vec: 51
 - ["4k 2048 raw", "4k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 512 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 128 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 denoising", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 512 raw", "4k 512 raw"]
 - ["4k 2048 raw", "4k 512 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 512 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 512 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 512 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "2k 2048 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 128 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "4k 32 raw"]
 - ["4k 2048 raw", "2k 2048 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "4k 128 raw", "4k 128 raw"]
 - ["4k 2048 raw", "4k 128 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 128 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "4k 32 raw", "4k 32 raw"]
 - ["4k 2048 raw", "4k 32 raw", "1k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 2048 raw"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 128 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "4k 32 denoising"]
 - ["4k 2048 raw", "1k 2048 raw", "1k 2048 raw"]

在有向图中查找从根到所有顶点的给定长度的所有路径

Finding all path of given length in directed graph from a root to all vertices

c++

boost

graph-theory

boost-graph

有 BGL

使用标准库定制