Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.generators.geometric

# -*- coding: utf-8 -*-
"""
Generators for geometric graphs.
"""
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>

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
#---------------------------------------------------------------------------

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
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"
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)))
return G

[docs]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()
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)
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)

[docs]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()
(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)):
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)):
return G

[docs]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: