0
\$\begingroup\$

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```
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ 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... \$\endgroup\$ Nov 6 '21 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.