Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/tree/decomposition.py: 30%

1r"""Function for computing a junction tree of a graph.""" 

2 

3from itertools import combinations 

4 

5import networkx as nx 

6from networkx.algorithms import chordal_graph_cliques, complete_to_chordal_graph, moral 

7from networkx.utils import not_implemented_for 

8 

9__all__ = ["junction_tree"] 

10 

11 

12@not_implemented_for("multigraph") 

13@nx._dispatch 

14def junction_tree(G): 

15 r"""Returns a junction tree of a given graph. 

16 

17 A junction tree (or clique tree) is constructed from a (un)directed graph G. 

18 The tree is constructed based on a moralized and triangulated version of G. 

19 The tree's nodes consist of maximal cliques and sepsets of the revised graph. 

20 The sepset of two cliques is the intersection of the nodes of these cliques, 

21 e.g. the sepset of (A,B,C) and (A,C,E,F) is (A,C). These nodes are often called 

22 "variables" in this literature. The tree is bipartite with each sepset 

23 connected to its two cliques. 

24 

25 Junction Trees are not unique as the order of clique consideration determines 

26 which sepsets are included. 

27 

28 The junction tree algorithm consists of five steps [1]_: 

29 

30 1. Moralize the graph 

31 2. Triangulate the graph 

32 3. Find maximal cliques 

33 4. Build the tree from cliques, connecting cliques with shared 

34 nodes, set edge-weight to number of shared variables 

35 5. Find maximum spanning tree 

36 

37 

38 Parameters 

39 ---------- 

40 G : networkx.Graph 

41 Directed or undirected graph. 

42 

43 Returns 

44 ------- 

45 junction_tree : networkx.Graph 

46 The corresponding junction tree of `G`. 

47 

48 Raises 

49 ------ 

50 NetworkXNotImplemented 

51 Raised if `G` is an instance of `MultiGraph` or `MultiDiGraph`. 

52 

53 References 

54 ---------- 

55 .. [1] Junction tree algorithm: 

56 https://en.wikipedia.org/wiki/Junction_tree_algorithm 

57 

58 .. [2] Finn V. Jensen and Frank Jensen. 1994. Optimal 

59 junction trees. In Proceedings of the Tenth international 

60 conference on Uncertainty in artificial intelligence (UAI’94). 

61 Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 360–366. 

62 """ 

63 

64 clique_graph = nx.Graph() 

65 

66 if G.is_directed(): 

67 G = moral.moral_graph(G) 

68 chordal_graph, _ = complete_to_chordal_graph(G) 

69 

70 cliques = [tuple(sorted(i)) for i in chordal_graph_cliques(chordal_graph)] 

71 clique_graph.add_nodes_from(cliques, type="clique") 

72 

73 for edge in combinations(cliques, 2): 

74 set_edge_0 = set(edge[0]) 

75 set_edge_1 = set(edge[1]) 

76 if not set_edge_0.isdisjoint(set_edge_1): 

77 sepset = tuple(sorted(set_edge_0.intersection(set_edge_1))) 

78 clique_graph.add_edge(edge[0], edge[1], weight=len(sepset), sepset=sepset) 

79 

80 junction_tree = nx.maximum_spanning_tree(clique_graph) 

81 

82 for edge in list(junction_tree.edges(data=True)): 

83 junction_tree.add_node(edge[2]["sepset"], type="sepset") 

84 junction_tree.add_edge(edge[0], edge[2]["sepset"]) 

85 junction_tree.add_edge(edge[1], edge[2]["sepset"]) 

86 junction_tree.remove_edge(edge[0], edge[1]) 

87 

88 return junction_tree