Problem definition.

In the Steiner tree problem we are given the set of nonterminals, the set of terminals and the metric m. Our goal is to find a minimum cost tree connecting all terminals (it can possibly contain some nonterminal nodes).

Solution

This is an implementation of the standard greedy approach. We consider a graph composed only out of the terminal nodes. The distances between terminal nodes are equal to the shortest path distance between these terminals in the original graph. We compute the minimum spanning tree T in this graph and lift the result tree to the original graph. We use a fast implementation of this approach proposed in [15], which does not build this graph explicitly, but only finds Voronoi regions around terminals.

If the input graph is not connected we return Steiner trees for all connected components. The value returned by the algorithm is a pair containing: the weight of the tree, and the lower bound on the weight of the optimal tree (equal to half of sum of distances in T).

Example

#include "test/test_utils/sample_graph.hpp"
#include "paal/greedy/steiner_tree_greedy.hpp"
#include <iostream>
int main() {
    typedef sample_graphs_metrics SGM;
    auto g = SGM::get_graph_steiner();
    auto index = get(boost::vertex_index, g);
    typedef boost::graph_traits<decltype(g)>::edge_descriptor Edge;
    std::set<Edge> steinerEdges;
    std::vector<int> color(num_vertices(g));
    {
        auto c = &color[0];
        put(c, SGM::A, paal::Terminals::TERMINAL);
        put(c, SGM::B, paal::Terminals::TERMINAL);
        put(c, SGM::C, paal::Terminals::TERMINAL);
        put(c, SGM::D, paal::Terminals::TERMINAL);
        put(c, SGM::E, paal::Terminals::NONTERMINAL);
    }
    paal::steiner_tree_greedy(
        g, std::inserter(steinerEdges, steinerEdges.begin()),
        boost::vertex_color_map(
            boost::make_iterator_property_map(color.begin(), index)));
    auto weight = get(boost::edge_weight, g);
    auto sum = 0;
    for (auto e : steinerEdges) {
        sum += get(weight, e);
    }
    std::cout << "result " << sum << std::endl;
}

example file is steiner_tree_greedy_example.cpp

Approximation Ratio equals 2

Complexity

Complexity of the algorithm is \(O(|E|*\log(|V|))\) where E is the number of edges and V is the number of vertices.

Memory complexity of the algorithm is \(O(|E|)\).

References

The algorithm is described in [15].