GraphUtilities.hpp

Go to the documentation of this file.

// _LICENSE_HEADER_
//
// Copyright (C) 2019 - 2025.
// Terms register on the GPL-3.0 license.
//
// This file can be redistributed and/or modified under the license terms.
//
// See top level LICENSE file for more details.
//
// This file can be used citing references in CITATION.cff file.
 
#ifndef __GraphUtilities_H
#define __GraphUtilities_H
 
#include "Eigen/Eigen"
#include <iostream>
#include <list>
#include <stack>
#include <unordered_map>
#include <vector>
 
namespace Gedim
{
class GraphUtilities final
{
  public:
    struct GraphAdjacencyData final
    {
        std::vector<std::vector<unsigned int>> GraphAdjacencyVertices;
        std::vector<std::unordered_map<unsigned int, unsigned int>> GraphAdjacencyVerticesMap;
        std::vector<std::vector<unsigned int>> GraphAdjacencyEdges;
        std::vector<std::unordered_map<unsigned int, unsigned int>> GraphAdjacencyEdgesMap;
    };
 
  private:
    void FillOrder(const unsigned int &v,
                   const std::vector<std::vector<unsigned int>> &graphAdjacency,
                   std::vector<bool> &visited,
                   std::stack<int> &stack) const;
 
  public:
    GraphUtilities(){};
    ~GraphUtilities(){};
 
    std::vector<std::vector<unsigned int>> ExtractSubGraph(const std::vector<std::vector<unsigned int>> &graphAdjacency,
                                                           const std::unordered_map<unsigned int, unsigned int> &subGraphFilter) const;
 
    GraphAdjacencyData GraphConnectivityToGraphAdjacency(const unsigned int &graphNumVertices,
                                                         const Eigen::MatrixXi &graphConnectivity,
                                                         const bool &directEdges = true) const;
 
    Eigen::MatrixXi GraphAdjacencyToGraphConnectivity(const unsigned int &graphNumEdges,
                                                      const std::vector<std::vector<unsigned int>> &graphAdjacency) const;
 
    std::vector<std::vector<unsigned int>> ComputeStronglyConnectedComponents(const std::vector<std::vector<unsigned int>> &graphAdjacency) const;
 
    void DepthFirstSearch(const unsigned int &vertex,
                          const std::vector<std::vector<unsigned int>> &graphAdjacency,
                          std::vector<bool> &visited,
                          std::list<unsigned int> &visitedVertices) const;
 
    std::vector<unsigned int> BreadthFirstSearch(const unsigned int &vertex,
                                                 const std::vector<std::vector<unsigned int>> &graphAdjacency) const;
 
    std::vector<std::vector<unsigned int>> ComputeAdjacencyTranspose(const std::vector<std::vector<unsigned int>> &graphAdjacency) const;
};
 
} // namespace Gedim
 
#endif // __GraphUtilities_H