OR-Tools  8.2
eulerian_path.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Utility to build Eulerian paths and tours on a graph. For more information,
15// see https://en.wikipedia.org/wiki/Eulerian_path.
16// As of 10/2015, only undirected graphs are supported.
17//
18// Usage:
19// - Building an Eulerian tour on a ReverseArcListGraph:
20// ReverseArcListGraph<int, int> graph;
21// // Fill graph
22// std::vector<int> tour = BuildEulerianTour(graph);
23//
24// - Building an Eulerian path on a ReverseArcListGraph:
25// ReverseArcListGraph<int, int> graph;
26// // Fill graph
27// std::vector<int> tour = BuildEulerianPath(graph);
28//
29#ifndef OR_TOOLS_GRAPH_EULERIAN_PATH_H_
30#define OR_TOOLS_GRAPH_EULERIAN_PATH_H_
31
32#include <vector>
33
35
36namespace operations_research {
37
38// Returns true if a graph is Eulerian, aka all its nodes are of even degree.
39template <typename Graph>
40bool IsEulerianGraph(const Graph& graph) {
41 typedef typename Graph::NodeIndex NodeIndex;
42 for (const NodeIndex node : graph.AllNodes()) {
43 if ((graph.OutDegree(node) + graph.InDegree(node)) % 2 != 0) {
44 return false;
45 }
46 }
47 // TODO(user): Check graph connectivity.
48 return true;
49}
50
51// Returns true if a graph is Semi-Eulerian, aka at most two of its nodes are of
52// odd degree.
53// odd_nodes is filled with odd nodes of the graph.
54template <typename NodeIndex, typename Graph>
55bool IsSemiEulerianGraph(const Graph& 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);
62 }
63 }
64 // TODO(user): Check graph connectivity.
65 return odd_nodes->size() <= 2;
66}
67
68// Builds an Eulerian path/trail on an undirected graph starting from node root.
69// Supposes the graph is connected and is eulerian or semi-eulerian.
70// This is an implementation of Hierholzer's algorithm.
71// If m is the number of edges in the graph and n the number of nodes, time
72// and memory complexity is O(n + m).
73template <typename NodeIndex, typename Graph>
74std::vector<NodeIndex> BuildEulerianPathFromNode(const Graph& graph,
75 NodeIndex root) {
76 typedef typename Graph::ArcIndex ArcIndex;
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();
84 }
85 while (!tour_stack.empty()) {
86 const NodeIndex node = tour_stack.back();
87 bool has_unvisited_edges = false;
88 for (const ArcIndex arc :
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;
97 break;
98 }
99 }
100 if (!has_unvisited_edges) {
101 tour.push_back(node);
102 tour_stack.pop_back();
103 }
104 }
105 }
106 return tour;
107}
108
109// Builds an Eulerian tour/circuit/cycle starting and ending at node root on an
110// undirected graph.
111// This function works only on Reverse graphs
112// (cf. ortools/graph/graph.h).
113// Returns an empty tour if either root is invalid or if a tour cannot be built.
114// As of 10/2015, assumes the graph is connected.
115template <typename NodeIndex, typename Graph>
116std::vector<NodeIndex> BuildEulerianTourFromNode(const Graph& graph,
117 NodeIndex root) {
118 std::vector<NodeIndex> tour;
119 if (IsEulerianGraph(graph)) {
120 tour = BuildEulerianPathFromNode(graph, root);
121 }
122 return tour;
123}
124
125// Same as above but without specifying a start/end root node (node 0 is taken
126// as default root).
127template <typename Graph>
128std::vector<typename Graph::NodeIndex> BuildEulerianTour(const Graph& graph) {
129 return BuildEulerianTourFromNode(graph, 0);
130}
131
132// Builds an Eulerian path/trail on an undirected graph.
133// This function works only on Reverse graphs
134// (cf. ortools/graph/graph.h).
135// Returns an empty tour if a tour cannot be built.
136// As of 10/2015, assumes the graph is connected.
137template <typename Graph>
138std::vector<typename Graph::NodeIndex> BuildEulerianPath(const Graph& graph) {
139 typedef typename Graph::NodeIndex NodeIndex;
140 std::vector<NodeIndex> path;
141 std::vector<NodeIndex> roots;
142 if (IsSemiEulerianGraph(graph, &roots)) {
143 const NodeIndex root = roots.empty() ? 0 : roots.back();
144 path = BuildEulerianPathFromNode(graph, root);
145 }
146 return path;
147}
148} // namespace operations_research
149
150#endif // OR_TOOLS_GRAPH_EULERIAN_PATH_H_
#define CHECK(condition)
Definition: base/logging.h:495
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsEulerianGraph(const Graph &graph)
Definition: eulerian_path.h:40
bool IsSemiEulerianGraph(const Graph &graph, std::vector< NodeIndex > *odd_nodes)
Definition: eulerian_path.h:55
std::vector< typename Graph::NodeIndex > BuildEulerianPath(const Graph &graph)
std::vector< typename Graph::NodeIndex > BuildEulerianTour(const Graph &graph)
std::vector< NodeIndex > BuildEulerianPathFromNode(const Graph &graph, NodeIndex root)
Definition: eulerian_path.h:74
std::vector< NodeIndex > BuildEulerianTourFromNode(const Graph &graph, NodeIndex root)
ListGraph Graph
Definition: graph.h:2360