"""
和弦图的算法。
一个图是和弦图，如果每个长度至少为4的环都有一条弦（连接环中不相邻两个节点的边）。
https://en.wikipedia.org/wiki/Chordal_graph
"""
import sys
import networkx as nx
from networkx.algorithms.components import connected_components
from networkx.utils import arbitrary_element, not_implemented_for
__all__ = [
"is_chordal",
"find_induced_nodes",
"chordal_graph_cliques",
"chordal_graph_treewidth",
"NetworkXTreewidthBoundExceeded",
"complete_to_chordal_graph",
]
class NetworkXTreewidthBoundExceeded(nx.NetworkXException):
"""在提供了树宽界限且已超出该界限时引发的异常"""
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable
def is_chordal(G):
"""检查图 G 是否为弦图。
一个图是弦图，如果每个长度至少为 4 的环都有一条弦（连接环中不相邻两个节点的边）。
Parameters
----------
G : 图
一个 NetworkX 图。
Returns
-------
chordal : bool
如果 G 是弦图则返回 True，否则返回 False。
Raises
------
NetworkXNotImplemented
该算法不支持 DiGraph、MultiGraph 和 MultiDiGraph。
Examples
--------
>>> e = [
... (1, 2),
... (1, 3),
... (2, 3),
... (2, 4),
... (3, 4),
... (3, 5),
... (3, 6),
... (4, 5),
... (4, 6),
... (5, 6),
... ]
>>> G = nx.Graph(e)
>>> nx.is_chordal(G)
True
Notes
-----
该程序尝试通过最大基数搜索遍历每个节点。当发现任意节点的分离集不是团时，返回 False。基于 [1] 中的算法。
自环被忽略。
References
----------
.. [1] R. E. Tarjan 和 M. Yannakakis，简单的线性时间算法
用于测试图的弦性，测试超图的无环性，以及
选择性地简化无环超图，SIAM J. Comput., 13 (1984),
pp. 566–579.
"""
if len(G.nodes) <= 3:
return True
return len(_find_chordality_breaker(G)) == 0
[docs]
@nx._dispatchable
def find_induced_nodes(G, s, t, treewidth_bound=sys.maxsize):
"""返回从节点 s 到节点 t 路径中的诱导节点集合。
Parameters
----------
G : 图
一个无弦的 NetworkX 图
s : 节点
寻找诱导节点的源节点
t : 节点
寻找诱导节点的目标节点
treewidth_bound: 浮点数
图 H 可接受的最大树宽。一旦超过 treewidth_bound，搜索诱导节点的过程将终止。
Returns
-------
induced_nodes : 节点集合
在图 G 中从节点 s 到节点 t 路径中的诱导节点集合
Raises
------
NetworkXError
该算法不支持 DiGraph、MultiGraph 和 MultiDiGraph。
如果输入图是这些类之一的实例，将引发 :exc:`NetworkXError` 。
该算法只能应用于无弦图。如果输入图被发现是非无弦的，将引发 :exc:`NetworkXError` 。
Examples
--------
>>> G = nx.Graph()
>>> G = nx.generators.classic.path_graph(10)
>>> induced_nodes = nx.find_induced_nodes(G, 1, 9, 2)
>>> sorted(induced_nodes)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Notes
-----
G 必须是一个无弦图，且 (s,t) 是一条不在 G 中的边。
如果提供了 treewidth_bound，一旦超过 treewidth_bound，搜索诱导节点的过程将终止。
该算法灵感来源于 [1] 中的算法 4。
诱导节点的正式定义也可以在该参考文献中找到。
自环被忽略
References
----------
.. [1] 学习有界树宽贝叶斯网络。
Gal Elidan, Stephen Gould; JMLR, 9(Dec):2699--2731, 2008.
http://jmlr.csail.mit.edu/papers/volume9/elidan08a/elidan08a.pdf
"""
if not is_chordal(G):
raise nx.NetworkXError("Input graph is not chordal.")
H = nx.Graph(G)
H.add_edge(s, t)
induced_nodes = set()
triplet = _find_chordality_breaker(H, s, treewidth_bound)
while triplet:
(u, v, w) = triplet
induced_nodes.update(triplet)
for n in triplet:
if n != s:
H.add_edge(s, n)
triplet = _find_chordality_breaker(H, s, treewidth_bound)
if induced_nodes:
# Add t and the second node in the induced path from s to t.
induced_nodes.add(t)
for u in G[s]:
if len(induced_nodes & set(G[u])) == 2:
induced_nodes.add(u)
break
return induced_nodes
[docs]
@nx._dispatchable
def chordal_graph_cliques(G):
"""返回弦图的所有最大团。
该算法将图分解为连通分量，并在每个分量中执行最大基数搜索以获取团。
Parameters
----------
G : 图
一个 NetworkX 图
Yields
------
节点的不变集合
最大团，每个团是一个 `G` 中节点的不变集合。团的顺序是任意的。
Raises
------
NetworkXError
该算法不支持有向图、多重图和多重有向图。
该算法只能应用于弦图。如果输入图被发现为非弦图，则引发 :exc:`NetworkXError` 。
Examples
--------
>>> e = [
... (1, 2),
... (1, 3),
... (2, 3),
... (2, 4),
... (3, 4),
... (3, 5),
... (3, 6),
... (4, 5),
... (4, 6),
... (5, 6),
... (7, 8),
... ]
>>> G = nx.Graph(e)
>>> G.add_node(9)
>>> cliques = [c for c in chordal_graph_cliques(G)]
>>> cliques[0]
frozenset({1, 2, 3})
"""
for C in (G.subgraph(c).copy() for c in connected_components(G)):
if C.number_of_nodes() == 1:
if nx.number_of_selfloops(C) > 0:
raise nx.NetworkXError("Input graph is not chordal.")
yield frozenset(C.nodes())
else:
unnumbered = set(C.nodes())
v = arbitrary_element(C)
unnumbered.remove(v)
numbered = {v}
clique_wanna_be = {v}
while unnumbered:
v = _max_cardinality_node(C, unnumbered, numbered)
unnumbered.remove(v)
numbered.add(v)
new_clique_wanna_be = set(C.neighbors(v)) & numbered
sg = C.subgraph(clique_wanna_be)
if _is_complete_graph(sg):
new_clique_wanna_be.add(v)
if not new_clique_wanna_be >= clique_wanna_be:
yield frozenset(clique_wanna_be)
clique_wanna_be = new_clique_wanna_be
else:
raise nx.NetworkXError("Input graph is not chordal.")
yield frozenset(clique_wanna_be)
[docs]
@nx._dispatchable
def chordal_graph_treewidth(G):
"""返回弦图 G 的树宽。
Parameters
----------
G : 图
一个 NetworkX 图
Returns
-------
treewidth : int
图中最大团的大小减一。
Raises
------
NetworkXError
该算法不支持 DiGraph、MultiGraph 和 MultiDiGraph。
该算法只能应用于弦图。如果输入的图被发现是非弦图，则引发 :exc:`NetworkXError` 。
Examples
--------
>>> e = [
... (1, 2),
... (1, 3),
... (2, 3),
... (2, 4),
... (3, 4),
... (3, 5),
... (3, 6),
... (4, 5),
... (4, 6),
... (5, 6),
... (7, 8),
... ]
>>> G = nx.Graph(e)
>>> G.add_node(9)
>>> nx.chordal_graph_treewidth(G)
3
References
----------
.. [1] https://en.wikipedia.org/wiki/Tree_decomposition#Treewidth
"""
if not is_chordal(G):
raise nx.NetworkXError("Input graph is not chordal.")
max_clique = -1
for clique in nx.chordal_graph_cliques(G):
max_clique = max(max_clique, len(clique))
return max_clique - 1
def _is_complete_graph(G):
"""如果G是一个完全图，则返回True。"""
if nx.number_of_selfloops(G) > 0:
raise nx.NetworkXError("Self loop found in _is_complete_graph()")
n = G.number_of_nodes()
if n < 2:
return True
e = G.number_of_edges()
max_edges = (n * (n - 1)) / 2
return e == max_edges
def _find_missing_edge(G):
"""给定一个非完全图 G，返回一个缺失的边。"""
nodes = set(G)
for u in G:
missing = nodes - set(list(G[u].keys()) + [u])
if missing:
return (u, missing.pop())
def _max_cardinality_node(G, choices, wanna_connect):
"""返回在图G中与wanna_connect中的节点有更多连接的choices中的节点。
"""
max_number = -1
for x in choices:
number = len([y for y in G[x] if y in wanna_connect])
if number > max_number:
max_number = number
max_cardinality_node = x
return max_cardinality_node
def _find_chordality_breaker(G, s=None, treewidth_bound=sys.maxsize):
"""给定一个图 G，从节点 s 开始（如果提供了 s）或从任意节点开始进行最大基数搜索，尝试找到一个非弦环。
如果找到一个非弦环，则返回 (u,v,w)，其中 u,v,w 是与 s 一起参与该环的三个节点。
忽略所有自环。
"""
if len(G) == 0:
raise nx.NetworkXPointlessConcept("Graph has no nodes.")
unnumbered = set(G)
if s is None:
s = arbitrary_element(G)
unnumbered.remove(s)
numbered = {s}
current_treewidth = -1
while unnumbered: # and current_treewidth <= treewidth_bound:
v = _max_cardinality_node(G, unnumbered, numbered)
unnumbered.remove(v)
numbered.add(v)
clique_wanna_be = set(G[v]) & numbered
sg = G.subgraph(clique_wanna_be)
if _is_complete_graph(sg):
# The graph seems to be chordal by now. We update the treewidth
current_treewidth = max(current_treewidth, len(clique_wanna_be))
if current_treewidth > treewidth_bound:
raise nx.NetworkXTreewidthBoundExceeded(
f"treewidth_bound exceeded: {current_treewidth}"
)
else:
# sg is not a clique,
# look for an edge that is not included in sg
(u, w) = _find_missing_edge(sg)
return (u, v, w)
return ()
[docs]
@not_implemented_for("directed")
@nx._dispatchable(returns_graph=True)
def complete_to_chordal_graph(G):
"""返回一个将 G 补全为弦图的副本
向 G 的副本添加边以创建一个弦图。一个图 G=(V,E) 被称为弦图，如果对于每个长度大于 3 的环，存在两个非相邻节点通过一条边（称为弦）连接。
Parameters
----------
G : NetworkX 图
无向图
Returns
-------
H : NetworkX 图
G 的弦图增强
alpha : 字典
G 的节点消除顺序
Notes
-----
计算图的弦图增强有不同的方法。这里使用的算法称为 MCS-M，给出了图的至少最小（局部）三角剖分。注意，这种三角剖分不一定是全局最小。
https://en.wikipedia.org/wiki/Chordal_graph
References
----------
.. [1] Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004)
用于计算图的最小三角剖分的最大基数搜索。算法学报。39. 287-298. 10.1007/s00453-004-1084-3.
Examples
--------
>>> from networkx.algorithms.chordal import complete_to_chordal_graph
>>> G = nx.wheel_graph(10)
>>> H, alpha = complete_to_chordal_graph(G)
"""
H = G.copy()
alpha = {node: 0 for node in H}
if nx.is_chordal(H):
return H, alpha
chords = set()
weight = {node: 0 for node in H.nodes()}
unnumbered_nodes = list(H.nodes())
for i in range(len(H.nodes()), 0, -1):
# get the node in unnumbered_nodes with the maximum weight
z = max(unnumbered_nodes, key=lambda node: weight[node])
unnumbered_nodes.remove(z)
alpha[z] = i
update_nodes = []
for y in unnumbered_nodes:
if G.has_edge(y, z):
update_nodes.append(y)
else:
# y_weight will be bigger than node weights between y and z
y_weight = weight[y]
lower_nodes = [
node for node in unnumbered_nodes if weight[node] < y_weight
]
if nx.has_path(H.subgraph(lower_nodes + [z, y]), y, z):
update_nodes.append(y)
chords.add((z, y))
# during calculation of paths the weights should not be updated
for node in update_nodes:
weight[node] += 1
H.add_edges_from(chords)
return H, alpha
