Per the

The output of the code is correctly:

MST Solution:
[0 1]: 1.000000
[2 0]: 1.000000

Is it the case that the document is not updated and in recent boost versions, the algorithm can actually work with directed graphs?

CodePudding user response：

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