Recursive DFS to find Euler Cycle

Question

I have referred to this for what constitutes as an Euler Cycle: https://xlinux.nist.gov/dads/HTML/eulercycle.html

This assignment required me to use Depth First Search and have the methods I have included. I am also required to use the Graph class provided here: https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Graph.java.html

I have tested and in my eyes, it works well. Code wise, I feel like it has a lot to improve hence I am here to ask for simple/general advice.

import edu.princeton.cs.algs4.GraphGenerator;

import java.util.ArrayList;
import java.util.LinkedList;

public class EulerFinder {
    private Graph g;
    private boolean[] visited;
    private  ArrayList<Integer> order = new ArrayList<>();

    public EulerFinder(Graph g) {
        System.out.println("og graph for reference:\n");
        System.out.println(g);
        System.out.println("------------------------------");
        this.g = g;
        visited = new boolean[g.E()];
        if (hasCycle(g)) {
            System.out.println("The cycle for the generated graph is: ");
            for (int vertex : verticesInCycle()) {
                System.out.println(vertex);
            }
        } else {
            System.out.println("No Euler cycle could be found");
        }
    }
    public static void main(String[] args) {
        Graph graph1 = new Graph(4);
        graph1.addEdge(3, 1);
        graph1.addEdge(1, 0);
        graph1.addEdge(0, 2);
        graph1.addEdge(2, 3);
        //Graph graph = GraphGenerator.eulerianCycle(5, 5);
        EulerFinder result = new EulerFinder(graph1);
    }

    public boolean hasCycle(Graph g) {
        if (!evenDegree(g))
            return false;
        return true;
    }
    private boolean evenDegree(Graph g) {
        for(int i = 0; i < g.V(); i++) {
            if(g.degree(i) %2 != 0)
                return false;
        }
        return true;
    }
    private void DFS(int vertex) {
        order.add(vertex);

        visited[vertex] = true;
        Iterable<Integer> next = g.adj(vertex);
        for (int adj : next) {
            if(!visited[adj]) {
                DFS(adj);
            }
        }
    }


    public ArrayList<Integer> verticesInCycle() {
        if (g.E() > 0) {
            DFS(g.E() - 1);
        } else
            System.out.println("\nNone! There must be more than 0 edges...");
        return order;
    }

}

the output for the above example (from main) yields:

og graph for reference:

4 vertices, 4 edges 
0: 2 1 
1: 0 3 
2: 3 0 
3: 2 1 

------------------------------
The cycle for the generated graph is: 
3
2
0
1

Process finished with exit code 0```

Azahe · Accepted Answer · 2021-11-05 14:52:49Z

Given it seems to be princeton.cs.algs4 course task I am not entirely sure what would be the best answer here. I'd assume you are suppose to learn and learning limited number of things at a time (here DFS and euler cycles?) is pretty good practice, so in terms of what purpose does this code serve if you wrote it, it works and you understand why - it seems already pretty good.

Assuming you are asking for tips outside of the above scope that you can consider:

writing tests - in general high quality, production-grade, code usually requires some automatic correctness verification, most often represented by tests (unit, integration etc... here probably unit tests are enough), you can consider writing tests for this solution - then you will not need to feel that it is correct - you will be able to prove it :)
limiting mutability - from my experience during studies this point was not emphasized enough, generally its easier to reason about the code if fields are immutable by default - and only strictly necessary state is mutable
Using IDE with some static analysis (like Intelij Idea with SonarLint plugin... and default inspections for java - you can find them in options) - it will not be perfect but should point out such classics like:

    public boolean hasCycle(Graph g) {
        if (!evenDegree(g))
            return false;
        return true;
    }

that could be replaced with (not to mention that inner function could be inlined):

    public boolean hasCycle(Graph g) {
        return evenDegree(g);
    }

Names - its not that big thing in such a project but in general abbreviations (like g for graph) are not always more readable - you can try to think on them a little
Formatting - you should aim for being consistent with your braces, newlines etc (sometimes in if/else blocks you have {}, sometimes not, some newlines are surprising) - its a cosmetic but still, professionals are expected not to introduce such noise (good IDE can help you with it too)

Don't stress on those too much though - its rather expected for learning programs to feel clunky (especially algorithmic ones).

Thank you for your comment. I was also curious as to a graph, i.e. 4 vertices. If 0-3 are all connected and even degree, and then vertex 3 is disconnected, is it still correct that my program outputs "3" instead of, say, "1,2,0"? My DFS will always choose the largest vertex possible... — William Golovlev
– William Golovlev, Commented Nov 6, 2021 at 2:31

Stack Exchange Network

Recursive DFS to find Euler Cycle

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Recursive DFS to find Euler Cycle

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions