Graph coloring project in C++

Question

I recently had to submit my 12th grade final project in C++, so I decided to make a game engine! That panned out just as you would expect (I am not touching OpenGL until they touch OOP), so I switched and ended up making a project on graph coloring instead!

For context, in the actual project this was used to calculate an exam schedule for a list of students read from a file, but I will not be including that since it would make things too long.

Did I follow good coding practices and make my teacher proud? Note that using STL was not the point of the project.

BTW, can anyone calculate the time complexity of this graph-coloring algorithm (in terms of the \$O(\ldots{})\$ notation)? I have no idea 😅.

Here is some further context:

1. There is a literal limit on how advanced this code can be. My board doesn't specify a version, so all teachers default to (shock, and horror! ⊂（゜Д゜⊂) ) Turbo C++. It is a miracle I could sneak in templates.
2. There are actually 40 other scripts where I had to make a linked-list twice, so you know where I copied it from. The graph code is virgin fresh tho.
3. If you feel like it, compile it! Here is some test code(compiled with G++ 7.3.0) for a graph of integers. The repo also has the final project and the other scripts, so please do check them out too, if you are up to it!

---

graph.h

#if !defined(VARAD_GRAPH_H_INCLUDED)
  #define VARAD_GRAPH_H_INCLUDED

  #include "list.h"

  namespace graph_h {
    // Add const to type if it is a pointer
    template <class T>
    struct AddConstToType {
      typedef T type;
    };
    template <class T>
    struct AddConstToType<T*> {
      typedef const T* type;
    };

    template <class T>
    class BinaryFunctor {
      public :
        virtual bool function(const typename AddConstToType<T>::type& a, const typename AddConstToType<T>::type& b) const = 0;
        inline bool operator()(const typename AddConstToType<T>::type& a, const typename AddConstToType<T>::type& b) const {
          return function(a, b);
        }
    };
  }

  template <class T>
  class Graph {
    public :
      class Vertex {
        public : 
          T data;
          List<Vertex*> edges;
          // Vertex Constructors
          Vertex() : data(), edges() {}
          // Weird cast of const T new_data to T so that it can be copied to data
          Vertex(const typename graph_h::AddConstToType<T>::type& new_data) : data((T)new_data), edges() {}
          Vertex(const typename graph_h::AddConstToType<T>::type& new_data, Vertex** edge_list, unsigned int edge_count) 
            : data((T)new_data), edges(edge_list, edge_count) {}
          Vertex(const Vertex& old_vertex) : data(old_vertex.data), edges(old_vertex.edges) {}
          // Equivalence checks are dependent on the Vertex data, not the edges
          inline bool operator==(const Vertex& other_vertex) const {
            return data == other_vertex.data;
          }
          inline bool operator!=(const Vertex& other_vertex) const {
            return not (*this == other_vertex.data) ;
          }
          // Functions for edge management
          bool isConnected() const {
            return edges.len() != 0;
          }
          bool isConnectedWithVertex(const Vertex* const other_vertex) const {
            if (other_vertex != nullptr and other_vertex != this)
              return edges.includes(other_vertex) != -1;
            return false;
          }
          bool isConnectedWithVertex(const Vertex& other_vertex) const {
            return isConnectedWithVertex(&other_vertex);
          }
          void connectTo(const Vertex* const other_vertex) {
            if (other_vertex != nullptr and other_vertex != this) {
              if (edges.includes(other_vertex) == -1)
                edges.append(other_vertex);
            }
          }
          void disconnectFrom(const Vertex* const other_vertex) {
            if (other_vertex != nullptr and other_vertex != this) {
              int i = edges.includes(other_vertex);
              if (i != -1)
                edges.remove(i);
            }
          }
          void connectTo(const Vertex& other_vertex) {
            connectTo(&other_vertex);
          }
          void disconnectFrom(const Vertex& other_vertex) {
            disconnectFrom(&other_vertex);
          }
          // Vertex Destructor
          ~Vertex() {
            data.~T();
            for (typename List<Vertex*>::Iterator connected_vertex(edges); not connected_vertex.hasEnded(); connected_vertex++)
              connected_vertex()->disconnectFrom(this);
            edges.~List();
          }
      };

      List<Vertex> vertices;

      Graph() : vertices() {}
      Graph(Graph& old_graph) : vertices(old_graph.vertices) {}

      void makeVertex(const typename graph_h::AddConstToType<T>::type& data) {
        vertices.append(Vertex(data));
      }
      void removeVertex(unsigned int index) {
        vertices.remove(index);
      }

      void connectVertices(unsigned int i_1, unsigned int i_2) {
        Vertex* v_1 = &(vertices[i_1]);
        Vertex* v_2 = &(vertices[i_2]);

        if (v_1 == v_2 or v_1 == nullptr or v_2 == nullptr)
          return;

        v_1->connectTo(v_2);
        v_2->connectTo(v_1);
      }
      void disconnectVertices(unsigned int i_1, unsigned int i_2) {
        Vertex* v_1 = &(vertices[i_1]);
        Vertex* v_2 = &(vertices[i_2]);

        if (v_1 == v_2 or v_1 == nullptr or v_2 == nullptr)
          return;

        v_1->disconnectFrom(v_2);
        v_2->disconnectFrom(v_1);
      }

      void makeConnections(const graph_h::BinaryFunctor<T>& func) {
        // Cycle through each possible vertex pair and connect them
        // if the given function returns true
        for (typename List<Vertex>::Iterator i(vertices); not i.hasEnded(); i++) 
          for (typename List<Vertex>::Iterator j = i + 1; not j.hasEnded(); j++) 
            if (func(i().data, j().data)) {
              i().connectTo(j());
              j().connectTo(i());
            }
      }

      List<List<Vertex*>> colorVertices() {
        List<List<Vertex*>> color_list;

        for (typename List<Vertex>::Iterator i(vertices); not i.hasEnded(); i++) {
          typename List<List<Vertex*>>::Iterator color(color_list);
          // Determine if vertex is connected to any other colored vertex
          bool is_connected = true;
          // Come out color-checking loop if colors have run out or 
          // the current vertex is not connected to any vertex of the given color

          // Don't increment color if none are connected
          for (; not (color.hasEnded() or not is_connected); is_connected ? color++ : color)
            // Come out of vertex-connection-checking loop
            // if there are no more vertices to check or
            // the current vertex is connected to any vertex of the given color
            for (typename List<Vertex*>::Iterator j( (is_connected = false, color()) ); not (j.hasEnded() or is_connected); ++j)
              is_connected |= i().isConnectedWithVertex(j());
          // If current vertex was not connected to any in the last color,
          // switch back to it
          if (color.hasEnded() and not is_connected)
            color.last();
          if (not color.hasEnded()) {
            // Color the vertex if an unconnected color was found
            color().append(&i());
          } else {
            // Make a new color if the vertex is connected to all the current colors
            List<Vertex*> new_color;
            new_color.append(&i());
            color_list.append(new_color);
          }
        }

        return color_list;
      }
  };

