Problem
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.
Solution
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;
}
}
}
(Usually, Eulerian circuits are considered for undirected finite graphs.)
The question is tagged java – 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.)