#8. Eulerian Cycle / Eulerian Path

欧拉回路: A Cycle with each edge exactly once.

Eulerian Cycle Eulerian Path
Undirected Graph Every vertex has an even degree Every vertex has an even degree or only 2 vertices can have odd degree
Directed Graph Every vertex has the same indegree and outdegree At most 1 vertex has (outdegree) - (indegree) = 1, and at most 1 vertex has (indegree)- (outdegree) = 1, and all other vertices has the same indegree and outdegree
  • If a graph has an Eulerian Cycle, it must have an Eulerian Path

#8.1 Eulerian Cycle for Directed Graph

A directed graph has an Euler Cycle iff:

  1. Every vertex with non-zero degree belong to a single strongly connected component
  2. Every vertex must have the same indegree and outdegree

[Notes]

  • A singleton is a valid node in the eulerian graph. Because eulerian cycle or eulerian path visit each edge once, there is no need to visit that singleton node.
  • In a directed graph, an eulerian path has only one starting node and only one end node. Starting node has (outdegree) - (indegree) = 1, while end node has (indegree) - (outdegree) = 1

Java: Check if the graph has Eulerian Cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static boolean hasEulerCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
return isStronglyConnected(graph) && hasSameDegree(graph);
}
private static boolean isStronglyConnected(final Map<Integer, Set<Integer>> graph) {
final List<Set<Integer>> scc = StronglyConnectedComponent.scc(graph);
return scc.size() == 1;
}
private static boolean hasSameDegree(final Map<Integer, Set<Integer>> graph) {
final Map<Integer, Integer> degrees = new HashMap<>();
for (final int v : graph.keySet()) {
degrees.putIfAbsent(v, 0);
for (final int adj : graph.get(v)) {
degrees.putIfAbsent(adj, 0);
degrees.put(v, degrees.get(v) - 1);
degrees.put(adj, degrees.get(v) + 1);
}
}
for (final int v : graph.keySet()) {
if (degrees.get(v) != 0) {
return false;
}
}
return true;
}

#8.2 Hierholzer’s Algorithm

Find Euler path/cycle in Directed graph

特别注意这个implementation. 当处理Euler Path/Cycle的问题时,如果需要自己构建graph, 不需要用Inner class来构建Edge, 然后再用类似于Set的数据结构来记录edge的访问情况.

Java Hierholzer’s Algorithm

仔细理解一下下面的code, 用一个Queue来构建adjacency list会省了很多事.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static List<Integer> findEulerPath(final Map<Integer, Queue<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final List<Integer> res = new LinkedList<>();
// if there is no cycle, src must have 0 indegree.
final int src = computeIndegreeAndGetSource(graph);
if (src == -1) {
// Euler Cycle, any vertex can be a source, since it's a cycle.
for (final int v : graph.keySet()) {
dfs(v, graph, res);
break;
}
} else {
// Euler Path
dfs(src, graph, res);
}
return res;
}
private void dfs(final int v, final Map<Integer, Queue<Integer>> graph, final List<Integer> res) {
while (!graph.get(v).isEmpty()) {
final int adj = graph.get(v).poll();
dfs(adj, graph, res);
}
res.add(0, v);
}

Python Hierholzer’s Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# Problem: Given a graph, find the eulerian path or eulerian cycle if exists
# Directed graph
# A directed graph has eulerian cycle iff all vertices have the same indegree and outdegree
# A directed graph has eulerian path iff only one vertex has (outdegree) - (indegree) = 1,
# and only one vertex has (indegree) - (outdegree) = 1, and all other vertices have the same indegree
# and outdegree.
# All vertices with `non-zero` degree must be in the same connected component. Otherwise, the graph is disconnected,
# it's impossible to have eulerian path or cycle in a disconnected graph. However, a singleton is a valid node
# in an eulerian graph.
import collections
def euler_directed_graph(graph):
"""
:type graph: Dict[int, List[int]], a directed graph, which can have multiple edges from same src and dst
:rtype: List[int], eulerian path
"""
if not graph:
raise Exception("invalid graph")
# get indegree and outdegree for each node
indegree, outdegree = collections.defaultdict(lambda: 0), collections.defaultdict(lambda: 0)
# nodes have every vertex in the graph, including singleton and those without out-going edges
nodes = set()
# number of edges in the graph
edge_cnt = 0
for v in graph:
edge_cnt += len(graph[v])
for w in graph[v]:
indegree[w] += 1
outdegree[v] += 1
nodes.add(v)
nodes.add(w)
# find the starting node if there is a euler path
start = next(iter(nodes))
start_nodes, end_nodes = 0, 0
for v in nodes:
if indegree[v] - outdegree[v] > 1 or outdegree[v] - indegree[v] > 1:
raise Exception("no eulerian path or cycle")
if outdegree[v] - indegree[v] == 1:
start_nodes += 1
start = v
if indegree[v] - outdegree[v] == 1:
end_nodes += 1
# find eulerian path or cycle
path = []
dfs(start, graph, path)
# check if the graph is disconnected
if len(path) != edge_cnt + 1:
raise Exception("no eulerian path because the graph is disconnected")
return path[::-1]
def dfs(v, graph, path):
"""
:type v: int
:type graph: Dict[int, List[int]], a directed graph, which can have multiple edges from the same src and dst
:type path: List[int]
"""
while len(graph[v]) > 0:
# Must be pop to dedup, because in eulerian path, a vertex can be visited multiple times,
# we can not use a set to keep track visited node.
adj = graph[v].pop()
dfs(adj, graph, path)
path.append(v)
def main():
graph = {}
for v in range(7):
graph[v] = []
graph[1].append(2)
graph[1].append(3)
graph[2].append(2)
graph[2].append(4)
graph[2].append(4)
graph[3].append(1)
graph[3].append(2)
graph[3].append(5)
graph[4].append(3)
graph[4].append(6)
graph[5].append(6)
graph[6].append(3)
expected_path = [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
actual_path = euler_directed_graph(graph)
if expected_path.sort() != actual_path.sort():
raise Exception("wrong answer")
main()

#8.2 Eulerian Cycle/Path for Undirected Graph

An undirected graph has an Euler Cycle iff:

  1. Every vertex with non-zero degree belong to a single connected component
  2. Every vertex must have even number as its degree

Implementation中注意区分Directed Graph里的isStronglyConnected和Undirected Graph里的isConnected. Strongly Connected Component的概念只有在Directed Graph里才会出现!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static boolean hasEulerCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
return ConnectedComponent.isConnected(graph) && getNumberOfVerticesWithOddDegree(graph) == 0;
}
private static int getNumberOfVerticesWithOddDegree(final Map<Integer, Set<Integer>> graph) {
int count = 0;
for (final int v : graph.keySet()) {
if (graph.get(v).size() % 2 != 0) {
count++;
}
}
return count;
}

An undirected graph has an Euler Path iff:

  1. Every vertex with non-zero degree belong to a single strongly connected component
  2. Only 0 or 2 vertices are allowed to have odd number as its degree, all other vertices must have even number as their degrees.

找path和找cycle几乎一模一样, 唯一的区别就是判断奇数degree的结点个数是不是0或者2

1
2
3
4
5
6
7
8
public static boolean hasEulerPath(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final int oddDegrees getNumberOfVerticesWithOddDegree(graph);
return ConnectedComponent.isConnected(graph) && (oddDegrees == 0 || oddDegrees == 2);
}

Comments

01/03/2020