#endif

---

list.h

#if !defined(VARAD_LIST_H_INCLUDED)
  #define VARAD_LIST_H_INCLUDED

  namespace list_h {
    const int check_num = 0x1234abcd;

    // Make type const if it is a pointer
    template <class T>
    struct AddConstToType {
      typedef T type;
    };
    template <class T>
    struct AddConstToType<T*> {
      typedef const T* type;
    };

    template <class T>
    class BinaryFunctor {
      public :
        virtual bool function(const typename AddConstToType<T>::type& a, const typename AddConstToType<T>::type& b) const = 0;
        inline bool operator()(const typename AddConstToType<T>::type& a, const typename AddConstToType<T>::type& b) const {
          return function(a, b);
        }
    };
  }


  template <class T>
  class List {
    protected :
      class Node {
        public :
          T data;
          Node* next;
          Node* previous;
          const int check;

          Node() : check(list_h::check_num) {}
          // Weird cast of const T new_data to T so that it can be copied to data
          Node(const typename list_h::AddConstToType<T>::type& new_data, Node* prev, Node* nxt = nullptr)
            : check(list_h::check_num), data((T)new_data), previous(prev), next(nxt) {}
          Node(Node* prev) : check(list_h::check_num), previous(prev), next(nullptr) {}
          Node(const Node& old_node, Node* prev = nullptr) : Node(old_node.data, prev) {}
          ~Node() {
            data.~T();
            next = previous = nullptr;
          }

          bool isOk() const {
            return check == list_h::check_num;
          }
          Node* makeNext(const typename list_h::AddConstToType<T>::type& new_data) {
            Node* new_next = new Node(new_data, this);
            if (new_next != nullptr) next = new_next;
            return new_next;
          }
          Node* makeNext() {
            Node* new_next = new Node(this);
            if (new_next != nullptr) next = new_next;
            return new_next;
          }
      };

      Node* first;
      Node* last;
      unsigned int length;

      Node* getNode(int index) const {
        if (length == 0)
          index = 0;
        else if (index < 0)
          index = index % length + length;
        else
          index = index % length;

        Node* cur;
        if (2 * index < length) {
          cur = first;
          for (int i = 1; i <=index; i++) {
            cur = cur->next;
          }
        } else {
          cur = last;
          for (int i = length - 2; i >= index; i--) {
            cur = cur->previous;
          }
        }
        return cur;
      }

      void reCalculateLength() {
        length = 0;
        for(Node* read_head = first; read_head != nullptr; read_head = read_head->next, ++length);
      }

    public: 
      class Iterator {
        friend class List;

        const List& parent_list;
        Node* current;

        public :
          int position;

        private :
          // Custom Constructor for exact copying
          Iterator(const List& pops, Node* cur, int pos) : parent_list(pops), current(cur), position(pos) {}

        public :
          // Basic functions
          void first() {
            current = parent_list.first;
            position = 0;
          }
          void last() {
            current = parent_list.last;
            position = parent_list.length - 1;
          }          
          Iterator(const List& papa, bool start_at_first = true) : parent_list(papa) {
            if (start_at_first)
              first();
            else 
              last();
          };
          // Constructors
          Iterator(const Iterator& i) : parent_list(i.parent_list), current(i.current), position(i.position) {}
          Iterator& operator=(const Iterator& i) {
            if (&parent_list == &(i.parent_list)) {
              current = i.current;
              position = i.position;
            }/* else {
              ~Iterator();
              new(this) Iterator(i);
            }*/
            return *this;
          }

          bool hasEnded() const {
            return current == nullptr or position >= parent_list.length or position < 0;
          }
          bool operator==(const Node* const node) const {
            return current == node;
          }
          bool operator==(const Iterator& i) const {
            return current == i.current;
          }
          bool operator!=(const Node* const node) const {
            return not current == node;
          }
          bool operator!=(const Iterator& i) const {
            return not current == i.current;
          }
          Iterator& operator++() {
            if (current != nullptr) current = current->next;
            ++position;
            return *this;
          }
          Iterator& operator++(int) {
            return ++(*this);
          }
          inline Iterator& operator--() {
            if (current != nullptr) current = current->previous;
            --position;
            return *this;
          }
          inline Iterator& operator--(int) {
            return --(*this);
          }
          Iterator operator+(int index) {
            Node* new_current = current;
            if (index < 0)
              for(int i = index; i < 0; i++) {
                new_current = new_current->previous;
                if (new_current == nullptr)
                  break;
              }
            else 
              for (int i = index; i > 0; i--) {
                new_current = new_current->next;
                if (new_current == nullptr)
                  break;
              }
            return Iterator(parent_list, new_current, position + index);
          }
          inline Iterator operator-(int i) {
            return *this + (-i);
          }

          T& operator()() const {
            return current->data;
          }
      };
      // Basic Functions
      inline unsigned int len() const {
        return length;
      }
      T& operator[] (int index) const {
        return getNode(index)->data;
      }
      bool append(const typename list_h::AddConstToType<T>::type& new_data) {
        if (last == nullptr) {
          last = new Node(new_data, nullptr);
          first = last;
          if (last == nullptr)
            return false;
        } else {
          Node* new_last = last->makeNext(new_data);
          if (new_last == nullptr) return false;
          last = new_last;
        }
        ++length;
        return true;
      }
      bool prepend(const typename list_h::AddConstToType<T>::type& new_data) {
        if (last == nullptr) {
          first = last = new Node(new_data, nullptr);
          if (first == nullptr)
            return false;
        } else {
          Node* new_node = new Node(new_data, nullptr);
          if (new_node == nullptr)
            return false;
          new_node->next = first;
          first->previous = new_node;
          first = new_node;
        }
        ++length;
        return true;
      }
    private :
      void removeByPointer(Node* node) {
        if (node == nullptr)
          return;
        // Neighbour management
        if (node->next != nullptr) node->next->previous = node->previous;
        if (node->previous != nullptr) node->previous->next = node->next;
        // Boundary conditions
        if (node == first)
          first = node->next;
        if (node == last)
          last = node->previous;
        // Guillotine
        delete node;
        --length;
      }
    public :
      void remove(unsigned int index) {
        removeByPointer(getNode(index));
      }
      void remove(Iterator iter) {
        if (not iter.hasEnded())
          removeByPointer(iter.current);
      }
      // Constructors
      List() : first(nullptr), last(nullptr), length(0) {}
      List(const T* const data_arr, unsigned int len) : List() {
        for (int i = 0; i < len; ++i)
          if (not append(data_arr[i]))
            break;
      }
      List(unsigned int len) : List() {
        length = len;
        first = new Node(nullptr);
        if (first == nullptr)
          return;
        last = first;
        for (int i = 1; i < length; ++i) {
          Node* new_last = last->makeNext();
          if (new_last == nullptr)
            i = length;
          else
            last = new_last;
        }
      }
      List& operator=(const List& old_list) {
        length = old_list.length;
        if (length != 0) {
          for (Iterator i(old_list); not i.hasEnded(); ++i)
            if (not append(i()))
              break;
        } else {
          first = last = nullptr;
        }
        return *this;
      }
      List(const List& old_list) : List() {
        *this = old_list;
      }
      ~List() {
        if (length != 0) {
          for (Iterator i(*this, false); not i.hasEnded(); ) {
            Node* current = i.current;
            --i;
            delete current;
          }
          first = last = nullptr;
        }
      }

      bool insert(unsigned int index, const typename list_h::AddConstToType<T>::type& new_data) {
        if (index == length) 
          return append(new_data);
        else if (index == 0) 
          return prepend(new_data);

        Node* cur = getNode(index);
        if (cur == nullptr)
          return false;
        Node* new_node = new Node(new_data, nullptr);
        if (new_node == nullptr)
          return false;

        new_node->next = cur;
        new_node->previous = cur->previous;
        if (new_node->previous != nullptr) new_node->previous->next = new_node;
        cur->previous = new_node;
        ++length;
      }
      void truncate(int end) {
        // Domain folding
        if (length == 0)
          end = 0;
        else if (end < 0)
          end = end % length + length;
        else
          end = end % length;

        Iterator i(*this);
        for ( i.last(); not i.hasEnded() and i.position >= end; ) {
          Node* current = i.current;
          --i;
          delete current;
        }
        // Loose ends management
        last = i.current;
        if (i.current != nullptr) i.current->next = nullptr;
        length = end;
      }
      void slice(int start, int end, unsigned int step = 1) {
        // Domain folding
        if (length == 0)
          end = 0;
        else if (end < 0)
          end = end % length + length;
        else
          end = end % length;
        if (length == 0)
          start = 0;
        else if (start < 0)
          start = start % length + length;
        else
          start = start % length;

        if (start >= end)
          return;
        truncate(end);

        Iterator i(*this);
        for ( i.first(); not i.hasEnded() and i.position < start; ) {
          Node* current = i.current;
          ++i;
          delete current;
        }
        // Loose ends management
        first = i.current;
        if (i.current != nullptr) i.current->prev = nullptr;
        length -= start;
        // No iterators here because the list is dynamically changing
        if (step != 1 or step != 0) {
          for (int i = 0, offset = 0; i < length; ++i) {
            if ((i + offset) % step != 0) {
              remove(i);
              ++offset; --i;
            }
          }
          reCalculateLength();
        }
      }
      void swap(unsigned int i_1, unsigned int i_2) {
        Node* temp;
        // Ensure that i_1 <= i_2 
        if (i_1 > i_2) {
          unsigned int temp = i_1;
          i_1 = i_2;
          i_2 = temp;
        }
        if (i_1 == i_2) return;
        Node* node_1 = getNode(i_1);
        Node* node_2 = getNode(i_2);
        if (node_1 == nullptr or node_2 == nullptr) 
          return;

        // Check if list markers need to be changed
        if (i_1 == 0)
          first = node_2;
        else if (i_1 == length - 1)
          last = node_2;
        if (i_2 == 0)
          first = node_1;
        else if (i_2 == length - 1)
          last = node_1;
        // Alternate behaviour for adjacent swaps
        if (i_1 + 1 == i_2) {
          node_1->next = node_2->next;
          node_2->previous = node_1->previous;

          node_1->previous = node_2;
          node_2->next = node_1;

          if (node_1->next != nullptr) node_1->next->previous = node_1;
          if (node_2->previous != nullptr) node_2->previous->next = node_2;

          return;
        }
        // Standard swap behaviour
        temp = node_1->previous;
        node_1->previous = node_2->previous;
        node_2->previous = temp;

        temp = node_1->next;
        node_1->next = node_2->next;
        node_2->next = temp;
        // Correct neighbours addresses
        if (node_1->next != nullptr) node_1->next->previous = node_1;
        if (node_1->previous != nullptr) node_1->previous->next = node_1;

        if (node_2->next != nullptr) node_2->next->previous = node_2;
        if (node_2->previous != nullptr) node_2->previous->next = node_2;
      }
      void sort(const list_h::BinaryFunctor<T>& func) {
        class Dummy {
          public : 
            void quickSort(List& arr, unsigned int start, unsigned int end, const list_h::BinaryFunctor<T>& func) {
              if (end - start <= 1) 
                return;
              int pivotIndex = start;
              for (int i = start; i < end - 1; ++i) {
                if (func(arr[i], arr[end - 1])) {
                  arr.swap(i, pivotIndex);
                  ++pivotIndex;
                }
              }
              arr.swap(pivotIndex, end - 1);
              quickSort(arr, start, pivotIndex, func);
              quickSort(arr, pivotIndex + 1, end, func);
            }
        } dummy_dum_dum;
        dummy_dum_dum.quickSort(*this, 0, length, func);
      }
      int includes(const typename list_h::AddConstToType<T>::type& search_data) const {
        for (Iterator i(*this); not i.hasEnded(); i++) 
          if (i() == search_data and i.position < length)
            return i.position;

        return -1;
      }
  };
