Boost Kruskal minimum spanning tree algorithm -- undirected vs directed graph documentation

Solution 1:

I'd simplify the code Live

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>

using Graph =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                        boost::no_property,
                        boost::property<boost::edge_weight_t, double>>;

using Edge = Graph::edge_descriptor;

int main()
{
    Graph g(3); // 0..2

    /*auto [it, ok] =*/ add_edge(0, 1, {1}, g);
    add_edge(0, 2, {2}, g);
    add_edge(1, 0, {1}, g);
    add_edge(1, 2, {2}, g);
    add_edge(2, 0, {1}, g);
    add_edge(2, 1, {2}, g);

    auto cost = get(boost::edge_weight, g);
    std::vector<Edge> spanning_tree;
    kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

    std::cout << "MST Solution:\n";
    for (auto e : spanning_tree) {
        std::cout << e << ": " << cost[e] << "\n";
    }
}

If you insist on a loop to insert edges: Live

for (auto [i, j, c] : { std::tuple //
         {0, 1, 1.},
         {0, 2, 2.},
         {1, 0, 1.},
         {1, 2, 2.},
         {2, 0, 1.},
         {2, 1, 2.},
     })
{
    if (!add_edge(i, j, {c}, g).second)
        return 255;
}

The Question

If you don't meet the documented pre-conditions the output is unspecified. Unspecified doesn't mean it throws an exception (that would be specified). It might even accidentally (seem to) do the right thing.

The point is that the algorithm operates under the assumption that edges are - by definition - traversable in the reverse direction at the same cost. As soon as you deviate from that, the algorithm may give incorrect results. In fact, some algorithms might exhibit undefined behaviour (like, a Dijkstra with some weights negative might never complete).

You'd do better to

• Either convert your graph to be undirected
• satisfy the invariants of undirected graphs and verify that the algorithm works correctly for it
• Use an algorithm for MDST (Minimum Directed Spanning Tree), see e.g. Finding a minimum spanning tree on a directed graph