imstkGraph.h

/*
** This file is part of the Interactive Medical Simulation Toolkit (iMSTK)
** iMSTK is distributed under the Apache License, Version 2.0.
** See accompanying NOTICE for details.
*/

#pragma once

#include <cstdlib>
#include <unordered_set>
#include <vector>

namespace imstk
{
class Graph
{
using edgeType = std::unordered_set<size_t>;
using graphColorsType = std::pair<std::vector<unsigned short>, unsigned short>;
public:
    enum class ColoringMethod
    {
        Greedy,
        WelshPowell
    };

    Graph(const size_t size) { m_adjList.resize(size); }
    virtual ~Graph() = default;

    void addEdge(const size_t v, const size_t w);

    void getEdges(const size_t v, edgeType& edges) const;

    size_t size() const { return m_adjList.size(); }

    void print() const;

    void setDefaultColoringMethod(ColoringMethod method) { m_ColoringMethod = method; }

    graphColorsType doColoring(ColoringMethod method = ColoringMethod::WelshPowell,
                               bool           print = false) const;

protected:
    graphColorsType doColoringGreedy(bool print = false) const;

    graphColorsType doColoringWelshPowell(bool print = false) const;

    std::vector<edgeType> m_adjList;    
    ColoringMethod m_ColoringMethod = ColoringMethod::WelshPowell;
};
} // namespace imstk