#endif

Answer 1

That's a lot of code. Consider just using STL? ;)

Seriously, though, you wrote an entire List utility class, almost 500 lines of code, and:

• It doesn't work anything like std::list, so any coworker of yours (e.g., me) can't use their existing knowledge base to understand it.

• Your own code doesn't use half of the functionality you implemented (e.g., slice and sort). So those bits were wasted effort.

• Since you don't use that code, and I'm assuming you wrote no unit tests for it, the code probably doesn't work at all. Code that is unused and untested should be ripped out. Code that is used but untested... should be tested!

To expand on that first point, the unfamiliar API: It looks like the way you iterate over a list_h::List<T> is like this—

Iterator i(myList);
for (i.first(); not i.hasEnded(); ++i) {
    const T& elt = i.current->data;
    do_something_with(elt);
}

Compare this to the way we iterate over a standard container:

for (const T& elt : myList) {
    do_something_with(elt);
}

The standard containers can all be used with range-for-loops because they implement iterators with the standard interface: initialized with the return values of myList.begin() and myList.end(), compared with ==, dereferenced with *, and incremented with ++. Of that checklist, the only part you successfully copied was "incremented with ++."

---

Serious bug: Your destructors are all wrong. This indicates strongly to me that you have never tested this code.

~Node() {
    data.~T();
    next = previous = nullptr;
}

