- Algorithms, Binary Tree, Combinatorial, Graph, Graph Coloring

DSatur Algorithm for Graph Coloring

  #include #include #include #include using namespace std;  struct nodeInfo {    int sat;     int deg;     int vertex; };struct maxSat {    bool operator()(const nodeInfo& lhs,                    const nodeInfo& rhs) const    {                                        return tie(lhs.sat, lhs.deg, lhs.vertex)               > tie(rhs.sat, rhs.deg, rhs.vertex);    }};  class Graph {          int n;          vector adj;  public:        Graph(int numNodes)    {        n = numNodes;        adj.resize(n, vector());    }    ~Graph() { adj.clear(); }          void addEdge(int u, int v);              void DSatur();};  void Graph::addEdge(int u, int v){    adj[u].push_back(v);    adj[v].push_back(u);}  void Graph::DSatur(){    int u, i;    vector used(n, false);    vector c(n), d(n);    vector adjCols(n);    set Q;    set::iterator maxPtr;                                          for (u = 0; u < n; u++) {        c[u] = -1;        d[u] = adj[u].size();        adjCols[u] = set();        Q.emplace(nodeInfo{ 0, d[u], u });    }      while (!Q.empty()) {                                          maxPtr = Q.begin();        u = (*maxPtr).vertex;        Q.erase(maxPtr);                          for (int v : adj[u])            if (c[v] != -1)                used] = true;        for (i = 0; i < used.size(); i++)            if (used[i] == false)                break;        for (int v : adj[u])            if (c[v] != -1)                used] = false;                  c[u] = i;                                          for (int v : adj[u]) {            if (c[v] == -1) {                Q.erase(                    { int(adjCols[v].size()),                      d[v], v });                adjCols[v].insert(i);                d[v]--;                Q.emplace(nodeInfo{                    int(adjCols[v].size()),                    d[v], v });            }        }    }              for (u = 0; u < n; u++)        cout