Program Listing for File Diameter.hpp¶

/*
 * Diameter.hpp
 *
 *  Created on: 19.02.2014
 *      Author: Daniel Hoske, Christian Staudt
 */

#ifndef NETWORKIT_DISTANCE_DIAMETER_HPP_
#define NETWORKIT_DISTANCE_DIAMETER_HPP_

#include <networkit/auxiliary/SignalHandling.hpp>
#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {
enum DiameterAlgo {
    AUTOMATIC,
    EXACT,
    ESTIMATED_RANGE,
    ESTIMATED_SAMPLES,
    ESTIMATED_PEDANTIC,
    automatic = AUTOMATIC, // this + following added for backwards compatibility
    exact = EXACT,
    estimatedRange = ESTIMATED_RANGE,
    estimatedSamples = ESTIMATED_SAMPLES,
    estimatedPedantic = ESTIMATED_PEDANTIC
};

class Diameter final : public Algorithm {

public:
    Diameter(const Graph &G, DiameterAlgo algo = DiameterAlgo::AUTOMATIC, double error = -1.f,
             count nSamples = 0);

    void run() override;

    std::pair<count, count> getDiameter() const;

private:
    const Graph *G;
    DiameterAlgo algo;
    double error;
    count nSamples;
    std::pair<count, count> diameterBounds;

    std::pair<edgeweight, edgeweight> estimatedDiameterRange(const Graph &G, double error);

    edgeweight exactDiameter(const Graph &G);

    edgeweight estimatedVertexDiameter(const Graph &G, count samples);

    edgeweight estimatedVertexDiameterPedantic(const Graph &G);

    edgeweight estimatedVertexDiameterPedantic2(const Graph &G);
};

} /* namespace NetworKit */

#endif // NETWORKIT_DISTANCE_DIAMETER_HPP_