This method draws an Eulerian Circuit from a directed graph. The graph is represented by an array of Deques representing outgoing edges. It does not have to be Deques if there is a more efficient data type; as far as I can tell the Deque is the most efficient implementation of a stack but I could be wrong.

I've tried replacing the ArrayDeques with LinkedLists but it doesn't make any difference.

I've tried keeping an array edgeCount rather than checking the number of nodes using edges[currentVertexNumber].size() > 0. But that makes it slower.

import java.util.*;



class PrintCircuit{
    /**
     *
     * @param edges list of adjacent vertices for current edges
     * @return circuit in deque list
     */
    Deque<Integer> makeEulerianCircuit(Deque<Integer>[] edges, int numberOfNodes)
    {

        // return empty list for empty graph
        if (edges.length==0)
            return new LinkedList<>(); //empty graph

        // Stack for the path in the current iteration
        Deque<Integer> currentPath = new ArrayDeque<>();

        // queue for the final circuit
        Deque<Integer> circuit = new ArrayDeque<>();

        // start from any vertex
        currentPath.push(0);
        int currentVertexNumber = 0; // Current vertex

        while (!currentPath.isEmpty())
        {
            //if there are outgoing edges
            if (edges[currentVertexNumber].size() > 0)
            {
                currentPath.push(currentVertexNumber);
                int nextVertexNumber = edges[currentVertexNumber].pop();
                currentVertexNumber = nextVertexNumber;
            }

            // otherwise step back
            else
            {
                circuit.add(currentVertexNumber);
                currentVertexNumber = currentPath.pop();
            }
        }

        return circuit;

    }


    public static void main(String[] args)
    {

        PrintCircuit pc = new PrintCircuit();
        pc.inputAndPrintCircuit();

    }


    /**
     * Get the input, check to make sure the graph is even and run the printCircuit function
     */
    private void inputAndPrintCircuit(){
        Scanner scanner = new Scanner(System.in);
        int[] in = new int[2];
        in[0] = scanner.nextInt();
        in[1] = scanner.nextInt();
        Deque<Integer>[] edges = new Deque[in[0]];
        for(int i=0;i<in[0];i++)
        {
            edges[i] = new ArrayDeque<>();
        }

        // evenChecker is a Nx2 array where [0] = incoming edges and [1] = outgoing edges
        //should be equal or graph isn't Eulerian
        int[][] evenChecker = new int[in[0]][2];
        for (int i = 0; i < in[1]; i++) {
            int from = scanner.nextInt()-1;
            int to = scanner.nextInt()-1;
            evenChecker[from][0]++;
            evenChecker[to][1]++;
            edges[from].push(to);

        }
        if(!isGraphEven(evenChecker)){
            System.out.println("0");
            System.exit(0);
        } else {
            System.out.println("1");
        }
        Deque<Integer> circuit = makeEulerianCircuit(edges, in[0]);
        while(circuit.size()>1){
            int nextNode = circuit.pollLast()+1;
            System.out.print(nextNode + " ");
        }
        System.out.println();
    }

    /**
     * checks to make sure that incoming edges = outgoing edges
     * @param evenChecker a Nx2 array where [0] = incoming edges and [1] = outgoing edges
     * @return true if incoming eges = outgoing edges, false otherwise
     */
    private boolean isGraphEven(int[][] evenChecker){
        for(int[] evenCheck:evenChecker){
            if(evenCheck[0]!=evenCheck[1]){
                return false;
            }
        }
        return true;
    }



}

Is there anything that can make this faster? Better data structures? A more efficient algorithm? Right now it's not passing the assignment I'm writing it for, and I can't think of anything to make it work more efficiently.

Update: Here are the specifications of the assignment:

Task. Given a directed graph, find an Eulerian cycle in the graph or report that none exists.

Input Format. The first line contains integers n and m — the number of vertices and the number of edges, respectively. Each of the following m lines specifies an edge in the format “u v”. (As usual, we assume that the vertices of the graph are {1, 2, . . . , n}.) The graph may contain self-loops (that is, edges of the form (v, v)) and parallel edges (that is, several copies of the same edge). It is guaranteed that the graph is strongly connected.

Constraints. 1 ≤ n ≤ 104 ; n ≤ m ≤ 105 ; 1 ≤ u, v ≤ n.

