Is there some way of breaking of a recursive call before it goes all the way to the end

Ranch Hand

Posts: 37

posted 3 weeks ago

Number of slices to send:

Optional 'thank-you' note:

Send

Greetings-
In the following code I am trying to see if a graph has Eularian cycles, and I am goind recursive BFS. I would like to stop as soon as I find one cycle with all its vertices having an even degree. The entire VSCode project is at GitHub Repo here is a snipet:

public boolean eulerianBFS(Graph G) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        bfs(G, 0);
        return eulerian;
    }
private void bfs(Graph G, int i) {
        marked[i] = true;
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(i);
        First:
        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            for (int w : G.adj(v)) {
                if (marked[w]) {
                    // if it is marked, we have a cycle
                    cycle = new Stack<>();
                    eulerian = true;
                    for (int x = v; x != i; x = edgeTo[x]) {
                        if (G.degree(x) % 2 == 1) {
                            eulerian = false;
                        }
                        cycle.push(x);
                    }
                    cycle.push(w);
                    if (G.degree(w) % 2 == 1) {
                        eulerian = false;
                    }
                    cycle.push(i);
                    if (G.degree(i) % 2 == 1) {
                        eulerian = false;
                    }
                    if (eulerian == true){
                        System.out.println("Found a Eularian cycle.");
                        break First; // Jump our of the loop. I found a 
                    } 
                } else {
                    edgeTo[w] = v;
                    bfs(G, w);
                }
            }
        }
    }

All of my unit tests give me the right answer, but I might have an error. I can only go by the result I get. The repo has everything including the jar file library that has the other data structures I am using like Graph, Queue, and etc.

Lou Hamers

Bartender

Posts: 280

I like...

posted 3 weeks ago

2
Number of slices to send:

Optional 'thank-you' note:

Send

Sorry that I definitely don't have the brain power tonight to look closely, but I suggest for starters you try moving those for loops (especially the big one) into their own method calls, and use return statements instead.

I suspect that might lead you to your own solution, too. (...Maybe not, but breaking problems into smaller problems is generally a good strategy.) Someone will probably come along with better a suggestion soon, I'm sure.

Stephan van Hulst

Saloon Keeper

Posts: 15608

366

posted 3 weeks ago

3
Number of slices to send:

Optional 'thank-you' note:

Send

The big problem is that you're not really doing a breadth-first search. You're never adding any elements to the search queue. Instead, you're making a recursive call to bfs(), which turns this into a depth-first search.

A second issue is the use of instance fields where they should be local variables. Why are eulerian, marked, edgeTo and cycle not local variables?

Another issue are the names. Make your code clearer by changing your identifiers:

Change	To
`G.V()`	`graph.numberOfVertices()`
`bfs`	`findEulerianCycle`
`i`	`startVertex`
`v`	`currentVertex`
`w`	`adjacentVertex`

Campbell Ritchie

Marshal

Posts: 79392

377

posted 3 weeks ago

1
Number of slices to send:

Optional 'thank-you' note:

Send

Another issue: i % 2 == 1 is not a reliable way to find odd numbers; it will miss approximately 50% of them.

Mike Simmons

Master Rancher

Posts: 4905

posted 3 weeks ago

1
Number of slices to send:

Optional 'thank-you' note:

Send

Although, if the graph indices are guaranteed to be non-negative, this will not be an issue.