If you construct and then destroy a Node<std::unique_ptr<int>>, you'll find that the allocation is deleted twice (that's a "double-free bug"). Your hand-written destructor does not need to manually destroy the members (or base classes) of Node, any more than you ever need to manually destroy the local variables in the stack frame of a function.

Rule of thumb for 12th-graders: never, ever write foo.~Bar(). (Okay, let me revise that to allow for experimentation. Never write foo.~Bar() and expect the code to actually work correctly!)

You don't need to set next = previous = nullptr; either. It doesn't matter what value those members have, given that they're going to be destroyed either way.

---

Your namespaces are weird. Did your teacher tell you that list.h should put everything in namespace list_h, and graph.h should put everything in namespace graph_h? In the real world, we'd do something more like

// varad_list.h
namespace varad {
    template<class T> class List { ... };
}

// varad_graph.h
namespace varad {
    template<class T> class Graph { ... };
}

Namespaces are for preventing name collisions. When I see a repetitive redundant repetitive name like graph_h::Graph, I know something's wrong. On the other hand, the name varad::Graph actually tells me something in C++ese. "It's a Graph class. Whose Graph class? The Graph class that belongs to varad."

---

Again showing that you never compiled this code:

      bool operator!=(const Node* const node) const {
        return not current == node;
      }

