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

Question

Per the documentation, the minimum spanning tree algorithm implemented in boost should work only on undirected graphs. Yet, the following code that provides a directed graph as input to the algorithm seems to work just fine: (while building on MSVC Visual Studio 2019, there are no warnings related to boost)

#include <boost/property_map/property_map.hpp>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
using namespace boost;
typedef adjacency_list <vecS, vecS, directedS, no_property,
    property<edge_weight_t, double>>
    Graph_vvd_MST;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits_vvd;
property_map<Graph_vvd_MST, edge_weight_t>::type cost;
typedef Traits_vvd::edge_descriptor Edge;
std::vector < Edge > spanning_tree;
int main() {
    Graph_vvd_MST g;
    add_vertex(g);//0 th index vertex
    add_vertex(g);// 1 index vertex
    add_vertex(g);// 2 index vertex
    cost = get(edge_weight, g);
    //Add directed arcs
    for(int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            if (i == j)
                continue;
            std::pair<Traits_vvd::edge_descriptor, bool> AE = add_edge(i, j, g);
            assert(AE.second);
            if (i == 0 && j == 1)               cost[AE.first] = 1;
            if (i == 0 && j == 2)               cost[AE.first] = 2;
            if (i == 1 && j == 0)               cost[AE.first] = 1;
            if (i == 1 && j == 2)               cost[AE.first] = 2;
            if (i == 2 && j == 0)               cost[AE.first] = 1;
            if (i == 2 && j == 1)               cost[AE.first] = 2;
        }
    kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
    printf("MST Solution:\n");
    for (std::vector < Edge >::iterator ei = spanning_tree.begin();
        ei != spanning_tree.end(); ++ei) {
        int fr = source(*ei, g);
        int to = target(*ei, g);
        double cst = cost[*ei];
        printf("[%d %d]: %f \n", fr, to, cst);
    }
    getchar();
}

The code above generates the following bidirectional graph:

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?

Answer 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