FullComponentGeneratorCaller.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/graphalg/MinSteinerTreeModule.h>
#include <ogdf/graphalg/steiner_tree/FullComponentDecisions.h>
 
namespace ogdf {
template<typename T>
class EdgeWeightedGraph;
 
namespace steiner_tree {
 
template<typename T>
class FullComponentGeneratorCaller {
public:
    static void computeDistanceMatrix(NodeArray<NodeArray<T>>& distance,
            NodeArray<NodeArray<edge>>& pred, const EdgeWeightedGraph<T>& graph,
            const List<node>& terminals, const NodeArray<bool>& isTerminal, int restricted);
};
 
template<typename T>
void FullComponentGeneratorCaller<T>::computeDistanceMatrix(NodeArray<NodeArray<T>>& distance,
        NodeArray<NodeArray<edge>>& pred, const EdgeWeightedGraph<T>& graph,
        const List<node>& terminals, const NodeArray<bool>& isTerminal, int restricted) {
    if (steiner_tree::FullComponentDecisions::shouldUseDijkstra(restricted, graph.numberOfNodes(),
                graph.numberOfEdges(), terminals.size())) {
        if (restricted <= 3) {
            // for 2- and 3-restricted computations, it is ok to use SSSP from all terminals
            MinSteinerTreeModule<T>::allTerminalShortestPaths(graph, terminals, isTerminal,
                    distance, pred);
        } else {
            MinSteinerTreeModule<T>::allNodeShortestPaths(graph, terminals, isTerminal, distance,
                    pred);
        }
    } else {
        MinSteinerTreeModule<T>::allPairShortestPaths(graph, isTerminal, distance, pred);
    }
}
 
}
}