Kruskal.hpp

Go to the documentation of this file.

#ifndef GL_KRUSKAL_HPP
#define GL_KRUSKAL_HPP

#include "../structures/DisjointSets.hpp"
#include "../algorithms/TransitiveClosure.hpp"

namespace gl::algorithm {

//    Class declaration

template <class Graph>
class Kruskal {
  using Edge = typename Graph::Edge;
  using idx_t = typename Graph::idx_t;
  using val_t = typename Graph::val_t;
  using visit_list_t = typename Graph::visit_list_t;

public: 
  Kruskal();                                         
  explicit Kruskal(const Graph&);                    

  Kruskal(const Kruskal &) = default;                
  Kruskal(Kruskal &&) noexcept = default;            
  Kruskal &operator=(const Kruskal &) = default;     
  Kruskal &operator=(Kruskal &&) noexcept = default; 
  ~Kruskal() = default;                              

  std::function<std::pair<bool,gl::Color>(const idx_t src, const idx_t dest)> EdgeSelector(const gl::Color& trueColor = gl::Color("red"), const gl::Color& falseColor = gl::Color("black")) const;
  std::function<std::pair<bool,gl::Color>(const idx_t node)> NodeSelector(const gl::Color& trueColor = gl::Color("red"), const gl::Color& falseColor = gl::Color("white")) const;
  void compute(const Graph& graph);
  val_t getCost() const;
  Graph getMST() const;

private:
  bool isInitialized_ = false; 
  Graph result_;       
  val_t cost_;         
};

//    Member function implementations

template <class Graph>
Kruskal<Graph>::Kruskal() : isInitialized_(false) {}

template <class Graph>
Kruskal<Graph>::Kruskal(const Graph& graph) : isInitialized_(false) {
  compute(graph);
}

template <class Graph>
void Kruskal<Graph>::compute(const Graph& graph)
{
  // assert graph connectedness
  GL_ASSERT(gl::algorithm::transitiveClosure(graph,0).size() == graph.numNodes(),(std::string("Kruskal::compute | '")+graph.getGraphLabel()+std::string("' is not connected.\n")))

  std::vector<Edge> edges;
  Graph result(graph.numNodes(),std::string(std::string("MST of ")+graph.getGraphLabel()));
  val_t cost {0};
  DisjointSets disjointSets(graph.numNodes());

  // get vector of all edges in the graph
  for (auto it = graph.edge_cbegin(); it != graph.edge_cend(); ++it) 
  {
    edges.push_back(*it);
  }
  // sort edges by increasing weight
  std::sort(edges.begin(),edges.end(),[](const Edge& lhs, const Edge& rhs)
  {
    return lhs.weight() < rhs.weight();
  });
  
  // construct MST
  for(auto edge : edges) 
  {
    idx_t one = edge.source();
    idx_t two = edge.dest();
    
    idx_t setOne = disjointSets.find(one);
    idx_t setTwo = disjointSets.find(two);

    if (setOne != setTwo)
    {
      result.setEdge(edge);
      cost += edge.weight();
      disjointSets.merge(one,two);
    }
  }

  result_ = result;
  cost_ = cost;
  isInitialized_ = true;
}

template <class Graph>
std::function<std::pair<bool,gl::Color>(const typename Graph::idx_t src, const typename Graph::idx_t dest)> Kruskal<Graph>::EdgeSelector (const gl::Color& trueColor, const gl::Color& falseColor) const 
{
  GL_ASSERT(isInitialized_,"Kruskal::EdgeSelector | Kruskal has not been initialized with a graph.")
  return [trueColor, falseColor, this](const idx_t src, const idx_t dest) -> std::pair<bool,gl::Color> {
    if (result_.hasEdge(src,dest)) 
      return {true,trueColor};
    else
      return {false,falseColor};
  };
}

template <class Graph>
std::function<std::pair<bool,gl::Color>(const typename Graph::idx_t node)> Kruskal<Graph>::NodeSelector (const gl::Color& trueColor, const gl::Color& falseColor) const 
{
  GL_ASSERT(isInitialized_,"Kruskal::NodeSelector | Kruskal has not been initialized with a graph.")
  return [trueColor, falseColor, this](const idx_t node) -> std::pair<bool,gl::Color> {
    if (0 <= node && node < result_.numNodes())
      return {true,trueColor};
    else 
      return {false,falseColor};
  };
}

template <class Graph>
typename Kruskal<Graph>::val_t Kruskal<Graph>::getCost () const 
{
  GL_ASSERT(isInitialized_,"Kruskal::getCost | Kruskal has not been initialized with a graph.")
  return cost_;
}

template <class Graph>
Graph Kruskal<Graph>::getMST () const 
{
  GL_ASSERT(isInitialized_,"Kruskal::getMST | Kruskal has not been initialized with a graph.")
  auto result = result_;
  return result;
}

} // namespace gl::algorithm 

#endif // GL_Kruskal_HPP