Cycle in Directed graph to vector

Question

I created a class of a directed graph and a method for finding if graph has an Euler cycle and updating a vector accordingly.Is there any optimization or a nicer way to do this.

class Graph { 
private: 
 int V; // No. of vertices 
 list<int> *adj; // Pointer to array of lists 
 bool cycleHelper(int v, bool visited[], bool *reStack, vector<int> &path) const; // Helper for cycle() 
public: 
 Graph(int V); // Constructor 
 ~Graph(); // De-constructor Who wants to live forever when love must Die 
 void addEdge(int u, int w); // function to add an edge to graph 
 bool cycle(vector<int> &path) const; // Returns True if Graph has a circle, and sets path to its route 
}; 
Graph::Graph(int V) { 
 this->V = V; // Set Graph nodes 
 adj = new list<int>[V]; // V-dimention array of lists 
} 
Graph::~Graph() { 
 delete[] adj; 
} 
void Graph::addEdge(int u, int w) { 
 adj[u].push_back(w); // Add u to v's list. 
} 
bool Graph::cycleHelper(int v, bool visited[], bool *recStack, vector<int> &path) const { 
 if (visited[v] == false) { 
 // Mark the current node as visited and not in recursion stack 
 visited[v] = true; 
 recStack[v] = true; 
 for (auto i : adj[v]) {
 if ( i == path[0]) return true;
 else if (!visited[i] && cycleHelper(i, visited, recStack, path)){ 
 path.push_back(i); 
 return true;
 } 
 else if (recStack[i]){ 
 path.push_back(i); 
 return true;
 } 
 } 
 } 
 recStack[v] = false; // remove from recursion stack, I don't need u any more 
 return false; 
} 
bool Graph::cycle(vector<int> &path) const { 
 // Mark all the vertices as not visited and not part of recursion stack 
 bool *visited = new bool[V]; 
 bool *recStack = new bool[V]; 
 for (int i = 0; i < V; i++) { 
 visited[i] = false; 
 recStack[i] = false; 
 } 
 // Call the helper function 
 for (int i = 0; i < V; i++){ 
 path.push_back(i); 
 if (cycleHelper(i, visited, recStack, path)) { 
 //path.push_back(i);
 reverse(path.begin(),path.end());
 //if (path.begin()[0] == path.end()[-1]) path.pop_back(); 
 return true; 
 } 
 path.clear(); 
 } 
 path.clear(); 
 return false; 
} 

• hoffmale: It seems to me that this code is a solution to a problem on geeksforgeeks.org, using parts of a provided snippet. If this is the case, please include that in the question (preferably with link to the problem).

Answer 1

General stuff

• #includes are missing
• missing using namespace std; (which by itself is discouraged, especially in header files).
• Graph::cycles path result contains not only the cycle, but alse the vertices that led there (e.g. in A -> B -> C -> B, A would be included in path though it is not part of the cycle). This might or might not be intended.
• Inconsistency: Graph::cycleHelper takes visited as bool[], but recStack as bool *, even though the usage for both is the same.
• if(visited[v] == false) can easily be rewritten to if(!visited[v])
• Graph::cycle treats path as if it has full control over all elements already present. This behavior might be unexpected by users of the class and should at the very least be thouroughly documented.

Memory management

• Graph::cycle leaks both visited and recStack.
• Graph::addEdge never checks whether its parameters are in the valid range. If they aren't, there might be accesses to out-of-bounds memory.

These issues can be fixed by using appropriate data structures and error checking. Generally, prefer using RAII constructs (like std::unique_ptr or containers) for resource acquisition.

Data structures

• Prefer std::array (if size is statically known) or std::vector (if not) over raw arrays. This also helps with memory cleanup.
• Try to structure similarly used variables in their own class or struct.
• Prefer std::vector (preferred) or std::deque (if constant time frontal insertion/removal is needed) over std::list, unless you absolutely need constant time random insertion/removal (and even then, you might want to measure std::vector as it is surprisingly efficient on modern hardware).

Class design

• Some variables have very cryptic names and few (if any) documentation to their meaning.

  • Graph::V: Represents the number of vertices in the graph. Maybe rename to vertex_count or num_vertices or similar.
  • u and w in Graph::addEdge: There is not way to infer whether the edge is added from u to w or vice versa. Maybe rename to something like from and to?
  • Graph::cycle: cycle is an unfornate choice of name, as the verb cycle has a different meaning. hasCycle or findCycle better express the intention behind this member function.

