/usr/lib/python3/dist-packages/networkx/generators/geometric.py is in python3-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 | # -*- coding: utf-8 -*-
"""
Generators for geometric graphs.
"""
# Copyright (C) 2004-2011 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
from __future__ import print_function
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
'Dan Schult (dschult@colgate.edu)',
'Ben Edwards (BJEdwards@gmail.com)'])
__all__ = ['random_geometric_graph',
'waxman_graph',
'geographical_threshold_graph',
'navigable_small_world_graph']
from bisect import bisect_left
from functools import reduce
from itertools import product
import math, random, sys
import networkx as nx
#---------------------------------------------------------------------------
# Random Geometric Graphs
#---------------------------------------------------------------------------
def random_geometric_graph(n, radius, dim=2, pos=None):
r"""Return the random geometric graph in the unit cube.
The random geometric graph model places n nodes uniformly at random
in the unit cube Two nodes `u,v` are connected with an edge if
`d(u,v)<=r` where `d` is the Euclidean distance and `r` is a radius
threshold.
Parameters
----------
n : int
Number of nodes
radius: float
Distance threshold value
dim : int, optional
Dimension of graph
pos : dict, optional
A dictionary keyed by node with node positions as values.
Returns
-------
Graph
Examples
--------
>>> G = nx.random_geometric_graph(20,0.1)
Notes
-----
This uses an `n^2` algorithm to build the graph. A faster algorithm
is possible using k-d trees.
The pos keyword can be used to specify node positions so you can create
an arbitrary distribution and domain for positions. If you need a distance
function other than Euclidean you'll have to hack the algorithm.
E.g to use a 2d Gaussian distribution of node positions with mean (0,0)
and std. dev. 2
>>> import random
>>> n=20
>>> p=dict((i,(random.gauss(0,2),random.gauss(0,2))) for i in range(n))
>>> G = nx.random_geometric_graph(n,0.2,pos=p)
References
----------
.. [1] Penrose, Mathew, Random Geometric Graphs,
Oxford Studies in Probability, 5, 2003.
"""
G=nx.Graph()
G.name="Random Geometric Graph"
G.add_nodes_from(range(n))
if pos is None:
# random positions
for n in G:
G.node[n]['pos']=[random.random() for i in range(0,dim)]
else:
nx.set_node_attributes(G,'pos',pos)
# connect nodes within "radius" of each other
# n^2 algorithm, could use a k-d tree implementation
nodes = G.nodes(data=True)
while nodes:
u,du = nodes.pop()
pu = du['pos']
for v,dv in nodes:
pv = dv['pos']
d = sum(((a-b)**2 for a,b in zip(pu,pv)))
if d <= radius**2:
G.add_edge(u,v)
return G
def geographical_threshold_graph(n, theta, alpha=2, dim=2,
pos=None, weight=None):
r"""Return a geographical threshold graph.
The geographical threshold graph model places n nodes uniformly at random
in a rectangular domain. Each node `u` is assigned a weight `w_u`.
Two nodes `u,v` are connected with an edge if
.. math::
w_u + w_v \ge \theta r^{\alpha}
where `r` is the Euclidean distance between `u` and `v`,
and `\theta`, `\alpha` are parameters.
Parameters
----------
n : int
Number of nodes
theta: float
Threshold value
alpha: float, optional
Exponent of distance function
dim : int, optional
Dimension of graph
pos : dict
Node positions as a dictionary of tuples keyed by node.
weight : dict
Node weights as a dictionary of numbers keyed by node.
Returns
-------
Graph
Examples
--------
>>> G = nx.geographical_threshold_graph(20,50)
Notes
-----
If weights are not specified they are assigned to nodes by drawing randomly
from an the exponential distribution with rate parameter `\lambda=1`.
To specify a weights from a different distribution assign them to a
dictionary and pass it as the weight= keyword
>>> import random
>>> n = 20
>>> w=dict((i,random.expovariate(5.0)) for i in range(n))
>>> G = nx.geographical_threshold_graph(20,50,weight=w)
If node positions are not specified they are randomly assigned from the
uniform distribution.
References
----------
.. [1] Masuda, N., Miwa, H., Konno, N.:
Geographical threshold graphs with small-world and scale-free properties.
Physical Review E 71, 036108 (2005)
.. [2] Milan Bradonjić, Aric Hagberg and Allon G. Percus,
Giant component and connectivity in geographical threshold graphs,
in Algorithms and Models for the Web-Graph (WAW 2007),
Antony Bonato and Fan Chung (Eds), pp. 209--216, 2007
"""
G=nx.Graph()
# add n nodes
G.add_nodes_from([v for v in range(n)])
if weight is None:
# choose weights from exponential distribution
for n in G:
G.node[n]['weight'] = random.expovariate(1.0)
else:
nx.set_node_attributes(G,'weight',weight)
if pos is None:
# random positions
for n in G:
G.node[n]['pos']=[random.random() for i in range(0,dim)]
else:
nx.set_node_attributes(G,'pos',pos)
G.add_edges_from(geographical_threshold_edges(G, theta, alpha))
return G
def geographical_threshold_edges(G, theta, alpha=2):
# generate edges for a geographical threshold graph given a graph
# with positions and weights assigned as node attributes 'pos' and 'weight'.
nodes = G.nodes(data=True)
while nodes:
u,du = nodes.pop()
wu = du['weight']
pu = du['pos']
for v,dv in nodes:
wv = dv['weight']
pv = dv['pos']
r = math.sqrt(sum(((a-b)**2 for a,b in zip(pu,pv))))
if wu+wv >= theta*r**alpha:
yield(u,v)
def waxman_graph(n, alpha=0.4, beta=0.1, L=None, domain=(0,0,1,1)):
r"""Return a Waxman random graph.
The Waxman random graph models place n nodes uniformly at random
in a rectangular domain. Two nodes u,v are connected with an edge
with probability
.. math::
p = \alpha*exp(-d/(\beta*L)).
This function implements both Waxman models.
Waxman-1: `L` not specified
The distance `d` is the Euclidean distance between the nodes u and v.
`L` is the maximum distance between all nodes in the graph.
Waxman-2: `L` specified
The distance `d` is chosen randomly in `[0,L]`.
Parameters
----------
n : int
Number of nodes
alpha: float
Model parameter
beta: float
Model parameter
L : float, optional
Maximum distance between nodes. If not specified the actual distance
is calculated.
domain : tuple of numbers, optional
Domain size (xmin, ymin, xmax, ymax)
Returns
-------
G: Graph
References
----------
.. [1] B. M. Waxman, Routing of multipoint connections.
IEEE J. Select. Areas Commun. 6(9),(1988) 1617-1622.
"""
# build graph of n nodes with random positions in the unit square
G = nx.Graph()
G.add_nodes_from(range(n))
(xmin,ymin,xmax,ymax)=domain
for n in G:
G.node[n]['pos']=((xmin + (xmax-xmin))*random.random(),
(ymin + (ymax-ymin))*random.random())
if L is None:
# find maximum distance L between two nodes
l = 0
pos = list(nx.get_node_attributes(G,'pos').values())
while pos:
x1,y1 = pos.pop()
for x2,y2 in pos:
r2 = (x1-x2)**2 + (y1-y2)**2
if r2 > l:
l = r2
l=math.sqrt(l)
else:
# user specified maximum distance
l = L
nodes=G.nodes()
if L is None:
# Waxman-1 model
# try all pairs, connect randomly based on euclidean distance
while nodes:
u = nodes.pop()
x1,y1 = G.node[u]['pos']
for v in nodes:
x2,y2 = G.node[v]['pos']
r = math.sqrt((x1-x2)**2 + (y1-y2)**2)
if random.random() < alpha*math.exp(-r/(beta*l)):
G.add_edge(u,v)
else:
# Waxman-2 model
# try all pairs, connect randomly based on randomly chosen l
while nodes:
u = nodes.pop()
for v in nodes:
r = random.random()*l
if random.random() < alpha*math.exp(-r/(beta*l)):
G.add_edge(u,v)
return G
def navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None):
r"""Return a navigable small-world graph.
A navigable small-world graph is a directed grid with additional
long-range connections that are chosen randomly. From [1]_:
Begin with a set of nodes that are identified with the set of lattice
points in an `n \times n` square, `{(i,j): i\in {1,2,\ldots,n}, j\in {1,2,\ldots,n}}`
and define the lattice distance between two nodes `(i,j)` and `(k,l)`
to be the number of "lattice steps" separating them: `d((i,j),(k,l)) = |k-i|+|l-j|`.
For a universal constant `p`, the node `u` has a directed edge to every other
node within lattice distance `p` (local contacts) .
For universal constants `q\ge 0` and `r\ge 0` construct directed edges from `u` to `q`
other nodes (long-range contacts) using independent random trials; the i'th
directed edge from `u` has endpoint `v` with probability proportional to `d(u,v)^{-r}`.
Parameters
----------
n : int
The number of nodes.
p : int
The diameter of short range connections. Each node is connected
to every other node within lattice distance p.
q : int
The number of long-range connections for each node.
r : float
Exponent for decaying probability of connections. The probability of
connecting to a node at lattice distance d is 1/d^r.
dim : int
Dimension of grid
seed : int, optional
Seed for random number generator (default=None).
References
----------
.. [1] J. Kleinberg. The small-world phenomenon: An algorithmic
perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
"""
if (p < 1):
raise nx.NetworkXException("p must be >= 1")
if (q < 0):
raise nx.NetworkXException("q must be >= 0")
if (r < 0):
raise nx.NetworkXException("r must be >= 1")
if not seed is None:
random.seed(seed)
G = nx.DiGraph()
nodes = list(product(range(n),repeat=dim))
for p1 in nodes:
probs = [0]
for p2 in nodes:
if p1==p2:
continue
d = sum((abs(b-a) for a,b in zip(p1,p2)))
if d <= p:
G.add_edge(p1,p2)
probs.append(d**-r)
cdf = list(nx.utils.cumulative_sum(probs))
for _ in range(q):
target = nodes[bisect_left(cdf,random.uniform(0, cdf[-1]))]
G.add_edge(p1,target)
return G
|