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

• G. Sliepen: Maybe it makes your teacher proud, but frankly it is a bit annoying that students are still asked to reimplement standard library functions. The result is almost always poor, and that's not because of a fault of yours, but because you are being asked to reimplement something from scratch in just a week or two what lots of standard library developers have been working on for decades. It would be better if you could have two separate reviews: one for your List, and one for a Graph implementation that uses std::list.
• Varad Mahashabde: @G.Sliepen I must confess I don't actually know STL as of yet (●くろまる_●くろまる)
• L. F.: Hi Varad, welcome to Code Review! 1) Please always remember to tag the main language tag (c++) in addition to the specific version c++11. This is because tags are used for searching and many other related mechanisms. For example, people who follow the c++ tag may miss your question if you tag c++11 only. (I should have updated my watch list to c++*!) 2) Did you compile your code using Turbo-C++ or a modern compiler? Please clarify in your question. 3) Your github link gives me Page not found ... Make sure you've made your project public.
• Varad Mahashabde: @L.F. Forgot about the repository being private 😅

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.

• Varad Mahashabde: Thanks for answering! I do agree with all that you have said (the operator!=(~Node~ Iterator) was embarrassing TBH), but I do have a couple of nitpicks : 1) Intended interface for Iterator is Iterator i(MyList); typeof(T) == typeof(i()). current is private, it's just that List is a friend. 2) AddConstToType explicitly exists to allow for const& to pointer types. Link to source. (1/2)
• Varad Mahashabde: 3) Sure, maybe no one needs to access BinaryFunctor::function, but surely no harm could be incurred by leaving it there, right? Right? (2/2)
• Varad Mahashabde: Comment Edit: Maybe I should add a cast to T for List<T>::Iterator
• Quuxplusone: 2) Huh! Today I learned that C++ apparently lets you type-pun between pointer types that differ only in const, as long as you promise not to modify the type-punned object. That's a little scary. godbolt.org/z/-pY_OD 3) Unused and untested source code is always "harm." Not only do I have to read and think about it, I might also be tempted to use it (and then find out later that it doesn't work). The smaller your codebase, the easier it is to work with.

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.