Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/generators/harary_graph.py: 21%

1"""Generators for Harary graphs 

2 

3This module gives two generators for the Harary graph, which was 

4introduced by the famous mathematician Frank Harary in his 1962 work [H]_. 

5The first generator gives the Harary graph that maximizes the node 

6connectivity with given number of nodes and given number of edges. 

7The second generator gives the Harary graph that minimizes 

8the number of edges in the graph with given node connectivity and 

9number of nodes. 

10 

11References 

12---------- 

13.. [H] Harary, F. "The Maximum Connectivity of a Graph." 

14 Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962. 

15 

16""" 

17 

18import networkx as nx 

19from networkx.exception import NetworkXError 

20 

21__all__ = ["hnm_harary_graph", "hkn_harary_graph"] 

22 

23 

24@nx._dispatchable(graphs=None, returns_graph=True) 

25def hnm_harary_graph(n, m, create_using=None): 

26 r"""Return the Harary graph with given numbers of nodes and edges. 

27 

28 The Harary graph $H_{n, m}$ is the graph that maximizes node connectivity 

29 with $n$ nodes and $m$ edges. 

30 

31 This maximum node connectivity is known to be $\lfloor 2m/n \rfloor$. [1]_ 

32 

33 Parameters 

34 ---------- 

35 n: integer 

36 The number of nodes the generated graph is to contain. 

37 

38 m: integer 

39 The number of edges the generated graph is to contain. 

40 

41 create_using : NetworkX graph constructor, optional (default=nx.Graph) 

42 Graph type to create. If graph instance, then cleared before populated. 

43 

44 Returns 

45 ------- 

46 NetworkX graph 

47 The Harary graph $H_{n, m}$. 

48 

49 See Also 

50 -------- 

51 hkn_harary_graph 

52 

53 Notes 

54 ----- 

55 This algorithm runs in $O(m)$ time. 

56 The implementation follows [2]_. 

57 

58 References 

59 ---------- 

60 .. [1] F. T. Boesch, A. Satyanarayana, and C. L. Suffel, 

61 "A Survey of Some Network Reliability Analysis and Synthesis Results," 

62 Networks, pp. 99-107, 2009. 

63 

64 .. [2] Harary, F. "The Maximum Connectivity of a Graph." 

65 Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962. 

66 """ 

67 

68 if n < 1: 

69 raise NetworkXError("The number of nodes must be >= 1!") 

70 if m < n - 1: 

71 raise NetworkXError("The number of edges must be >= n - 1 !") 

72 if m > n * (n - 1) // 2: 

73 raise NetworkXError("The number of edges must be <= n(n-1)/2") 

74 

75 # Get the floor of average node degree. 

76 d = 2 * m // n 

77 

78 offset = d // 2 

79 H = nx.circulant_graph(n, range(1, offset + 1), create_using=create_using) 

80 

81 half = n // 2 

82 if (n % 2 == 0) or (d % 2 == 0): 

83 # If d is odd; n must be even. 

84 if d % 2 == 1: 

85 # Add edges diagonally. 

86 H.add_edges_from((i, i + half) for i in range(half)) 

87 

88 r = 2 * m % n 

89 # Add remaining edges at offset + 1. 

90 H.add_edges_from((i, i + offset + 1) for i in range(r // 2)) 

91 else: 

92 # Add the remaining m - n * offset edges between i and i + half. 

93 H.add_edges_from((i, (i + half) % n) for i in range(m - n * offset)) 

94 

95 return H 

96 

97 

98@nx._dispatchable(graphs=None, returns_graph=True) 

99def hkn_harary_graph(k, n, create_using=None): 

100 r"""Return the Harary graph with given node connectivity and node number. 

101 

102 The Harary graph $H_{k, n}$ is the graph that minimizes the number of 

103 edges needed with given node connectivity $k$ and node number $n$. 

104 

105 This smallest number of edges is known to be $\lceil kn/2 \rceil$ [1]_. 

106 

107 Parameters 

108 ---------- 

109 k: integer 

110 The node connectivity of the generated graph. 

111 

112 n: integer 

113 The number of nodes the generated graph is to contain. 

114 

115 create_using : NetworkX graph constructor, optional (default=nx.Graph) 

116 Graph type to create. If graph instance, then cleared before populated. 

117 

118 Returns 

119 ------- 

120 NetworkX graph 

121 The Harary graph $H_{k, n}$. 

122 

123 See Also 

124 -------- 

125 hnm_harary_graph 

126 

127 Notes 

128 ----- 

129 This algorithm runs in $O(kn)$ time. 

130 The implementation follows [2]_. 

131 

132 References 

133 ---------- 

134 .. [1] Weisstein, Eric W. "Harary Graph." From MathWorld--A Wolfram Web 

135 Resource. http://mathworld.wolfram.com/HararyGraph.html. 

136 

137 .. [2] Harary, F. "The Maximum Connectivity of a Graph." 

138 Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962. 

139 """ 

140 

141 if k < 1: 

142 raise NetworkXError("The node connectivity must be >= 1!") 

143 if n < k + 1: 

144 raise NetworkXError("The number of nodes must be >= k+1 !") 

145 

146 # In case of connectivity 1, simply return the path graph. 

147 if k == 1: 

148 return nx.path_graph(n, create_using) 

149 

150 offset = k // 2 

151 H = nx.circulant_graph(n, range(1, offset + 1), create_using=create_using) 

152 

153 half = n // 2 

154 if (k % 2 == 0) or (n % 2 == 0): 

155 # If k is odd; n must be even. 

156 if k % 2 == 1: 

157 # Add edges diagonally. 

158 H.add_edges_from((i, i + half) for i in range(half)) 

159 else: 

160 # Add half + 1 edges between i and i + half. 

161 H.add_edges_from((i, (i + half) % n) for i in range(half + 1)) 

162 

163 return H