BlowupComponents.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/graphalg/steiner_tree/goemans/BlowupGraph.h>
 
//#define OGDF_STEINER_TREE_GOEMANS_BLOWUP_COMPONENTS_LOGGING
 
namespace ogdf {
namespace steiner_tree {
namespace goemans {
 
template<typename T>
class BlowupComponents {
protected:
    // To represent Gamma(X) [the set of all components in the blowup graph], we give
    //  - terminals, source and target the component id 0
    //  - all other nodes a component id > 0. Nodes with same id belong to the same component.
    // Note that this is also fine for 2-components with only one edge, since this
    // is a core edge and hence a dummy node is inserted.
    NodeArray<int> componentId;
    // We also save lists of terminals for each component in the specified array buffer.
    ArrayBuffer<ArrayBuffer<node>> componentTerminals;
    // To efficiently traverse the found component, we save the edge from the root of the component
    ArrayBuffer<edge> componentRootEdge;
    // Finally a component -> cost array.
    ArrayBuffer<T> componentCost;
 
    int maxId; // == the size of the arraybuffers
 
    void initializeComponent(edge rootEdge, const BlowupGraph<T>& blowupGraph) {
        List<node> queue;
        const node start = rootEdge->target();
        queue.pushBack(start);
        componentRootEdge.push(rootEdge);
        componentTerminals.push(ArrayBuffer<node>());
        auto& terms = componentTerminals[maxId];
        if (!blowupGraph.getOriginal(start)) { // start node is a core edge
            componentCost.push(blowupGraph.getCost(rootEdge));
        } else {
            componentCost.push(0);
        }
        T& cost = componentCost[maxId];
        ++maxId;
        while (!queue.empty()) {
            const node v = queue.popBackRet();
            componentId[v] = maxId;
            for (adjEntry adj : v->adjEntries) {
                const node w = adj->twinNode();
                if (componentId[w] < 0) {
                    // count coreEdge cost only once
                    if (blowupGraph.getOriginal(v)) { // v is no core edge
                        cost += blowupGraph.getCost(adj->theEdge());
                    }
                    if (blowupGraph.isTerminal(w)) {
                        terms.push(w);
                    } else {
                        queue.pushBack(w);
                    }
                }
            }
        }
#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_COMPONENTS_LOGGING
        std::cout << " * component with terminals " << terms << " starting with edge " << rootEdge
                  << " having cost " << cost << " and capacity "
                  << blowupGraph.getCapacity(rootEdge) << std::endl;
#endif
    }
 
public:
    BlowupComponents(const BlowupGraph<T>& blowupGraph)
        : componentId(blowupGraph.getGraph(), -1), maxId(0) {
        componentId[blowupGraph.getSource()] = 0;
        componentId[blowupGraph.getPseudotarget()] = 0;
        componentId[blowupGraph.getTarget()] = 0;
 
#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_COMPONENTS_LOGGING
        std::cout << "Finding components in blowup graph:" << std::endl;
#endif
        for (node t : blowupGraph.terminals()) {
            for (adjEntry rootAdj : t->adjEntries) {
                const edge rootEdge = rootAdj->theEdge();
                if (rootEdge->source() != t) {
                    continue;
                }
                const node r = rootAdj->twinNode();
                OGDF_ASSERT(r == rootEdge->target());
                if (componentId[r] < 0) {
                    initializeComponent(rootEdge, blowupGraph);
                }
            }
        }
 
        // now set terminals to id 0   [XXX: why dont we keep -1?]
        for (node t : blowupGraph.terminals()) {
            componentId[t] = 0;
        }
    }
 
    const ArrayBuffer<node>& terminals(int id) const {
        OGDF_ASSERT(id > 0);
        return componentTerminals[id - 1];
    }
 
    int id(node v) const { return componentId[v]; }
 
    const T& cost(int id) const {
        OGDF_ASSERT(id > 0);
        return componentCost[id - 1];
    }
 
    int size() const { return maxId; }
 
    edge rootEdge(int id) const {
        OGDF_ASSERT(id > 0);
        return componentRootEdge[id - 1];
    }
 
    void setRootEdge(int id, edge e) // beware of using!
    {
        OGDF_ASSERT(id > 0);
        componentRootEdge[id - 1] = e;
        OGDF_ASSERT(componentTerminals[id - 1].linearSearch(e->source()) != -1);
    }
};
 
}
}
}