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

user_11203604 0
Viewed 374

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

I have the following graph enter image description here

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.

boost-graph graph-theory boost c++
2 Answers

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
user_165820

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 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 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"]
user_853710
Related