Boost BGL BFS Find all unique paths from Source to Target

Question

I am using Boost BGL C++ and I need the Graph to do a BFS from a Source vertex to a target vertex and return all the unique paths.

Right now, I thought of a way to use a filtered graph to get a subset of the graph containing paths from source to target but i realised that it was basically not filtering since the filtered graph included vertex that are visited but not part of a path from source to target. Is there any way to get this information or a different approach is better?

Code for reference:

boost::filtered_graph<DirectedGraph, boost::keep_all, std::function<bool(VertexDescr)>> Graph::getUniquePathsFromSource(VertexDescr source, VertexDescr target, DirectedGraph const & g)
{
    std::vector<double> distances(num_vertices(g));
    std::vector<boost::default_color_type> colormap(num_vertices(g));

    // Run BFS and record all distances from the source node
    breadth_first_search(g, source,
        visitor(make_bfs_visitor(boost::record_distances(distances.data(), boost::on_tree_edge())))
        .color_map(colormap.data())
    );

    for (auto vd : boost::make_iterator_range(vertices(g)))
        if (colormap.at(vd) == boost::default_color_type{})
            distances.at(vd) = -1;

    distances[source] = -2;

    boost::filtered_graph<DirectedGraph, boost::keep_all, std::function<bool(VertexDescr)>>
        fg(g, {}, [&](VertexDescr vd) { return distances[vd] != -1; });

    // Print edge list
    std::cout << "filtered out-edges:" << std::endl;
    std::cout << "Source Vertex: " << source << std::endl;

    auto ei = boost::edges(fg);

    typedef boost::property_map<DirectedGraph, boost::edge_weight_t>::type WeightMap;
    WeightMap weights = get(boost::edge_weight, fg);

    for (auto it = ei.first; it != ei.second; ++it)
    {
        if (source != boost::target(*it, g)) {
            std::cout << "Edge Probability " << *it << ": " << get(weights, *it) << std::endl;
        }
    }

    return fg;
}

Input (vertex1, vertex2, weight):

0 1 0.001
0 2 0.1
0 3 0.001
1 5 0.001
2 3 0.001
3 4 0.1
1 482 0.1
482 635 0.001
4 705 0.1
705 5 0.1
1 1491 0.01
1 1727 0.01
1 1765 0.01

Output (For Source = 0, Target = 5):

Source Vertex: 0
Edge Probability (0,1): 0.001
Edge Probability (0,2): 0.1
Edge Probability (0,3): 0.001
Edge Probability (1,5): 0.001
Edge Probability (1,482): 0.1
Edge Probability (1,1491): 0.01
Edge Probability (1,1727): 0.01
Edge Probability (1,1765): 0.01
Edge Probability (2,3): 0.001
Edge Probability (3,4): 0.1
Edge Probability (4,705): 0.1
Edge Probability (482,635): 0.001
Edge Probability (705,5): 0.1

Expected Output:

0->1->5
0->3->4->705->5
0->2->3->4->705->5

Answer 1

I wouldn't use the BFS algorithm because it uses colormaps to track visited nodes. However, if you want all distinct paths you will not want to skip already-visited nodes (because you may skip alternative paths then).

Instead, I'd implement a brute-force breadth-first recursive algorithm that simply visits all adjacent nodes unless they're already in the current path.

All state required is the current path.

The idea is explained in more detail here: https://www.quora.com/How-should-I-find-all-distinct-simple-paths-between-2-given-nodes-in-an-undirected-graph

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp> // print_graph
using namespace boost;
using Graph = adjacency_list<vecS, listS, directedS, property<vertex_index_t, int>, property<edge_weight_t, double> >;
Graph read_graph();

using Vertex = Graph::vertex_descriptor;
using Path = std::vector<Vertex>;

template <typename Report>
void all_paths_helper(Vertex from, Vertex to, Graph const& g, Path& path, Report const& callback) {
    path.push_back(from);

    if (from == to) {
        callback(path);
    } else {
        for (auto out : make_iterator_range(out_edges(from, g))) {
            auto v = target(out, g);
            if (path.end() == std::find(path.begin(), path.end(), v)) {
                all_paths_helper(v, to, g, path, callback);
            }
        }
    }

    path.pop_back();
}

template <typename Report>
void all_paths(Vertex from, Vertex to, Graph const& g, Report const& callback) {
    Path state;
    all_paths_helper(from, to, g, state, callback);
}

int main() {
    auto g = read_graph();
    print_graph(g, std::cout);

    auto by_vertex_id = [&](int id) {
        return *find_if(vertices(g), [&](Vertex vd) { return id == get(vertex_index, g, vd); });
    };

    all_paths(by_vertex_id(0), by_vertex_id(5), g, [&](Path const& path) {
            std::cout << "Found path ";
            for (auto v : path)
                std::cout << get(vertex_index, g, v) << " ";
            std::cout << "\n";
        });
    std::cout.flush();
}

// immaterial to the task, reading the graph
Graph read_graph() {
    std::istringstream iss(R"(
        0 1 0.001
        0 2 0.1
        0 3 0.001
        1 5 0.001
        2 3 0.001
        3 4 0.1
        1 482 0.1
        482 635 0.001
        4 705 0.1
        705 5 0.1
        1 1491 0.01
        1 1727 0.01
        1 1765 0.01)");

    Graph g;
    auto vertex = [&,idx=std::map<int,Vertex>{}](int id) mutable {
        auto it = idx.find(id);
        if (it != idx.end())
            return it->second;
        return idx.emplace(id, add_vertex(id, g)).first->second;
    };

    for (std::string line; getline(iss, line);) {
        std::istringstream ls(line);
        int s,t; double w;
        if (ls >> s >> t >> w) {
            add_edge(vertex(s), vertex(t), w, g);
        } else {
            std::cerr << "Skipped invalid line '" << line << "'\n";
        }
    }

    return g;
}

Which prints:

1 --> 5 482 1491 1727 1765 
0 --> 1 2 3 
2 --> 3 
3 --> 4 
5 --> 
4 --> 705 
482 --> 635 
635 --> 
705 --> 5 
1491 --> 
1727 --> 
1765 --> 
Found path 0 1 5 
Found path 0 2 3 4 705 5 
Found path 0 3 4 705 5