• There is an implicit assumption that "vertex index" == "vertex value". If there ever is a case where this assumption does not hold, the whole class will have to be redesigned.

• Graph::cycle violates the Single Responsibility Principle (SRP). It does two things ("check whether there is a cycle" and "return the cycle"), which might benefit users of the class that want both operations, but hinders other users that only want one of the operations.
• Graph is built upon the assumption that no more vertices will be added after construction. While this might be true in your specific use case, this won't be true in general.
• A specific edge might be added multiple times, which might increase worst case runtimes (as iteration of the edges of a vertex can become greater than \$\mathcal{O}(n)\$

Amending all the points

If I had to implement this, the result would look like this:

#include <vector>
#include <algorithm>
#include <stdexcept>
#include <deque>
class graph {
 using node_type = int;
 class vertex {
 node_type value;
 std::vector<vertex *> edges;
 bool visited = false;
 bool marked = false;
 public:
 vertex(node_type name) : value{name}, edges{} {}
 node_type name() const { return value; }
 bool is_marked() const { return marked; }
 void clear_flags() { visited = false; marked = false; }
 bool has_edge(vertex *to) const {
 return std::find(std::begin(edges), std::end(edges), to) != std::end(edges);
 }
 void add_edge(vertex *to) {
 if(!has_edge(to)) edges.push_back(to);
 }
 vertex *find_first_marked_edge() {
 auto match = std::find_if(std::begin(edges), std::end(edges), [](auto& edge){ return edge->marked; });
 if(match == std::end(edges)) return nullptr;
 return *match;
 }
 bool is_part_of_cycle() {
 if(marked) return true;
 if(visited) return false;
 visited = true;
 marked = true;
 for(auto& edge : edges) {
 if(edge->is_part_of_cycle()) return true;
 }
 marked = false;
 return false;
 }
 };
 std::vector<vertex> vertices;
public:
 graph() = default;
 graph(std::initializer_list<node_type> init) : vertices{} {
 for(auto& name : init) {
 add_vertex(name);
 }
 }
 void add_vertex(const node_type& name) {
 if(std::find_if(std::begin(vertices), std::end(vertices), [&](auto& vert){ return vert.name() == name; }) != std::end(vertices)) {
 throw std::invalid_argument{"a vertex with this name already exists"};
 }
 vertices.emplace_back(name);
 }
 void add_edge(node_type from, node_type to) {
 auto& from_vert = find_vertex(from);
 auto& to_vert = find_vertex(to);
 from_vert.add_edge(&to_vert);
 }
 bool has_cycle() {
 for(auto& vert : vertices) {
 vert.clear_flags();
 }
 for(auto& vert : vertices) {
 if(vert.is_part_of_cycle()) return true;
 }
 return false;
 }
 std::deque<node_type> find_first_cycle() {
 auto cycle = std::deque<node_type>{};
 if(!has_cycle()) return cycle;
 auto cycle_iter = find_first_marked_vertex();
 while(std::find(std::begin(cycle), std::end(cycle), cycle_iter->name()) == std::end(cycle)) {
 cycle.push_back(cycle_iter->name());
 cycle_iter = cycle_iter->find_first_marked_edge();
 }
 while(cycle.front() != cycle_iter->name()) cycle.pop_front();
 return cycle;
 }
private:
 vertex& find_vertex(node_type name) {
 auto match = std::find_if(std::begin(vertices), std::end(vertices), [&](auto& vert){ return vert.name() == name; });
 if(match == std::end(vertices)) {
 throw std::invalid_argument{"vertex could not be found"};
 }
 return *match;
 }
 vertex* find_first_marked_vertex() {
 auto match = std::find_if(std::begin(vertices), std::end(vertices), [](auto& vert){ return vert.is_marked(); });
 if(match == std::end(vertices)) return nullptr;
 return &*match;
 }
};

Points to note:

• graph::vertex encapsulates all information about a vertex. I changed recStack to marked, since many graph algorithms work with marked vertices.
• No manual memory management (= no memory leaks). Everything is owned by containers.
• I introduced some descriptive helper functions. This makes the code much more readable.
• If the value of the vertices ever needs to be changed (or templated), only the definition of graph::node_type needs to be adjusted.
• For a more deterministic performance, graph::vertex::edges could be kept sorted at all times.
• Some functions have a first in their names, as there might be more results (in the general case).

• Stavros Avramidis: Thanks for the answer. I appreciate you wrote a sum up with your own version ( I think you just couldn't resist to cose)
• hoffmale: @StavrosAvramidis: It's more that I described all the general steps, but the transformation as a whole is just of this big a scale. Just encapsulating all state in vertex is a huge leap that isn't easy to do starting from the original code. Also: "cose"?
• Stavros Avramidis: *code 😂, Also just a note you didn't implement a function to set a vector to the path of the cycle .
• hoffmale: @StavrosAvramidis: See graph::find_first_cycle. There are many ways to fill a std::vector from a std::deque (e.g. using std::copy), or the implementation could be changed to return a std::vector if absolutely needed.
• Stavros Avramidis: Yes, thanks I just pointed out as a note not a complain.

Answer 2

Set your editor to trim trailing whitespace from lines when you save!

---

list<int> *adj; // Pointer to array of lists 

The style in C++ is to put the * or & with the type, not the identifier. This is called out specifically near the beginning of Stroustrup’s first book, and is an intentional difference from C style.

---

Graph::~Graph() { 
 delete[] adj; 
} 

Pointer to array? You know about vectors, why not use it here? At the very least, make it a unique_ptr to the same kind of raw allocation.

⧺C.149 — no naked new or delete.

Once you do that, you can get rid of the manually supplied destructor. Everything in the class knows what to do.

---

adj[u].push_back(w); // Add u to v's list. 

Isn’t that adding w to u’s list? Either the comment is pointless (and wrong) because it duplicates what the code says, or it is saying something important but is completely unclear as to what you mean.

---

Graph::Graph(int V) { 
 this->V = V; // Set Graph nodes 
 adj = new list<int>[V]; // V-dimention array of lists 
} 

Use the member-init list in the constructor!
And, changing adj to a vector, we have

Graph::Graph(int V)
 : V{V}, adj(V)
{ } 

---

bool Graph::cycleHelper(int v, bool visited[], bool *recStack, vector<int> &path) const { 

The visited[] array notation is actually just passing a pointer, with no length information. You should pass a container^※(注記) by reference. You use a different notation for recStack, but you use it with subscripts, so this is also really a container.

It is literally cryptic and deceptive to read this declaration and understand what is being passed! It should be clear that they are containers, not pointers to single values; it should bundle the legal size in one name and not be implicit sized by context.

---

if (visited[v] == false) { 

Comparing against a boolean is silly. The value is already a boolean — use it.

if (!visited[v])

But, you have the bulk of the function indented under this, and only two lines otherwise. You have the test backwards — already visited is the special case.

if (visited[v]) {
 recStack[v] = false;
 return false;
 }
visited[v] = true;
⋮ etc. // Note you are back at the top of function scope, not nested in something.

---

bool *visited = new bool[V]; 
bool *recStack = new bool[V]; 

Again, you know how to use vector^※(注記)

---

※(注記) vector<bool> is weird

I just noticed that the times you used raw memory allocations is with bool. So maybe you know this, and are avoiding specifically std::vector<bool> specialization.

That’s not clear in the code. You should document the decision and the problem, and use type alias names to abstract what you actually chose (and can update it easily).

A couple easy work-arounds are

1 use deque instead
2 use a uint_8 instead of bool

But you can also use Boost.Container’s vector class, which does not have the same mis-feature.

• Stavros Avramidis: Thanks for the answer. I use array instead of vectors where i will have a fixed length, but I understand that if I use vector I will not have to bring up and down the memory like when i use raw array.
• JDługosz: Uh.... I think you got that wrong. std::list is for inserting/deleting from the middle without changing the address of other elements. It is very slow to use in general.
• Stavros Avramidis: I meant array sorry :P
• Stavros Avramidis: except you meant why I use list instead of vector in privates?
• JDługosz: Use a vector initialized to N elements of some value. If you must save the few bytes by remembering the current size/capacity, use unique_ptr of T[] in the same manner you use T* now; but that does not make the function call arguments any clearer (the proper thing there would be to use gsl::span, but just use vector).