tarjan.h

Go to the documentation of this file.

#ifndef GRAPHLIB_ALGORITHMS_TARJAN_H
#define GRAPHLIB_ALGORITHMS_TARJAN_H
 
#include <functional>
#include <map>
#include <stack>
 
#include "GraphLib/internal/concepts.h"

 
namespace GraphLib {


template <Internal::valid_directed_graph_type G>
std::vector<std::vector<typename G::id_type>> tarjan(const G& graph)
{
    using id_type = typename G::id_type;
 
    std::vector<std::vector<id_type>> sccs;
    std::map<id_type, int> disc; // discovery values; Order, in der die Nodes besucht wurden
    std::map<id_type, int> low;  // niedrigste erreichbare discovery value aka lowlink value
    std::map<id_type, bool> on_stack;
    std::stack<id_type> st;
    int time = 0;
 
    std::function<void(id_type)> strongconnect = [&](id_type node) {
        disc[node] = low[node] = ++time;
        st.push(node);
        on_stack[node] = true;
 
        // starte DFS für Nachfolger
        for (id_type neighbor : graph.get_neighbors(node)) {
            if (disc.find(neighbor) == disc.end()) {
                // Nachbar noch nicht besucht
                strongconnect(neighbor);
                low[node] = std::min(low[node], low[neighbor]);
            } else if (on_stack[neighbor]) {
                // Update low link value nur wenn nachbar auf stack
                low[node] = std::min(low[node], disc[neighbor]);
            }
        }
 
        // Falls node root von SCC, poppe Stack und erschaffe component;
        // geschieht, falls die discovery order gleich des lowlink value ist,
        // also falls die Node sich selber erreichen kann, nachdem DFS durch ist.
        if (low[node] == disc[node]) {
            std::vector<id_type> component;
            id_type w;
            do {
                w = st.top();
                st.pop();
                on_stack[w] = false;
                component.push_back(w);
            } while (w != node);
            sccs.push_back(component);
        }
    };
 
    // Finde SCCs für jede Node; Nodes, die schon teil einer SCC sind und eine disc-value haben, werden ignoriert
    for (const auto& node : graph.get_nodes()) {
        if (disc.find(node) == disc.end()) {
            strongconnect(node);
        }
    }
 
    return sccs;
}

} // namespace GraphLib
 
#endif