graphs.eulerian_path_and_circuit_for_undirected_graph

Functions

check_circuit_or_path(graph, max_node)	For checking in graph has euler path or circuit
check_euler(→ None)	Args:
dfs(u, graph, visited_edge[, path])	Using dfs for finding eulerian path traversal
main(→ None)

Module Contents

graphs.eulerian_path_and_circuit_for_undirected_graph.check_circuit_or_path(graph, max_node)

For checking in graph has euler path or circuit

Args:

graph: The graph to check max_node: The maximum node to check

Returns:

Type of graph, and its circuit or path

Example:

>>> check_circuit_or_path({1: [2, 3], 2: [1, 3], 3: [1, 2]}, 10)
(1, -1)
>>> check_circuit_or_path({1: [2, 3, 4], 2: [], 3: [1, 2], 4: [], 5: [4]}, 10)
(2, 5)
>>> check_circuit_or_path({1: [2, 3, 1], 2: [2], 3: [1, 3], 4: [1], 5: []}, 10)
(3, 4)
>>> check_circuit_or_path({1: [], 2: [], 3: [1, 2]}, 10)
(1, -1)
>>> check_circuit_or_path({1: [], 2: []}, 10)
(1, -1)

graphs.eulerian_path_and_circuit_for_undirected_graph.check_euler(graph, max_node) → None

Args:

graph: The graph to check max_node: The maximum node to check

Example:

>>> check_euler({1: [2, 3], 2: [1, 3], 3: [1, 2]}, 10)
graph has a Euler cycle
[1, 2, 3, 1]
>>> check_euler({1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}, 10)
graph has a Euler path
[5, 4, 1, 2, 3, 1]
>>> check_euler({1: [2, 3, 1], 2: [2, 3, 4], 3: [1, 3], 4: [1], 5: []}, 10)
graph is not Eulerian
no path
>>> check_euler({1: [], 2: [], 3: [1, 2]}, 10)
graph has a Euler cycle
[1]
>>> check_euler({1: [], 2: []}, 10)
graph has a Euler cycle
[1]

graphs.eulerian_path_and_circuit_for_undirected_graph.dfs(u, graph, visited_edge, path=None)

Using dfs for finding eulerian path traversal Args:

u: The start_node graph: The graph to check visited_edge: Specify if a node has been visited or not path: Optional path parameter

Returns:

Path

Example:

>>> visited_edge = [[False] * 11 for _ in range(11)]
>>> dfs(1, {1: [2, 3], 2: [1, 3], 3: [1, 2]}, visited_edge)
[1, 2, 3, 1]
>>> dfs(5, {1: [2, 3, 4], 2: [1, 3], 3: [1], 4: [1, 5], 5: [4]}, visited_edge)
[5, 4, 1]
>>> dfs(1, {1: [], 2: [], 3: [1, 2]}, visited_edge)
[1]
>>> dfs(1, {1: [], 2: []}, visited_edge)
[1]
>>> dfs(1, {1: [], 2: []}, visited_edge, [1, 3])
[1, 3, 1]

graphs.eulerian_path_and_circuit_for_undirected_graph.main() → None