Voronoi.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/graphalg/Dijkstra.h>
 
#include <map>
 
namespace ogdf {
 
 
template<typename T>
class Voronoi {
protected:
    NodeArray<edge> m_predecessor;
    NodeArray<T> m_distance;
    NodeArray<node> m_seedOfNode;
    std::map<node, ArrayBuffer<node>> m_nodeList;
    const Graph& m_graph;
    const List<node>& m_seeds;
 
    void computeVoronoiRegions(const Graph& G, const EdgeArray<T>& weights, const List<node>& seeds);
 
public:
    Voronoi(const Graph& G, const EdgeArray<T>& weights, const List<node>& seeds)
        : m_seedOfNode(G), m_nodeList(), m_graph(G), m_seeds(seeds) {
        computeVoronoiRegions(G, weights, seeds);
    }
 
    const Graph& getGraph() const { return m_graph; }
 
    const List<node>& getSeeds() const { return m_seeds; }
 
    edge predecessorEdge(node v) const { return m_predecessor[v]; }
 
    node predecessor(node v) const {
        edge tmp = predecessorEdge(v);
        return tmp ? tmp->opposite(v) : nullptr;
    }
 
    T distance(node v) const { return m_distance[v]; }
 
    node seed(node v) const { return m_seedOfNode[v]; }
 
    const ArrayBuffer<node>& nodesInRegion(node v) const {
        return m_nodeList.find(seed(v))->second;
    }
};
 
 
template<typename T>
void Voronoi<T>::computeVoronoiRegions(const Graph& G, const EdgeArray<T>& weights,
        const List<node>& seeds) {
    Dijkstra<T> sssp;
    sssp.call(G, weights, seeds, m_predecessor, m_distance);
 
    // extract Voronoi seeds for each node and Voronoi regions for each seed
    NodeArray<bool> processed(G, false);
    for (node seed : seeds) {
        processed[seed] = true;
        m_seedOfNode[seed] = seed;
        m_nodeList[seed].push(seed);
    }
 
    for (node u : G.nodes) {
        ArrayBuffer<node> foundNodes;
        node v;
        for (v = u; !processed[v]; v = predecessor(v)) {
            processed[v] = true;
            foundNodes.push(v);
        }
 
        for (node passedNode : foundNodes) {
            m_seedOfNode[passedNode] = m_seedOfNode[v];
            m_nodeList[m_seedOfNode[v]].push(passedNode);
        }
    }
}
 
}