# Recursive DFS to find Euler Cycle

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;

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);
//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) {

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

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


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);
}

1. 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
2. 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... Nov 6 '21 at 2:31