Click here to Skip to main content
15,031,687 members
Please Sign up or sign in to vote.
1.50/5 (2 votes)
See more:
I am making a directed Graph class. I want find if there is any Cycle and update a vector with it's path accordingly. My Function some times work but others add two times the last edge of the path.So i guess it needs to be tydied up.

Example: having a Graph with these paths

0->1, 0->2, 1->2, 2->3, 3->4, 4->0, 4->6, 1->5, 5->6

should set the vector to [0 2 3 4] or anything else valid.

I can obviously do something like this:
C++
if (path.end()[-2]==path.end()[-1]) path.pop_back();


What I have tried:

C++
Graph{
    private:
        int V;			// No. of vertices
        list<int> *adj; // Pointer to array containing adjacency lists
        ...
    };
          

    bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack, vector<int> &path) const {
        if (visited[v] == false) {
            // Mark the current node as visited and part of recursion stack
            visited[v] = true;
            recStack[v] = true;
    
            // Recur for all the vertices adjacent to this vertex
            list<int>::iterator i;
            for (i = adj[v].begin(); i != adj[v].end(); ++i) {
                if (!visited[*i] && isCyclicUtil(*i, visited, recStack, path)){
                    path.push_back(*i);
                    return true;}
                else if (recStack[*i]){
                    path.push_back(*i);
                    return true;}
            }
        }
        recStack[v] = false; // remove the vertex from recursion stack
        path.pop_back();
        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 recursive helper function to detect cycle in different DFS trees
        for (int i = 0; i < V; i++){
            path.push_back(i);
            if (isCyclicUtil(i, visited, recStack, path)) {
                reverse(path.begin(),path.end());
                //path.pop_back();
                return true;
            }
            path.clear();
        }
        path.clear();
        return false;
    }
Posted
Updated 20-May-21 7:11am
v3

Just wow.
C++
if (path.end()[-2]==path.end()[-1]) path.pop_back();
Is this allowed?! I have no idea. Negative indices normally aren't allowed, but I see what you're trying to do. The standard way to write
C++
path.end()[-1]
is
C++
std::prev(path.end()) // this is an iterator, so dereference it to look at the vector entry
Now do you see the problem? Not only are you hacking to cover up your bug, your code doesn't do what you think. Which two entries contain the repeated vertex? Even if using a negative index on the end() iterator works, think about what your code is saying.

To find out why a vertex is repeated, use a debugger. This is a small program, so it's tempting to debug it by hand. But that's not working, so learn how to use a debugger. When you're dealing with a larger program, it's the only way to find and fix bugs.

EDIT: I'm not going to manually debug your code, but I came back to it and noticed this:
C++
if (visited[v] == false)
Although that's legal, it's standard to simply write
C++
if (!visited[v])
   
v4
Comments
Richard MacCutchan 16-May-21 8:30am
   
Nothing wrong with negative subscripts, as long as path.end()[-x] still addresses a valid member of the array.
Greg Utas 16-May-21 8:35am
   
It's always a good day when you learn something!
Richard MacCutchan 16-May-21 8:37am
   
Yes, if only I could remember it all.
gklempe27 16-May-21 14:50pm
   
Did you find any solution to my problem?
Greg Utas 16-May-21 15:33pm
   
It's unlikely that anyone here will debug your code. If you poke around these forums, you will find tons of examples of people asking, "Where's the bug in my code?" And unless the bug is staring us right in the face, the answer is almost always that you need to learn how to use a debugger so that you can find the bug yourself. Your development environment should have a breakpoint debugger. If for some reason it doesn't, your functions can write to the console to show the parameters they received, the updates they made to data structures, and so on.
Richard MacCutchan 17-May-21 3:03am
   
Sorry, no. I don't really understand what that code is doing, or what it is supposed to be doing.
Quote:
My Function some times work but others add two times the last edge of the path.

With same dataset or with another one ?
Quote:
So i guess it needs to be tydied up.

Time to learn how debugger works.
Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900