Give names to things
There are several problems with this variable declaration:
vector <vector <pair <int, int> > > graph;
First, the variable should probably not named graph, as that is already the name of the class it is in. Since the outer std::vector contains information about each vertex in the graph, I would name this variable vertices.
Second, it is very hard to see what the type of this variable represents. If you would translate it to English, it says "a graph is a vector of a vector of a pair of integers". That is not very helpful at all. It would be much nicer if the declaration would say something similar to: "a graph is a set of vertices, and each vertex has a list of neihbors". Translated back into C++, that could look like:
struct Edge {
int vertex;
int weight;
};
struct Vertex {
std::vector<Edge> neighbors;
};
std::vector<Vertex> vertices;
Third, the pair<int, int> is now an Edge, but it still contains two ints. You can make aliases for these ints to make the meaning of it even more clear, while also making it easier to change those types later:
using VertexID = int;
using Weight = int;
struct Edge {
VertexID vertex;
Weight weight;
}
Choose the right type for indices and weights
An int might not be large enough to store all possible indices into a std::vector. The proper type to use that is guaranteed to be large enough to be able to index every item in memory is std::size_t. It also has the advantage that it matches the return type of std::vector::size(), so you won't get any warnings from the compiler about comparing signed and unsigned integers.
For weights, maybe an int is the right type. But do consider the maximum value you need, and if negative weights are allowed. If not, an unsigned integer type might be more appropriate.
Don't store redundant information
There is no need to store num_ver if you have a vector of vertices. You can just use vertices.size() instead. Apart from using memory unnecessarily, if two values that should be the same go out of sync (maybe because of programming errors), you will run into problems. So it is best to avoid it.
Use std::vector<bool> for the white/grey/black sets
A std::vector<int> is not the most optimal way to store which color a vertex has during your cycle-finding algorithm. Finding and erasing random items in a std::vector are \$O(N)\$ operations, where \$N\$ is the size of the vector. Instead, use std::vector<bool>, like you did for visited. For example, dfs_cyc then becomes:
visited[i] = true;
white_set[i] = false;
grey_set[i] = true;
for (VertexID j = 0; j < vertices[i].neighbors.size(); j++) {
VertexID neighbor = vertices[i].neighbors[j].vertex;
if (black_set[neighbor]) {
continue;
}
if (gray_set[neighbor]) {
stack.push(neighbor);
return true;
}
...
}
gray_set[i] = false;
black_set[i] = true;
return false;
Make find_cycles() return the cycles
The problem with find_cycles() calling print_cycles() is that this is now the only things the function can do: print cycles. If instead you don't print them out immediately, but just return the set of cycles found, the caller can decide what to do with the cycles: either print them, or do something else. It could look like:
struct Cycle {
std::vector<VertexID> vertices;
};
std::vector<Cycle> Graph::find_cycles() {
std::vector<Cycle> cycles;
...
...
if (dfs_cyc(...)) {
if (stack.top() != i)
stack.push(i);
cycles.push_back(pop_cycle(stack));
}
...
...
return cycles;
}
Cycle Graph::pop_cycle(std::stack<VertexID> &stack) {
Cycle cycle;
VertexID start = stack.top();
while (true) {
cycle.vertices.push_back(stack.top());
if (stack.top() == start)
break;
stack.pop();
};
return cycle;
}
Avoid putting everything into a class
Java requires all functions to be part of a class, but that is not a requirement in C++. Consider that a graph algorithm is not part of a graph, but rather something that acts upon a graph. So, you could make class Graph a simple struct instead;
struct Graph {
...
struct Vertex {
...
};
std::vector<Vertex> vertices;
};
And have find_cycles() be a free-standing function that takes a Graph as an input:
std::vector<Cycle> find_cycles(const Graph &graph) {
...
};
Then your main() could look like:
Graph graph;
graph.vertices.push_back(...);
...
Cycles cycles = find_cycles(graph);
for (auto &cycle: cycles)
print_cycles(cycle);
Use '\n' instead of std::endl
Prefer using '\n' instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed, which is usually not necessary and will lower performance.
Can it crash?
Your code doesn't contain any obvious bugs, you are using STL containers so there are no memory allocation issues to worry about. There are two things I would worry about:
Input validation: are the vertex indices stored in the graph valid indices? If you are reading adjacency lists from a file for example, and there is a number in such a list that is equal or larger than the number of vertices in your graph, then you risk accessing an element past the end of the vector of vertices. This will cause a segmentation fault if you are lucky, or worse the algorithm will continue but the results are undefined.
Infinite loops. If there is an error in the algorithm, it might be that it never terminates. This would then cause it to go into an infinite loop, if you are lucky it would use more and more memory and eventually crash because you run out of memory. However, your code is fine; the only place where such a thing could happen is when dfs_cyc() calls itself recursively, but this only happens for vertices in the white set, and every time it calls itself, it moves that vertex from the white to the grey set, so this guarantees termination.
Note that computers do not have infinite memory, so technically it might still crash if your input is large enough; either because it cannot do heap allocations for the std::vectors you create, or because dfs_cyc() calls itself with such a high recursion depth that you run out of stack space.
