Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: eulerian_path
Note: This documentation is automatically generated.
Utility to build Eulerian paths and tours on a graph. For more information, see https://en.wikipedia.org/wiki/Eulerian_path. As of 10/2015, only undirected graphs are supported.
Usage:
- Building an Eulerian tour on a ReverseArcListGraph:
ReverseArcListGraph<int, int> graph;
// Fill graph
std::vector<int> tour = BuildEulerianTour(graph);
- Building an Eulerian path on a ReverseArcListGraph:
ReverseArcListGraph<int, int> graph;
// Fill graph
std::vector<int> tour = BuildEulerianPath(graph);
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThe C++ \u003ccode\u003eeulerian_path\u003c/code\u003e utility helps build Eulerian paths and tours on undirected graphs.\u003c/p\u003e\n"],["\u003cp\u003eIt provides functions like \u003ccode\u003eBuildEulerianPath\u003c/code\u003e, \u003ccode\u003eBuildEulerianTour\u003c/code\u003e, and helper functions to check graph properties.\u003c/p\u003e\n"],["\u003cp\u003eUsage involves creating a \u003ccode\u003eReverseArcListGraph\u003c/code\u003e, filling it, and then calling the appropriate function to get the path or tour as a \u003ccode\u003estd::vector\u003c/code\u003e of node indices.\u003c/p\u003e\n"],["\u003cp\u003eAs of October 2015, the utility only supports undirected graphs, meaning edges are bidirectional.\u003c/p\u003e\n"],["\u003cp\u003eRefer to the linked Wikipedia page for a detailed explanation of Eulerian paths and tours.\u003c/p\u003e\n"]]],["This C++ utility builds Eulerian paths and tours on undirected graphs using `ReverseArcListGraph`. Key functions include `BuildEulerianPath` and `BuildEulerianTour`, which generate a vector representing the path or tour. `BuildEulerianPathFromNode` and `BuildEulerianTourFromNode` allow specifying a starting node. Additionally, `IsEulerianGraph` and `IsSemiEulerianGraph` check if a graph is Eulerian or semi-Eulerian.\n"],null,["# eulerian_path\n\nC++ Reference: eulerian_path\n============================\n\n\nNote: This documentation is automatically generated.\nUtility to build Eulerian paths and tours on a graph. For more information, see \u003chttps://en.wikipedia.org/wiki/Eulerian_path\u003e. As of 10/2015, only undirected graphs are supported. \n\nUsage: \n- Building an Eulerian tour on a ReverseArcListGraph: \nReverseArcListGraph\\\u003cint, int\\\u003e graph; \n// Fill graph \nstd::vector\\\u003cint\\\u003e tour = BuildEulerianTour(graph); \n\n\u003cbr /\u003e\n\n- Building an Eulerian path on a ReverseArcListGraph: \nReverseArcListGraph\\\u003cint, int\\\u003e graph; \n// Fill graph \nstd::vector\\\u003cint\\\u003e tour = BuildEulerianPath(graph); \n\n| Function | Type | Arguments | Comments |\n|----------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------|-----------|----------|\n| [`BuildEulerianPath`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/eulerian_path.h#L138) | Return type: `std::vector\u003ctypename Graph::NodeIndex\u003e ` Arguments: `const Graph& graph` \u003cbr /\u003e |\n| [`BuildEulerianPathFromNode`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/eulerian_path.h#L74) | Return type: `std::vector\u003cNodeIndex\u003e ` Arguments: `const Graph& graph, NodeIndex root` \u003cbr /\u003e |\n| [`BuildEulerianTour`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/eulerian_path.h#L128) | Return type: `std::vector\u003ctypename Graph::NodeIndex\u003e ` Arguments: `const Graph& graph` \u003cbr /\u003e |\n| [`BuildEulerianTourFromNode`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/eulerian_path.h#L116) | Return type: `std::vector\u003cNodeIndex\u003e ` Arguments: `const Graph& graph, NodeIndex root` \u003cbr /\u003e |\n| [`IsEulerianGraph`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/eulerian_path.h#L40) | Return type: `bool ` Arguments: `const Graph& graph` \u003cbr /\u003e |\n| [`IsSemiEulerianGraph`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/eulerian_path.h#L55) | Return type: `bool ` Arguments: `const Graph& graph, std::vector\u003cNodeIndex\u003e* odd_nodes` \u003cbr /\u003e |"]]