Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / harary_graph.py @ 5cef0f13

History | View | Annotate | Download (6.08 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2018-2019 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, 1142-1146, 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. 99-107, 2009.
71

72
    .. [2] Harary, F. "The Maximum Connectivity of a Graph."
73
      Proc. Nat. Acad. Sci. USA 48, 1142-1146, 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*(n-1)//2:
81
        raise NetworkXError("The number of edges must be <= n(n-1)/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 MathWorld--A 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, 1142-1146, 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