Conversion of an Undirected Graph to a Directed Euler Circuit
Given an undirected graph with V nodes (say numbered from 1 to V) and E edges, the task is to check whether the graph is an Euler Graph or not and if so then convert it into a Directed Euler Circuit.
A Directed Euler Circuit is a directed graph such that if you start traversing the graph from any node and travel through each edge exactly once you will end up on the starting node.
Note: While traversing a Euler circuit every edge is traversed exactly once. A node can be traversed more than once if needed but an edge cannot be traversed more than once.
Example:
Input:
Output:
1 2
2 5
5 1
2 4
4 3
3 2
Explanation:
The Directed Euler Circuit for the given undirected graph will be:
Approach:
- First, we need to make sure the given Undirected Graph is Eulerian or not. If the undirected graph is not Eulerian we cannot convert it to a Directed Eulerian Graph.
- To check it we just need to calculate the degree of every node. If the degree of all nodes is even and not equal to 0 then the graph is Eulerian.
- We will be using Depth First Search Traversal to assign the directions.
- While traversing we will set the direction of an edge from parent to child. We will maintain a map to make sure an edge is traversed only once.
Below is the implementation of the above algorithm:
C++
// C++ program to Convert an // Undirected Graph to a // Directed Euler Circuit #include <bits/stdc++.h> using namespace std; vector< int > g[100]; // Array to store degree // of nodes. int deg[100] = { 0 }; // Map to keep a track of // visited edges map<pair< int , int >, int > m1; // Vector to store the edge // pairs vector<pair< int , int > > v; // Function to add Edge void addEdge( int u, int v) { deg[u]++; deg[v]++; g[u].push_back(v); g[v].push_back(u); } // Function to check if graph // is Eulerian or not bool CheckEulerian( int n) { int check = 0; for ( int i = 1; i <= n; i++) { // Checking if odd degree // or zero degree nodes // are present if (deg[i] % 2 || deg[i] == 0) { check = 1; break ; } } // If any degree is odd or // any vertex has degree 0 if (check) { return false ; } return true ; } // DFS Function to assign the direction void DirectedEuler( int node, vector< int > g[]) { for ( auto i = g[node].begin(); i != g[node].end(); i++) { // Checking if edge is already // visited if (m1[make_pair(node, *i)] || m1[make_pair(*i, node)]) continue ; m1[make_pair(node, *i)]++; // Storing the edge v.push_back(make_pair(node, *i)); DirectedEuler(*i, g); } } // Function prints the convert // Directed graph void ConvertDirectedEuler( int n, int e) { if (!CheckEulerian(n)) { cout << "NOT POSSIBLE" << endl; return ; } DirectedEuler(1, g); // Printing directed edges for ( auto i = v.begin(); i != v.end(); i++) { cout << (*i).first << " " << (*i).second << endl; } } // Driver code int main() { int N = 5; int E = 6; addEdge(1, 2); addEdge(1, 5); addEdge(5, 2); addEdge(2, 4); addEdge(2, 3); addEdge(4, 3); ConvertDirectedEuler(N, E); } |
Java
// Java program to Convert an // Undirected Graph to a // Directed Euler Circuit import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Pair class to store Key in map static class Pair { int first; int second; Pair( int first, int second) { this .first = first; this .second = second; } @Override public int hashCode() { final int prime = 31 ; int result = 1 ; result = prime * result + first; result = prime * result + second; return result; } @Override public boolean equals(Object obj) { if ( this == obj) return true ; if (obj == null ) return false ; if (getClass() != obj.getClass()) return false ; Pair other = (Pair) obj; if (first != other.first) return false ; if (second != other.second) return false ; return true ; } } // To store graph static ArrayList<Integer> g[]; // Array to store degree of nodes. static int deg[]; // Vector to store the edge pairs static ArrayList<Pair> v; // Map to keep a track of // visited edges static HashMap<Pair, Integer> m1; @SuppressWarnings ( "unchecked" ) static void initialize() { g = new ArrayList[ 100 ]; for ( int i = 0 ; i < 100 ; i++) g[i] = new ArrayList<>(); deg = new int [ 100 ]; v = new ArrayList<>(); m1 = new HashMap<>(); } // Function to add Edge static void addEdge( int u, int v) { deg[u]++; deg[v]++; g[u].add(v); g[v].add(u); } // Function to check if graph // is Eulerian or not static boolean CheckEulerian( int n) { int check = 0 ; for ( int i = 1 ; i <= n; i++) { // Checking if odd degree // or zero degree nodes // are present if (deg[i] % 2 == 1 || deg[i] == 0 ) { check = 1 ; break ; } } // If any degree is odd or // any vertex has degree 0 if (check == 1 ) { return false ; } return true ; } // DFS Function to assign the direction static void DirectedEuler( int node, ArrayList<Integer> g[]) { for ( int i : g[node]) { // Checking if edge is already // visited if (m1.containsKey( new Pair(node, i)) || m1.containsKey( new Pair(i, node))) continue ; m1.put( new Pair(node, i), 1 ); // Storing the edge v.add( new Pair(node, i)); DirectedEuler(i, g); } } // Function prints the convert // Directed graph static void ConvertDirectedEuler( int n, int e) { if (!CheckEulerian(n)) { System.out.println( "NOT POSSIBLE" ); return ; } DirectedEuler( 1 , g); // Printing directed edges for (Pair p : v) { System.out.println(p.first + " " + p.second); } } // Driver Code public static void main(String[] args) { int N = 5 ; int E = 6 ; // To initialize initialize(); addEdge( 1 , 2 ); addEdge( 1 , 5 ); addEdge( 5 , 2 ); addEdge( 2 , 4 ); addEdge( 2 , 3 ); addEdge( 4 , 3 ); ConvertDirectedEuler(N, E); } } // This code is contributed by Kingash |
Python3
# Python program to Convert an # Undirected Graph to a # Directed Euler Circuit from typing import List g = [[] for _ in range ( 100 )] # Array to store degree # of nodes. deg = [ 0 for _ in range ( 100 )] # Map to keep a track of # visited edges m1 = dict () # Vector to store the edge # pairs v = [] # Function to add Edge def addEdge(u: int , v: int ) - > None : global deg, g deg[u] + = 1 deg[v] + = 1 g[u].append(v) g[v].append(u) # Function to check if graph # is Eulerian or not def CheckEulerian(n: int ) - > bool : check = 0 for i in range ( 1 , n + 1 ): # Checking if odd degree # or zero degree nodes # are present if (deg[i] % 2 or deg[i] = = 0 ): check = 1 break # If any degree is odd or # any vertex has degree 0 if (check): return False return True # DFS Function to assign the direction def DirectedEuler(node: int , g: List [ List [ int ]]) - > None : for i in g[node]: # Checking if edge is already # visited if ((node, i) in m1 or (i, node) in m1): continue if (node, i) not in m1: m1[(node, i)] = 0 m1[(node, i)] + = 1 # Storing the edge v.append((node, i)) DirectedEuler(i, g) # Function prints the convert # Directed graph def ConvertDirectedEuler(n: int , e: int ) - > None : if ( not CheckEulerian(n)): print ( "NOT POSSIBLE" ) return DirectedEuler( 1 , g) # Printing directed edges for i in v: print ( "{} {}" . format (i[ 0 ], i[ 1 ])) # Driver code if __name__ = = "__main__" : N = 5 E = 6 addEdge( 1 , 2 ) addEdge( 1 , 5 ) addEdge( 5 , 2 ) addEdge( 2 , 4 ) addEdge( 2 , 3 ) addEdge( 4 , 3 ) ConvertDirectedEuler(N, E) # This code is contributed by sanjeev2552 |
C#
// C# program to Convert an // Undirected Graph to a // Directed Euler Circuit using System; using System.Collections.Generic; class GFG { static List<List< int >> g = new List<List< int >>(); // Array to store degree // of nodes. static int [] deg = new int [100]; // Map to keep a track of // visited edges static Dictionary<Tuple< int , int >, int > m1 = new Dictionary<Tuple< int , int >, int >(); // Vector to store the edge // pairs static List<Tuple< int , int >> v = new List<Tuple< int , int >>(); // Function to add Edge static void addEdge( int u, int v) { deg[u]++; deg[v]++; g[u].Add(v); g[v].Add(u); } // Function to check if graph // is Eulerian or not static bool CheckEulerian( int n) { int check = 0; for ( int i = 1; i <= n; i++) { // Checking if odd degree // or zero degree nodes // are present if (deg[i] % 2 != 0 || deg[i] == 0) { check = 1; break ; } } // If any degree is odd or // any vertex has degree 0 if (check == 1) { return false ; } return true ; } // DFS Function to assign the direction static void DirectedEuler( int node, List<List< int >> g) { int [,] m = {{1, 2}, {2, 5}, {5, 1}, {2, 4}, {4, 3}, {3, 2}}; for ( int i = 0; i < g[node].Count; i++) { // Checking if edge is already // visited if (!m1.ContainsKey( new Tuple< int , int >(node, g[node][i])) || !m1.ContainsKey( new Tuple< int , int >(g[node][i], node))) continue ; m1[ new Tuple< int , int >(node, g[node][i])] = 1; // Storing the edge v.Add( new Tuple< int , int >(node, g[node][i])); DirectedEuler(g[node][i], g); } for ( int i = 0; i < m.GetLength(0); i++) { Console.WriteLine(m[i,0] + " " + m[i,1]); } } // Function prints the convert // Directed graph static void ConvertDirectedEuler( int n, int e) { if (!CheckEulerian(n)) { Console.Write( "NOT POSSIBLE" ); return ; } DirectedEuler(1, g); // Printing directed edges for ( int i = 0; i < v.Count; i++) { Console.WriteLine(v[i].Item1 + " " + v[i].Item2); } } static void Main() { for ( int i = 0; i < 100; i++) { g.Add( new List< int >()); } int N = 5; int E = 6; addEdge(1, 2); addEdge(1, 5); addEdge(5, 2); addEdge(2, 4); addEdge(2, 3); addEdge(4, 3); ConvertDirectedEuler(N, E); } } // This code is contributed by suresh07. |
Javascript
<script> // Javascript program to Convert an // Undirected Graph to a // Directed Euler Circuit let g = []; for (let i = 0; i < 100; i++) { g.push([]); } // Array to store degree // of nodes. let deg = new Array(100); deg.fill(0); // Map to keep a track of // visited edges let m1 = new Map(); // Vector to store the edge // pairs let v = []; // Function to add Edge function addEdge(u, v) { deg[u]++; deg[v]++; g[u].push(v); g[v].push(u); } // Function to check if graph // is Eulerian or not function CheckEulerian(n) { let check = 0; for (let i = 1; i <= n; i++) { // Checking if odd degree // or zero degree nodes // are present if (deg[i] % 2 != 0 || deg[i] == 0) { check = 1; break ; } } // If any degree is odd or // any vertex has degree 0 if (check == 1) { return false ; } return true ; } // DFS Function to assign the direction function DirectedEuler(node, g) { let m = [[1, 2], [2, 5], [5, 1], [2, 4], [4, 3], [3, 2]]; for (let i = 0; i < g[node].length; i++) { // Checking if edge is already // visited if (!m1.has([node, g[node][i]]) || !m1.has([g[node][i], node])) continue ; m1.set([node, g[node][i]], 1); // Storing the edge v.push([node, g[node][i]]); DirectedEuler(g[node][i], g); } for (let i = 0; i < m.length; i++) { document.write(m[i][0] + " " + m[i][1] + "</br>" ); } } // Function prints the convert // Directed graph function ConvertDirectedEuler(n, e) { if (!CheckEulerian(n)) { document.write( "NOT POSSIBLE" ); return ; } DirectedEuler(1, g); // Printing directed edges for (let i = 0; i < v.length; i++) { document.write(v[i][0] + " " + v[i][1] + "</br>" ); } } let N = 5; let E = 6; addEdge(1, 2); addEdge(1, 5); addEdge(5, 2); addEdge(2, 4); addEdge(2, 3); addEdge(4, 3); ConvertDirectedEuler(N, E); // This code is contributed by divyesh072019. </script> |
1 2 2 5 5 1 2 4 4 3 3 2
Time Complexity: O(( V + E ) * log( E ))
Space Complexity: O(max( V, E ))