graph.hpp

Go to the documentation of this file.

 
#include <fstream>
#include <functional>
#include <vector>
 
enum class AlgorithmAccuracy { APPROXIMATE, EXACT };
 
class Graph {
   private:
    size_t vertexCount;
 
    size_t vertexAndEdgeCount;
 
    std::vector<std::vector<int>> adjacencyMatrix;
 
    static constexpr size_t ESTIMATE_MULTIPLIER = 10;
 
    auto maxCliqueHelper(size_t currentVertex,
                         std::vector<size_t>& currentClique,
                         std::vector<std::vector<size_t>>& maxCliques,
                         AlgorithmAccuracy accuracy, size_t& currentExecution,
                         size_t executionLimit, auto adjacencyFunction) const
        -> void;
 
    [[nodiscard]] auto totalConnections(const std::vector<size_t>& clique) const
        -> size_t;
 
    [[nodiscard]] auto edgeCount(const std::vector<size_t>& clique) const
        -> size_t;
 
   public:
    Graph() : vertexCount{0}, vertexAndEdgeCount{0} {}
 
    explicit Graph(const std::vector<std::vector<int>>&& adjacencyMatrix);
 
    explicit Graph(std::istream& graphStream);
 
    explicit Graph(std::istream&& graphStream) : Graph{graphStream} {}
 
    [[nodiscard]] static auto fromFilename(const std::string& filename)
        -> Graph;
 
    [[nodiscard]] auto getVertexCount() const -> size_t { return vertexCount; }
 
    [[nodiscard]] auto toDotLang() const -> std::string;
 
    [[nodiscard]] auto operator[](size_t row) const -> std::vector<int>;
 
    friend auto operator<<(std::ostream& outputStream, const Graph& graph)
        -> std::ostream&;
 
    friend auto operator==(const Graph& lhs, const Graph& rhs) -> bool;
 
    [[nodiscard]] auto getSize() const -> size_t;
 
    [[nodiscard]] auto metricDistanceTo(
        const Graph& rhs,
        AlgorithmAccuracy accuracy = AlgorithmAccuracy::EXACT) const -> size_t;
 
    [[nodiscard]] auto modularProduct(const Graph& rhs) -> Graph;
 
    [[nodiscard]] auto maxClique(
        AlgorithmAccuracy accuracy = AlgorithmAccuracy::EXACT) const
        -> std::vector<size_t>;
 
    [[nodiscard]] auto modifiedMaxClique(
        AlgorithmAccuracy accuracy = AlgorithmAccuracy::EXACT) const
        -> std::vector<size_t>;
 
    [[nodiscard]] auto maxSubgraph(
        const Graph& rhs, AlgorithmAccuracy accuracy = AlgorithmAccuracy::EXACT)
        -> Graph;
 
    [[nodiscard]] auto maxCliqueGraph(AlgorithmAccuracy accuracy) const
        -> Graph;
 
    [[nodiscard]] auto subGraph(std::vector<size_t>& vertices) const -> Graph;
};