Suppose current is (Node*)0x12345678. Then what is not current?— Right, it's the boolean false. Can you compare a bool with a pointer? Nope.

---

Finally (although there's much much more to unpack here), I want to talk about BinaryFunctor.

// Make type const if it is a pointer
template <class T>
struct AddConstToType {
  typedef T type;
};
template <class T>
struct AddConstToType<T*> {
  typedef const T* type;
};

template <class T>
class BinaryFunctor {
  public :
    virtual bool function(const typename AddConstToType<T>::type& a, const typename AddConstToType<T>::type& b) const = 0;
    inline bool operator()(const typename AddConstToType<T>::type& a, const typename AddConstToType<T>::type& b) const {
      return function(a, b);
    }
};

void sort(const list_h::BinaryFunctor<T>& func) {
    [...]
}

Your AddConstToType doesn't do anything except break your code for non-const-qualified pointers. (Again, you never compiled this code to test it.) If I make a List<int*> and then try to .sort it, I'll just get a bunch of errors about how an lvalue of type int* cannot be bound to a reference of type const int*&.

Your BinaryFunctor uses something kind of like the Non-Virtual Interface Idiom, which is cool; but to get all the way there, you should make virtual bool function a private method. Nobody should ever be calling it directly, right? They should be going via the public operator(). And derived classes don't need access to virtual bool function either — they can override a private method just as easily as they can override a public one.

But really you shouldn't have BinaryFunctor at all. C++ already has first-class "function objects" — lambdas, and pointers to functions, and std::function<bool(const T&)> objects, and so on and so forth. You seem to want a List<T>::sort(F) that can accept any kind of predicate type F, just like List<T> can accept any kind of object type T. You already know how to express that in C++. Use a template!

template<class F>
void sort(const F& func) {
    [...]
}

And then don't reinvent quickSort. (I guarantee that your implementation is wrong. I don't know how, but I'm confident that if you write a bunch of unit tests, you'll find out pretty quick.) Just use std::sort.

Or, as I implied at the beginning of this review: just delete the entire sort function. You never use it! And code that is unused and untested never works.

Answer 2

A few notes to add to the existing answer(s):

• It is not wrong use not in place of ! but I'd like to claim that most programmers will find it odd. Shorthand operators are much more common and likely make parsing the code faster for most readers.

• It appears that your algorithm is not exact (i.e., it is not guaranteed to find an optimal coloring for every possible input). Rather, it looks to be the well-known greedy heuristic that goes through the vertices in some order, and always assigns to each vertex the lowest available color. As such, in principle, it can be implemented to run in linear time but I'm not certain what the complexity of all your List methods for example are.

• Your internal storage for a graph is definitely not optimal. That is, your lists rely on pointers and there is no guarantee consecutive elements would be stored consecutively in memory (i.e., we should expect cache misses when accessing elements in your list). Storing and processing large graphs with your implementation will likely be slow. If you are curious about a faster implementation, you can have a look at my earlier graph related answer here.