2
Utilities for networkx package
8
These are not imported into the base networkx namespace but
9
can be accessed, for example, as
12
>>> networkx.utils.is_string_like('spam')
5
16
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
7
18
# Aric Hagberg <hagberg@lanl.gov>
8
19
# Dan Schult <dschult@colgate.edu>
9
20
# Pieter Swart <swart@lanl.gov>
10
# Distributed under the terms of the GNU Lesser General Public License
11
# http://www.gnu.org/copyleft/lesser.html
21
# All rights reserved.
14
25
### some cookbook stuff
16
27
# used in deciding whether something is a bunch of nodes, edges, etc.
17
28
# see G.add_nodes and others in Graph Class in networkx/base.py
18
29
def is_singleton(obj):
19
""" Is string_like or not iterable. """
30
"""Is string_like or not iterable."""
20
31
return hasattr(obj,"capitalize") or not hasattr(obj,"__iter__")
22
33
def is_string_like(obj): # from John Hunter, types-free version
42
53
def flatten(obj, result=None):
43
""" Return flattened version of (possibly nested) iterable obj. """
54
""" Return flattened version of (possibly nested) iterable object. """
44
55
if not iterable(obj) or is_string_like(obj):
52
63
flatten(item, result)
53
64
return obj.__class__(result)
55
def iterable_to_string(obj, sep=''):
57
Return string obtained by concatenating the string representation
58
of each element of an iterable obj, with an optional internal string
63
return sep.join([str(i) for i in obj])
65
66
def is_list_of_ints( intlist ):
66
67
""" Return True if list is a list of ints. """
67
68
if not isinstance(intlist,list): return False
201
# some helpers for choosing random sequences from distributions
202
# uses pygsl: pygsl.sourceforge.org, but not all its functionality.
203
# note: gsl's default number generator is the same as Python's
206
def gsl_pareto_sequence(n,exponent=1.0,scale=1.0,seed=None):
208
Return sample sequence of length n from a Pareto distribution.
214
print "Import error: not able to import pygsl"
217
random._inst = random.Random()
219
seed=random.randint(1,2**32-1)
222
return rng.pareto(exponent,scale,n)
224
def gsl_powerlaw_sequence(n,exponent=2.0,scale=1.0,seed=None):
226
Return sample sequence of length n from a power law distribution.
232
print "Import error: not able to import pygsl"
235
random._inst = random.Random()
237
seed=random.randint(1,2**32-1)
240
return rng.pareto(exponent-1,scale,n)
242
def gsl_poisson_sequence(n,mu=1.0,seed=None):
244
Return sample sequence of length n from a Poisson distribution.
250
print "Import error: not able to import pygsl"
253
random._inst = random.Random()
255
seed=random.randint(1,2**32-1)
258
return rng.poisson(mu,n)
260
def gsl_uniform_sequence(n,seed=None):
262
Return sample sequence of length n from a uniform distribution.
268
print "Import error: not able to import pygsl"
271
random._inst = random.Random()
273
seed=random.randint(1,2**32-1)
276
return rng.uniform(n)
279
202
# The same helpers for choosing random sequences from distributions
280
203
# uses Python's random module
281
204
# http://www.python.org/doc/current/lib/module-random.html
341
264
# choose from CDF
342
265
seq=[bisect.bisect_left(cdf,s)-1 for s in inputseq]
269
"""Union-find data structure.
271
Each unionFind instance X maintains a family of disjoint sets of
272
hashable objects, supporting the following two methods:
274
- X[item] returns a name for the set containing the given item.
275
Each set is named by an arbitrarily-chosen one of its members; as
276
long as the set remains unchanged it will keep the same name. If
277
the item is not yet part of a set in X, a new singleton set is
280
- X.union(item1, item2, ...) merges the sets containing each item
281
into a single larger set. If any item is not yet part of a set
282
in X, it is added to X as one of the members of the merged set.
284
Union-find data structure. Based on Josiah Carlson's code,
285
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
286
with significant additional changes by D. Eppstein.
287
http://www.ics.uci.edu/~eppstein/PADS/UnionFind.py
292
"""Create a new empty union-find structure."""
296
def __getitem__(self, object):
297
"""Find and return the name of the set containing the object."""
299
# check for previously unknown object
300
if object not in self.parents:
301
self.parents[object] = object
302
self.weights[object] = 1
305
# find path of objects leading to the root
307
root = self.parents[object]
308
while root != path[-1]:
310
root = self.parents[root]
312
# compress the path and return
313
for ancestor in path:
314
self.parents[ancestor] = root
318
"""Iterate through all items ever found or unioned by this structure."""
319
return iter(self.parents)
321
def union(self, *objects):
322
"""Find the sets containing the objects and merge them all."""
323
roots = [self[x] for x in objects]
324
heaviest = max([(self.weights[r],r) for r in roots])[1]
327
self.weights[heaviest] += self.weights[r]
328
self.parents[r] = heaviest