Mixed Graph Euler Circuit

This is a graph orientation problem. Please search for the keyword for more details.

This problem determines whether a mixed graph has an eulerian circuit, and asks to print a solution.

1) Instantiate two graphs, G_undirected and G_directed. Storing undirected and directed edges independently.
2) First freely assign all undirected edges in the graph to be one direction
3) Then, calculate the in degree and out degree differences of each vertex.
4) Create two new vertices s, t.
For each vertex u , indegree[u] > outdegree[u] ,
Create an edge ( u , t ) = indegree[u] - outdegree[u] .

For each vertex u , indegree[u] < outdegree[u] , Create en edge ( s , u ) = outdegree[u] - indegree[u] . 5) Perform maximum flow from s to t. If total flow equals that going out from s or going into t , Euler Circuit exists. 6) Lastly, merge the flow graph with the directed graph portion. Perform a euler circuit ( DFS ) to print the euler circuit.

Pseudocode as follows : ================================================================ // Graph setup
Original Graph G ;
Hide all directed edges ;
Assign all undirected edges a single direction ;

For each vertex v :
{
if ( indegree[v] - outdegree[v] > 0 )
create an edge with ( v , tank ) of capacity ( (indegree[v]-outdegree[v]) / 2 )
if ( indegree[v] - outdegree[v] < face="courier new"> create an edge with ( source , v ) of capacity ( (outdegree[v]-indegree[v]) / 2 )
}

total_flow = maximum_flow(G);

if ( total_flow == out_flow(source) || total_flow == in_flow(tank) )
{
// there is eulerian circuit
Assign the directions of the undirected edges as in the flow graph and merge with the original directed edge only graph.
Circuit = get_euler_circuit(G);
print_path(Circuit);
}

================================================================



Follow ups :

I'll just update this with a more verbal explanation.
Actually, when you are forcing a direction in 2), you are trying to then link the vertices with uneven in and out indegrees, and trying to "dampen" the difference each iteration if a flow is possible by reversing the edges used to flow. ( so the in degree of a vertex - 1 and out degree of a vertice + 1 , making it more even ), eventually it reaches a state where all vertices in degree equals out degree.

All vertices in-degree == out-degree.
Done!

By the way, this graph is assumed to be connected.


Problem Source :
http://acm.uva.es/p/v107/10735.html