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?

score 2 · Accepted Answer · answered Jan 22 '22 at 17:41

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

fair enough. I'd wish boost implementers could come up with some sort of debug mode assertion that throws an exception atleast when fed with the wrong graph type. There would not be any release mode performance penalty due to this. — Tryer, Jan 23 '22 at 03:56
That would merely prevent you from using your graph even if you KNOW the invariants to hold. So, rather than rigidly checking a concept (no concepts exist for directionality, see https://valelab4.ucsf.edu/svn/3rdpartypublic/boost/libs/graph/doc/graph_concepts.html#fig:graph-concepts) you could wish for an assertion that detects when preconditions are violated. However, often times that cannot be done without extra storage cost, Really, documentation is _the place_ for this. Just like how `x = a/b;` compiles even though b could be 0. — sehe, Jan 23 '22 at 12:39

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

1 Answers1

The Question