Source code for networkx.algorithms.tree.decomposition

r"""用于计算图的连接树的函数。"""

from itertools import combinations

import networkx as nx
from networkx.algorithms import chordal_graph_cliques, complete_to_chordal_graph, moral
from networkx.utils import not_implemented_for

__all__ = ["junction_tree"]




@not_implemented_for("multigraph")
@nx._dispatchable(returns_graph=True)
def junction_tree(G):
    r"""返回给定图的连接树。

连接树（或团树）是从一个（无）向图 G 构建的。该树基于 G 的道德化和三角化版本构建。树的节点由修正图的最大团和分离集组成。两个团的分离集是这些团节点的交集，例如，(A,B,C) 和 (A,C,E,F) 的分离集是 (A,C)。这些节点在此文献中通常称为“变量”。该树是二分的，每个分离集与其两个团相连。

连接树不是唯一的，因为团的考虑顺序决定了包含哪些分离集。

连接树算法包括五个步骤 [1]_：

1. 道德化图
2. 三角化图
3. 找到最大团
4. 从团构建树，连接共享节点的团，设置边权重为共享变量的数量
5. 找到最大生成树

Parameters
----------
G : networkx.Graph
    有向或无向图。

Returns
-------
junction_tree : networkx.Graph
    `G` 对应的连接树。

Raises
------
NetworkXNotImplemented
    如果 `G` 是 `MultiGraph` 或 `MultiDiGraph` 的实例，则引发此异常。

References
----------
.. [1] 连接树算法：
   https://en.wikipedia.org/wiki/Junction_tree_algorithm

.. [2] Finn V. Jensen 和 Frank Jensen。1994。最优连接树。在第十届国际人工智能不确定性会议（UAI’94）的会议记录中。Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 360–366.
"""

    clique_graph = nx.Graph()

    if G.is_directed():
        G = moral.moral_graph(G)
    chordal_graph, _ = complete_to_chordal_graph(G)

    cliques = [tuple(sorted(i)) for i in chordal_graph_cliques(chordal_graph)]
    clique_graph.add_nodes_from(cliques, type="clique")

    for edge in combinations(cliques, 2):
        set_edge_0 = set(edge[0])
        set_edge_1 = set(edge[1])
        if not set_edge_0.isdisjoint(set_edge_1):
            sepset = tuple(sorted(set_edge_0.intersection(set_edge_1)))
            clique_graph.add_edge(edge[0], edge[1], weight=len(sepset), sepset=sepset)

    junction_tree = nx.maximum_spanning_tree(clique_graph)

    for edge in list(junction_tree.edges(data=True)):
        junction_tree.add_node(edge[2]["sepset"], type="sepset")
        junction_tree.add_edge(edge[0], edge[2]["sepset"])
        junction_tree.add_edge(edge[1], edge[2]["sepset"])
        junction_tree.remove_edge(edge[0], edge[1])

    return junction_tree