Search of Eulerian cycle
Eulerian cycle, or circuit is a closed path which visits every edge of a graph just once.
Graphonline.ru uses search algorithm based on cycles.
Let’s consider the general case, the case of oriented multigraph, possibly with self-loops. Moreover, we assume that there is a eulerian path in the graph and it consists of one vertex at least. In order to find the eulerian trail we will take into account that a eulerian path is the aggregation of all simple cycles of the graph. Consequently, our task is to find all the cycles effectively and combine them into one, effectively as well.
Besides, before searching for a cycle, the service checks whether a cycle exists or not. In this regard there is a search of vertices degree.
You may find more detailed information about the algorithm in Wikipedia.
The implementation of the algorithm in C++ may be found in our repository on GitHub: The implementation of Eulerian trail search in Graphoffline.
How to use
- Create a graph.
- Select “Find Eulerian cycle” in the menu bar.