eulerianTrail

This program aims to find Eulerian trails and cycles in a connected graph. The underlying algorithm is the so-called Fleury's algorithm.

The algorithm

The algorithm states that Eulerian trail exists in a graph if and only if the number of odd degrees in the graph is either 0 or 2.

1. Validate if Eulerian trail exist in the graph
2. If so, choose a starting point as follows:
   1. If the number of odd vertices is 2, pick one of them (here the first odd one)
   2. If there are no odd vertices pick any arbitrary vertex (here the first one)
3. u = starting point
4. While there are edges in the graph, do:
   1. Find edges going out from u
      1. Always go for non-bridge edges
      2. If there are no non-bridge edges left, choose a bridge
   2. Store the other vertex of the edge (nextVertex)
   3. Remove the edge from graph
   4. nextVertex = u

Usage

You can pass a command line argument pointing to an adjacency matrix that contains the graph.

Disclaimer

This source code is only for demonstration purposes for a university class without any performance considerations or optimizations.