29 #ifndef OR_TOOLS_GRAPH_EULERIAN_PATH_H_
30 #define OR_TOOLS_GRAPH_EULERIAN_PATH_H_
34 #include "ortools/base/logging.h"
39 template <
typename Graph>
42 for (
const NodeIndex node : graph.AllNodes()) {
43 if ((graph.OutDegree(node) + graph.InDegree(node)) % 2 != 0) {
54 template <
typename NodeIndex,
typename Graph>
56 std::vector<NodeIndex>* odd_nodes) {
57 CHECK(odd_nodes !=
nullptr);
58 for (
const NodeIndex node : graph.AllNodes()) {
59 const int degree = graph.OutDegree(node) + graph.InDegree(node);
60 if (degree % 2 != 0) {
61 odd_nodes->push_back(node);
65 return odd_nodes->size() <= 2;
73 template <
typename NodeIndex,
typename Graph>
77 std::vector<bool> unvisited_edges(graph.num_arcs(),
true);
78 std::vector<NodeIndex> tour;
79 if (graph.IsNodeValid(root)) {
80 std::vector<NodeIndex> tour_stack = {root};
81 std::vector<ArcIndex> active_arcs(graph.num_nodes());
82 for (
const NodeIndex node : graph.AllNodes()) {
83 active_arcs[node] = *(graph.OutgoingOrOppositeIncomingArcs(node)).begin();
85 while (!tour_stack.empty()) {
87 bool has_unvisited_edges =
false;
89 graph.OutgoingOrOppositeIncomingArcsStartingFrom(
90 node, active_arcs[node])) {
91 const ArcIndex edge = arc < 0 ? graph.OppositeArc(arc) : arc;
92 if (unvisited_edges[edge]) {
93 has_unvisited_edges =
true;
94 active_arcs[node] = arc;
95 tour_stack.push_back(graph.Head(arc));
96 unvisited_edges[edge] =
false;
100 if (!has_unvisited_edges) {
101 tour.push_back(node);
102 tour_stack.pop_back();
115 template <
typename NodeIndex,
typename Graph>
118 std::vector<NodeIndex> tour;
127 template <
typename Graph>
137 template <
typename Graph>
140 std::vector<NodeIndex> path;
141 std::vector<NodeIndex> roots;
143 const NodeIndex root = roots.empty() ? 0 : roots.back();
150 #endif // OR_TOOLS_GRAPH_EULERIAN_PATH_H_