graphs.hpp

Go to the documentation of this file.

/*************************************************************************
 *
 *  Project
 *                         _____ _____  __  __ _____
 *                        / ____|  __ \|  \/  |  __ \
 *  ___  _ __   ___ _ __ | |  __| |__) | \  / | |__) |
 * / _ \| '_ \ / _ \ '_ \| | |_ |  ___/| |\/| |  ___/
 *| (_) | |_) |  __/ | | | |__| | |    | |  | | |
 * \___/| .__/ \___|_| |_|\_____|_|    |_|  |_|_|
 *      | |
 *      |_|
 *
 * Copyright (C) Akiel Aries, <akiel@akiel.org>, et al.
 *
 * This software is licensed as described in the file LICENSE, which
 * you should have received as part of this distribution. The terms
 * among other details are referenced in the official documentation
 * seen here : https://akielaries.github.io/openGPMP/ along with
 * important files seen in this project.
 *
 * You may opt to use, copy, modify, merge, publish, distribute
 * and/or sell copies of the Software, and permit persons to whom
 * the Software is furnished to do so, under the terms of the
 * LICENSE file. As this is an Open Source effort, all implementations
 * must be of the same methodology.
 *
 *
 *
 * This software is distributed on an AS IS basis, WITHOUT
 * WARRANTY OF ANY KIND, either express or implied.
 *
 ************************************************************************/
 
#ifndef __GRAPHS_HPP__
#define __GRAPHS_HPP__
 
#include <cstdint>
// #include <limits>
#include <set>
#include <stack>
#include <vector>
 
namespace gpmp {
 
/*
 * @class Graph
 * @brief Graph class containing several utility methods and algorithms
 */
class Graph {
  public:
    int vertices;
    std::vector<std::vector<std::pair<int, int>>> adj_list;
 
    Graph(int v) : vertices(v), adj_list(v) {
    }
 
    void add_edge(int v, int w, int weight);
 
    void dfs(int start);
 
    void dfs_rec(int v, std::vector<bool> &visited);
 
    void bfs(int start);
 
    void dijkstra(int start);
 
    void bellman_ford(int start);
 
    std::vector<std::pair<int, std::pair<int, int>>> kruskal();
 
    void floyd_warshall();
 
    void topo_sort();
 
    std::vector<std::vector<int>> connected_components();
 
    bool is_bipartite();
 
    std::vector<double> betweenness_centrality();
 
    bool has_hamiltonian_circuit();
 
    bool has_eulerian_path();
 
    int eccentricity(int vertex);
 
    int radius();
 
    std::vector<int> greedy_coloring();
 
    int chromatic_number();
 
    std::vector<std::pair<int, int>> match_cardinality();
 
    std::vector<std::pair<int, int>> match_wt();
 
    bool is_planar();
 
    void planar_gen(int num_vertices, double radius);
 
    bool has_k5();
 
    bool has_k33();
 
    bool is_k33(const std::set<int> &k_vertices);
 
    double euclid_dist(const std::pair<double, double> &point1,
                       const std::pair<double, double> &point2);
 
    std::vector<uint64_t> compress();
 
    void decompress(const std::vector<uint64_t> &compressed);
 
  private:
    std::vector<bool> is_matched;
    void topo_sort_util(int v,
                        std::vector<bool> &visited,
                        std::stack<int> &topo_stack);
 
    int find(std::vector<int> &parent, int i);
 
    void union_sets(std::vector<int> &parent, int x, int y);
 
    void dfs_connected_components(int v,
                                  std::vector<bool> &visited,
                                  std::vector<int> &component);
 
    int choose_random_neighbor(int vertex);
 
    bool hamiltonian_circuit_util(int v,
                                  std::vector<bool> &visited,
                                  std::vector<int> &path,
                                  int count);
};
 
} // namespace gpmp
 
#endif