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```

Answer 1

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:

1. 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 :)
2. 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
3. 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);
 }

4. 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
5. 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).

• William Golovlev: 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...