Output Format. If the graph has no Eulerian cycle, output 0. Otherwise output 1 in the first line and a sequence v1, v2, . . . , vm of vertices in the second line. This sequence should traverse an Eulerian cycle in the graph: (v1, v2),(v2, v3), . . . ,(vm−1, vm),(vm, v1) should all be edges of the graph and each edge of the graph should appear in this sequence exactly once. As usual, the graph may contain many Eulerian cycles (in particular, each Eulerian cycle may be traversed starting from any of its vertices). You may output any one of them.

Here is some sample input: Input:

3 4

2 3

2 2

1 2

3 1

Output:

1

1 2 2 3

I've also updated the above to include the entire program.

  • 4
    Why does this return an Eulerian circuit? It seems like it just does a depth first search. – JS1 Mar 3 at 5:30
  • In what sense it doesn't pass the assignment? – vnp Mar 3 at 7:00
  • anything that can make this [… pass] the assignment without a proper specification what the code is to achieve there is no way to improve it systematically. Where is the javadoc for makeEulerianCircuit()? What algorithm are you trying to implement? – greybeard Mar 3 at 8:17
  • I've now included the whole program plus javadocs and the specifications of the assignment. – jimboweb Mar 3 at 14:03
  • @vnp it does not pass the assignment because it's too slow. There are 47 tests; my program passes the first 40-43 before running over the expected time to pass. – jimboweb Mar 5 at 16:40
up vote 1 down vote accepted

