"""
欧拉回路和图。
"""
from itertools import combinations
import networkx as nx
from ..utils import arbitrary_element, not_implemented_for
__all__ = [
"is_eulerian",
"eulerian_circuit",
"eulerize",
"is_semieulerian",
"has_eulerian_path",
"eulerian_path",
]
[docs]
@nx._dispatchable
def is_eulerian(G):
"""当且仅当 `G` 是欧拉图时返回 True。
一个图是 *欧拉图* 当且仅当它有一个欧拉回路。一个 *欧拉回路* 是一个闭合路径，它恰好包含图中每条边一次。
具有孤立顶点（即度数为零的顶点）的图不被认为具有欧拉回路。因此，如果图不连通（或对于有向图不强连通），此函数返回 False。
Parameters
----------
G : NetworkX 图
一个图，可以是有向的或无向的。
Examples
--------
>>> nx.is_eulerian(nx.DiGraph({0: [3], 1: [2], 2: [3], 3: [0, 1]}))
True
>>> nx.is_eulerian(nx.complete_graph(5))
True
>>> nx.is_eulerian(nx.petersen_graph())
False
如果你希望允许具有孤立顶点的图具有欧拉回路，可以先移除这些顶点，然后调用 `is_eulerian` ，如下例所示。
>>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])
>>> G.add_node(3)
>>> nx.is_eulerian(G)
False
>>> G.remove_nodes_from(list(nx.isolates(G)))
>>> nx.is_eulerian(G)
True
"""
if G.is_directed():
# Every node must have equal in degree and out degree and the
# graph must be strongly connected
return all(
G.in_degree(n) == G.out_degree(n) for n in G
) and nx.is_strongly_connected(G)
# An undirected Eulerian graph has no vertices of odd degree and
# must be connected.
return all(d % 2 == 0 for v, d in G.degree()) and nx.is_connected(G)
[docs]
@nx._dispatchable
def is_semieulerian(G):
"""返回 True 当且仅当 `G` 是半欧拉图。
如果 `G` 具有欧拉路径但没有欧拉回路，则它是半欧拉图。
See Also
--------
has_eulerian_path
is_eulerian
"""
return has_eulerian_path(G) and not is_eulerian(G)
def _find_path_start(G):
"""返回一个适合作为欧拉路径起点的顶点。
如果路径不存在，返回None。
"""
if not has_eulerian_path(G):
return None
if is_eulerian(G):
return arbitrary_element(G)
if G.is_directed():
v1, v2 = (v for v in G if G.in_degree(v) != G.out_degree(v))
# Determines which is the 'start' node (as opposed to the 'end')
if G.out_degree(v1) > G.in_degree(v1):
return v1
else:
return v2
else:
# In an undirected graph randomly choose one of the possibilities
start = [v for v in G if G.degree(v) % 2 != 0][0]
return start
def _simplegraph_eulerian_circuit(G, source):
if G.is_directed():
degree = G.out_degree
edges = G.out_edges
else:
degree = G.degree
edges = G.edges
vertex_stack = [source]
last_vertex = None
while vertex_stack:
current_vertex = vertex_stack[-1]
if degree(current_vertex) == 0:
if last_vertex is not None:
yield (last_vertex, current_vertex)
last_vertex = current_vertex
vertex_stack.pop()
else:
_, next_vertex = arbitrary_element(edges(current_vertex))
vertex_stack.append(next_vertex)
G.remove_edge(current_vertex, next_vertex)
def _multigraph_eulerian_circuit(G, source):
if G.is_directed():
degree = G.out_degree
edges = G.out_edges
else:
degree = G.degree
edges = G.edges
vertex_stack = [(source, None)]
last_vertex = None
last_key = None
while vertex_stack:
current_vertex, current_key = vertex_stack[-1]
if degree(current_vertex) == 0:
if last_vertex is not None:
yield (last_vertex, current_vertex, last_key)
last_vertex, last_key = current_vertex, current_key
vertex_stack.pop()
else:
triple = arbitrary_element(edges(current_vertex, keys=True))
_, next_vertex, next_key = triple
vertex_stack.append((next_vertex, next_key))
G.remove_edge(current_vertex, next_vertex, next_key)
[docs]
@nx._dispatchable
def eulerian_circuit(G, source=None, keys=False):
"""返回一个在图 `G` 中的欧拉回路的边迭代器。
*欧拉回路* 是一个包含图中每条边恰好一次的闭合路径。
Parameters
----------
G : NetworkX 图
一个图，可以是 directed 或 undirected。
source : 节点, 可选
回路的起始节点。
keys : bool
如果为 False，此函数生成的边格式为 ``(u, v)`` 。否则，边格式为 ``(u, v, k)`` 。
此选项在 `G` 不是多图时被忽略。
Returns
-------
edges : 迭代器
欧拉回路中的边迭代器。
Raises
------
NetworkXError
如果图不是欧拉图。
See Also
--------
is_eulerian
Notes
-----
这是一个线性时间实现的算法，改编自 [1]。
关于欧拉回路的一般信息，参见 [2]。
References
----------
.. [1] J. Edmonds, E. L. Johnson.
Matching, Euler tours and the Chinese postman.
Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
.. [2] https://en.wikipedia.org/wiki/Eulerian_path
Examples
--------
在无向图中获取欧拉回路::
>>> G = nx.complete_graph(3)
>>> list(nx.eulerian_circuit(G))
[(0, 2), (2, 1), (1, 0)]
>>> list(nx.eulerian_circuit(G, source=1))
[(1, 2), (2, 0), (0, 1)]
获取欧拉回路中的顶点序列::
>>> [u for u, v in nx.eulerian_circuit(G)]
[0, 2, 1]
"""
if not is_eulerian(G):
raise nx.NetworkXError("G is not Eulerian.")
if G.is_directed():
G = G.reverse()
else:
G = G.copy()
if source is None:
source = arbitrary_element(G)
if G.is_multigraph():
for u, v, k in _multigraph_eulerian_circuit(G, source):
if keys:
yield u, v, k
else:
yield u, v
else:
yield from _simplegraph_eulerian_circuit(G, source)
[docs]
@nx._dispatchable
def has_eulerian_path(G, source=None):
"""返回 True 当且仅当 `G` 具有欧拉路径。
欧拉路径是图中的一条路径，该路径恰好使用图的每条边一次。如果指定了 `source` ，则此函数检查是否存在从节点 `source` 开始的欧拉路径。
有向图具有欧拉路径当且仅当：
- 最多一个顶点的出度 - 入度 = 1，
- 最多一个顶点的入度 - 出度 = 1，
- 其他每个顶点的入度和出度相等，
- 并且其所有顶点都属于基础无向图的单个连通分量。
如果 `source` 不是 None，则从 `source` 开始的欧拉路径存在，如果没有任何其他节点的出度 - 入度 = 1。这等价于存在欧拉回路或 `source` 的出度 - 入度 = 1 并且上述条件成立。
无向图具有欧拉路径当且仅当：
- 恰好零个或两个顶点的度数为奇数，
- 并且其所有顶点都属于单个连通分量。
如果 `source` 不是 None，则从 `source` 开始的欧拉路径存在，如果存在欧拉回路或 `source` 的度数为奇数并且上述条件成立。
具有孤立顶点（即度数为零的顶点）的图不被认为具有欧拉路径。因此，如果图不连通（或有向图不强连通），此函数返回 False。
Parameters
----------
G : NetworkX 图
要查找欧拉路径的图。
source : 节点, 可选
路径的起始节点。
Returns
-------
Bool : 如果 G 具有欧拉路径，则为 True。
Examples
--------
如果你希望允许具有孤立顶点的图具有欧拉路径，可以先移除这些顶点，然后调用 `has_eulerian_path` ，如下例所示。
>>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])
>>> G.add_node(3)
>>> nx.has_eulerian_path(G)
False
>>> G.remove_nodes_from(list(nx.isolates(G)))
>>> nx.has_eulerian_path(G)
True
See Also
--------
is_eulerian
eulerian_path
"""
if nx.is_eulerian(G):
return True
if G.is_directed():
ins = G.in_degree
outs = G.out_degree
# Since we know it is not eulerian, outs - ins must be 1 for source
if source is not None and outs[source] - ins[source] != 1:
return False
unbalanced_ins = 0
unbalanced_outs = 0
for v in G:
if ins[v] - outs[v] == 1:
unbalanced_ins += 1
elif outs[v] - ins[v] == 1:
unbalanced_outs += 1
elif ins[v] != outs[v]:
return False
return (
unbalanced_ins <= 1 and unbalanced_outs <= 1 and nx.is_weakly_connected(G)
)
else:
# We know it is not eulerian, so degree of source must be odd.
if source is not None and G.degree[source] % 2 != 1:
return False
# Sum is 2 since we know it is not eulerian (which implies sum is 0)
return sum(d % 2 == 1 for v, d in G.degree()) == 2 and nx.is_connected(G)
[docs]
@nx._dispatchable
def eulerian_path(G, source=None, keys=False):
"""返回一个遍历欧拉路径上各边的迭代器。
Parameters
----------
G : NetworkX 图
要在其中寻找欧拉路径的图。
source : 节点或 None（默认：None）
开始搜索的节点。None 表示搜索所有起始节点。
keys : 布尔值（默认：False）
指示是否生成边三元组 (u, v, edge_key)。
默认生成边二元组
Yields
------
沿着欧拉路径的边元组。
警告：如果提供的 `source` 不是欧拉路径的起始节点，
即使存在欧拉路径，也会引发错误。
"""
if not has_eulerian_path(G, source):
raise nx.NetworkXError("Graph has no Eulerian paths.")
if G.is_directed():
G = G.reverse()
if source is None or nx.is_eulerian(G) is False:
source = _find_path_start(G)
if G.is_multigraph():
for u, v, k in _multigraph_eulerian_circuit(G, source):
if keys:
yield u, v, k
else:
yield u, v
else:
yield from _simplegraph_eulerian_circuit(G, source)
else:
G = G.copy()
if source is None:
source = _find_path_start(G)
if G.is_multigraph():
if keys:
yield from reversed(
[(v, u, k) for u, v, k in _multigraph_eulerian_circuit(G, source)]
)
else:
yield from reversed(
[(v, u) for u, v, k in _multigraph_eulerian_circuit(G, source)]
)
else:
yield from reversed(
[(v, u) for u, v in _simplegraph_eulerian_circuit(G, source)]
)
[docs]
@not_implemented_for("directed")
@nx._dispatchable(returns_graph=True)
def eulerize(G):
"""将图转换为欧拉图。
如果 `G` 是欧拉图，则结果是作为多图的 `G` ，否则结果是基础简单图为 `G` 的最小（就边数而言）多图。
Parameters
----------
G : NetworkX 图
一个无向图
Returns
-------
G : NetworkX 多图
Raises
------
NetworkXError
如果图不连通。
See Also
--------
is_eulerian
eulerian_circuit
References
----------
.. [1] J. Edmonds, E. L. Johnson.
匹配，欧拉环游和中国邮差问题。
数学规划，第5卷，第1期（1973年），111-114。
.. [2] https://en.wikipedia.org/wiki/Eulerian_path
.. [3] http://web.math.princeton.edu/math_alive/5/Notes1.pdf
Examples
--------
>>> G = nx.complete_graph(10)
>>> H = nx.eulerize(G)
>>> nx.is_eulerian(H)
True
"""
if G.order() == 0:
raise nx.NetworkXPointlessConcept("Cannot Eulerize null graph")
if not nx.is_connected(G):
raise nx.NetworkXError("G is not connected")
odd_degree_nodes = [n for n, d in G.degree() if d % 2 == 1]
G = nx.MultiGraph(G)
if len(odd_degree_nodes) == 0:
return G
# get all shortest paths between vertices of odd degree
odd_deg_pairs_paths = [
(m, {n: nx.shortest_path(G, source=m, target=n)})
for m, n in combinations(odd_degree_nodes, 2)
]
# use the number of vertices in a graph + 1 as an upper bound on
# the maximum length of a path in G
upper_bound_on_max_path_length = len(G) + 1
# use "len(G) + 1 - len(P)",
# where P is a shortest path between vertices n and m,
# as edge-weights in a new graph
# store the paths in the graph for easy indexing later
Gp = nx.Graph()
for n, Ps in odd_deg_pairs_paths:
for m, P in Ps.items():
if n != m:
Gp.add_edge(
m, n, weight=upper_bound_on_max_path_length - len(P), path=P
)
# find the minimum weight matching of edges in the weighted graph
best_matching = nx.Graph(list(nx.max_weight_matching(Gp)))
# duplicate each edge along each path in the set of paths in Gp
for m, n in best_matching.edges():
path = Gp[m][n]["path"]
G.add_edges_from(nx.utils.pairwise(path))
return G
