import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Record;
// A category to retailer a graph edge
class Edge
int supply, dest;
public Edge(int supply, int dest)
this.supply = supply;
this.dest = dest;
// A category to signify a graph object
class Graph
// A listing of lists to signify an adjacency record
Record<Record<Integer>> adjList;
// shops indegree of a vertex
Record<Integer> in;
// Constructor
Graph(int n)
adjList = new ArrayList<>();
for (int i = 0; i < n; i++)
adjList.add(new ArrayList<>());
// initialize indegree of every vertex by 0
in = new ArrayList<>(Collections.nCopies(n, 0));
// Utility perform so as to add an edge (u, v) to the graph
void addEdge(int u, int v)
// add an edge from supply to vacation spot
adjList.get(u).add(v);
// increment in-degree of vacation spot vertex by 1
in.set(v, in.get(v) + 1);
class Predominant
{
// Operate to carry out DFS traversal on the graph
public static void DFS(Graph graph, int v, boolean[] found)
// mark the present node as found
found[v] = true;
// do for each edge (v, u)
for (int u: graph.adjList.get(v))
// `u` isn’t found
if (!found[u])
DFS(graph, u, found);
// Operate to exchange all of the directed edges of the graph with undirected edges
// and produce an undirected graph
public static Graph getUndirectedGraph(Graph graph, int n)
Graph g = new Graph(n);
for (int u = 0; u < n; u++)
for (int v: graph.adjList.get(u)) // for each edge (u, v)
g.addEdge(v, u);
g.addEdge(u, v);
return g;
// Operate to examine if all vertices with a non-zero diploma in a graph
// belong to a single linked part
public static boolean isConnected(Graph graph, int n)
// preserve observe of all beforehand visited vertices in DFS
boolean[] visited = new boolean[n];
// begin DFS from the primary vertex with a non-zero diploma
for (int i = 0; i < n; i++)
if (graph.adjList.get(i).measurement() > 0)
DFS(graph, i, visited);
break;
// if a single DFS name could not go to all vertices with a non-zero diploma,
// the graph accommodates multiple linked part
for (int i = 0; i < n; i++)
if (!visited[i] && graph.adjList.get(i).measurement() > 0)
return false;
return true;
// Operate to examine if a directed graph has an Eulerian path
public static boolean hasEulerPath(Graph graph, int n)
/*
The next loop checks the next situations to find out if an
Eulerian path can exist or not:
a. At most one vertex within the graph has `out-degree = 1 + in-degree`.
b. At most one vertex within the graph has `in-degree = 1 + out-degree`.
c. Relaxation all vertices have `in-degree == out-degree`.
If both of the above situation fails, the Euler path cannot exist.
*/
boolean x = false, y = false;
for (int i = 0; i < n; i++)
int out_degree = graph.adjList.get(i).measurement();
int in_degree = graph.in.get(i);
if (out_degree != in_degree)
if (!x && out_degree – in_degree == 1)
x = true;
else if (!y && in_degree – out_degree == 1)
y = true;
else
return false;
// contemplate given edges as undirected and examine if all non-isolated vertices
// belong to a single linked part
return isConnected(getUndirectedGraph(graph, n), n);
public static void principal(String[] args)
// Record of graph edges as per the above diagram
Record<Edge> edges = Arrays.asList(new Edge(0, 1), new Edge(1, 2),
new Edge(2, 3), new Edge(3, 1), new Edge(1, 4), new Edge(4, 3),
new Edge(3, 0), new Edge(0, 5), new Edge(5, 4)
);
// whole variety of nodes within the graph (labelled from 0 to five)
int n = 6;
// construct a directed graph from the above edges
Graph graph = new Graph(n);
// add edges to the directed graph
for (Edge edge: edges)
graph.addEdge(edge.supply, edge.dest);
if (hasEulerPath(graph, n))
System.out.println(“The graph has an Eulerian path”);
else
System.out.println(“The Graph does not have an Eulerian path”);
}
