Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/geometric.py: 21%
131 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Generators for geometric graphs.
2"""
4import math
5from bisect import bisect_left
6from itertools import accumulate, combinations, product
8import networkx as nx
9from networkx.utils import py_random_state
11__all__ = [
12 "geometric_edges",
13 "geographical_threshold_graph",
14 "navigable_small_world_graph",
15 "random_geometric_graph",
16 "soft_random_geometric_graph",
17 "thresholded_random_geometric_graph",
18 "waxman_graph",
19]
22@nx._dispatch(node_attrs="pos_name")
23def geometric_edges(G, radius, p=2, *, pos_name="pos"):
24 """Returns edge list of node pairs within `radius` of each other.
26 Parameters
27 ----------
28 G : networkx graph
29 The graph from which to generate the edge list. The nodes in `G` should
30 have an attribute ``pos`` corresponding to the node position, which is
31 used to compute the distance to other nodes.
32 radius : scalar
33 The distance threshold. Edges are included in the edge list if the
34 distance between the two nodes is less than `radius`.
35 pos_name : string, default="pos"
36 The name of the node attribute which represents the position of each
37 node in 2D coordinates. Every node in the Graph must have this attribute.
38 p : scalar, default=2
39 The `Minkowski distance metric
40 <https://en.wikipedia.org/wiki/Minkowski_distance>`_ used to compute
41 distances. The default value is 2, i.e. Euclidean distance.
43 Returns
44 -------
45 edges : list
46 List of edges whose distances are less than `radius`
48 Notes
49 -----
50 Radius uses Minkowski distance metric `p`.
51 If scipy is available, `scipy.spatial.cKDTree` is used to speed computation.
53 Examples
54 --------
55 Create a graph with nodes that have a "pos" attribute representing 2D
56 coordinates.
58 >>> G = nx.Graph()
59 >>> G.add_nodes_from([
60 ... (0, {"pos": (0, 0)}),
61 ... (1, {"pos": (3, 0)}),
62 ... (2, {"pos": (8, 0)}),
63 ... ])
64 >>> nx.geometric_edges(G, radius=1)
65 []
66 >>> nx.geometric_edges(G, radius=4)
67 [(0, 1)]
68 >>> nx.geometric_edges(G, radius=6)
69 [(0, 1), (1, 2)]
70 >>> nx.geometric_edges(G, radius=9)
71 [(0, 1), (0, 2), (1, 2)]
72 """
73 # Input validation - every node must have a "pos" attribute
74 for n, pos in G.nodes(data=pos_name):
75 if pos is None:
76 raise nx.NetworkXError(
77 f"Node {n} (and all nodes) must have a '{pos_name}' attribute."
78 )
80 # NOTE: See _geometric_edges for the actual implementation. The reason this
81 # is split into two functions is to avoid the overhead of input validation
82 # every time the function is called internally in one of the other
83 # geometric generators
84 return _geometric_edges(G, radius, p, pos_name)
87def _geometric_edges(G, radius, p, pos_name):
88 """
89 Implements `geometric_edges` without input validation. See `geometric_edges`
90 for complete docstring.
91 """
92 nodes_pos = G.nodes(data=pos_name)
93 try:
94 import scipy as sp
95 except ImportError:
96 # no scipy KDTree so compute by for-loop
97 radius_p = radius**p
98 edges = [
99 (u, v)
100 for (u, pu), (v, pv) in combinations(nodes_pos, 2)
101 if sum(abs(a - b) ** p for a, b in zip(pu, pv)) <= radius_p
102 ]
103 return edges
104 # scipy KDTree is available
105 nodes, coords = list(zip(*nodes_pos))
106 kdtree = sp.spatial.cKDTree(coords) # Cannot provide generator.
107 edge_indexes = kdtree.query_pairs(radius, p)
108 edges = [(nodes[u], nodes[v]) for u, v in sorted(edge_indexes)]
109 return edges
112@py_random_state(5)
113@nx._dispatch(graphs=None)
114def random_geometric_graph(
115 n, radius, dim=2, pos=None, p=2, seed=None, *, pos_name="pos"
116):
117 """Returns a random geometric graph in the unit cube of dimensions `dim`.
119 The random geometric graph model places `n` nodes uniformly at
120 random in the unit cube. Two nodes are joined by an edge if the
121 distance between the nodes is at most `radius`.
123 Edges are determined using a KDTree when SciPy is available.
124 This reduces the time complexity from $O(n^2)$ to $O(n)$.
126 Parameters
127 ----------
128 n : int or iterable
129 Number of nodes or iterable of nodes
130 radius: float
131 Distance threshold value
132 dim : int, optional
133 Dimension of graph
134 pos : dict, optional
135 A dictionary keyed by node with node positions as values.
136 p : float, optional
137 Which Minkowski distance metric to use. `p` has to meet the condition
138 ``1 <= p <= infinity``.
140 If this argument is not specified, the :math:`L^2` metric
141 (the Euclidean distance metric), p = 2 is used.
142 This should not be confused with the `p` of an Erdős-Rényi random
143 graph, which represents probability.
144 seed : integer, random_state, or None (default)
145 Indicator of random number generation state.
146 See :ref:`Randomness<randomness>`.
147 pos_name : string, default="pos"
148 The name of the node attribute which represents the position
149 in 2D coordinates of the node in the returned graph.
151 Returns
152 -------
153 Graph
154 A random geometric graph, undirected and without self-loops.
155 Each node has a node attribute ``'pos'`` that stores the
156 position of that node in Euclidean space as provided by the
157 ``pos`` keyword argument or, if ``pos`` was not provided, as
158 generated by this function.
160 Examples
161 --------
162 Create a random geometric graph on twenty nodes where nodes are joined by
163 an edge if their distance is at most 0.1::
165 >>> G = nx.random_geometric_graph(20, 0.1)
167 Notes
168 -----
169 This uses a *k*-d tree to build the graph.
171 The `pos` keyword argument can be used to specify node positions so you
172 can create an arbitrary distribution and domain for positions.
174 For example, to use a 2D Gaussian distribution of node positions with mean
175 (0, 0) and standard deviation 2::
177 >>> import random
178 >>> n = 20
179 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
180 >>> G = nx.random_geometric_graph(n, 0.2, pos=pos)
182 References
183 ----------
184 .. [1] Penrose, Mathew, *Random Geometric Graphs*,
185 Oxford Studies in Probability, 5, 2003.
187 """
188 # TODO Is this function just a special case of the geographical
189 # threshold graph?
190 #
191 # half_radius = {v: radius / 2 for v in n}
192 # return geographical_threshold_graph(nodes, theta=1, alpha=1,
193 # weight=half_radius)
194 #
195 G = nx.empty_graph(n)
196 # If no positions are provided, choose uniformly random vectors in
197 # Euclidean space of the specified dimension.
198 if pos is None:
199 pos = {v: [seed.random() for i in range(dim)] for v in G}
200 nx.set_node_attributes(G, pos, pos_name)
202 G.add_edges_from(_geometric_edges(G, radius, p, pos_name))
203 return G
206@py_random_state(6)
207@nx._dispatch(graphs=None)
208def soft_random_geometric_graph(
209 n, radius, dim=2, pos=None, p=2, p_dist=None, seed=None, *, pos_name="pos"
210):
211 r"""Returns a soft random geometric graph in the unit cube.
213 The soft random geometric graph [1] model places `n` nodes uniformly at
214 random in the unit cube in dimension `dim`. Two nodes of distance, `dist`,
215 computed by the `p`-Minkowski distance metric are joined by an edge with
216 probability `p_dist` if the computed distance metric value of the nodes
217 is at most `radius`, otherwise they are not joined.
219 Edges within `radius` of each other are determined using a KDTree when
220 SciPy is available. This reduces the time complexity from :math:`O(n^2)`
221 to :math:`O(n)`.
223 Parameters
224 ----------
225 n : int or iterable
226 Number of nodes or iterable of nodes
227 radius: float
228 Distance threshold value
229 dim : int, optional
230 Dimension of graph
231 pos : dict, optional
232 A dictionary keyed by node with node positions as values.
233 p : float, optional
234 Which Minkowski distance metric to use.
235 `p` has to meet the condition ``1 <= p <= infinity``.
237 If this argument is not specified, the :math:`L^2` metric
238 (the Euclidean distance metric), p = 2 is used.
240 This should not be confused with the `p` of an Erdős-Rényi random
241 graph, which represents probability.
242 p_dist : function, optional
243 A probability density function computing the probability of
244 connecting two nodes that are of distance, dist, computed by the
245 Minkowski distance metric. The probability density function, `p_dist`,
246 must be any function that takes the metric value as input
247 and outputs a single probability value between 0-1. The scipy.stats
248 package has many probability distribution functions implemented and
249 tools for custom probability distribution definitions [2], and passing
250 the .pdf method of scipy.stats distributions can be used here. If the
251 probability function, `p_dist`, is not supplied, the default function
252 is an exponential distribution with rate parameter :math:`\lambda=1`.
253 seed : integer, random_state, or None (default)
254 Indicator of random number generation state.
255 See :ref:`Randomness<randomness>`.
256 pos_name : string, default="pos"
257 The name of the node attribute which represents the position
258 in 2D coordinates of the node in the returned graph.
260 Returns
261 -------
262 Graph
263 A soft random geometric graph, undirected and without self-loops.
264 Each node has a node attribute ``'pos'`` that stores the
265 position of that node in Euclidean space as provided by the
266 ``pos`` keyword argument or, if ``pos`` was not provided, as
267 generated by this function.
269 Examples
270 --------
271 Default Graph:
273 G = nx.soft_random_geometric_graph(50, 0.2)
275 Custom Graph:
277 Create a soft random geometric graph on 100 uniformly distributed nodes
278 where nodes are joined by an edge with probability computed from an
279 exponential distribution with rate parameter :math:`\lambda=1` if their
280 Euclidean distance is at most 0.2.
282 Notes
283 -----
284 This uses a *k*-d tree to build the graph.
286 The `pos` keyword argument can be used to specify node positions so you
287 can create an arbitrary distribution and domain for positions.
289 For example, to use a 2D Gaussian distribution of node positions with mean
290 (0, 0) and standard deviation 2
292 The scipy.stats package can be used to define the probability distribution
293 with the .pdf method used as `p_dist`.
295 ::
297 >>> import random
298 >>> import math
299 >>> n = 100
300 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
301 >>> p_dist = lambda dist: math.exp(-dist)
302 >>> G = nx.soft_random_geometric_graph(n, 0.2, pos=pos, p_dist=p_dist)
304 References
305 ----------
306 .. [1] Penrose, Mathew D. "Connectivity of soft random geometric graphs."
307 The Annals of Applied Probability 26.2 (2016): 986-1028.
308 .. [2] scipy.stats -
309 https://docs.scipy.org/doc/scipy/reference/tutorial/stats.html
311 """
312 G = nx.empty_graph(n)
313 G.name = f"soft_random_geometric_graph({n}, {radius}, {dim})"
314 # If no positions are provided, choose uniformly random vectors in
315 # Euclidean space of the specified dimension.
316 if pos is None:
317 pos = {v: [seed.random() for i in range(dim)] for v in G}
318 nx.set_node_attributes(G, pos, pos_name)
320 # if p_dist function not supplied the default function is an exponential
321 # distribution with rate parameter :math:`\lambda=1`.
322 if p_dist is None:
324 def p_dist(dist):
325 return math.exp(-dist)
327 def should_join(edge):
328 u, v = edge
329 dist = (sum(abs(a - b) ** p for a, b in zip(pos[u], pos[v]))) ** (1 / p)
330 return seed.random() < p_dist(dist)
332 G.add_edges_from(filter(should_join, _geometric_edges(G, radius, p, pos_name)))
333 return G
336@py_random_state(7)
337@nx._dispatch(graphs=None)
338def geographical_threshold_graph(
339 n,
340 theta,
341 dim=2,
342 pos=None,
343 weight=None,
344 metric=None,
345 p_dist=None,
346 seed=None,
347 *,
348 pos_name="pos",
349 weight_name="weight",
350):
351 r"""Returns a geographical threshold graph.
353 The geographical threshold graph model places $n$ nodes uniformly at
354 random in a rectangular domain. Each node $u$ is assigned a weight
355 $w_u$. Two nodes $u$ and $v$ are joined by an edge if
357 .. math::
359 (w_u + w_v)p_{dist}(r) \ge \theta
361 where `r` is the distance between `u` and `v`, `p_dist` is any function of
362 `r`, and :math:`\theta` as the threshold parameter. `p_dist` is used to
363 give weight to the distance between nodes when deciding whether or not
364 they should be connected. The larger `p_dist` is, the more prone nodes
365 separated by `r` are to be connected, and vice versa.
367 Parameters
368 ----------
369 n : int or iterable
370 Number of nodes or iterable of nodes
371 theta: float
372 Threshold value
373 dim : int, optional
374 Dimension of graph
375 pos : dict
376 Node positions as a dictionary of tuples keyed by node.
377 weight : dict
378 Node weights as a dictionary of numbers keyed by node.
379 metric : function
380 A metric on vectors of numbers (represented as lists or
381 tuples). This must be a function that accepts two lists (or
382 tuples) as input and yields a number as output. The function
383 must also satisfy the four requirements of a `metric`_.
384 Specifically, if $d$ is the function and $x$, $y$,
385 and $z$ are vectors in the graph, then $d$ must satisfy
387 1. $d(x, y) \ge 0$,
388 2. $d(x, y) = 0$ if and only if $x = y$,
389 3. $d(x, y) = d(y, x)$,
390 4. $d(x, z) \le d(x, y) + d(y, z)$.
392 If this argument is not specified, the Euclidean distance metric is
393 used.
395 .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29
396 p_dist : function, optional
397 Any function used to give weight to the distance between nodes when
398 deciding whether or not they should be connected. `p_dist` was
399 originally conceived as a probability density function giving the
400 probability of connecting two nodes that are of metric distance `r`
401 apart. The implementation here allows for more arbitrary definitions
402 of `p_dist` that do not need to correspond to valid probability
403 density functions. The :mod:`scipy.stats` package has many
404 probability density functions implemented and tools for custom
405 probability density definitions, and passing the ``.pdf`` method of
406 scipy.stats distributions can be used here. If ``p_dist=None``
407 (the default), the exponential function :math:`r^{-2}` is used.
408 seed : integer, random_state, or None (default)
409 Indicator of random number generation state.
410 See :ref:`Randomness<randomness>`.
411 pos_name : string, default="pos"
412 The name of the node attribute which represents the position
413 in 2D coordinates of the node in the returned graph.
414 weight_name : string, default="weight"
415 The name of the node attribute which represents the weight
416 of the node in the returned graph.
418 Returns
419 -------
420 Graph
421 A random geographic threshold graph, undirected and without
422 self-loops.
424 Each node has a node attribute ``pos`` that stores the
425 position of that node in Euclidean space as provided by the
426 ``pos`` keyword argument or, if ``pos`` was not provided, as
427 generated by this function. Similarly, each node has a node
428 attribute ``weight`` that stores the weight of that node as
429 provided or as generated.
431 Examples
432 --------
433 Specify an alternate distance metric using the ``metric`` keyword
434 argument. For example, to use the `taxicab metric`_ instead of the
435 default `Euclidean metric`_::
437 >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
438 >>> G = nx.geographical_threshold_graph(10, 0.1, metric=dist)
440 .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry
441 .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance
443 Notes
444 -----
445 If weights are not specified they are assigned to nodes by drawing randomly
446 from the exponential distribution with rate parameter $\lambda=1$.
447 To specify weights from a different distribution, use the `weight` keyword
448 argument::
450 >>> import random
451 >>> n = 20
452 >>> w = {i: random.expovariate(5.0) for i in range(n)}
453 >>> G = nx.geographical_threshold_graph(20, 50, weight=w)
455 If node positions are not specified they are randomly assigned from the
456 uniform distribution.
458 References
459 ----------
460 .. [1] Masuda, N., Miwa, H., Konno, N.:
461 Geographical threshold graphs with small-world and scale-free
462 properties.
463 Physical Review E 71, 036108 (2005)
464 .. [2] Milan Bradonjić, Aric Hagberg and Allon G. Percus,
465 Giant component and connectivity in geographical threshold graphs,
466 in Algorithms and Models for the Web-Graph (WAW 2007),
467 Antony Bonato and Fan Chung (Eds), pp. 209--216, 2007
468 """
469 G = nx.empty_graph(n)
470 # If no weights are provided, choose them from an exponential
471 # distribution.
472 if weight is None:
473 weight = {v: seed.expovariate(1) for v in G}
474 # If no positions are provided, choose uniformly random vectors in
475 # Euclidean space of the specified dimension.
476 if pos is None:
477 pos = {v: [seed.random() for i in range(dim)] for v in G}
478 # If no distance metric is provided, use Euclidean distance.
479 if metric is None:
480 metric = math.dist
481 nx.set_node_attributes(G, weight, weight_name)
482 nx.set_node_attributes(G, pos, pos_name)
484 # if p_dist is not supplied, use default r^-2
485 if p_dist is None:
487 def p_dist(r):
488 return r**-2
490 # Returns ``True`` if and only if the nodes whose attributes are
491 # ``du`` and ``dv`` should be joined, according to the threshold
492 # condition.
493 def should_join(pair):
494 u, v = pair
495 u_pos, v_pos = pos[u], pos[v]
496 u_weight, v_weight = weight[u], weight[v]
497 return (u_weight + v_weight) * p_dist(metric(u_pos, v_pos)) >= theta
499 G.add_edges_from(filter(should_join, combinations(G, 2)))
500 return G
503@py_random_state(6)
504@nx._dispatch(graphs=None)
505def waxman_graph(
506 n,
507 beta=0.4,
508 alpha=0.1,
509 L=None,
510 domain=(0, 0, 1, 1),
511 metric=None,
512 seed=None,
513 *,
514 pos_name="pos",
515):
516 r"""Returns a Waxman random graph.
518 The Waxman random graph model places `n` nodes uniformly at random
519 in a rectangular domain. Each pair of nodes at distance `d` is
520 joined by an edge with probability
522 .. math::
523 p = \beta \exp(-d / \alpha L).
525 This function implements both Waxman models, using the `L` keyword
526 argument.
528 * Waxman-1: if `L` is not specified, it is set to be the maximum distance
529 between any pair of nodes.
530 * Waxman-2: if `L` is specified, the distance between a pair of nodes is
531 chosen uniformly at random from the interval `[0, L]`.
533 Parameters
534 ----------
535 n : int or iterable
536 Number of nodes or iterable of nodes
537 beta: float
538 Model parameter
539 alpha: float
540 Model parameter
541 L : float, optional
542 Maximum distance between nodes. If not specified, the actual distance
543 is calculated.
544 domain : four-tuple of numbers, optional
545 Domain size, given as a tuple of the form `(x_min, y_min, x_max,
546 y_max)`.
547 metric : function
548 A metric on vectors of numbers (represented as lists or
549 tuples). This must be a function that accepts two lists (or
550 tuples) as input and yields a number as output. The function
551 must also satisfy the four requirements of a `metric`_.
552 Specifically, if $d$ is the function and $x$, $y$,
553 and $z$ are vectors in the graph, then $d$ must satisfy
555 1. $d(x, y) \ge 0$,
556 2. $d(x, y) = 0$ if and only if $x = y$,
557 3. $d(x, y) = d(y, x)$,
558 4. $d(x, z) \le d(x, y) + d(y, z)$.
560 If this argument is not specified, the Euclidean distance metric is
561 used.
563 .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29
565 seed : integer, random_state, or None (default)
566 Indicator of random number generation state.
567 See :ref:`Randomness<randomness>`.
568 pos_name : string, default="pos"
569 The name of the node attribute which represents the position
570 in 2D coordinates of the node in the returned graph.
572 Returns
573 -------
574 Graph
575 A random Waxman graph, undirected and without self-loops. Each
576 node has a node attribute ``'pos'`` that stores the position of
577 that node in Euclidean space as generated by this function.
579 Examples
580 --------
581 Specify an alternate distance metric using the ``metric`` keyword
582 argument. For example, to use the "`taxicab metric`_" instead of the
583 default `Euclidean metric`_::
585 >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
586 >>> G = nx.waxman_graph(10, 0.5, 0.1, metric=dist)
588 .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry
589 .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance
591 Notes
592 -----
593 Starting in NetworkX 2.0 the parameters alpha and beta align with their
594 usual roles in the probability distribution. In earlier versions their
595 positions in the expression were reversed. Their position in the calling
596 sequence reversed as well to minimize backward incompatibility.
598 References
599 ----------
600 .. [1] B. M. Waxman, *Routing of multipoint connections*.
601 IEEE J. Select. Areas Commun. 6(9),(1988) 1617--1622.
602 """
603 G = nx.empty_graph(n)
604 (xmin, ymin, xmax, ymax) = domain
605 # Each node gets a uniformly random position in the given rectangle.
606 pos = {v: (seed.uniform(xmin, xmax), seed.uniform(ymin, ymax)) for v in G}
607 nx.set_node_attributes(G, pos, pos_name)
608 # If no distance metric is provided, use Euclidean distance.
609 if metric is None:
610 metric = math.dist
611 # If the maximum distance L is not specified (that is, we are in the
612 # Waxman-1 model), then find the maximum distance between any pair
613 # of nodes.
614 #
615 # In the Waxman-1 model, join nodes randomly based on distance. In
616 # the Waxman-2 model, join randomly based on random l.
617 if L is None:
618 L = max(metric(x, y) for x, y in combinations(pos.values(), 2))
620 def dist(u, v):
621 return metric(pos[u], pos[v])
623 else:
625 def dist(u, v):
626 return seed.random() * L
628 # `pair` is the pair of nodes to decide whether to join.
629 def should_join(pair):
630 return seed.random() < beta * math.exp(-dist(*pair) / (alpha * L))
632 G.add_edges_from(filter(should_join, combinations(G, 2)))
633 return G
636@py_random_state(5)
637@nx._dispatch(graphs=None)
638def navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None):
639 r"""Returns a navigable small-world graph.
641 A navigable small-world graph is a directed grid with additional long-range
642 connections that are chosen randomly.
644 [...] we begin with a set of nodes [...] that are identified with the set
645 of lattice points in an $n \times n$ square,
646 $\{(i, j): i \in \{1, 2, \ldots, n\}, j \in \{1, 2, \ldots, n\}\}$,
647 and we define the *lattice distance* between two nodes $(i, j)$ and
648 $(k, l)$ to be the number of "lattice steps" separating them:
649 $d((i, j), (k, l)) = |k - i| + |l - j|$.
651 For a universal constant $p >= 1$, the node $u$ has a directed edge to
652 every other node within lattice distance $p$---these are its *local
653 contacts*. For universal constants $q >= 0$ and $r >= 0$ we also
654 construct directed edges from $u$ to $q$ other nodes (the *long-range
655 contacts*) using independent random trials; the $i$th directed edge from
656 $u$ has endpoint $v$ with probability proportional to $[d(u,v)]^{-r}$.
658 -- [1]_
660 Parameters
661 ----------
662 n : int
663 The length of one side of the lattice; the number of nodes in
664 the graph is therefore $n^2$.
665 p : int
666 The diameter of short range connections. Each node is joined with every
667 other node within this lattice distance.
668 q : int
669 The number of long-range connections for each node.
670 r : float
671 Exponent for decaying probability of connections. The probability of
672 connecting to a node at lattice distance $d$ is $1/d^r$.
673 dim : int
674 Dimension of grid
675 seed : integer, random_state, or None (default)
676 Indicator of random number generation state.
677 See :ref:`Randomness<randomness>`.
679 References
680 ----------
681 .. [1] J. Kleinberg. The small-world phenomenon: An algorithmic
682 perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
683 """
684 if p < 1:
685 raise nx.NetworkXException("p must be >= 1")
686 if q < 0:
687 raise nx.NetworkXException("q must be >= 0")
688 if r < 0:
689 raise nx.NetworkXException("r must be >= 1")
691 G = nx.DiGraph()
692 nodes = list(product(range(n), repeat=dim))
693 for p1 in nodes:
694 probs = [0]
695 for p2 in nodes:
696 if p1 == p2:
697 continue
698 d = sum((abs(b - a) for a, b in zip(p1, p2)))
699 if d <= p:
700 G.add_edge(p1, p2)
701 probs.append(d**-r)
702 cdf = list(accumulate(probs))
703 for _ in range(q):
704 target = nodes[bisect_left(cdf, seed.uniform(0, cdf[-1]))]
705 G.add_edge(p1, target)
706 return G
709@py_random_state(7)
710@nx._dispatch(graphs=None)
711def thresholded_random_geometric_graph(
712 n,
713 radius,
714 theta,
715 dim=2,
716 pos=None,
717 weight=None,
718 p=2,
719 seed=None,
720 *,
721 pos_name="pos",
722 weight_name="weight",
723):
724 r"""Returns a thresholded random geometric graph in the unit cube.
726 The thresholded random geometric graph [1] model places `n` nodes
727 uniformly at random in the unit cube of dimensions `dim`. Each node
728 `u` is assigned a weight :math:`w_u`. Two nodes `u` and `v` are
729 joined by an edge if they are within the maximum connection distance,
730 `radius` computed by the `p`-Minkowski distance and the summation of
731 weights :math:`w_u` + :math:`w_v` is greater than or equal
732 to the threshold parameter `theta`.
734 Edges within `radius` of each other are determined using a KDTree when
735 SciPy is available. This reduces the time complexity from :math:`O(n^2)`
736 to :math:`O(n)`.
738 Parameters
739 ----------
740 n : int or iterable
741 Number of nodes or iterable of nodes
742 radius: float
743 Distance threshold value
744 theta: float
745 Threshold value
746 dim : int, optional
747 Dimension of graph
748 pos : dict, optional
749 A dictionary keyed by node with node positions as values.
750 weight : dict, optional
751 Node weights as a dictionary of numbers keyed by node.
752 p : float, optional (default 2)
753 Which Minkowski distance metric to use. `p` has to meet the condition
754 ``1 <= p <= infinity``.
756 If this argument is not specified, the :math:`L^2` metric
757 (the Euclidean distance metric), p = 2 is used.
759 This should not be confused with the `p` of an Erdős-Rényi random
760 graph, which represents probability.
761 seed : integer, random_state, or None (default)
762 Indicator of random number generation state.
763 See :ref:`Randomness<randomness>`.
764 pos_name : string, default="pos"
765 The name of the node attribute which represents the position
766 in 2D coordinates of the node in the returned graph.
767 weight_name : string, default="weight"
768 The name of the node attribute which represents the weight
769 of the node in the returned graph.
771 Returns
772 -------
773 Graph
774 A thresholded random geographic graph, undirected and without
775 self-loops.
777 Each node has a node attribute ``'pos'`` that stores the
778 position of that node in Euclidean space as provided by the
779 ``pos`` keyword argument or, if ``pos`` was not provided, as
780 generated by this function. Similarly, each node has a nodethre
781 attribute ``'weight'`` that stores the weight of that node as
782 provided or as generated.
784 Examples
785 --------
786 Default Graph:
788 G = nx.thresholded_random_geometric_graph(50, 0.2, 0.1)
790 Custom Graph:
792 Create a thresholded random geometric graph on 50 uniformly distributed
793 nodes where nodes are joined by an edge if their sum weights drawn from
794 a exponential distribution with rate = 5 are >= theta = 0.1 and their
795 Euclidean distance is at most 0.2.
797 Notes
798 -----
799 This uses a *k*-d tree to build the graph.
801 The `pos` keyword argument can be used to specify node positions so you
802 can create an arbitrary distribution and domain for positions.
804 For example, to use a 2D Gaussian distribution of node positions with mean
805 (0, 0) and standard deviation 2
807 If weights are not specified they are assigned to nodes by drawing randomly
808 from the exponential distribution with rate parameter :math:`\lambda=1`.
809 To specify weights from a different distribution, use the `weight` keyword
810 argument::
812 ::
814 >>> import random
815 >>> import math
816 >>> n = 50
817 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
818 >>> w = {i: random.expovariate(5.0) for i in range(n)}
819 >>> G = nx.thresholded_random_geometric_graph(n, 0.2, 0.1, 2, pos, w)
821 References
822 ----------
823 .. [1] http://cole-maclean.github.io/blog/files/thesis.pdf
825 """
826 G = nx.empty_graph(n)
827 G.name = f"thresholded_random_geometric_graph({n}, {radius}, {theta}, {dim})"
828 # If no weights are provided, choose them from an exponential
829 # distribution.
830 if weight is None:
831 weight = {v: seed.expovariate(1) for v in G}
832 # If no positions are provided, choose uniformly random vectors in
833 # Euclidean space of the specified dimension.
834 if pos is None:
835 pos = {v: [seed.random() for i in range(dim)] for v in G}
836 # If no distance metric is provided, use Euclidean distance.
837 nx.set_node_attributes(G, weight, weight_name)
838 nx.set_node_attributes(G, pos, pos_name)
840 edges = (
841 (u, v)
842 for u, v in _geometric_edges(G, radius, p, pos_name)
843 if weight[u] + weight[v] >= theta
844 )
845 G.add_edges_from(edges)
846 return G