ioftools / networkxMiCe / networkxmaster / networkx / generators / harary_graph.py @ 5cef0f13
History  View  Annotate  Download (6.08 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20182019 by

3 
# Weisheng Si <w.si@westernsydney.edu.au>

4 
# All rights reserved.

5 
# BSD license.

6 
#

7 
# Authors: Weisheng Si (w.si@westernsydney.edu.au)

8 
#

9 
"""Generators for Harary graphs

10 

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

12 
introduced by the famous mathematician Frank Harary in his 1962 work [1]_.

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

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

15 
The second generator gives the Harary graph that minimizes

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

17 
number of nodes.

18 

19 
References

20 


21 
.. [1] Harary, F. "The Maximum Connectivity of a Graph."

22 
Proc. Nat. Acad. Sci. USA 48, 11421146, 1962.

23 

24 
"""

25  
26 
import networkx as nx 
27 
from networkx.exception import NetworkXError 
28  
29 
__all__ = ['hnm_harary_graph', 'hkn_harary_graph'] 
30  
31  
32 
def hnm_harary_graph(n, m, create_using=None): 
33 
"""Returns the Harary graph with given numbers of nodes and edges.

34 

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

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

37 

38 
This maximum node connectivity is known to be floor($2m/n$). [1]_

39 

40 
Parameters

41 


42 
n: integer

43 
The number of nodes the generated graph is to contain

44 

45 
m: integer

46 
The number of edges the generated graph is to contain

47 

48 
create_using : NetworkX graph constructor, optional Graph type

49 
to create (default=nx.Graph). If graph instance, then cleared

50 
before populated.

51 

52 
Returns

53 


54 
NetworkX graph

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

56 

57 
See Also

58 


59 
hkn_harary_graph

60 

61 
Notes

62 


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

64 
It is implemented by following the Reference [2]_.

65 

66 
References

67 


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

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

70 
Networks, pp. 99107, 2009.

71 

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

73 
Proc. Nat. Acad. Sci. USA 48, 11421146, 1962.

74 
"""

75  
76 
if n < 1: 
77 
raise NetworkXError("The number of nodes must be >= 1!") 
78 
if m < n  1: 
79 
raise NetworkXError("The number of edges must be >= n  1 !") 
80 
if m > n*(n1)//2: 
81 
raise NetworkXError("The number of edges must be <= n(n1)/2") 
82  
83 
# Construct an empty graph with n nodes first

84 
H = nx.empty_graph(n, create_using) 
85 
# Get the floor of average node degree

86 
d = 2*m // n

87  
88 
# Test the parity of n and d

89 
if (n % 2 == 0) or (d % 2 == 0): 
90 
# Start with a regular graph of d degrees

91 
offset = d // 2

92 
for i in range(n): 
93 
for j in range(1, offset+1): 
94 
H.add_edge(i, (i  j) % n) 
95 
H.add_edge(i, (i + j) % n) 
96 
if d & 1: 
97 
# in case d is odd; n must be even in this case

98 
half = n // 2

99 
for i in range(0, half): 
100 
# add edges diagonally

101 
H.add_edge(i, i+half) 
102 
# Get the remainder of 2*m modulo n

103 
r = 2*m % n

104 
if r > 0: 
105 
# add remaining edges at offset+1

106 
for i in range(0, r//2): 
107 
H.add_edge(i, i+offset+1)

108 
else:

109 
# Start with a regular graph of (d  1) degrees

110 
offset = (d  1) // 2 
111 
for i in range(n): 
112 
for j in range(1, offset+1): 
113 
H.add_edge(i, (i  j) % n) 
114 
H.add_edge(i, (i + j) % n) 
115 
half = n // 2

116 
for i in range(0, m  n*offset): 
117 
# add the remaining m  n*offset edges between i and i+half

118 
H.add_edge(i, (i+half) % n) 
119  
120 
return H

121  
122  
123 
def hkn_harary_graph(k, n, create_using=None): 
124 
"""Returns the Harary graph with given node connectivity and node number.

125 

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

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

128 

129 
This smallest number of edges is known to be ceil($kn/2$) [1]_.

130 

131 
Parameters

132 


133 
k: integer

134 
The node connectivity of the generated graph

135 

136 
n: integer

137 
The number of nodes the generated graph is to contain

138 

139 
create_using : NetworkX graph constructor, optional Graph type

140 
to create (default=nx.Graph). If graph instance, then cleared

141 
before populated.

142 

143 
Returns

144 


145 
NetworkX graph

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

147 

148 
See Also

149 


150 
hnm_harary_graph

151 

152 
Notes

153 


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

155 
It is implemented by following the Reference [2]_.

156 

157 
References

158 


159 
.. [1] Weisstein, Eric W. "Harary Graph." From MathWorldA Wolfram Web

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

161 

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

163 
Proc. Nat. Acad. Sci. USA 48, 11421146, 1962.

164 
"""

165  
166 
if k < 1: 
167 
raise NetworkXError("The node connectivity must be >= 1!") 
168 
if n < k+1: 
169 
raise NetworkXError("The number of nodes must be >= k+1 !") 
170  
171 
# in case of connectivity 1, simply return the path graph

172 
if k == 1: 
173 
H = nx.path_graph(n, create_using) 
174 
return H

175  
176 
# Construct an empty graph with n nodes first

177 
H = nx.empty_graph(n, create_using) 
178  
179 
# Test the parity of k and n

180 
if (k % 2 == 0) or (n % 2 == 0): 
181 
# Construct a regular graph with k degrees

182 
offset = k // 2

183 
for i in range(n): 
184 
for j in range(1, offset+1): 
185 
H.add_edge(i, (i  j) % n) 
186 
H.add_edge(i, (i + j) % n) 
187 
if k & 1: 
188 
# odd degree; n must be even in this case

189 
half = n // 2

190 
for i in range(0, half): 
191 
# add edges diagonally

192 
H.add_edge(i, i+half) 
193 
else:

194 
# Construct a regular graph with (k  1) degrees

195 
offset = (k  1) // 2 
196 
for i in range(n): 
197 
for j in range(1, offset+1): 
198 
H.add_edge(i, (i  j) % n) 
199 
H.add_edge(i, (i + j) % n) 
200 
half = n // 2

201 
for i in range(0, half+1): 
202 
# add half+1 edges between i and i+half

203 
H.add_edge(i, (i+half) % n) 
204  
205 
return H