This is going to be a performance at the cost of readability post, see explicit praise for the comments, only for a regular code review.
There always are "microefficiencies" one could worry about - and shouldn't, at least not until all bigger points are taken care of and a problem persists.
Still, it is advisable to start with emphasis on readability and improve the algorithm there.
One thing that might catch a would-be performance coder unawares is Java io performance - in particular, java.util.Scanner gets bashed. (I haven't tried to do useful measurements, I suspect it is comparatively bad only with big input files and no buffering.) For the hell of it:

/** Parses InputStream for smallish natural numbers: <code>char</code>s.
 * Skips non-digits; returns -1 - '0' on end-of-file */
class Chars { boolean hasCurrent; char current;
    final java.io.InputStream in;
    Chars() { this(System.in); }
    Chars(java.io.InputStream in) {
        this.in = in instanceof java.io.BufferedInputStream
            ? in : new java.io.BufferedInputStream(in);
    }
    /** @return current <code>char</code>. */
    public char current() {
        if (!hasCurrent)
            throw new RuntimeException("no current char");
        return current;
    }
    /** @return next <code>char</code>. */
    public char next() {
        try { int c, n = 0;
            while (!Character.isDigit(c = in.read()))
                if (-1 == c) // EOF
                    break; // throw? return 0?
            n = c - '0';
            while (Character.isDigit(c = in.read()))
                n = 10*n + c - '0';
            hasCurrent = true;
            return current = (char)n;
        } catch (IOException e) { throw new RuntimeException(e); }
    }
}

Another point is memory occupancy at every level of the hierarchy. The Constraints read no number exceeds 105 - short or char should do fine instead of int.
Instead of counting incoming and outgoing edges separately, keep balances (incremented for one, decremented for the other): graph not Eularian if any balance differs from zero after input.
As a rule, instantiate "Java Collection Framework classes" using an expected size where possible. Here, no vertex will have more than m-n outgoing edges - but even instantiating n "Array-Collection"s with that size is Θ(n*m). Not specifying a capacity leads to Θ(mlogm) time if "almost all" edges are from one vertex.
java.util.LinkedList<E> should be linear, but with high factors - for the hell of it:

/** Graph vertex keeping a <code>List</code> of successors.
 * (Only <code>add()</code> and <code>iterator()</code> are useful.) */
static class Vertex extends java.util.AbstractList<Vertex>
    implements java.util.Iterator<Vertex>//, List<Vertex> 
{
    Object label;
    static class Node {
        Node next;
        final Vertex v;
        public Node(Vertex v, Node next) {
            this.v = v;
            this.next = next;
        }
        @Override
        public String toString() {
            return new StringBuilder("N_").append(v.label).toString();
        }
    }
    Vertex.Node first;
//  static class Iterator implements java.util.Iterator<Vertex> {
        Vertex.Node next;
//      public Iterator(Vertex.Node first) { next = first; }
        public boolean hasNext() { return null != next; }
        public Vertex next() {
            Vertex current = next.v;
            next = next.next;
            return current;
        }
//  }

    public Vertex(Object label) { this.label = label; }
    static public final Vertex[]NONE = {};
    @Override
    public String toString() {
        return new StringBuilder("V_").append(label).toString();
    }

    @Override
    public boolean add(Vertex v) {
        first = new Node(v, first);
        return true;
    }
    @Override
    public Iterator<Vertex> iterator() {
        next = first;
        return this;
    }
    @Override
    public Vertex get(int index) { return null; }
    @Override
    public int size() { return null == first ? 0 : 1; }
}

(There would be a way to use arrays, only - "FORTRAN", don't currently feel like coding that.)
Using above Vertex and an open coded stack:

/** @param vertices (index 0 shall not be used)
 * @param totalEdges total number of edges
 * @return circuit */
static Vertex[]
makeEulerianCircuit(Vertex[] vertices, int totalEdges) {
    if (vertices.length == 0) // empty graph
        return Vertex.NONE;
    // Stack for the path in the current iteration
    Vertex[] currentPath = new Vertex[totalEdges];//nVertices may be too low
    int top = -1;
    // final circuit
    Vertex[] circuit = new Vertex[totalEdges];
    int visit = circuit.length;
    // start from any vertex
    Vertex currentVertex = vertices[1];
    while (true) {//currentVertex.iterator()
        if (currentVertex.hasNext()) { // there is another outgoing edge
            currentPath[++top] = currentVertex;
            currentVertex = currentVertex.next();
        } else { // otherwise step back
            circuit[--visit] = currentVertex;
            currentVertex = currentPath[top--];
            if (top < 0)
                return circuit;
        }
    }
}
  • Thank you greybeard. Sorry for my cranky response from before. I appreciate all of your input and I learned some useful things from it. I especially didn't know that Scanner doesn't have good performance. I will mark this as the answer to the question, because it does seem like it would speed things up, though I probably won't actually do it because they changed the assignment required runtime so I passed anyway and I am completely sick of this program.. – jimboweb Mar 6 at 22:52

(Usually, Eulerian circuits are considered for undirected finite graphs.)
The question is tagged - while the syntax of the code presented looks the type, the variable handling looks Fortran.
makeEulerianCircuit() and (inputAndPrintCircuit) are instance members - needlessly. While it may be useful to have an abstraction input&print, having it print the result of a non-trivial algorithm looks odd. Specify and implement an input() method (and have that handle input using try with resources).
inputAndPrintCircuit() shifts vertex numbers to differ from the problem statement - don't.
Why have an array in[] to hold input values that do have different meaning? Just use nVertices and nEdges. Similarly, consider using nOutgoing[] and nIncoming[] instead of a two-dimensional array. (Given a constant time size() for the collections of outgoing edges, you could do without nOutgoing[].)
Much as I like code commented: // empty graph is redundant (I'd drop the comment before the conditional statement and let // empty graph comment the condition (slightly overstating the issue - a connected graph without edges still might contain one vertex; input spec: nVertices ≤ nEdges).)
You don't need int nextVertexNumber - assign edges[currentVertexNumber].pop() to currentVertexNumber directly.
I think makeEulerianCircuit() depends on edges[] specifying a (strongly) connected graph: its doc comment should reflect that.

An alternative design would introduce a class Vertex, each instance holding an assortment of other vertices that can be reached from this one.

Up to now, I didn't try and convince myself makeEulerianCircuit() does indeed put together an Eulerian circuit for each connected "even" graph - in part due to lack of a test scaffold in the question.

Is there anything that can make this faster? Better data structures? A more efficient algorithm?
I think this implements Hierholzer's algorithm in O(m) (with a bit of hand-waving around adding up to m - n edges to an ArrayDeque taking Θ(mlogm) time - with constants "never" allowing LinkedList to be faster). (If that was true, there shouldn't be a performance issue - I should really set up a test.)

  • First of all , thank you for responding. Just to be clear, except for the last sentence everything is a critique of my coding style, rather than an answer to the question I asked, and that your answer to the question that I asked is that you don't know? To answer your questions: it does return an eulerian circuit, in my tests and the assignment's tests; it's just too slow. You can see the test here: github.com/jimboweb/hierholzer3 . And the reason the coding style "looks like Fortran" is because I've stripped it to the bare minimum in an attempt to be fast enough to pass. – jimboweb Mar 5 at 16:43
  • From What topics can I ask about here?: Do I want feedback about any or all facets of the code? Feel free to call attention to specific areas you are concerned about (performance, formatting, etc). However, any aspect of the code posted is fair game for feedback and criticism. How do I write a good answer?: Every answer must make at least one insightful observation about the code in the question. … Answers need not cover every issue in every line of the code. – greybeard Mar 6 at 11:13
  • Okay, sorry, I should have just listened to your ideas. – jimboweb Mar 6 at 22:46

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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