Boost Graph Library - Minimum Spanning Tree of a Directed Graph

Question

I have a problem that requires me to find the minimum spanning tree of a directed graph in Boost Graph Library.

My first try was to use the depth first search and DFS-visitor. My plan was to ignore all the edges except the tree edges callback. This doesn't work and I give the example below on why.

My question is if I can make my dfs-visitor create a minimum spanning tree of a directed graph in BGL.

There are algorithms for it and has been discussed here (Finding a minimum spanning tree on a directed graph) and I can't tell if it's been implemented for BGL or not or it's just a simple modification of something that's already in BGL.

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/depth_first_search.hpp>


struct my_visitor : public boost::dfs_visitor<>
{
    template <class Edge, class Graph>
    void back_edge(Edge e, const Graph&) 
    {
        std::cout << "Back edge: " << e << std::endl;
    }

    template <class Edge, class Graph>
    void forward_or_cross_edge(Edge u, const Graph& g)
    {
        std::cout << "Forward or cross edge: " << u << std::endl;
    }

    template <class Edge, class Graph>
    void tree_edge(Edge u, const Graph& g)
    {
        std::cout << "Tree Edge: " << u << std::endl;
    }
};


int main()
{
    using namespace boost;

    typedef boost::adjacency_list< listS, vecS, bidirectionalS > digraph;

    // Construct the directed graph
    digraph g(2);

    add_edge(1, 0, g);
    //add_edge(0, 1, g);

    my_visitor vis2;
    boost::depth_first_search(g, visitor(vis2));

    return 0;
}

Here is the example that fails. If I have the following directed graph

digraph G {
0;
1;
1->0 ;
}

In depth first search dfs-visitor, 1->0 is classified as a forward edge.

If the graph was changed so that the edge is 0->1, then it is a tree edge.

From the strict definition of the forward edge and the source code of DFS, since vertex 0 is visited before vertex 1, it is a forward edge.

However, the edge 1->0 is still a tree edge in a technical sense and from the definition given in their page as http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/graph_theory_review.html.

Forward edges are non-tree edges (u,v) that connect a vertex u to a descendant v in a search tree.

So, is there a simple solution in BGL or do I have to implement one of the algorithms in BGL for it?

Answer 1

The problem you are dealing with is, as you may already know, the search for a spanning arborescence of minimum weight as we are dealing with directed graphs. An arborescence is a graph with a designated root vertex r such that all other vertices are reachable from r, i.e. there exists a path from r to all other vertices in the graph.

Unfortunately there is no algorithm in the Boost Graph Library which solves this problem, so you need to use either a 3rd party implementation like this one or implement one yourself. The implementation (by atofigh on github.com) given above uses Edmond's algorithm, which is a popular algorithm for solving the spanning arborescence problem.

Keep in mind that algorithms like Kruskal's algorithm or Prim's algorithm do not work on directed graphs due to the cut property not working on directed graphs.

Answer 2

I ended up using Edmonds's Algorithm from here. Thanks HueHang but I ended up finding the algorithm before and using it before I got your reply. The question remained unanswered for about 3 weeks.

Here is my simple test program using the edmonds_optimum_branching.hpp.

#include <iostream>
#include <vector>
#include <utility>
#include <iterator>
#include <cerrno>
#include <boost/concept_check.hpp>
#include <boost/operators.hpp>
#include <boost/multi_array.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>

#include "edmonds_optimum_branching.hpp"

typedef boost::property<boost::edge_weight_t, double>       EdgeProperty;
typedef boost::adjacency_list<boost::listS,
                              boost::vecS,
                              boost::directedS,
                              boost::no_property,
                              EdgeProperty>                 Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor       Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor         Edge;

void main()
{
    const int N = 3;
    Graph G(N);

    std::vector<Vertex> the_vertices;
    BOOST_FOREACH (Vertex v, vertices(G))
        the_vertices.push_back(v);

    add_edge(the_vertices[0], the_vertices[2], 1.0, G);
    add_edge(the_vertices[2], the_vertices[1], 1.0, G);
    add_edge(the_vertices[1], the_vertices[0], 1.0, G);

    std::vector<Edge> branching;
    edmonds_optimum_branching<true, false, false>(G,
        get(boost::vertex_index_t(), G),
        get(boost::edge_weight_t(), G),
        static_cast<Vertex *>(0),
        static_cast<Vertex *>(0),
        std::back_inserter(branching));

    for each (Edge e in branching)
        std::cout << "(" << boost::source(e, G) << ", " << boost::target(e, G) << ")\t" << std::endl;
}

I get the correct answer as (2, 1) and (0, 2) when the run the sample code.

The algorithm returns the edges for the optimum branching. It also has weighted edges and can find the minimum or maximum weight tree. I just use weight 1 as in the example above since I don't need weighted graphs. It can also pick the root for the arborescence.