Program Listing for File MaxentStress.hpp¶

/*
 * MaxentStress.hpp
 *
 *  Created on: 22.01.2014
 *      Author: Henning Meyerhenke and Michael Wegner
 */

#ifndef NETWORKIT_VIZ_MAXENT_STRESS_HPP_
#define NETWORKIT_VIZ_MAXENT_STRESS_HPP_

#include <memory>

#include <networkit/algebraic/CSRMatrix.hpp>
#include <networkit/auxiliary/StringTools.hpp>
#include <networkit/distance/AlgebraicDistance.hpp>
#include <networkit/numerics/LinearSolver.hpp>
#include <networkit/viz/GraphLayoutAlgorithm.hpp>
#include <networkit/viz/Octree.hpp>

namespace NetworKit {

using CoordinateVector =
    std::vector<Vector>; // more meaningful and shorter name for coordinates stored by dimension

struct ForwardEdge {
    node head;
    edgeweight weight;
};

class MaxentStress final : public GraphLayoutAlgorithm<double> {
public:
    enum GraphDistance { EDGE_WEIGHT, ALGEBRAIC_DISTANCE };

    enum LinearSolverType {
        LAMG,
        CONJUGATE_GRADIENT_IDENTITY_PRECONDITIONER,
        CONJUGATE_GRADIENT_DIAGONAL_PRECONDITIONER
    };

    struct ResultStats {
        double rhsTime = 0.0;
        double approxEntropyTerm = 0.0;
        double solveTime = 0.0;
    };

    MaxentStress(const Graph &G, count dim, count k, double tolerance,
                 LinearSolverType linearSolverType = LAMG, bool fastComputation = false,
                 GraphDistance graphDistance = EDGE_WEIGHT);

    MaxentStress(const Graph &G, count dim, const std::vector<Point<double>> &coordinates, count k,
                 double tolerance, LinearSolverType linearSolverType = LAMG,
                 bool fastComputation = false, GraphDistance graphDistance = EDGE_WEIGHT);

    ~MaxentStress() override = default;

    void run() override;

    void scaleLayout();

    double computeScalingFactor();

    double fullStressMeasure();

    double maxentMeasure();

    double meanDistanceError();

    double ldme();

    void setQ(double q) { this->q = q; }

    void setAlpha(double alpha) { this->alpha = alpha; }

    void setAlphaReduction(double alphaReduction) { this->alphaReduction = alphaReduction; }

    void setFinalAlpha(double finalAlpha) { this->finalAlpha = finalAlpha; }

    void setConvergenceThreshold(double convThreshold) {
        this->convThreshold = convThreshold * convThreshold;
    }

    double getRhs() { return this->resultStats.rhsTime; };

    double getApproxEntropyTerm() { return this->resultStats.approxEntropyTerm; };

    double getSolveTime() { return this->resultStats.solveTime; };

private:
    ResultStats runAlgo();

    LinearSolver<CSRMatrix> &solver;

    ResultStats resultStats;

    double q, alpha, alphaReduction, finalAlpha, convThreshold;

    bool coordinatesProvided;

    bool fastComputation;

    count maxSolvesPerAlpha;

    std::vector<std::vector<ForwardEdge>> knownDistances;

    count knownDistancesCardinality;

    count dim;

    bool hasRun;

    bool isConverged(const CoordinateVector &newCoords, const CoordinateVector &oldCoords);

    void setupWeightedLaplacianMatrix();

    void computeCoordinateLaplacianTerm(const CoordinateVector &coordinates, CoordinateVector &rhs);

    CoordinateVector computeRepulsiveForces(const CoordinateVector &coordinates,
                                            CoordinateVector &b) const;

    void approxRepulsiveForces(const CoordinateVector &coordinates, const Octree<double> &octree,
                               double theta, CoordinateVector &b) const;

    void randomInitCoordinates(CoordinateVector &coordinates) const;

    void randomSphereCoordinates(CoordinateVector &coordinates) const;

    double squaredDistance(const CoordinateVector &coordinates, index i, index j) const;

    inline double distance(const CoordinateVector &coordinates, const index i,
                           const index j) const {
        return std::sqrt(squaredDistance(coordinates, i, j));
    }

    double squaredDistance(const CoordinateVector &coordinates1,
                           const CoordinateVector &coordinates2, index i, index j) const;

    inline double distance(const CoordinateVector &coordinates1,
                           const CoordinateVector &coordinates2, const index i,
                           const index j) const {
        return std::sqrt(squaredDistance(coordinates1, coordinates2, i, j));
    }

    double squaredLength(const CoordinateVector &coordinates, index i) const;

    inline double length(const CoordinateVector &coordinates, const index i) const {
        return std::sqrt(squaredLength(coordinates, i));
    }

    inline double weightingFactor(double edgeWeight) const {
        return 1.0 / (edgeWeight * edgeWeight);
    }

    inline double sign(const double value) const { return (value >= 0.0) - (value < 0.0); }

    inline Point<double> getPoint(const CoordinateVector &coordinates, index i) const {
        Point<double> p(coordinates.size());
        for (index d = 0; d < p.getDimensions(); ++d) {
            assert(coordinates[d].getDimension() > i);
            p[d] = coordinates[d][i];
        }

        return p;
    }

    void computeKnownDistances(count k, GraphDistance graphDistance);

    void addKNeighborhoodOfVertex(node u, count k);

    void computeAlgebraicDistances(const Graph &graph, count k);
};

} /* namespace NetworKit */
#endif // NETWORKIT_VIZ_MAXENT_STRESS_HPP_