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

First of all, if I make any English mistake, sorry in advance.

I have the following graph

And I need to find all paths of an n length (4 vertices for example) starting only from "4K 2048 raw". I use C and I cannot change the language. I use the Boost Graph library and tried to understand their DFS visitor concept without success.

I even accept path like "4k 2048 raw" -> "4k 2048 raw" -> "4k 2048 raw" -> "4k 2048 raw" for example.

I use a graph like a generator. If anyone have a solution, with or without the BGL, thank you.

CodePudding user response：

Algorithm using depth first search ( 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

CodePudding user response：

Why not post the graph, and save your answerers 10 minutes of their life:

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;
}

Compare the result { 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; } " rel="nofollow noreferrer">online.

With BGL

You can, but I doubt it is really helpful as the algorithm you describe doesn't readily exist, or implementing it on the BFS/DFS visitors will be inefficient. Here's what it would look like to create a matching 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)));
}

Prints

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 ;
}

Which renders to 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 ; } " rel="nofollow noreferrer">the same

~~Note that I'm not even attempting to implementing the path search at this time~~.

Applying depth_first_visit doesn't really help us, because it doesn't visit any vertex twice, so you get only a minimal subset of the paths you're after:

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());

Prints

["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"]

Bespoke Using Standard Library

Using just the standard library (and libfmt since range-formatting is not yet in the standard):

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));
}

Output for 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"]