Combinations without repetition of elements in a list

Question

I have an undirected boost::adjacency_graph. Given a vertex, I want to find all the pair of edges for which the vertex is the source.

As an example, if I have

0 --- 1 --- 2

the pairs for 0 and 2 will be the empty set and for 1 will be ((1,0), (1,2))

for

0 --- 1 --- 2  
       \--- 3

the pairs for 0, 2 and 3 will the empty set, while for 1 will be

((1,0), (1,2))
((1,0), (1,3))
((1,2), (1,3))

I was thinking about something like

std::vector<std::pair<edge, edge> edges;
for (const auto vertex : boost::make_iterator_range(boost::vertices(graph))) {
    for (const auto outEdge1 : boost::make_iterator_range(boost::out_edges(vertex, graph))) {
            for (const auto outEdge2 : boost::make_iterator_range(boost::out_edges(vertex, graph))) {
                if (outEdge != outEdge2) edges.push_back(outEdge1, outEdge2);
       }
   }
}

but this will fail, as it will add for example ((1,0), (1, 2)) and ((1,2), (1, 0))

How can I avoid that? I think this is just the combinations without repetition of the out edges for the vertex

Given the out edges

(1,0) 
(1,2)
(1,3)

How can I get the combinations?

Answer 1

To do this cleanly, I'd love to use ranges and a combinations algorithm. Sadly, none is standardized, so we'd need to implement something ourselves using e.g. next_combination described here (and in many other places).

However, in the interest of quick demonstration, you could write it as a filtered cartesian product:

This uses Ranges-v3 as the "new" cartesian_product is only a standards proposal yet

for(auto v : make_iterator_range(vertices(g))) {
    auto ee    = copy_range<EE>(make_iterator_range(out_edges(v, g)));
    auto combi = v::cartesian_product(ee, ee) | v::filter([](auto&& p) {
                     auto& [a, b] = p;
                     return a < b;
                 });

    fmt::print("Edge pairs from {}: {}\n", v, fmt::join(combi, "\n\t"));
}

As a bout of completely misplaced of premature optimization, I made EE a small_vector

This prints Live On Compiler Explorer

Edge pairs from 0:
Edge pairs from 1: ((1,0), (1,2))
        ((1,0), (1,3))
        ((1,2), (1,3))
Edge pairs from 2:
Edge pairs from 3:

Live Demo

Live On Compiler Explorer

#include <boost/container/small_vector.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
#include <range/v3/all.hpp>
using boost::make_iterator_range;
namespace r = ranges;
namespace v = r::views;

int main() {
    using G  = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    using E  = G::edge_descriptor;
    using EE = boost::container::small_vector<E, 10>; // premature optimization :)
    G g;

    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(1, 3, g);
    write_graphviz(std::cout, g);

    for(auto v : make_iterator_range(vertices(g))) {
        auto ee    = copy_range<EE>(make_iterator_range(out_edges(v, g)));
        auto combi = v::cartesian_product(ee, ee) | v::filter([](auto&& pair) {
                         auto& [a, b] = pair;
                         return a < b;
                     });

        fmt::print("Edge pairs from {}: {}\n", v, fmt::join(combi, "\n\t"));
    }
}

Full output

graph G {
0;
1;
2;
3;
0--1 ;
1--2 ;
1--3 ;
}
Edge pairs from 0: 
Edge pairs from 1: ((1,0), (1,2))
    ((1,0), (1,3))
    ((1,2), (1,3))
Edge pairs from 2: 
Edge pairs from 3: