You have a directed graph that is symmetrical in the sense that iff there is an A->B edge then B->A exists as well. Does this graph always have an Euler circuit without repeating any edges (assuming that the graph is strongly connected) ? Any quick algorithm for it ?
In practice this problem is the same as asking if it is possible to run all paths in a park in both directions in an optimal manner.
It seems the following. Since the graph is strongly connected and $\operatorname{in-degree}(v)=\operatorname{out-degree}(v)$ for each its vertex $v$, the graph has an Euler circuit, which can be found in $O(E)$ time (see p.70 in the script of a lecture “Round trips” in Algorithmic Graph Theory by Joachim Spoerhase and Alexander Wolff. From the other side, it is clear that there is no essentially asymptotically quicker algorithm.